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

Understand

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.