We analyze a class of estimators based on convex relaxation for solving high-dimensional matrix decomposition problems. The observations are the noisy realizations of the sum of an (appproximately) low rank matrix $\Theta^\star$ with a second matrix $\Gamma^\star$ endowed with a complementary form of low-dimensional structure. We derive a general theorem that gives upper bounds on 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. We then specialize this result to two cases that have been studied in the context of robust PCA: 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 for 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, we establish matching lower bounds on the minimax error, showing that our results cannot be improved beyond constant factors. The sharpness of our theoretical predictions is confirmed by numerical simulations.

通过矩阵分解问题中的凸松弛方法，结合核范数和分解式正则化，我们分析了一个能得到估计值的一般性定理，该定理可以适用于低秩矩阵、稀疏矩阵及一些可压缩的高维矩阵。我们利用了峰态条件，得到了确定性和随机性噪声矩阵的非渐近性弗罗贝尼乌斯误差界，同时也证实了最小化误差的下限和数值模拟结果的契合度。

通过凸松弛进行嘈杂矩阵分解：在高维度中获得最优速率