CaltechAUTHORS
  A Caltech Library Service

Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting

Saunderson, J. and Chandrasekaran, V. and Parrilo, P. A. and Willsky, A. S. (2012) Diagonal and Low-Rank Matrix Decompositions, Correlation Matrices, and Ellipsoid Fitting. SIAM Journal on Matrix Analysis and Applications, 33 (4). pp. 1395-1416. ISSN 0895-4798. doi:10.1137/120872516. https://resolver.caltech.edu/CaltechAUTHORS:20121004-133456681

[img] PDF - Published Version
See Usage Policy.

343kB
[img]
Preview
PDF - Submitted Version
See Usage Policy.

367kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20121004-133456681

Abstract

In this paper we establish links between, and new results for, three problems that are not usually considered together. The first is a matrix decomposition problem that arises in areas such as statistical modeling and signal processing: given a matrix X formed as the sum of an unknown diagonal matrix and an unknown low rank positive semidefinite matrix, decompose X into these constituents. The second problem we consider is to determine the facial structure of the set of correlation matrices, a convex set also known as the elliptope. This convex body, and particularly its facial structure, plays a role in applications from combinatorial optimization to mathematical finance. The third problem is a basic geometric question: given points v1, v2, … , vn ∈ R^k (where n > k) determine whether there is a centered ellipsoid passing exactly through all of the points. We show that in a precise sense these three problems are equivalent. Furthermore we establish a simple sufficient condition on a subspace U that ensures any positive semidefinite matrix L with column space U can be recovered from D+L for any diagonal matrix D using a convex optimization-based heuristic known as minimum trace factor analysis. This result leads to a new understanding of the structure of rank-deficient correlation matrices and a simple condition on a set of points that ensures there is a centered ellipsoid passing through them.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://doi.org/10.1137/120872516DOIArticle
http://arxiv.org/abs/1204.1220arXivDiscussion Paper
ORCID:
AuthorORCID
Saunderson, J.0000-0002-5456-0180
Parrilo, P. A.0000-0003-1132-8477
Additional Information:© 2012 Society for Industrial and Applied Mathematics. Received by the editors April 5, 2012; accepted for publication (in revised form) by M. L. Overton October 17, 2012; published electronically December 19, 2012. This research was funded in part by Shell International Exploration and Production, Inc., under P.O. 450004440 and in part by the Air Force Office of Scientific Research under grant FA9550-11-1-0305. The authors would like to thank Prof. Sanjoy Mitter for helpful discussions and the anonymous reviewers for carefully reading the manuscript and providing many helpful suggestions.
Funders:
Funding AgencyGrant Number
Shell International Exploration Production, Inc.450004440
Air Force Office of Scientific Research (AFOSR)FA9550-11-1-0305
Subject Keywords:elliptope, minimum trace factor analysis, Frisch scheme, semidefinite programming, subspace coherence
Issue or Number:4
Classification Code:AMS subject classifications. 90C22, 52A20, 62H25, 93B30
DOI:10.1137/120872516
Record Number:CaltechAUTHORS:20121004-133456681
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20121004-133456681
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:34685
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:04 Oct 2012 22:22
Last Modified:09 Nov 2021 23:09

Repository Staff Only: item control page