Noisy matrix decomposition via convex relaxation: Optimal rates in high dimensions

By Alekh Agarwal, Sahand N. Negahban, Martin J. Wainwright. 2011

444 citations recorded by the source corpus.

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 $\mathfrak{X}$ of the sum of an approximately) low rank matrix $\Theta^\star$ with a second matrix $\Gamma^\star$ 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 $(\Theta^\star, \Gamma^\star)$ obtained by solving a convex optimization problem that combines the nuclear norm with a general decomposable regularizer. Our results utilize 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 non-asymptotic Frobenius error bounds for both deterministic and stochastic noise matrices, and applies to matrices $\Theta^\star$ that can be exactly or approximately low rank, and matrices $\Gamma^\star$ 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 predictions is confirmed by numerical simulations.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Principal Components and Regularized Estimation of Factor Models (2017, background): “For such problems, which seem more comparable to our setup, Agarwal et al. (2012) obtains an error bound in the Frobenius norm for L and for S under the assumption that P P P √ mn is eﬀectively a restriction on the sum of the eigenvalues of the low rank component L .”
Robust Lasso With Missing and Grossly Corrupted Observations (2011, neutral): “Also, assuming that n ≥ Ck log p and s ≤ min{C1 nγ2 logn , C2n} for some small constants C,C1, C2, Then with probability greater than 1−c1 exp(−c2n), the error set (h, f) = (β̂ − β?, ê− e?) is bounded by ‖h‖2 + ‖f‖2 ≤ 384 ( 1 γ √ σ2k log p n + √ σ2s log n n ) .”
Estimating structured high-dimensional covariance and precision matrices: Optimal rates and adaptive estimation (2016, unknown): “See, e.g., Candès et al. (2011) and Agarwal et al. (2012).”
Provable Inductive Matrix Completion (2013, background): “While in general low-rank matrix estimation that satisﬁes given (aﬃne) observations is NP-hard, several recent results present conditions under which the optimal solution can be recovered exactly or approximately [2, 1, 3, 13, 7, 6, 8, 9].”
Large Covariance Estimation by Thresholding Principal Orthogonal Complements (2011, unknown): “(2011), Luo (2011), Agarwal et al. (2012) and Pati et al.”
Group Lasso with Overlaps: the Latent Group Lasso approach (2011, background): “(2009), or Agarwal et al. (2011) on robust PCA and matrix decomposition in which a matrix is decomposed in a low rank matrix regularized by the trace norm and a sparse or column-sparse matrix regularized by an `1 or group `1-norm.”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, methodology): “One line of work concerns the setting where the non-zero entries of S∗ are randomly located [19, 22], whereas another line of work focuses on deterministic models [20, 35, 1].”