Diagonal and low-rank decompositions and fitting ellipsoids to random points
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...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/90825 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 |
| _version_ | 1826201879452844032 |
|---|---|
| author | Saunderson, James F. Parrilo, Pablo A. Willsky, Alan S. |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Saunderson, James F. Parrilo, Pablo A. Willsky, Alan S. |
| author_sort | Saunderson, James F. |
| collection | MIT |
| description | 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[superscript β] for β ϵ (5/6, 1) and some constant c. |
| first_indexed | 2024-09-23T11:58:18Z |
| format | Article |
| id | mit-1721.1/90825 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:58:18Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/908252022-10-01T07:20:56Z Diagonal and low-rank decompositions and fitting ellipsoids to random points Saunderson, James F. Parrilo, Pablo A. Willsky, Alan S. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Saunderson, James F. Parrilo, Pablo A. Willsky, Alan S. 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[superscript β] for β ϵ (5/6, 1) and some constant c. United States. Air Force Office of Scientific Research (AFOSR under Grant FA9550-12-1-0287) United States. Air Force Office of Scientific Research (AFOSR under Grant FA9550-11-1-0305) 2014-10-09T15:53:41Z 2014-10-09T15:53:41Z 2013-12 Article http://purl.org/eprint/type/ConferencePaper 978-1-4673-5717-3 978-1-4673-5714-2 978-1-4799-1381-7 0743-1546 INSPEC Accession Number: 14157643 http://hdl.handle.net/1721.1/90825 Saunderson, James, Pablo A. Parrilo, and Alan S. Willsky. “Diagonal and Low-Rank Decompositions and Fitting Ellipsoids to Random Points.” 52nd IEEE Conference on Decision and Control (12-13 December 2013), Firenze, Italy. IEEE. p.6031-6036. https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 en_US http://dx.doi.org/10.1109/CDC.2013.6760842 52nd IEEE Conference on Decision and Control Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) MIT web domain |
| spellingShingle | Saunderson, James F. Parrilo, Pablo A. Willsky, Alan S. Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title | Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title_full | Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title_fullStr | Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title_full_unstemmed | Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title_short | Diagonal and low-rank decompositions and fitting ellipsoids to random points |
| title_sort | diagonal and low rank decompositions and fitting ellipsoids to random points |
| url | http://hdl.handle.net/1721.1/90825 https://orcid.org/0000-0003-1132-8477 https://orcid.org/0000-0003-0149-5888 |
| work_keys_str_mv | AT saundersonjamesf diagonalandlowrankdecompositionsandfittingellipsoidstorandompoints AT parrilopabloa diagonalandlowrankdecompositionsandfittingellipsoidstorandompoints AT willskyalans diagonalandlowrankdecompositionsandfittingellipsoidstorandompoints |