Diagonal and low-rank decompositions and fitting ellipsoids to random points

James Saunderson, Pablo A. Parrilo, Alan S. Willsky

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


Identifying a subspace containing signals of interest in additive noise is a basic system identification problem. Under natural assumptions, this problem is known as the Frisch scheme and can be cast as decomposing an n × n positive definite matrix as the sum of an unknown diagonal matrix (the noise covariance) and an unknown low-rank matrix (the signal covariance). Our focus in this paper is a natural class of random instances, where the low-rank matrix has a uniformly distributed random column space. In this setting we analyze the behavior of a well-known convex optimization-based heuristic for diagonal and low-rank decomposition called minimum trace factor analysis (MTFA). Conditions for the success of MTFA have an appealing geometric reformulation as finding a (convex) ellipsoid that exactly interpolates a given set of n points. Under the random model, the points are chosen according to a Gaussian distribution. Numerical experiments suggest a remarkable threshold phenomenon: if the (random) column space of the n × n lowrank matrix has codimension as small as 2 √ n then with high probability MTFA successfully performs the decomposition task, otherwise it fails with high probability. In this work we provide numerical evidence and prove partial results in this direction, showing that with high probability MTFA recovers such random low-rank matrices of corank at least cnβ for β ∈ (5/6, 1) and some constant c.

Original languageEnglish
Title of host publicationProceedings of the 52nd IEEE Conference on Decision and Control, CDC 2013
Subtitle of host publicationDecember 10-13, 2013, Firenze, Italy
PublisherIEEE, Institute of Electrical and Electronics Engineers
Number of pages6
ISBN (Electronic)9781467357173
ISBN (Print)9781467357142
Publication statusPublished - 2013
Externally publishedYes
EventIEEE Conference on Decision and Control 2013 - Florence, Italy
Duration: 10 Dec 201313 Dec 2013
Conference number: 52nd
https://ieeexplore.ieee.org/xpl/conhome/6749719/proceeding (Proceedings)


ConferenceIEEE Conference on Decision and Control 2013
Abbreviated titleCDC 2013
Internet address

Cite this