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.

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

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

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

Singular Value Decomposition (and Principal Component Analysis) is one of the
most widely used techniques for dimensionality reduction: successful and
efficiently computable, it is nevertheless plagued by a well-known,
well-documented sensitivity to outliers. Recent work has considered the setting
where each point has a few arbitrarily corrupted components. Yet, in
applications of SVD or PCA such as robust collaborative filtering or
bioinformatics, malicious agents, defective genes, or simply corrupted or
contaminated experiments may effectively yield entire points that are
completely corrupted.
We present an efficient convex optimization-based algorithm we call Outlier
Pursuit, that under some mild assumptions on the uncorrupted points (satisfied,
e.g., by the standard generative assumption in PCA problems) recovers the exact
optimal low-dimensional subspace, and identifies the corrupted points. Such
identification of corrupted points that do not conform to the low-dimensional
approximation, is of paramount interest in bioinformatics and financial
applications, and beyond. Our techniques involve matrix decomposition using
nuclear norm minimization, however, our results, setup, and approach,
necessarily differ considerably from the existing line of work in matrix
completion and matrix decomposition, since we develop an approach to recover
the correct column space of the uncorrupted matrix, rather than the exact
matrix itself. In any problem where one seeks to recover a structure rather
than the exact initial matrices, techniques developed thus far relying on
certificates of optimality, will fail. We present an important extension of
these methods, that allows the treatment of such problems.

该文介绍了一种名为 Outlier Pursuit 的基于凸优化的算法，该算法使用矩阵分解来恢复未损坏矩阵的正确列空间，并确定损坏的点。此算法在基因组学和金融应用中具有重要意义。

通过离群值追踪实现鲁棒的 PCA

Robust PCA via Outlier Pursuit

Suppose we are given a matrix that is formed by adding an unknown sparse
matrix to an unknown low-rank matrix. Our goal is to decompose the given matrix
into its sparse and low-rank components. Such a problem arises in a number of
applications in model and system identification, and is NP-hard in general. In
this paper we consider a convex optimization formulation to splitting the
specified matrix into its components, by minimizing a linear combination of the
$\ell_1$ norm and the nuclear norm of the components. We develop a notion of
\emph{rank-sparsity incoherence}, expressed as an uncertainty principle between
the sparsity pattern of a matrix and its row and column spaces, and use it to
characterize both fundamental identifiability as well as (deterministic)
sufficient conditions for exact recovery. Our analysis is geometric in nature,
with the tangent spaces to the algebraic varieties of sparse and low-rank
matrices playing a prominent role. When the sparse and low-rank matrices are
drawn from certain natural random ensembles, we show that the sufficient
conditions for exact recovery are satisfied with high probability. We conclude
with simulation results on synthetic matrix decomposition problems.

本文采用基于凸优化的方法，通过最小化矩阵的 $l_1$ 范数和核范数的线性组合，将一个矩阵分解为它的稀疏和低秩部分。我们提出了一种新的概念来表征稀疏矩阵和其行列空间之间的不确定性原理，并用它来确定精确恢复的充分条件，同时提出了一些仿真结果。