Ellipsoid fitting and diagonal and low-rank matrix decompositions

Abstract:

Suppose an n x n matrix X is the sum of a diagonal and a positive semidefinite low-rank matrix. Decomposing X into these unknown constituents is a classical problem usually referred to as factor analysis or the Frisch scheme. Such a decomposition has applications in statistics, array processing, optics, and elsewhere.

We will discuss a new analysis of minimum trace factor analysis, a well known convex heuristic for this problem. Our analysis reduces to an appealing geometric problem: that of deciding whether there is an ellipsoid passing exactly through a set of points related to the column space of the low-rank matrix. We give both deterministic and `randomized' sufficient conditions on the column space of the low-rank matrix that ensure the convex program successfully decomposes X. These conditions indicate that in high-dimensional settings minimum trace factor analysis is typically a very good heuristic.

Biography:

James Saunderson is a second year graduate student in LIDS, co-advised by Prof. Alan Willsky and Prof. Pablo Parrilo.