Boyd, Stephen and Xiao, Lin (2005) LeastSquares Covariance Matrix Adjustment. SIAM Journal on Matrix Analysis and Applications, 27 (2). pp. 532546. ISSN 08954798. http://resolver.caltech.edu/CaltechAUTHORS:BOYsiamjmaa05

PDF
See Usage Policy. 187Kb 
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:BOYsiamjmaa05
Abstract
We consider the problem of finding the smallest adjustment to a given symmetric $n \times n$ matrix, as measured by the Euclidean or Frobenius norm, so that it satisfies some given linear equalities and inequalities, and in addition is positive semidefinite. This leastsquares covariance adjustment problem is a convex optimization problem, and can be efficiently solved using standard methods when the number of variables (i.e., entries in the matrix) is modest, say, under $1000$. Since the number of variables is $n(n+1)/2$, this corresponds to a limit around $n=45$. Malick [{\it SIAM J. Matrix Anal.\ Appl.,} 26 (2005), pp. 272284] studies a closely related problem and calls it the semidefinite leastsquares problem. In this paper we formulate a dual problem that has no matrix inequality or matrix variables, and a number of (scalar) variables equal to the number of equality and inequality constraints in the original leastsquares covariance adjustment problem. This dual problem allows us to solve far larger leastsquares covariance adjustment problems than would be possible using standard methods. Assuming a modest number of constraints, problems with $n=1000$ are readily solved by the dual method. The dual method coincides with the dual method proposed by Malick when there are no inequality constraints and can be obtained as an extension of his dual method when there are inequality constraints. Using the dual problem, we show that in many cases the optimal solution is a low rank update of the original matrix. When the original matrix has structure, such as sparsity, this observation allows us to solve very large leastsquares covariance adjustment problems.
Item Type:  Article 

Additional Information:  © 2005 Society for Industrial and Applied Mathematics ∗Received by the editors June 11, 2004; accepted for publication (in revised form) by L. Vanderberghe April 4, 2005; published electronically November 22, 2005. We are grateful to Andrew Ng for suggesting the problem to us and to two anonymous reviewers for very useful suggestions and comments. 
Subject Keywords:  matrix nearness problems, covariance matrix, leastsquares, semidefinite leastsquares 
Record Number:  CaltechAUTHORS:BOYsiamjmaa05 
Persistent URL:  http://resolver.caltech.edu/CaltechAUTHORS:BOYsiamjmaa05 
Alternative URL:  http://dx.doi.org/10.1137/040609902 
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  1382 
Collection:  CaltechAUTHORS 
Deposited By:  Archive Administrator 
Deposited On:  13 Jan 2006 
Last Modified:  26 Dec 2012 08:44 
Repository Staff Only: item control page