Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions
March 6, 2012
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Mathematical Statistics
2013
|
| Online Access: | http://hdl.handle.net/1721.1/76239 |
| _version_ | 1826201154679209984 |
|---|---|
| author | Agarwal, Alekh Negahban, Sahand N. Wainwright, Martin J. |
| 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 Agarwal, Alekh Negahban, Sahand N. Wainwright, Martin J. |
| author_sort | Agarwal, Alekh |
| collection | MIT |
| description | March 6, 2012 |
| first_indexed | 2024-09-23T11:47:23Z |
| format | Article |
| id | mit-1721.1/76239 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:47:23Z |
| publishDate | 2013 |
| publisher | Institute of Mathematical Statistics |
| record_format | dspace |
| spelling | mit-1721.1/762392022-09-27T21:53:14Z Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions Agarwal, Alekh Negahban, Sahand N. Wainwright, Martin J. Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Negahban, Sahand N. March 6, 2012 We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are noisy realizations of a linear transformation [bar through "X" symbol] of the sum of an (approximately) low rank matrix Θ⋆ with a second matrix Γ⋆ endowed with a complementary form of low-dimensional structure; this set-up includes many statistical models of interest, including factor analysis, multi-task regression and robust covariance estimation. We derive a general theorem that bounds the Frobenius norm error for an estimate of the pair (Θ⋆,Γ⋆) obtained by solving a convex optimization problem that combines the nuclear norm with a general decomposable regularizer. Our results use a “spikiness” condition that is related to, but milder than, singular vector incoherence. We specialize our general result to two cases that have been studied in past work: low rank plus an entrywise sparse matrix, and low rank plus a columnwise sparse matrix. For both models, our theory yields nonasymptotic Frobenius error bounds for both deterministic and stochastic noise matrices, and applies to matrices Θ⋆ that can be exactly or approximately low rank, and matrices Γ⋆ that can be exactly or approximately sparse. Moreover, for the case of stochastic noise matrices and the identity observation operator, we establish matching lower bounds on the minimax error. The sharpness of our nonasymptotic predictions is confirmed by numerical simulations. National Science Foundation (U.S.) (Grant CDI-0941742) 2013-01-10T18:31:05Z 2013-01-10T18:31:05Z 2012-08 2012-03 Article http://purl.org/eprint/type/JournalArticle 0090-5364 http://hdl.handle.net/1721.1/76239 Agarwal, Alekh, Sahand Negahban, and Martin J. Wainwright. “Noisy Matrix Decomposition via Convex Relaxation: Optimal Rates in High Dimensions.” The Annals of Statistics 40.2 (2012): 1171–1197. © 2012 Institute of Mathematical Statistics en_US http://dx.doi.org/10.1214/12-aos1000 The Annals of Statistics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Mathematical Statistics Institute of Mathematical Statistics |
| spellingShingle | Agarwal, Alekh Negahban, Sahand N. Wainwright, Martin J. Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title | Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title_full | Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title_fullStr | Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title_full_unstemmed | Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title_short | Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions |
| title_sort | noisy matrix decomposition via convex relaxation optimal rates in high dimensions |
| url | http://hdl.handle.net/1721.1/76239 |
| work_keys_str_mv | AT agarwalalekh noisymatrixdecompositionviaconvexrelaxationoptimalratesinhighdimensions AT negahbansahandn noisymatrixdecompositionviaconvexrelaxationoptimalratesinhighdimensions AT wainwrightmartinj noisymatrixdecompositionviaconvexrelaxationoptimalratesinhighdimensions |