Approximate least squares parameter estimation with structured observations

The solution of inverse problems where the parameter being estimated has a known structure has been widely studied. In this work, we consider the situation where it is not appropriate to assume a structure for the parameter, but the observations on which the estimate are based are structured; specifically, when the observations are parametrized by a decomposable graphical model. This translates to structured sparsity of the inverse covariance matrix for Gaussian distributed observation vectors. We present an approximate least squares method which takes advantage of the structure to reduce the complexity of least squares. The approximate least squares method can be implemented recursively for even lower complexity. It is shown that the proposed method is asymptotically equivalent to least squares parameter estimation for a large number of observations. The properties of the algorithm are verified by simulation.