text:
\section{Introduction}

This work studies additive decompositions of matrices into sparse (outliers) and
low-rank components.
Such decompositions have found applications in a variety of numerical
problems, including system identification~\citep{CSPW09}, latent variable
graphical modeling~\citep{CPW10}, and principal component
analysis~\citep{CLMW09}.
In these settings, the user has an input matrix $Y \in \mathbb{R}^{m \times n}$
which is believed to be the sum of a sparse matrix $X_S$ and a low-rank
matrix $X_L$.
For instance, in the application to principal component analysis, $X_L$
represents a matrix of $m$ data points from a low-dimensional subspace of
$\mathbb{R}^n$, and is corrupted by a sparse matrix $X_S$ of errors before being
observed as
\[
\begin{array}{ccccc}
Y & = & X_S & + & X_L . \\
&
& \text{\scriptsize{(sparse)}}
&
& \text{\scriptsize{(low-rank)}}
\\
\end{array}
\]
The goal is to recover the original data matrix $X_L$ (and the error
components $X_S$) from the corrupted observations $Y$.
In the latent variable model application of~\citet{CPW10}, $Y$ represents
the precision matrix over visible nodes of a Gaussian graphical model, and
$X_S$ represents the precision matrix over the visible nodes when
conditioned on the hidden nodes.
In general, $Y$ may be dense as a result of dependencies between visible
nodes through the hidden nodes.
However, $X_S$ will be sparse when the visible nodes are mostly independent
after conditioning on the hidden nodes, and the difference $X_L = Y - X_S$
will be low-rank when the number of hidden nodes is small.
The goal is then to infer the relevant dependency structure from just the
visible nodes and measurements of their correlations.

Even if the matrix $Y$ is exactly the sum of a sparse matrix $X_S$ and a
low-rank matrix $X_L$, it may be impossible to identify these components
from the sum.
For instance, the sparse matrix $X_S$ may be low-rank, or the low-rank
matrix $X_L$ may be sparse.
In such cases, these components may be confused for each other, and thus
the desired decomposition of $Y$ may not be identifiable.
Therefore, one must impose conditions on the sparse and low-rank components
in order to guarantee their identifiability from $Y$.

We present sufficient conditions under which $X_S$ and $X_L$ are
identifiable from the sum $Y$.
Essentially, we require that $X_S$ not be too dense in any single row or
column, and that the singular vectors of $X_L$ not be too sparse.
The level of denseness and sparseness are considered jointly in the
conditions in order to obtain the weakest possible conditions.
Under a mild strengthening of the condition, we also show that $X_S$ and
$X_L$ can be recovered by solving certain convex programs, and that the
solution is robust under small perturbations of $Y$.
The first program we consider is
\[ \min \ \lambda \|X_S\|_\v1 + \|X_L\|_* \]
(subject to certain feasibility constraints such as $\|X_S+X_L-Y\| \leq
\epsilon$)
where $\|\cdot\|_\v1$ is the entry-wise $1$-norm and $\|\cdot\|_*$ is the
trace norm.
These norms are natural convex surrogates for the sparsity of $X_S$ and the
rank of $X_L$~\citep{T96,F02}, which are generally intractable to optimize.
We also considered a regularized formulation
\[ \min \ \frac1{2\mu} \|X_S+X_L-Y\|_\v2^2 + \lambda\|X_S\|_\v1 + \|X_L\|_*
\]
where $\|\cdot\|_\v2$ is the Frobenius norm;
such a formulation may be more suitable in certain applications and enjoys
different recovery guarantees.

\subsection{Related work}

Our work closely follows that of~\citet{CSPW09}, who initiated the study
of rank-sparsity incoherence and its application to matrix decompositions.
There, the authors identify parameters that
characterize the incoherence of $X_S$ and $X_L$ sufficient to guarantee
identifiability and recovery using convex programs.
However, their analysis of this characterization yields conditions that are
significantly stronger than those given in the our present work.
For instance, the allowed fraction of non-zero entries in $X_S$ is quickly
vanishing as a function of the matrix size, even under the most favorable
conditions on $X_L$; our analysis does not have this restriction and allows
$X_S$ to have up to $\Omega(mn)$ non-zero entries when $X_L$ is low-rank
and has non-sparse singular vectors.
Therefore, for instance, in the application to principal component
analysis, our analysis allows for up to a constant fraction of the data
matrix entries to be corrupted by noise of arbitrary magnitude, whereas the
analysis of~\citeauthor{CSPW09} requires that it decrease as a function of
the matrix dimensions.
Moreover, \citeauthor{CSPW09} only consider exact decompositions, which may
be unrealistic in certain applications; we allow for approximate
decompositions, and study the effect of perturbations on the accuracy of
the recovered components.

The application to principal component analysis with gross sparse errors
was studied by~\citet{CLMW09}, building on previous results and analysis
techniques for the related matrix completion problem
(\emph{e.g.},~\citealt{CR09,G09}).
The sparse errors model studied by~\citeauthor{CLMW09} requires that the
support of the sparse matrix $X_S$ be random, which can be unrealistic in
some settings.
However, the conditions are significantly weaker than those
of~\citet{CSPW09}: for instance, they allow for $\Omega(mn)$ non-zero
entries in $X_S$.
Our work makes no probabilistic assumption on the sparsity pattern of $X_S$
and instead studies purely deterministic structural conditions.
The price we pay, however, is roughly a factor of $\rank(X_L)$ in what is
allowed for the support size of $X_S$ (relative to the probabilistic
analysis of~\citeauthor{CLMW09}).
Narrowing this gap with alternative deterministic conditions is an
interesting open problem.
Follow-up work to~\citep{CLMW09} studies the robustness of the recovery
procedure~\citep{ZWLCM10}, as well as quantitatively weaker conditions on
$X_S$~\citep{GWLCM10}, but these works are only considered under the random
support model.
Our work is therefore largely complementary to these probabilistic
analyses.

\subsection{Outline}

We describe our main results in Section~\ref{section:results}.
In Section~\ref{section:prelim}, we review a number of technical tools such
as matrix and operator norms that are used to characterize the
rank-sparsity incoherence properties of the desired decomposition.
Section~\ref{section:incoherence} analyses these incoherence properties in
detail, giving sufficient conditions for identifiability as well as for
certifying the (approximate) optimality of a target decomposition for our
optimization formulations.
The main recovery guarantees are proved in Sections~\ref{section:opt1}
and~\ref{section:opt2}.

\section{Main results} \label{section:results}

Fix an observation matrix $Y \in \mathbb{R}^{m \times n}$.
Our goal is to (approximately) decompose the matrix $Y$ into the sum of a
sparse matrix $X_S$ and a low-rank matrix $X_L$.

\subsection{Optimization formulations}

We consider two convex optimization problems over $(X_S,X_L) \in \mathbb{R}^{m
\times n} \times \mathbb{R}^{m \times n}$.
The first is the constrained formulation (parametrized by $\lambda > 0$,
$\epsilon_\v1 \geq 0$, and $\epsilon_* \geq 0$)
\begin{equation} \label{eq:opt1}
\begin{array}{cl}
\min & \lambda \|X_S\|_\v1 + \|X_L\|_* \\
\text{s.t.} & \|X_S+X_L-Y\|_\v1 \leq \epsilon_\v1 \\
& \|X_S+X_L-Y\|_* \leq \epsilon_*
\end{array}
\end{equation}
where $\|\cdot\|_\v1$ is the entry-wise $1$-norm, and $\|\cdot\|_*$ is the
trace norm (\emph{i.e.}, sum of singular values).
The second is the regularized formulation (with regularization parameter
$\mu > 0$)
\begin{equation} \label{eq:opt2}
\begin{array}{cl}
\min & \frac1{2\mu} \|X_S+X_L-Y\|_\v2^2 + \lambda \|X_S\|_\v1 + \|X_L\|_*
\end{array}
\end{equation}
where $\|\cdot\|_\v2$ is the Frobenius norm (entry-wise $2$-norm).

We also consider adding a constraint to control $\|X_L\|_\v\infty$, the
entry-wise $\infty$-norm of $X_L$.
To~\eqref{eq:opt1}, we add the constraint
\[ \|X_L\|_\v\infty \leq b \]
and to~\eqref{eq:opt2}, we add
\[ \|X_S-Y\|_\v\infty \leq b \]
The parameter $b$ is intended as a natural bound for $X_L$ and is typically
known in applications.
For example, in image processing, the values of interest may lie in the
interval $[0,255]$, and hence, we may take $b = 500$ as a relaxation of the
box constraint $[0,255]$.
The core of our analyses do not rely on these additional constraints; we
only consider them to obtain improved robustness guarantees for recovering
$X_L$, which may be important in some applications.

\subsection{Identifiability conditions}

Our first result is a refinement of the \emph{rank-sparsity incoherence}
notion developed by~\citet{CSPW09}.
We characterize a target decomposition of $Y$ into $Y = \bar{X}_S + \bar{X}_L$ by the
projection operators to subspaces associated with $\bar{X}_S$ and $\bar{X}_L$.
Let
\[
{\bar{\Omega}} \ = \
\Omega(\bar{X}_S) \ := \
\{ X \in \mathbb{R}^{m \times n} : \supp(X) \subseteq \supp(\bar{X}_S) \}
\]
be the space of matrices whose supports are subsets of the support of
$\bar{X}_S$, and let $\mathcal{P}_{{\bar{\Omega}}}$ be the orthogonal projector to ${\bar{\Omega}}$ under the
inner product $\ang{A,B} = \tr(A^\top B)$, where $\mathcal{P}_{\bar{\Omega}}(M)$ is given by
\[ [\mathcal{P}_{\bar{\Omega}}(M)]_{i,j}
= \left\{ \begin{array}{cl}
M_{i,j} & \text{if $(i,j) \in \supp(\bar{X}_S)$} \\
0 & \text{otherwise}
\end{array} \right.
\ \forall i \in [m], j \in [n]
.
\]
Furthermore, let
\[
{\bar{T}} \ = \
T(\bar{X}_L) \ := \
\{ X_1 + X_2 \in \mathbb{R}^{m \times n} : \range(X_1) \subseteq
\range(\bar{X}_L), \ \range(X_2^\top) \subseteq \range(\bar{X}_L^\top) \}
\]
be the span of matrices either in the row-space or column-space of $\bar{X}_L$,
and let $\mathcal{P}_{{\bar{T}}}$ be the orthogonal projector to ${\bar{T}}$, again, under the
inner product $\ang{A,B} = \tr(A^\top B)$; this is given by
\[ \mathcal{P}_{\bar{T}}(M) = \bar{U}\bU^\top M + M \bar{V}\bV^\top - \bar{U}\bU^\top M \bar{V}\bV^\top
\]
where $\bar{U} \in \mathbb{R}^{m \times \bar{r}}$ and $\bar{V} \in \mathbb{R}^{n \times \bar{r}}$ are,
respectively, matrices of left and right orthonormal singular vectors
corresponding to the non-zero singular values of $\bar{X}_L$, and $\bar{r}$ is the
rank of $\bar{X}_L$.
We will see that certain operator norms of $\mathcal{P}_{{\bar{\Omega}}}$ and $\mathcal{P}_{{\bar{T}}}$ can be
bounded in terms of structural properties of $\bar{X}_S$ and $\bar{X}_L$.
The first property measures the maximum number of non-zero entries in any
row or column of $\bar{X}_S$:
\begin{equation*}
\alpha(\rho) \ := \ \max\left\{ \rho \|\sign(\bar{X}_S)\|_{1\to1}, \
\rho^{-1} \|\sign(\bar{X}_S)\|_{\infty\to\infty} \right\}
\end{equation*}
where $\|M\|_{p\to q} := \max \{ \|Mv\|_q : v \in \mathbb{R}^n, \|v\|_p \leq 1 \}$,
\[
\sign(M)_{i,j} = \left\{ \begin{array}{rl}
-1 & \text{if $M_{i,j} < 0$} \\
0 & \text{if $M_{i,j} = 0$} \\
+1 & \text{if $M_{i,j} > 0$}
\end{array} \right.
\quad \forall i \in [m], j \in [n]
\]
and $\rho > 0$ is a balancing parameter to accommodate disparity between
the number of rows and columns; a natural choice for the balancing
parameter is $\rho := \sqrt{n/m}$.
We remark that $\rho$ is only a parameter for the analysis; the
optimization formulations do not directly involve $\rho$.
Note that $\bar{X}_S$ may have $\Omega(mn)$ non-zero entries and
$\alpha(\sqrt{n/m}) = O(\sqrt{mn})$ as long as the non-zero entries of
$\bar{X}_S$ are spread out over the entire matrix.
Conversely, a sparse matrix with just $O(m + n)$ could have
$\alpha(\sqrt{n/m}) = \sqrt{mn}$ by having all of its non-zero entries in
just a few rows and columns.

The second property measures the sparseness of the singular vectors of
$\bar{X}_L$:
\begin{equation*}
\beta(\rho) \ := \
\rho^{-1}\|\bar{U}\bU^\top\|_\v\infty
+ \rho \|\bar{V}\bV^\top\|_\v\infty
+ \|\bar{U}\|_{2\to\infty} \|\bar{V}\|_{2\to\infty}
.
\end{equation*}
For instance, if the singular vectors of $\bar{X}_L$ are perfectly aligned with
the coordinate axes, then $\beta(\rho) = \Omega(1)$.
On the other hand, if the left and right singular vectors have entries
bounded by $\sqrt{c/m}$ and $\sqrt{c/n}$, respectively, for some $c \geq
1$, then $\beta(\sqrt{n/m}) \leq 3c\bar{r}/\sqrt{mn}$.

Our main identifiability result is the following.
\begin{theorem} \label{theorem:identifiability}
If $\inf_{\rho > 0} \alpha(\rho) \beta(\rho) < 1$, then ${\bar{\Omega}} \cap {\bar{T}}
= \{ 0 \}$.
\end{theorem}
Theorem~\ref{theorem:identifiability} is an immediate consequence of the
following lemma (also given as Lemma~\ref{lemma:dual-composition-bound}).
\begin{lemma} \label{lemma:composition}
For all $M \in \mathbb{R}^{m\times n}$,
$\|\mathcal{P}_{{\bar{\Omega}}}(\mathcal{P}_{{\bar{T}}}(M))\|_\v1 \leq \inf_{\rho > 0} \alpha(\rho)
\beta(\rho) \|M\|_\v1$.
\end{lemma}
\begin{proof}[Proof of Theorem~\ref{theorem:identifiability}]
Take any $M \in {\bar{\Omega}} \cap {\bar{T}}$.
By Lemma~\ref{lemma:composition}, $\|\mathcal{P}_{{\bar{\Omega}}}(\mathcal{P}_{{\bar{T}}}(M))\|_\v1 \leq \alpha(\rho) \beta(\rho) \|M\|_\v1$.
On the other hand, $\mathcal{P}_{{\bar{\Omega}}}(\mathcal{P}_{{\bar{T}}}(M)) = M$, so $\alpha(\rho)\beta(\rho)
< 1$ implies $\|M\|_\v1 = 0$, \emph{i.e.}, $M = 0$.
\end{proof}
Clearly, if ${\bar{\Omega}} \cap {\bar{T}}$ contains a matrix other than $0$, then $\{ (\bar{X}_S
+ M, \bar{X}_L - M) : M \in {\bar{\Omega}} \cap {\bar{T}} \}$ gives a family of sparse/low-rank
decompositions of $Y = \bar{X}_S + \bar{X}_L$ with at least the same sparsity and
rank as $(\bar{X}_S,\bar{X}_L)$.
Conversely, if ${\bar{\Omega}} \cap {\bar{T}} = \{ 0 \}$, then any matrix in the direct sum
${\bar{\Omega}} \oplus {\bar{T}}$ has exactly one decomposition into a matrix $A \in {\bar{\Omega}}$
plus a matrix $B \in {\bar{T}}$, and in this sense $(\bar{X}_S,\bar{X}_L)$ is identifiable.

Note that, as we have argued above, the condition $\inf_{\rho>0}
\alpha(\rho)\beta(\rho) < 1$ may be achieved even by matrices $\bar{X}_S$ with
$\Omega(mn)$ non-zero entries, provided that the non-zero entries of $\bar{X}_S$
are sufficiently spread out, and that $\bar{X}_L$ is low-rank and has singular
vectors far from the coordinate bases.
This is in contrast with the conditions studied by~\citet{CSPW09}.
Their analysis uses a different characterization of $\bar{X}_S$ and $\bar{X}_L$,
which leads to a stronger identifiability condition in certain cases.
Roughly, if $\bar{X}_S$ has an approximately symmetric sparsity pattern (so
$\|\sign(\bar{X}_S)\|_{1\to1} \approx \|\sign(\bar{X}_S)\|_{\infty\to\infty}$), then
\citeauthor{CSPW09} require $\alpha(1) \sqrt{\beta(1)} < 1$ for square $n
\times n$ matrices.\footnote{\citet{CSPW09} do not explicitly work out the
non-square case, but claim that $n$ can be replaced in their analysis by
the larger matrix dimension $\max\{m,n\}$.  However this does not seem
possible, and the analysis there should only lead to the quite  suboptimal
dimensionality dependency $\min\{m,n\}$.
This is because a rectangular matrix $\bar{X}_L$ will have left and right singular
vectors of different dimensions and thus different allowable ranges of
infinity norms.}
Since $\beta(1) = \Omega(1/n)$ for any $\bar{X}_L \in \mathbb{R}^{n \times n}$, the
condition implies $\alpha(1)^2 = O(n)$.
Therefore $\bar{X}_S$ must have at most $O(n)$ non-zero entries (or else
$\alpha(1)^2$ becomes super-linear).
In other words, the fraction of non-zero entries allowed in $\bar{X}_S$ by the
condition $\alpha(1) \sqrt{\beta(1)} < 1$ is quickly vanishing as a
function of $n$.

\subsection{Recovery guarantees}

Our next results are guarantees on (approximately) recovering the
sparse/low-rank decomposition $(\bar{X}_S,\bar{X}_L)$ from $Y = \bar{X}_S + \bar{X}_L$ via
solving either convex optimization problems~\eqref{eq:opt1}
or~\eqref{eq:opt2}.
We require a mild strengthening of the condition $\inf_{\rho>0}
\alpha(\rho)\beta(\rho) < 1$, as well as appropriate settings of $\lambda >
0$ and $\mu > 0$ for our recovery guarantees.
Before continuing, we first define another property of $\bar{X}_L$:
\[
\gamma := \ \|\bar{U}\bar{V}^\top\|_\v\infty
\]
which is approximately the same as (in fact, bounded above by) the third
term in the definition of $\beta(\rho)$.
The quantities $\alpha(\rho)$, $\beta(\rho)$, and $\gamma$ are central to our analysis.
Therefore we state the following proposition for reference, which provides a more intuitive understanding of their behavior.
This is the only part in which explicit dimensional dependencies comes into our analysis.
\begin{proposition} \label{proposition:alpha-beta-gamma}
  Let $m_0$ the maximum number of non-zero entries of $\bar{X}_S$ per column and
  $n_0$ be the maximum number of non-zero entries of $\bar{X}_S$ per row.
  Let $\bar{r}$ be the  rank of $\bar{U}$ and $\bar{V}$.
  Assume further that $m_0 \leq c_1 m/\bar{r}$ and $n_0 \leq c_1 n/\bar{r}$ for some $c_1 \in (0,1)$, and
  $\|\bar{U}\|_\v\infty \leq \sqrt{c_2/m}$ and $\|\bar{V}\|_\v\infty \leq \sqrt{c_2/n}$ for some $c_2 >0$.
  Then with $\rho=\sqrt{n/m}$, we have
  \[
  \alpha(\rho) \leq \frac{c_1}{\bar{r}}\sqrt{mn} ,
  \qquad \beta(\rho) \leq \frac{3 c_2 \bar{r}}{\sqrt{mn}} ,
  \qquad \gamma \leq  \frac{c_2 \bar{r}}{\sqrt{mn}} .
  \]
\end{proposition}

We now proceed  with conditions for the regularized formulation~\eqref{eq:opt2}.
Let $E := Y - (\bar{X}_S + \bar{X}_L)$ and
\begin{align*}
\epsilon_{2\to2} & \ := \ \|E\|_{2\to2} \\
\epsilon_\v\infty & \ := \ \|E\|_{\v\infty} + \|\mathcal{P}_{\bar{T}}(E)\|_{\v\infty} .
\end{align*}
We require the following, for some $\rho > 0$ and $c > 1$:
\begin{align}
& \alpha(\rho) \beta(\rho) < 1
\label{eq:opt2-cond1} \\
& \lambda \ \leq \
\frac{(1 - \alpha(\rho)\beta(\rho))(1-c \cdot \mu^{-1} \epsilon_{2\to2})
- c \cdot \alpha(\rho) \mu^{-1} \epsilon_\v\infty
- c \cdot \alpha(\rho) \gamma}
{c \cdot \alpha(\rho)}
\label{eq:opt2-cond2} \\
& \lambda \ \geq \ c \cdot \frac{\gamma
+ \mu^{-1}
 (2 - \alpha(\rho) \beta(\rho)) \epsilon_\v\infty}
{1 - \alpha(\rho) \beta(\rho) - c \cdot \alpha(\rho) \beta(\rho)}
\ > \ 0
.
\label{eq:opt2-cond3}
\end{align}
For instance, if for some $\rho > 0$,
\begin{equation} \label{eq:opt2-simple1}
\alpha(\rho) \gamma \leq \frac{1}{41}
\quad \text{and} \quad
\alpha(\rho) \beta(\rho) \leq \frac{3}{41}
,
\end{equation}
then the conditions are satisfied for $c = 2$ provided that $\mu$ and
$\lambda$ are chosen to satisfy
\begin{equation} \label{eq:opt2-simple2}
\mu \ \geq \ \max\left\{4 \cdot \epsilon_{2\to2}, \ \frac{2}{15} \cdot \frac{\epsilon_\v\infty}{\lambda}
\right\}
\quad \text{and} \quad
\frac{15}{2} \cdot \gamma
\ \leq \ \lambda \ \leq \
\frac{15}{82} \cdot \frac1{\alpha(\rho)}
.
\end{equation}
Note that (\ref{eq:opt2-simple1}) can be satisfied when $c_1 \leq c_2^{-1} /41$ in Proposition~\ref{proposition:alpha-beta-gamma}.

For the constrained formulation~\eqref{eq:opt1}, our analysis requires the
same conditions as above, except with $E$ set to $0$.
Note that our analysis still allows for approximate decompositions; it is
only the conditions that are formulated with $E = 0$.
Specifically, we require for some $\rho > 0$ and $c > 1$:
\begin{align}
& \alpha(\rho) \beta(\rho) < 1
\label{eq:opt1-cond1} \\
& \lambda \ \leq \
\frac{1 - \alpha(\rho)\beta(\rho)
- c \cdot \alpha(\rho) \gamma}
{c \cdot \alpha(\rho)}
\label{eq:opt1-cond2} \\
& \lambda \ \geq \ c \cdot \frac{\gamma}
{1 - \alpha(\rho) \beta(\rho) - c \cdot \alpha(\rho) \beta(\rho)}
\ > \ 0
.
\label{eq:opt1-cond3}
\end{align}
For instance, if for some $\rho > 0$,
\begin{equation} \label{eq:opt1-simple1}
\alpha(\rho) \gamma \leq \frac{1}{15}
\quad \text{and} \quad
\alpha(\rho) \beta(\rho) \leq \frac{1}{5}
,
\end{equation}
then the conditions are satisfied for $c = 2$ provided that
$\lambda$ is chosen to satisfy
\begin{equation} \label{eq:opt1-simple2}
5\gamma
\ \leq \ \lambda \ \leq \
\frac1{3\alpha(\rho)}
.
\end{equation}
Note that (\ref{eq:opt1-simple1}) can be satisfied when $c_1 \leq c_2^{-1} /15$
in Proposition~\ref{proposition:alpha-beta-gamma}.

In summary, Proposition~\ref{proposition:alpha-beta-gamma} shows that
our results can be applied even with $m_0=\Omega(m/\bar{r})$ and
$n_0=\Omega(n/\bar{r})$ outliers. In contrast, the results of \citet{CSPW09} only apply
under the condition $\max(m_0,n_0) = O(\sqrt{\min(m,n)/\bar{r}})$, which is significantly stronger.
Moreover, unlike the analysis of~\citet{CLMW09}, we do not have to assume
that $\supp(\bar{X}_S)$ is random.

The following theorem gives our recovery guarantee for the constrained
formulation~\eqref{eq:opt1}.

\begin{theorem} \label{theorem:opt1}
Fix a target pair $(\bar{X}_S,\bar{X}_L) \in \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n}$
satisfying $\|Y - (\bar{X}_S+\bar{X}_L)\|_\v1 \leq \epsilon_\v1$ and $\|Y -
(\bar{X}_S+\bar{X}_L)\|_* \leq \epsilon_*$.
Assume the conditions~\eqref{eq:opt1-cond1}, \eqref{eq:opt1-cond2}, and
\eqref{eq:opt1-cond3} hold for some $\rho > 0$ and $c > 1$.
Let $(\hat{X}_S,\hat{X}_L) \in \mathbb{R}^{m \times n}$ be the solution to the convex
optimization problem~\eqref{eq:opt1}.
We have
\begin{multline*}
\max\left\{ \|\hat{X}_S-\bar{X}_S\|_\v1, \ \|\hat{X}_L-\bar{X}_L\|_\v1 \right\}
\\
\leq \
\left(
1 +
(1-1/c)^{-1} \cdot
\frac{2-\alpha(\rho)\beta(\rho)}{1-\alpha(\rho)\beta(\rho)}
\right)
\cdot \epsilon_\v1
+ (1-1/c)^{-1} \cdot
\frac{2-\alpha(\rho)\beta(\rho)}{1-\alpha(\rho)\beta(\rho)}
\cdot
\epsilon_* / \lambda
.
\end{multline*}
If, in addition for some $b \geq \|\bar{X}_L\|_\v\infty$, either:
\begin{itemize}
\item the optimization problem~\eqref{eq:opt1} is augmented with the
constraint $\|X_L\|_\v\infty \leq b$, or

\item $\hat{X}_L$ is post-processed by replacing $[\hat{X}_L]_{i,j}$ with
$\min\{ \max\{ [\hat{X}_L]_{i,j}, -b\}, b \}$ for all $i,j$,

\end{itemize}
then we also have
\[
\|\hat{X}_L-\bar{X}_L\|_\v2 \ \leq \ \min\left\{ \|\hat{X}_L-\bar{X}_L\|_\v1, \ \sqrt{2b
\cdot \|\hat{X}_L-\bar{X}_L\|_\v1}
\right\}
. \]
\end{theorem}
The proof of Theorem~\ref{theorem:opt1} is in Section~\ref{section:opt1}.
It is clear that if $Y = \bar{X}_S + \bar{X}_L$, then we can set $\epsilon_\v1 =
\epsilon_* = 0$ and we obtain exact recovery: $\hat{X}_S = \bar{X}_S$ and $\hat{X}_L =
\bar{X}_L$.
Moreover, any perturbation $Y - (\bar{X}_S + \bar{X}_L)$ affects the accuracy of
$(\hat{X}_S,\hat{X}_L)$ in entry-wise $1$-norm by an amount $O(\epsilon_\v1 +
\epsilon_* / \lambda)$.
Note that here, the parameter $\lambda$ serves to balance the entry-wise
$1$-norm and trace norm of the perturbation in the same way it is used in
the objective function of~\eqref{eq:opt1}.
So, for instance, if we have the simplified
conditions~\eqref{eq:opt1-simple1}, then we may choose $\lambda =
\sqrt{(5/3)\gamma/\alpha(\rho)}$ to satisfy \eqref{eq:opt1-simple2}, upon
which the error bound becomes
\[
\max\left\{ \|\hat{X}_S-\bar{X}_S\|_\v1, \ \|\hat{X}_L-\bar{X}_L\|_\v1 \right\}
\ = \
O\left(
\epsilon_\v1 + \sqrt{\frac{\alpha(\rho)}{\gamma}} \cdot \epsilon_*
\right)
.
\]
It is possible to modify the constraints in~\eqref{eq:opt1} to use norms
other than $\|\cdot\|_\v1$ and $\|\cdot\|_*$; the analysis could at the
very least be modified by simply using standard relationships to change
between norms, although this may introduce new slack in the bounds.
Finally, the second part of the theorem shows how the accuracy of $\hat{X}_L$
in Frobenius norm can be improved by adding an additional constraint or by
post-processing the solution.

Now we state our recovery guarantees for the regularized
formulation~\eqref{eq:opt2}.
\begin{theorem} \label{theorem:opt2}
Fix a target pair $(\bar{X}_S,\bar{X}_L) \in \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n}$.
Let $E := Y - (\bar{X}_S + \bar{X}_L)$ and
\begin{align*}
\epsilon_{2\to2} & \ := \ \|E\|_{2\to2} \\
\epsilon_\v\infty & \ := \ \|E\|_{\v\infty} + \|\mathcal{P}_{\bar{T}}(E)\|_{\v\infty} \\
\epsilon_*' & \ := \ \|\mathcal{P}_{\bar{T}}(E)\|_* .
\end{align*}
Let $\bar{k} := |\supp(\bar{X}_S)|$ and $\bar{r} := \rank(\bar{X}_L)$.
Assume the conditions~\eqref{eq:opt2-cond1}, \eqref{eq:opt2-cond2}, and
\eqref{eq:opt2-cond3} hold for some $\rho > 0$ and $c > 1$.
Let $(\hat{X}_S,\hat{X}_L) \in \mathbb{R}^{m \times n}$ be the solution to the convex
optimization problem~\eqref{eq:opt2} augmented with the constraint
$\|X_S-Y\|_\v\infty \leq b$ for some $b \geq \|\bar{X}_S-Y\|_\v\infty$ ($b =
\infty$ is allowed).
Let
\begin{align*}
\bar{r}' \ := \
& \left(\lambda + \mu^{-1} \epsilon_\v\infty \right)
\cdot \frac{2\bar{k}}{1-\alpha(\rho)\beta(\rho)}
\cdot \left( \lambda + \gamma + \mu^{-1} \epsilon_\v\infty \right)
\\
& {}
+ \left( 1 + 2\mu^{-1} \epsilon_{2\to2} \right)
\cdot 2\bar{r}
\cdot \left(
\frac{2\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)}
\cdot \left( \lambda + \gamma + \mu^{-1} \epsilon_\v\infty \right)
+ 1 + 2\mu^{-1} \epsilon_{2\to2}
\right)
.
\end{align*}
We have
\begin{align*}
\|\hat{X}_S-\bar{X}_S\|_\v1
& \ \leq \
\frac
{
\bar{r}' \cdot (1-1/c)^{-1}\lambda^{-1} \cdot \mu
+ \lambda \bar{k} \cdot \mu
+ 2\sqrt{\bar{k}\bar{r}} \cdot \mu
+ \bar{k} \cdot \epsilon_\v\infty
}
{1-\alpha(\rho)\beta(\rho)}
\\
\|\hat{X}_S-\bar{X}_S\|_\v2 & \ \leq \ \min\left\{ \|\hat{X}_S-\bar{X}_S\|_\v1, \
\sqrt{2b \cdot \|\hat{X}_S-\bar{X}_S\|_\v1}
\right\} \\
\|\hat{X}_L-\bar{X}_L\|_*
& \ \leq \
\sqrt{2\bar{r}} \cdot \|\hat{X}_S-\bar{X}_S\|_\v2
+ \epsilon_*'
+ \left( \frac{\bar{r}' \cdot (1-1/c)^{-1}}{2} + 2\bar{r} \right) \cdot \mu
.
\end{align*}
\end{theorem}
The proof of Theorem~\ref{theorem:opt2} is in Section~\ref{section:opt2}.
As before, if $Y = \bar{X}_S + \bar{X}_L$ so $E = 0$, then we can set $\mu \to 0$ and
obtain exact recovery with $\hat{X}_S = \bar{X}_S$ and $\hat{X}_L = \bar{X}_L$.
When the perturbation $E$ is non-zero, we control the accuracy of $\bar{X}_S$ in
entry-wise $1$-norm and $2$-norm, and the accuracy of $\bar{X}_L$ in trace norm.
Under the simplified conditions~\eqref{eq:opt2-simple1}, we can choose
$\lambda = (15/82)/\alpha(\rho)$ and $\mu =
\max\{4\epsilon_{2\to2}, 2\epsilon_\v\infty / (15\lambda)\}$ to satisfy
\eqref{eq:opt2-simple2}; this leads to the error bounds
\begin{align*}
& \|\hat{X}_S-\bar{X}_S\|_\v1
= O\left(
\bar{r}\alpha(\rho)
\cdot \max\left\{\epsilon_{2\to2}, \ \alpha(\rho) \epsilon_\v\infty \right\}
\right)
\\
& \|\hat{X}_L-\bar{X}_L\|_*
= O\left(
\sqrt{\bar{r}} \cdot
\min\left\{ \sqrt{b \cdot \|\hat{X}_S-\bar{X}_S\|_\v1}, \
\|\hat{X}_S-\bar{X}_S\|_\v1 \right\}
+ \epsilon_*'
+ \bar{r} \cdot \max\left\{\epsilon_{2\to2}, \ \alpha(\rho) \epsilon_\v\infty
\right\}
\right)
\end{align*}
(here, we have used the facts
$\bar{k} \leq \alpha(\rho)^2$,
$\alpha(\rho)\lambda = \Theta(1)$,
and $\bar{r}' = O(\bar{r})$, which also implies that
$\bar{k} \cdot \epsilon_\v\infty= O(\alpha(\rho) \cdot \alpha(\rho) \epsilon_\v\infty)$).
Finally, note that if the constraint $\|X_S-Y\|_\v\infty \leq b$ is added
(\emph{i.e.}, $b < \infty$), then the requirement $b \geq
\|\bar{X}_S-Y\|_\v\infty$ can be satisfied with $b := \|\bar{X}_S\|_\v\infty +
\epsilon_\v\infty$.
This allows for a possibly improved bound on $\|\hat{X}_L-\bar{X}_L\|_*$.

\subsection{Examples}

We illustrate our main results with some simple examples.

\subsubsection{Random models}

We first consider a random model for the matrices $\bar{X}_S$ and
$\bar{X}_L$~\citep{CSPW09}.
Let the support of $\bar{X}_S$ be chosen uniformly at random $\tilde{k}$
times over the $[m] \times [n]$ matrix entries (so that one entry can be selected multiple times).
The value of the entries in the chosen support can be arbitrary.
With high probability, we have
\[
\|\sign(\bar{X}_S)\|_{1\to1} = O\left( \frac{\tilde{k}\log n}{n} \right)
\quad \text{and} \quad
\|\sign(\bar{X}_S)\|_{\infty\to\infty} = O\left( \frac{\tilde{k}\log m}{m} \right)
\]
so for $\rho := \sqrt{(n \log m)/(m \log n)}$, we have
\[
\alpha(\rho) = O\left( \tilde{k} \sqrt{\frac{(\log m)(\log n)}{mn}} \right)
.
\]
The logarithmic factors are due to collisions in the random process.
Now let $\bar{U}$ and $\bar{V}$ be chosen uniformly at random over all families of
$\bar{r}$ orthonormal vectors in $\mathbb{R}^m$ and $\mathbb{R}^n$, respectively.
Using arguments similar to those in~\citep{CR09}, one can show that with
high probability,
\begin{align*}
& \|\bar{U}\bU^\top\|_\v\infty = O\left( \frac{\bar{r} \log m}{m} \right)
&
&
\|\bar{V}\bV^\top\|_\v\infty = O\left( \frac{\bar{r} \log n}{n} \right)
\\
& \|\bar{U}\|_{2\to\infty} = O\left( \sqrt{\frac{\bar{r} \log m}{m}} \right)
&
&
\|\bar{V}\|_{2\to\infty} = O\left( \sqrt{\frac{\bar{r} \log n}{n}} \right)
,
\end{align*}
so for the previously chosen $\rho$, we have
\[
\beta(\rho) = O\left( \bar{r} \sqrt{\frac{(\log m)(\log n)}{mn}} \right)
\quad \text{and} \quad
\gamma = O\left( \bar{r} \sqrt{\frac{(\log m)(\log n)}{mn}} \right)
.
\]
Therefore
\[
\alpha(\rho)\beta(\rho) = O\left( \frac{\tilde{k} \bar{r} (\log m)(\log n)}{mn} \right)
\quad \text{and} \quad
\alpha(\rho)\gamma = O\left( \frac{\tilde{k} \bar{r} (\log m)(\log n)}{mn} \right)
,
\]
both of which are $\ll 1$ provided that
\[
\tilde{k} \leq \delta \cdot \frac{mn}{\bar{r}(\log m)(\log n)}
\]
for a small enough constant $\delta \in (0,1)$.
In other words, when $\bar{X}_L$ is low-rank, the matrix $\bar{X}_S$ can have nearly
a constant fraction of its entries be non-zero while still allowing for
exact decomposition of $Y = \bar{X}_S + \bar{X}_L$.
Our guarantee improves over that of~\citet{CSPW09} by roughly a factor of
$\Omega((mn)^{1/4})$, but is worse by a factor of $\bar{r} (\log m) (\log n)$
relative to the guarantees of~\citet{CLMW09} for the random model.
Therefore there is a gap between our generic deterministic analysis and a
direct probabilistic analysis of this random model, and this gap seems
unavoidable with sparsity conditions based on $\alpha(\rho)$.
It is an interesting open problem to find alternative characterizations of
$\supp(\bar{X}_S)$ that can narrow or close this gap.

\subsubsection{Principal component analysis with outliers}

Suppose $\bar{X}_L$ is matrix of $m$ data points lying in a low-dimensional
subspace of $\mathbb{R}^n$, and $Z$ is a random matrix with independent Gaussian
noise entries with variance $\sigma^2$.
Then $Y' = \bar{X}_L + Z$ is the standard model for principal component
analysis.
We augment the model with a sparse noise component $\bar{X}_S$ to obtain $Y =
\bar{X}_S + \bar{X}_L + Z$; here, we allow the non-zero entries of $\bar{X}_S$ to possibly
approach infinity.

According to Theorem~\ref{theorem:opt2}, we need to estimate
$\|Z\|_{2\to2}$, $\|Z\|_\v\infty$, $\|\mathcal{P}_{\bar{T}}(Z)\|_\v\infty$, and
$\|\mathcal{P}_{\bar{T}}(Z)\|_*$.
We have the following with high probability~\citep{DS01},
\[
\|Z\|_{2\to2} \leq \sigma\sqrt{m} + \sigma\sqrt{n} + O(\sigma)
.
\]
Using standard arguments with the rotational invariance of the Gaussian
distribution, we also have
\[
\|Z\|_\v\infty  \leq O(\sigma \log(mn))
\quad \text{and} \quad
\|\mathcal{P}_{\bar{T}}(Z)\|_\v\infty \leq O(\sigma \log(mn))
\]
with high probability.
Finally, by Lemma~\ref{lemma:projections}, we have
\[
\|\mathcal{P}_{\bar{T}}(Z)\|_*
\leq 2\bar{r} \|Z\|_{2\to2}
\leq 2\bar{r}\sigma\sqrt{m} + 2\bar{r}\sigma\sqrt{n} + O(\bar{r}\sigma)
.
\]
Suppose $(\bar{X}_S,\bar{X}_L)$ has $\alpha(\rho) \leq c_1 (\sqrt{mn}/\bar{r})$,
$\beta(\rho) = \Theta(\bar{r}/\sqrt{mn})$, and $\gamma = \Theta(\bar{r}/\sqrt{mn})$
and satisfies the simplified condition~\eqref{eq:opt2-simple1}.
This can be achieved with $c_1 c_2 \leq 1/41$ in Proposition~\ref{proposition:alpha-beta-gamma}.
Also assume $\lambda$ and $\mu$ are chosen to
satisfy~\eqref{eq:opt2-simple2}, and that $b \geq \|\bar{X}_L\|_\v\infty +
\epsilon_\v\infty$.
Then we note that $\bar{k}= O(c_1^2 mn/\bar{r}^2)$, and thus have from Theorem~\ref{theorem:opt2}
(see the discussion thereafter):
\begin{align*}
\|\hat{X}_S-\bar{X}_S\|_\v1
& = O\left(
 c_1 \sqrt{mn}
\max\{ \sigma \sqrt{m} + \sigma \sqrt{n}, \ \sigma \sqrt{mn} \log(mn) / \bar{r} \}
\right)
\\
& = O\left(
\sigma c_1 mn \log(mn)/\bar{r}
\right)
\\
\|\hat{X}_L-\bar{X}_L\|_*
& = O\left(
\sqrt{b \sigma c_1 mn \log(mn)/\bar{r}}
+ \bar{r} \sigma (\sqrt{m} + \sqrt{n}))
+ c_1 \sqrt{mn}
\right)
,
\end{align*}
where we may take $b=O(\sigma \log(mn)+\|X_L\|_\v\infty))$.

Now consider the situation where both $m, n \to \infty$, and assume that
$\|\bar{X}_L\|_\v\infty$ remains bounded.
If $c_1 (\log(mn))^2 = o(1)$, which implies that the we have at most
$o(m/(\log(mn))^2)$ outliers per column and $o(n/(\log(mn))^2)$ outliers per row,
then
\[
\|\hat{X}_L-\bar{X}_L\|_* = O( \bar{r} \sigma (\sqrt{m} + \sqrt{n}) ) .
\]
That is, the normalized trace norm $\|\hat{X}_L-\bar{X}_L\|_*/\sqrt{nm} \to 0$. This means that we can correctly recover
the principal components of $\bar{X}_L$ with both outliers and random noise, when both $m$ and $n$ are large
and $c_1 (\log(mn))^2=o(1)$ in Proposition~\ref{proposition:alpha-beta-gamma}.

\section{Technical preliminaries} \label{section:prelim}

\subsection{Norms, inner products, and projections}

Our analysis involves a variety of norms of vectors, matrices (viewed as
elements of a vector space as well as linear operators of vectors), and
linear operators of matrices; we define these and related notions in this
section.

\subsubsection{Entry-wise norms}

For any $p \in [1,\infty]$, define $\|v\|_p := (\sum_i |v_i|^p)^{1/p}$ be
the $p$-norm of a vector $v$ (with $\|v\|_\infty := \max_i |v_i|$).
Also, define $\|M\|_\v{p} := (\sum_{i,j} |M_{i,j}|^p)^{1/p}$ to be the
entry-wise $p$-norm of a matrix $M$ (again, with $\|M\|_\v\infty :=
\max_{i,j} |M_{i,j}|$).
Note that $\|\cdot\|_\v2$ corresponds to the Frobenius norm.

\subsubsection{Inner products, linear operators, and orthogonal
projections}

We endow $\mathbb{R}^{m \times n}$ with the inner product $\ang{\cdot,\cdot}$
between matrices that induces the Frobenius norm $\|\cdot\|_\v2$; this is
given by $\ang{M,N} = \tr(M^\top N)$.

For a linear operator $\mathcal{T} : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$, we denote
its adjoint by $\mathcal{T}^*$; this is the unique linear operator that satisfies
$\ang{\mathcal{T}^*(M),N} = \ang{M,\mathcal{T}(N)}$ for all $M \in \mathbb{R}^{m \times n}$ and
$N \in \mathbb{R}^{m \times n}$
(in this work, we only consider bounded linear operators).
For any two linear operators $\mathcal{T}_1$ and $\mathcal{T}_2$, we let $\mathcal{T}_1 \circ \mathcal{T}_2$
denote their composition as defined by $(\mathcal{T}_1 \circ \mathcal{T}_2)(M) :=
\mathcal{T}_1(\mathcal{T}_2(M))$.

Given a subspace $W \subseteq \mathbb{R}^{m \times n}$, we let $W^\perp$ denote its
orthogonal complement, and let $\mathcal{P}_W : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$
denote the orthogonal projector to $W$ with respect to $\ang{\cdot,\cdot}$,
\emph{i.e.}, the unique linear operator with range $W$ and satisfying
${\mathcal{P}_W}^* = \mathcal{P}_W$ and $\mathcal{P}_W \circ \mathcal{P}_W = \mathcal{P}_W$.

\subsubsection{Induced norms}

For any two vector norms $\|\cdot\|_p$ and $\|\cdot\|_q$, define
$\|M\|_{p\to q} := \max_{x\neq0} \|Mx\|_q / \|x\|_p$ to be the corresponding
induced operator norm of a matrix $M$.
Our analysis uses the following special cases which have alternative
definitions:
\begin{itemize}
\item $\|M\|_{1\to1} = \max_j \|Me_j\|_1$,
\item $\|M\|_{1\to2} = \max_j \|Me_j\|_2$,
\item $\|M\|_{2\to2} = \text{spectral norm of $M$ (\emph{i.e.}, largest
singular value of $M$)}$,
\item $\|M\|_{2\to\infty} = \max_i \|M^\top e_i\|_2$, and
\item $\|M\|_{\infty\to\infty} = \max_i \|M^\top e_i\|_1$.
\end{itemize}
Here, $e_i$ is the $i$th coordinate vector which has a $1$ in the $i$th
position and $0$ elsewhere.

Finally, we also consider induced operator norms of linear matrix operators
$\mathcal{T} : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ (in particular, projection
operators with respect to $\ang{\cdot,\cdot}$).
For any two matrix norms $\|\cdot\|_{\diamondsuit}$ and
$\|\cdot\|_{\heartsuit}$, define $\|\mathcal{T}\|_{\diamondsuit\to\heartsuit} :=
\max_{M \neq 0} \|\mathcal{T}(M)\|_{\heartsuit} / \|M\|_{\diamondsuit}$.

\subsubsection{Other norms}

The trace norm (or nuclear norm) $\|M\|_*$ of a matrix $M$ is the sum of
the singular values of $M$.
We will also make use of a hybrid matrix norm $\|\cdot\|_{\sharp(\rho)}$,
parametrized by $\rho > 0$, which we define by
\[
\|M\|_{\sharp(\rho)}
:= \max\{ \rho\|M\|_{1\to1}, \ \rho^{-1} \|M\|_{\infty\to\infty} \}
.
\]
Also define $\|M\|_{\flat(\rho)} := \sup_{\|N\|_{\sharp(\rho)} \leq 1}
\ang{M,N}$, \emph{i.e.}, the dual of $\|\cdot\|_{\sharp(\rho)}$ (see
below).

\subsubsection{Dual pairs}

The matrix norm $\|\cdot\|_{\heartsuit}$ is said to be dual to
$\|\cdot\|_{\spadesuit}$ if, for all $M \in \mathbb{R}^{m \times n}$,
$\|M\|_{\heartsuit} = \sup_{\|N\|_{\spadesuit} \leq 1} \ang{M,N}$.

\begin{proposition} \label{proposition:holder}
Fix any matrix norm $\|\cdot\|_{\spadesuit}$, and let
$\|\cdot\|_{\heartsuit}$ be its dual.
For all $M \in \mathbb{R}^{m \times n}$ and $N \in \mathbb{R}^{m \times n}$, we have
\[
\ang{M,N} \leq \|M\|_{\spadesuit} \|N\|_{\heartsuit}
.
\]
\end{proposition}

\begin{proposition} \label{proposition:operator-dual}
Fix any any linear matrix operator $\mathcal{T} : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times
n}$ and any pair of matrix norms $\|\cdot\|_{\spadesuit}$ and
$\|\cdot\|_{\clubsuit}$.
We have
\[
\|\mathcal{T}\|_{\spadesuit\to\clubsuit}
\ = \
\|\mathcal{T}^*\|_{\diamondsuit\to\heartsuit}
,
\]
where $\|\cdot\|_{\heartsuit}$ is dual to $\|\cdot\|_{\spadesuit}$,
and $\|\cdot\|_{\diamondsuit}$ is dual to $\|\cdot\|_{\clubsuit}$.
\end{proposition}

The following pairs of matrix norms are dual to each other:
\begin{enumerate}
\item $\|\cdot\|_\v{p}$ and $\|\cdot\|_\v{q}$ where $1/p + 1/q = 1$;

\item $\|\cdot\|_*$ and $\|\cdot\|_{2\to2}$;

\item $\|\cdot\|_{\sharp(\rho)}$ and $\|\cdot\|_{\flat(\rho)}$ (by
definition).

\end{enumerate}

\subsubsection{Some lemmas}

First we show that the $\|\cdot\|_{\sharp(\rho)}$ norm (for any $\rho > 0$)
bounds the spectral norm $\|\cdot\|_{2\to2}$.
\begin{lemma} \label{lemma:spectral-bound}
For any $M \in \mathbb{R}^{m\times n}$, we have for all $\rho > 0$,
\[
\|M\|_{2\to2} \leq \|M\|_{\sharp(\rho)} .
\]
\end{lemma}
\begin{proof}
Let $\sigma$ be the largest singular value of $M$, and let $u \in \mathbb{R}^m$ and
$v \in \mathbb{R}^n$ be, respectively, associated left and right singular vectors.
Then
\[
\left\| \left[ \begin{array}{cc}
0 & \rho M \\
\rho^{-1} M^\top & 0
\end{array} \right]
\left[ \begin{array}{c}
\rho^{1/2} u \\
\rho^{-1/2} v
\end{array} \right]
\right\|_1
=
\left\|
\left[ \begin{array}{c}
\rho^{1/2} Mv \\
\rho^{-1/2} M^\top u
\end{array} \right]
\right\|_1
=
\sigma \left\|
\left[ \begin{array}{c}
\rho^{1/2} u \\
\rho^{-1/2} v
\end{array} \right]
\right\|_1
.
\]
Moreover, by definition of $\|\cdot\|_{1\to1}$,
\[
\left\| \left[ \begin{array}{cc}
0 & \rho M \\
\rho^{-1/2} M^\top & 0
\end{array} \right]
\left[ \begin{array}{c}
\rho^{1/2} u \\
\rho^{-1/2} v
\end{array} \right]
\right\|_1
\leq
\left\| \left[ \begin{array}{cc}
0 & \rho M \\
\rho^{-1} M^\top & 0
\end{array} \right]
\right\|_{1\to1}
\left\|
\left[ \begin{array}{c}
\rho^{1/2} u \\
\rho^{-1/2} v
\end{array} \right]
\right\|_1
.
\]
Therefore
\begin{align*}
\|M\|_{2\to2}
\ = \sigma
& \leq \left\| \left[ \begin{array}{cc}
0 & \rho M \\
\rho^{-1} M^\top & 0
\end{array} \right]
\right\|_{1\to1} \\
& = \max\{ \|\rho^{-1} M^\top\|_{1\to1}, \|\rho M\|_{1\to1}\}
\ = \max\{ \rho^{-1} \|M\|_{\infty\to\infty}, \rho \|M\|_{1\to1}\}
\ = \|M\|_{\sharp(\rho)}
.
\qedhere
\end{align*}
\end{proof}

The following lemma is the dual of Lemma~\ref{lemma:spectral-bound}.

\begin{lemma} \label{lemma:trace-bound}
For any $M \in \mathbb{R}^{m\times n}$, we have for all $\rho > 0$,
\[
\|M\|_{\flat(\rho)} \leq \|M\|_* .
\]
\end{lemma}
\begin{proof}
We know that $\|M\|_{\flat(\rho)}=\ang{M,N}$ for some matrix $N$ such that
$\|N\|_{\sharp(\rho)}=1$.
Therefore $\|N\|_{2\to2} \leq 1$ from Lemma~\ref{lemma:spectral-bound}, and
thus using Proposition~\ref{proposition:holder},
\[
\|M\|_{\flat(\rho)}= \ang{M,N} \leq \|M\|_{*}\|N\|_{2\to2} \leq \|M\|_* .
\qedhere
\]
\end{proof}

Finally we state a lemma concerning the invertibility of a certain block-form
operator used in our analysis.
\begin{lemma} \label{lemma:block-inverse}
Fix any matrix norm $\|\cdot\|_\spadesuit$ on $\mathbb{R}^{m \times n}$ and linear
operators $\mathcal{T}_1 : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ and $\mathcal{T}_2 : \mathbb{R}^{m
\times n} \to \mathbb{R}^{m \times n}$.
Let $\mathcal{I} : \mathbb{R}^{m \times n} \to \mathbb{R}^{m \times n}$ be the identity operator,
and suppose $\|\mathcal{T}_1 \circ \mathcal{T}_2\|_{\spadesuit\to\spadesuit} < 1$.
\begin{enumerate}
\item $\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2$ is invertible and satisfies
\[
\|(\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1}\|_{\spadesuit\to\spadesuit}
\leq
\frac{1}{1 - \|\mathcal{T}_1 \circ \mathcal{T}_2\|_{\spadesuit\to\spadesuit}}
. \]

\item The linear operator on $\mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n}$
\[
\left[ \begin{array}{cc}
\mathcal{I} & \mathcal{T}_1 \\
\mathcal{T}_2 & \mathcal{I}
\end{array} \right]
\]
is invertible, and its inverse is given by
\begin{align*}
\left[ \begin{array}{cc}
\mathcal{I} & \mathcal{T}_1 \\
\mathcal{T}_2 & \mathcal{I}
\end{array} \right]^{-1}
& =
\left[ \begin{array}{cc}
(\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1}
& -(\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1} \circ \mathcal{T}_1
\\
-\mathcal{T}_2 \circ (\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1}
& \mathcal{I} + \mathcal{T}_2 \circ (\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1} \circ \mathcal{T}_1
\end{array} \right]
\\
& =
\left[ \begin{array}{cc}
(\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1}
& -(\mathcal{I} - \mathcal{T}_1 \circ \mathcal{T}_2)^{-1} \circ \mathcal{T}_1
\\
-(\mathcal{I} - \mathcal{T}_2 \circ \mathcal{T}_1)^{-1} \circ \mathcal{T}_2
& (\mathcal{I} - \mathcal{T}_2 \circ \mathcal{T}_1)^{-1}
\end{array} \right]
.
\end{align*}

\end{enumerate}
\end{lemma}
\begin{proof}
The first claim is a standard application of Taylor expansions.
The second claim then follows from formulae of block matrix inverses using
Schur complements.
\end{proof}

\subsection{Projection operators and subdifferential sets}

Recall the definitions of the following subspaces
\begin{equation*}
\Omega(X_S) := \{ X \in \mathbb{R}^{m \times n} : \supp(X) \subseteq
\supp(X_S) \}
\end{equation*}
and
\begin{equation*}
T(X_L) := \{ X_1 + X_2 \in \mathbb{R}^{m \times n} : \range(X_1) \subseteq
\range(X_L), \range(X_2^\top) \subseteq \range(X_L^\top) \}
.
\end{equation*}
The orthogonal projectors to these spaces are given in the following
proposition.
\begin{proposition} \label{proposition:projections}
Fix any $X_S \in \mathbb{R}^{m \times n}$ and $X_L \in \mathbb{R}^{m \times n}$.
For any matrix $M \in \mathbb{R}^{m \times n}$,
\[ [\mathcal{P}_{\Omega(X_S)}(M)]_{i,j}
= \left\{ \begin{array}{cl}
M_{i,j} & \text{if $(i,j) \in \supp(X_S)$} \\
0 & \text{otherwise}
\end{array} \right.
\]
for all $1 \leq i \leq m$ and $1 \leq j \leq n$,
and
\[ \mathcal{P}_{T(X_L)}(M) = UU^\top M + M VV^\top - UU^\top M VV^\top
\]
where $U$ and $V$ are the matrices of left and right singular vectors of
$X_L$.
\end{proposition}
\begin{lemma} \label{lemma:projections}
Under the setting of Proposition~\ref{proposition:projections},
\begin{align*}
\|\mathcal{P}_{\Omega(X_S)}(M)\|_\v1 & \leq \sqrt{|\supp(X_S)|}
\|\mathcal{P}_{\Omega(X_S)}(M)\|_\v2 \leq \sqrt{|\supp(X_S)|} \|M\|_\v2 \\
\|\mathcal{P}_{\Omega(X_S)}(M)\|_\v1 & \leq |\supp(X_S)|
\|\mathcal{P}_{\Omega(X_S)}(M)\|_\v\infty \leq |\supp(X_S)| \|M\|_\v\infty \\
\|\mathcal{P}_{T(X_L)}(M)\|_{2\to2} & \leq 2 \|M\|_{2\to2} \\
\|\mathcal{P}_{T(X_L)}(M)\|_* & \leq 2 \rank(X_L) \|M\|_{2\to2} \\
\|\mathcal{P}_{T(X_L)}(M)\|_\v2 & \leq 2\sqrt{\rank(X_L)} \|M\|_{2\to2}
.
\end{align*}
\end{lemma}
\begin{proof}
The first and second claims rely on the fact that
$|\supp(\mathcal{P}_{\Omega(X_S)}(M))| \leq |\supp(X_S)|$, as well as the fact that
$\mathcal{P}_{\Omega(X_S)}$ is an orthonormal projector with respect to the inner
product that induces the $\|\cdot\|_\v2$ norm.
For the third claim, note that
\[ \|\mathcal{P}_{T(X_L)}(M)\|_{2\to2}
\leq \|UU^\top M\|_{2\to2} + \|(I-UU^\top)MVV^\top\|_{2\to2}
\leq 2\|M\|_{2\to2}
. \]
The remaining claims use a similar decomposition as the third claim as well
as the fact that
\[ \max\{\rank(UU^\top M),\rank((I-UU^\top)MVV^\top)\} \leq \rank(X_L) .
\qedhere
\]
\end{proof}

Define
\[
\sign(X_S) \in \{-1,0,+1\}^{m\times n}
\]
to be the matrix whose $(i,j)$th entry is $\sign([X_S]_{i,j})$,
and define
\[
\orth(X_L) := UV^\top ,
\]
where $U$ and $V$, respectively, are
matrices of the left and right orthonormal singular vectors of $X_L$
corresponding to non-zero singular values.
The following proposition characterizes the subdifferential sets for the
non-smooth norms $\|\cdot\|_\v1$ and $\|\cdot\|_*$~\citep{W92}.
\begin{proposition} \label{proposition:subgradient}
The subdifferential set of $X_S \mapsto \|X_S\|_\v1$ is
\begin{equation*}
\partial_{X_S} (\|X_S\|_\v1)
= \{ G \in \mathbb{R}^{m \times n} : \|G\|_\v\infty \leq 1, \mathcal{P}_{\Omega(X_S)}(G)
= \sign(X_S) \}
;
\end{equation*}
the subdifferential set of $X_L \mapsto \|X_L\|_*$ is
\begin{equation*}
\partial_{X_L} (\|X_L\|_*)
= \{ G \in \mathbb{R}^{m \times n} : \|G\|_{2\to2} \leq 1, \mathcal{P}_{T(X_L)}(G) =
\orth(X_L)
\}
.
\end{equation*}
\end{proposition}

The following lemma is a simple consequence of subgradient properties.
\begin{lemma} \label{lemma:subgradient}
Fix $\lambda > 0$ and define the function $g(X_S,X_L) := \lambda
\|X_S\|_\v1 + \|X_L\|_*$.
Consider any $(\bar{X}_S,\bar{X}_L)$ in $\mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n}$.
If there exists $Q \in \mathbb{R}^{m \times n}$ such that: $Q$ is a subgradient of
$\lambda \|X_S\|_\v1$ at $X_S=\bar{X}_S$, $Q$ is a subgradient of $\|X_L\|_*$ at
$X_L=\bar{X}_L$, and $\|\mathcal{P}_{\Omega(\bar{X}_S)^\perp}(Q)\|_\v\infty \leq \lambda / c$ and
$\|\mathcal{P}_{T(\bar{X}_L)^\perp}(Q)\|_{2\to2} \leq 1 / c$ for some $c > 1$, then
\[
g(X_S,X_L) - g(\bar{X}_S,\bar{X}_L)
\ \geq \
\ang{Q,X_S + X_L - \bar{X}_S - \bar{X}_L}
+ (1-1/c) \left( \lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp}(X_S - \bar{X}_S)\|_\v1
+ \|\mathcal{P}_{{\bar{T}}^\perp}(X_L - \bar{X}_L)\|_* \right)
\]
for all $(X_S,X_L) \in \mathbb{R}^{m \times n} \times \mathbb{R}^{m \times n}$.
\end{lemma}
\begin{proof}
Let ${\bar{\Omega}} := \Omega(\bar{X}_S)$, ${\bar{T}} := T(\bar{X}_L)$, ${\Delta_S} := X_S - \bar{X}_S$, and ${\Delta_L}
: X_L - \bar{X}_L$.
For any subgradient $G \in \partial_{X_S}(\lambda\|\bar{X}_S\|_\v1)$, we have $G
- Q = \mathcal{P}_{{\bar{\Omega}}}(G) + \mathcal{P}_{{\bar{\Omega}}^\perp}(G) - \mathcal{P}_{{\bar{\Omega}}}(Q) - \mathcal{P}_{{\bar{\Omega}}^\perp}(Q) =
\mathcal{P}_{{\bar{\Omega}}^\top}(G) - \mathcal{P}_{{\bar{\Omega}}^\top}(Q)$.
Therefore
\begin{align*}
\lefteqn{
\lambda \|\bar{X}_S + {\Delta_S}\|_\v1 - \lambda \|\bar{X}_S\|_\v1 - \ang{Q,{\Delta_S}}
} \\
& \geq \sup \{ \ang{G,{\Delta_S}}
- \ang{Q,{\Delta_S}} : G \in \partial_{X_S}(\lambda \|\bar{X}_S\|_\v1) \}\\
& \geq \sup \{ \ang{G-Q,{\Delta_S}} : G \in \partial_{X_S}(\lambda \|\bar{X}_S\|_\v1) \} \\
& = \sup \{ \ang{\mathcal{P}_{{\bar{\Omega}}^\perp}(G) - \mathcal{P}_{{\bar{\Omega}}^\perp}(Q),{\Delta_S}}
: G \in \partial_{X_S}(\lambda \|\bar{X}_S\|_\v1) \} \\
& = \sup \{ \ang{\mathcal{P}_{{\bar{\Omega}}^\perp}(G) - \mathcal{P}_{{\bar{\Omega}}^\perp}(Q),\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})}
: G \in \partial_{X_S}(\lambda \|\bar{X}_S\|_\v1) \} \\
& = \sup \{ \ang{\mathcal{P}_{{\bar{\Omega}}^\perp}(G),\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})}
- \ang{\mathcal{P}_{{\bar{\Omega}}^\perp}(Q),\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})}
: G \in \partial_{X_S}(\lambda \|\bar{X}_S\|_\v1) \} \\
& = \lambda  \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
- \ang{\mathcal{P}_{{\bar{\Omega}}^\perp}(Q),\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})} \\
& \geq \lambda  \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
- \|\mathcal{P}_{{\bar{\Omega}}^\perp}(Q)\|_\v\infty \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1 \\
& \geq \lambda  (1-1/c) \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
\end{align*}
where the second-to-last inequality uses the duality of $\|\cdot\|_\v1$ and
$\|\cdot\|_\v\infty$ and Proposition~\ref{proposition:operator-dual}.
Similarly,
\begin{align*}
\|\bar{X}_L - {\Delta_L}\|_* - \|\bar{X}_L\|_* -\ang{Q,{\Delta_L}}
& \geq (1-1/c) \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_*
\end{align*}
by noting the duality of $\|\cdot\|_*$ and $\|\cdot\|_{2\to2}$.
Combining these gives the desired inequality.
\end{proof}

\section{Rank-sparsity incoherence} \label{section:incoherence}

Throughout this section, we fix a target $(\bar{X}_S,\bar{X}_L) \in \mathbb{R}^{m \times n}
\times \mathbb{R}^{m \times n}$, and let ${\bar{\Omega}} := \Omega(\bar{X}_S)$ and ${\bar{T}} :=
T(\bar{X}_L)$.
Also let $\bar{U}$ and $\bar{V}$ be, respectively, matrices of the left and right
singular vectors of $\bar{X}_L$ corresponding to non-zero singular values.
Recall the following structural properties of $\bar{X}_S$ and $\bar{X}_L$:
\begin{align*}
\alpha(\rho) & \ := \ \|\sign(\bar{X}_S)\|_{\sharp(\rho)}
\ = \ \max\{ \rho \|\sign(\bar{X}_S)\|_{1\to1}, \ \rho^{-1}
\|\sign(\bar{X}_S)\|_{\infty\to\infty} \}
; \\
\beta(\rho) &
\ := \ \rho^{-1}\|\bar{U}\bU^\top\|_\v\infty
+ \rho \|\bar{V}\bV^\top\|_\v\infty
+ \|\bar{U}\|_{2\to\infty} \|\bar{V}\|_{2\to\infty}
; \\
\gamma & \ := \ \|\orth(\bar{X}_L)\|_\v\infty \ = \ \|\bar{U}\bar{V}^\top\|_\v\infty
.
\end{align*}
The parameter $\rho$ is a balancing parameter to handle disparity between
row and column dimensions.
The quantity $\alpha(\rho)$ is the maximum number of non-zero entries
in any single row or column.
The quantities $\beta(\rho)$ and $\gamma$ measure the coherence of the
singular vectors of $\bar{X}_L$, that is, the alignment of the singular vectors
with the coordinate bases.
For instance, under the conditions of Proposition~\ref{proposition:alpha-beta-gamma},
we have (with $\rho=\sqrt{n/m}$)
\[
\alpha(\rho) \leq c_1\sqrt{mn} , \quad
\beta\left(\rho \right)
\ \leq \ \frac{3c_2\rank(\bar{X}_L)}{\sqrt{mn}}
\quad \text{and} \quad
\gamma \ \leq \ \frac{c_2\rank(\bar{X}_L)}{\sqrt{mn}}
 \]
for some constants $c_1$ and $c_2$.

\subsection{Operator norms of projection operators}

We show that under the condition $\inf_{\rho > 0} \alpha(\rho)\beta(\rho) <
1$, the pair $(\bar{X}_S,\bar{X}_L)$ is identifiable from its sum $\bar{X}_S +
\bar{X}_L$~(Theorem~\ref{theorem:identifiability}).
This is achieved by proving that the composition of projection operators
$\mathcal{P}_{{\bar{\Omega}}}$ and $\mathcal{P}_{{\bar{T}}}$ is a contraction as per
Lemma~\ref{lemma:composition}, which in turn implies that ${\bar{\Omega}} \cap {\bar{T}} =
\{0\}$.

The following two lemmas bound the projection operators $\mathcal{P}_{{\bar{\Omega}}}$ and
$\mathcal{P}_{{\bar{T}}}$ in complementary norms.
\begin{lemma} \label{lemma:sparse-bound}
For any $M \in \mathbb{R}^{m\times n}$ and $p \in \{1,\infty\}$, we have
\[ \|\mathcal{P}_{{\bar{\Omega}}}(M)\|_{p\to p} \leq \|\sign(\bar{X}_S)\|_{p \to p} \|M\|_\v\infty . \]
This implies, for all $\rho > 0$,
\[ \|\mathcal{P}_{{\bar{\Omega}}}\|_{\v\infty\to\sharp(\rho)} \leq \alpha(\rho) . \]
\end{lemma}
\begin{proof}
Define $s(X_S) \in \{0,1\}^{m \times n}$ to be the entry-wise absolute
value of $\sign(X_S)$.
We have
\begin{align*}
\|\mathcal{P}_{{\bar{\Omega}}}(M)\|_{p \to p}
& = \max\{ \|\mathcal{P}_{{\bar{\Omega}}}(M)v\|_p : \|v\|_p \leq 1 \} \\
& \leq \|\mathcal{P}_{\bar{\Omega}}(M)\|_\v\infty \max\{ \|s(\mathcal{P}_{{\bar{\Omega}}}(M))v\|_p : \|v\|_p \leq 1 \} \\
& \leq \|M\|_\v\infty \max\{ \|s(\bar{X}_S)v\|_p : \|v\|_p \leq 1 \} \\
& = \|M\|_\v\infty \|\sign(\bar{X}_S)\|_{p \to p}
.
\end{align*}
The second part follows from the definitions of $\|\cdot\|_{\sharp(\rho)}$ and
$\alpha(\rho)$.
\end{proof}

\begin{lemma} \label{lemma:lowrank-bound}
For any $M \in \mathbb{R}^{m\times n}$, we have
\[ \|\mathcal{P}_{{\bar{T}}}(M)\|_\v\infty \leq
\|\bar{U}\bU^\top\|_\v\infty \|M\|_{1\to1}
+ \|\bar{V}\bV^\top\|_\v\infty \|M\|_{\infty\to\infty}
+ \|\bar{U}\|_{2\to\infty} \|\bar{V}\|_{2\to\infty} \|M\|_{2\to2}
. \]
This implies, for all $\rho > 0$,
\[ \|\mathcal{P}_{{\bar{T}}}\|_{\sharp(\rho)\to\v\infty} \leq \beta(\rho) . \]
\end{lemma}
\begin{proof}
We have $\|\mathcal{P}_{{\bar{T}}}(M)\|_\v\infty = \|\bar{U}\bU^\top M + M\bar{V}\bV^\top -
\bar{U}\bU^\top M \bar{V}\bV^\top\|_\v\infty \leq \|\bar{U}\bU^\top M\|_\v\infty +
\|M\bar{V}\bV^\top\|_\v\infty + \|\bar{U}\bU^\top M \bar{V}\bV^\top\|_\v\infty$ by the
triangle inequality.
The bounds for each term now follow from the definitions:
\begin{align*}
\|\bar{U}\bU^\top M\|_\v\infty
& = \max_i \|M^\top \bar{U}\bU^\top e_i\|_\infty \\
& \leq \|M^\top\|_{\infty\to\infty} \max_i \|\bar{U}\bU^\top e_i\|_\infty \\
& = \|M\|_{1\to1} \|\bar{U}\bU^\top\|_\v\infty
;
\end{align*}
\begin{align*}
\|M\bar{V}\bV^\top\|_\v\infty
& = \max_j \|M\bar{V}\bV^\top e_j\|_\infty \\
& \leq \|M\|_{\infty\to\infty} \max_j \|\bar{V}\bV^\top e_j\|_\infty \\
& = \|M\|_{\infty\to\infty} \|\bar{V}\bV\|_\v\infty
;
\end{align*}
and
\begin{align*}
\|\bar{U}\bU^\top M\bar{V}\bV^\top\|_\v\infty
& = \max_{i,j} |e_i^\top \bar{U}(\bar{U}^\top M \bar{V}) \bar{V}^\top e_j| \\
& \leq \max_{i,j} \|\bar{U}^\top e_i\|_2 \|\bar{U}^\top M \bar{V}\|_{2\to2} \|\bar{V}^\top
e_j\|_2
\quad \text{(Cauchy-Schwarz)} \\
& \leq \|M\|_{2\to2} \|\bar{U}\|_{2\to\infty} \|\bar{V}\|_{2\to\infty} \\
& \leq \|M\|_{\sharp(\rho)} \|\bar{U}\|_{2\to\infty} \|\bar{V}\|_{2\to\infty}
\quad \text{(Lemma~\ref{lemma:spectral-bound})}
.
\end{align*}
The second part now follows the definition of $\beta(\rho)$.
\end{proof}

Now we show that the composition of $\mathcal{P}_{{\bar{\Omega}}}$ and $\mathcal{P}_{{\bar{T}}}$ gives a
contraction under the certain norms and their duals.
\begin{lemma} \label{lemma:composition-bound}
For all $\rho>0$,
\begin{enumerate}
\item $\|\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}}\|_{\sharp(\rho)\to\sharp(\rho)}
\leq \alpha(\rho) \beta(\rho)$;
\item $\|\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}}\|_{\v\infty\to\v\infty} \leq \alpha(\rho)
\beta(\rho)$;
\end{enumerate}
\end{lemma}
\begin{proof}
Immediate from Lemma~\ref{lemma:sparse-bound} and
Lemma~\ref{lemma:lowrank-bound}.
\end{proof}

\begin{lemma} \label{lemma:dual-composition-bound}
For all $\rho>0$,
\begin{enumerate}
\item $\|\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}}\|_{\flat(\rho)\to\flat(\rho)}
\leq \alpha(\rho) \beta(\rho)$;
\item $\|\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}}\|_{\v1\to\v1}
\leq \alpha(\rho) \beta(\rho)$.
\end{enumerate}
\end{lemma}
\begin{proof}
First note that $(\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}})^* = \mathcal{P}_{{\bar{\Omega}}}^* \circ \mathcal{P}_{{\bar{T}}}^*
= \mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}}$ because $\mathcal{P}_{{\bar{\Omega}}}$ and $\mathcal{P}_{{\bar{T}}}$ are
self-adjoint, and similarly $(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})^* = \mathcal{P}_{{\bar{T}}} \circ
\mathcal{P}_{{\bar{\Omega}}}$.
Now the claim follows by Proposition~\ref{proposition:operator-dual} and
Lemma~\ref{lemma:composition-bound}, using the facts that
$\|\cdot\|_{\flat(\rho)}$ is dual to $\|\cdot\|_{\sharp(\rho)}$ and that
$\|\cdot\|_\v1$ is dual to $\|\cdot\|_\v\infty$.
\end{proof}
Note that Lemma~\ref{lemma:composition} is encompassed by
Lemma~\ref{lemma:dual-composition-bound}.
Another consequence of these contraction properties is the following
uncertainty principle, analogous to one stated by~\citet{CSPW09},
which effectively states that a matrix $X$ cannot have both
$\|\sign(X)\|_{\sharp(\rho)}$ and $\|\orth(X)\|_\v\infty$ simultaneously
small.
\begin{theorem} \label{theorem:uncertainty}
If $X = \bar{X}_S = \bar{X}_L \neq 0$, then $\inf_{\rho > 0}
\alpha(\rho)\beta(\rho) \geq 1$.
\end{theorem}
\begin{proof}
Note that the non-zero element $X$ lives in ${\bar{\Omega}} \cap {\bar{T}}$, so we get the
conclusion by the contrapositive of Theorem~\ref{theorem:identifiability}.
\end{proof}

\subsection{Dual certificate}

The incoherence properties allow us to construct an approximate dual
certificate $(Q_{\bar{\Omega}}, Q_{\bar{T}}) \in {\bar{\Omega}} \times {\bar{T}}$ that is central to the
analysis of the optimization problems~\eqref{eq:opt1} and~\eqref{eq:opt2}.

The certificate is constructed as the solution to the linear system
\[
\left\{ \begin{array}{rcr}
\mathcal{P}_{{\bar{\Omega}}}(Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E) & = & \lambda \sign(\bar{X}_S) \\
\mathcal{P}_{{\bar{T}}}(Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E) & = & \orth(\bar{X}_L)
\end{array} \right.
\]
for some matrix $E \in \mathbb{R}^{m \times n}$; this can be equivalently written
as
\[
\left[ \begin{array}{cc}
\mathcal{I} & \mathcal{P}_{{\bar{\Omega}}} \\
\mathcal{P}_{{\bar{T}}} & \mathcal{I}
\end{array} \right]
\left[ \begin{array}{c}
Q_{\bar{\Omega}} \\
Q_{\bar{T}} \\
\end{array} \right]
=
\left[ \begin{array}{r}
\lambda \sign(\bar{X}_S) - \mu^{-1} \mathcal{P}_{{\bar{\Omega}}}(E) \\
\orth(\bar{X}_L) - \mu^{-1} \mathcal{P}_{{\bar{T}}}(E)
\end{array} \right]
.
\]
We show the existence of the dual certificate $(Q_{\bar{\Omega}},Q_{\bar{T}})$ under the
conditions~\eqref{eq:opt2-cond1}, \eqref{eq:opt2-cond2}, and
\eqref{eq:opt2-cond3} relative to an arbitrary matrix $E$.
Recall that the recovery guarantees for the constrained formulation
requires the conditions with $E = 0$, while the guarantees for the
regularized formulation takes $E = Y - (\bar{X}_S + \bar{X}_L)$.
\begin{theorem} \label{theorem:dual-cert}
Pick any $c > 1$, $\rho > 0$, and $E \in \mathbb{R}^{m \times n}$.
Let $\bar{k} := |\supp(\bar{X}_S)|$ and $\bar{r} := \rank(\bar{X}_L)$.
Let
\begin{align*}
\epsilon_{2\to2} & := \|E\|_{2\to2} \\
\epsilon_\v\infty & := \|E\|_{\v\infty} + \|\mathcal{P}_{\bar{T}}(E)\|_{\v\infty} .
\end{align*}
If the following conditions hold:
\begin{align}
& \alpha(\rho) \beta(\rho) < 1
\label{eq:cond1} \\
&
\lambda \ \leq \
\frac{(1 - \alpha(\rho)\beta(\rho))(1-c \cdot \mu^{-1} \epsilon_{2\to2})
- c \cdot \alpha(\rho) \mu^{-1} \epsilon_\v\infty
- c \cdot \alpha(\rho) \gamma}
{c \cdot \alpha(\rho)}
\label{eq:cond2} \\
& \lambda \ \geq \ c \cdot \frac{\gamma
+ \mu^{-1}
 (2 - \alpha(\rho) \beta(\rho)) \epsilon_\v\infty}
{1 - \alpha(\rho) \beta(\rho) - c \cdot \alpha(\rho) \beta(\rho)}
\ > \ 0
\label{eq:cond3}
\end{align}
(these are a restatement of~\eqref{eq:opt2-cond1}, \eqref{eq:opt2-cond2},
and \eqref{eq:opt2-cond3}),
then
\begin{align*}
Q_{\bar{\Omega}} & := (\mathcal{I} - \mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})^{-1}
\left( \lambda \sign(\bar{X}_S)
- \mathcal{P}_{{\bar{\Omega}}}(\orth(\bar{X}_L))
- \mu^{-1} (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)
\right)
\in {\bar{\Omega}}
\quad \text{and}
\\
Q_{\bar{T}} & := (\mathcal{I} - \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}})^{-1}
\left( \orth(\bar{X}_L)
- \lambda \mathcal{P}_{{\bar{T}}}(\sign(\bar{X}_S))
- \mu^{-1} (\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(E)
\right)
\in {\bar{T}}
\end{align*}
are well-defined and satisfy
\[
\begin{array}{rcr}
\mathcal{P}_{{\bar{\Omega}}}(Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E) & = & \lambda \sign(\bar{X}_S)\\
\mathcal{P}_{{\bar{T}}}(Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E) & = & \orth(\bar{X}_L)
\end{array}
\]
and
\[
\begin{array}{lcl}
\|\mathcal{P}_{{\bar{\Omega}}^\perp} (Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E) \|_\v\infty & \leq & \lambda/c \\
\|\mathcal{P}_{{\bar{T}}^\perp} (Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E)\|_{2\to2} & \leq & 1/c .
\end{array}
\]
Moreover,
\begin{align*}
\|Q_{\bar{\Omega}} \|_{2\to2}
& \leq
\frac{\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right) \\
\|Q_{\bar{T}} \|_{2\to2}
& \leq
\frac{2\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right)
+ 1 + 2\mu^{-1}\epsilon_{2\to2}
\\
\|Q_{\bar{T}}\|_* & \leq 2\bar{r} \|Q_{\bar{T}}\|_{2\to2}
\\
\|Q_{\bar{T}} \|_{\v\infty}
& \leq
\frac{1}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right) \\
\|Q_{\bar{\Omega}} \|_{\v\infty}
& \leq
\frac{2}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right)
\\
\|Q_{\bar{\Omega}}\|_\v1 & \leq \bar{k} \|Q_{\bar{\Omega}}\|_\v\infty
\\
\|Q_{\bar{\Omega}} + Q_{\bar{T}}\|_\v2^2
& \leq
\lambda \|Q_{\bar{\Omega}}\|_\v1
\left( 1 + \mu^{-1} \lambda^{-1} \epsilon_\v\infty \right)
+ \|Q_{\bar{T}}\|_*
\left( 1 + 2\mu^{-1}\epsilon_{2\to2} \right)
.
\end{align*}
\end{theorem}
\begin{remark}
The dual certificate constitutes an approximate subgradient in the sense
that $Q_{\bar{\Omega}} + Q_{\bar{T}} + \mu^{-1} E$ is a subgradient of both $\lambda
\|X_S\|_\v1$ at $X_S = \bar{X}_S$, and $\|X_L\|_*$ at $X_L = \bar{X}_L$.
\end{remark}
\begin{proof}
Under the condition~\eqref{eq:cond1}, we have $\alpha(\rho) \beta(\rho) <
1$, and therefore Lemma~\ref{lemma:composition-bound} and
Lemma~\ref{lemma:block-inverse} imply that the operators $\mathcal{I} - \mathcal{P}_{{\bar{\Omega}}}
\circ \mathcal{P}_{{\bar{T}}}$ and $\mathcal{I} - \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}}$ are invertible and
satisfy
\[
\max\left\{
\|(\mathcal{I} - \mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})^{-1}\|_{\sharp(\rho)\to\sharp(\rho)}
, \
\|(\mathcal{I} - \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}})^{-1}\|_{\v\infty\to\v\infty}
\right\}
\ \leq \ \frac1{1-\alpha(\rho) \beta(\rho)}
.
\]
Thus $Q_{\bar{\Omega}}$ and $Q_{\bar{T}}$ are well-defined.
We can bound $\|Q_{\bar{\Omega}}\|_{2\to2}$ as
\begin{align*}
\|Q_{\bar{\Omega}}\|_{2\to2}
& \leq \|Q_{\bar{\Omega}}\|_{\sharp(\rho)}
\quad \text{(Lemma~\ref{lemma:spectral-bound})} \\
& = \left\| (I - \mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})^{-1}
\left( \lambda \sign(\bar{X}_S)
- \mathcal{P}_{{\bar{\Omega}}}(\orth(\bar{X}_L))
- \mu^{-1} (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E) \right)
\right\|_{\sharp(\rho)}
\\
& \leq
\frac1{1-\alpha(\rho)\beta(\rho)} \cdot
\left\|
\lambda \sign(\bar{X}_S)
- \mathcal{P}_{{\bar{\Omega}}}(\orth(\bar{X}_L))
- \mu^{-1} (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)
\right\|_{\sharp(\rho)}
\\
& \leq
\frac1{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda \|\sign(\bar{X}_S)\|_{\sharp(\rho)}
+ \|\mathcal{P}_{{\bar{\Omega}}}(\orth(\bar{X}_L))\|_{\sharp(\rho)}
+ \mu^{-1} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_{\sharp(\rho)}
\right)
\\
& \leq
\frac{\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \|\mathcal{P}_{{\bar{T}}^\perp}(E)\|_\v\infty
\right)
\quad \text{(Lemma~\ref{lemma:sparse-bound})}
\\
& \leq
\frac{\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right)
.
\end{align*}
Above, we have used the bound $\|\mathcal{P}_{{\bar{T}}^\perp}(E)\|_\v\infty = \|E -
\mathcal{P}_{{\bar{T}}}(E)\|_\v\infty \leq \epsilon_\v\infty$.
Therefore,
\begin{align*}
\|\mathcal{P}_{{\bar{T}}^\perp}(Q_{\bar{\Omega}} + \mu^{-1} E)\|_{2\to2}
& \leq \|(I-\bar{U}\bU^\top) Q_{\bar{\Omega}} (I-\bar{V}\bV^\top)\|_{2\to2}
+ \mu^{-1} \|P_{{\bar{T}}^\perp}(E)\|_{2\to2}
\\
& \leq \|Q_{\bar{\Omega}}\|_{2\to2} + \mu^{-1} \epsilon_{2\to2} \\
& \leq
\frac{\alpha(\rho)}{1-\alpha(\rho) \beta(\rho)} \cdot (\lambda +
\gamma +  \mu^{-1} \epsilon_\v\infty)
+ \mu^{-1} \epsilon_{2\to2}
.
\end{align*}
The condition~\eqref{eq:cond2} now implies that this quantity is at most
$1/c$.

Now we bound $\|Q_{\bar{T}}\|_\v\infty$ as
\begin{align*}
\|Q_{\bar{T}}\|_\v\infty
& =
\left\|
(\mathcal{I} - \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}})^{-1}
\left(
\orth(\bar{X}_L)
- \lambda \mathcal{P}_{{\bar{T}}}(\sign(\bar{X}_S)
- \mu^{-1} (\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(E)
\right)
\right\|_\v\infty
\\
& \leq
\frac1{1-\alpha(\rho)\beta(\rho)} \cdot
\left\|
\orth(\bar{X}_L)
- \lambda \mathcal{P}_{{\bar{T}}} (\sign(\bar{X}_S)
- \mu^{-1} (\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(E)
\right\|_\v\infty
\\
& \leq
\frac1{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\|\orth(\bar{X}_L)\|_\v\infty
+ \lambda \|\mathcal{P}_{{\bar{T}}}(\sign(\bar{X}_S))\|_\v\infty
+ \mu^{-1} \|(\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(E)\|_\v\infty
\right)
\\
& \leq
\frac1{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\gamma
+ \lambda \alpha(\rho) \beta(\rho)
+ \mu^{-1} \epsilon_\v\infty
\right)
\quad \text{(Lemma~\ref{lemma:composition-bound})}
.
\end{align*}
Above, we have used the bound $\|(\mathcal{P}_{{\bar{T}}}\circ\mathcal{P}_{{\bar{\Omega}}^\perp})(E)\|_\v\infty =
\|\mathcal{P}_{\bar{T}}(E) - (\mathcal{P}_{\bar{T}}\circ\mathcal{P}_{\bar{\Omega}})(E)\|_\v\infty \leq \|\mathcal{P}_{\bar{T}}(E)\|_\v\infty
+ \alpha(\rho)\beta(\rho)\|E\|_\v\infty \leq \epsilon_\v\infty$.
Therefore,
\begin{align*}
\|\mathcal{P}_{{\bar{\Omega}}^\perp}(Q_{\bar{T}} +\mu^{-1} E)\|_\v\infty
& \leq \|Q_{\bar{T}}\|_\v\infty + \mu^{-1}\|\mathcal{P}_{{\bar{\Omega}}^\perp}(E)\|_\v\infty \\
& \leq \frac1{1-\alpha(\rho) \beta(\rho)}
\cdot
\left(
\gamma
+ \lambda \alpha(\rho) \beta(\rho)
+ \mu^{-1} \epsilon_\v\infty
\right)
+ \mu^{-1} \epsilon_\v\infty
.
\end{align*}
The condition~\eqref{eq:cond3} now implies that this quantity is at most
$\lambda/c$.

We also have
\begin{align*}
\|Q_{\bar{T}} \|_{2\to2}
& = \|\mathcal{P}_{{\bar{T}}}(Q_{\bar{\Omega}} + \mu^{-1} E) - \orth(\bar{X}_L)\|_{2\to2} \\
& \leq
\frac{2\alpha(\rho)}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right)
+ 1 + 2\mu^{-1} \epsilon_{2\to2}
\end{align*}
since $\|\mathcal{P}_{\bar{T}}(Q_{\bar{\Omega}})\|_{2\to2}\leq 2 \|Q_{\bar{\Omega}}\|_{2\to2}$
and $\|\mathcal{P}_{\bar{T}}(E)\|_{2\to2} \leq 2\epsilon_{2\to2}$
by Lemma~\ref{lemma:projections}, and
\begin{align*}
\|Q_{\bar{\Omega}} \|_{\v\infty}
& = \|P_{{\bar{\Omega}}}(Q_{\bar{T}} + \mu^{-1} E) - \lambda \sign(\bar{X}_S)\|_{\v\infty} \\
& \leq
\frac{1}{1-\alpha(\rho)\beta(\rho)} \cdot
\left(
\lambda
+  \gamma
+  \mu^{-1} \epsilon_\v\infty
\right) + \lambda + \mu^{-1} \epsilon_\v\infty .
\end{align*}
The bounds on $\|Q_{\bar{T}}\|_*$ and $\|Q_{\bar{\Omega}}\|_\v1$ follow from the facts that
$\rank(Q_{\bar{T}}) \leq 2\bar{r}$ and $\|\supp(Q_{\bar{\Omega}})\| \leq \bar{k}$.
Finally,
\begin{align*}
\|Q_{\bar{\Omega}} + Q_{\bar{T}}\|_{\v2}^2
& = \ang{Q_{\bar{\Omega}},\mathcal{P}_{\bar{\Omega}}(Q_{\bar{\Omega}} + Q_{\bar{T}})} + \ang{Q_{\bar{T}},\mathcal{P}_{\bar{T}}(Q_{\bar{\Omega}} + Q_{\bar{T}})} \\
& = \ang{Q_{\bar{\Omega}}, \lambda \mathcal{P}_{{\bar{\Omega}}}(\sign(\bar{X}_S)) - \mu^{-1} \mathcal{P}_{{\bar{\Omega}}}(E)}
+ \ang{Q_{\bar{T}},\mathcal{P}_{{\bar{T}}}(\orth(\bar{X}_L)) - \mu^{-1} \mathcal{P}_{{\bar{T}}}(E)} \\
& \leq \lambda \|Q_{\bar{\Omega}}\|_{\v1}
\left( 1 + \mu^{-1}\lambda^{-1} \|\mathcal{P}_{\bar{\Omega}}(E)\|_\v\infty \right)
+ \|Q_{\bar{T}}\|_*
\left( 1 + \mu^{-1} \|\mathcal{P}_{\bar{T}}(E)\|_{2\to2} \right)
\\
& \leq \lambda \|Q_{\bar{\Omega}}\|_{\v1}
\left( 1 + \mu^{-1}\lambda^{-1} \epsilon_\v\infty \right)
+ \|Q_{\bar{T}}\|_*
\left( 1 + 2\mu^{-1} \epsilon_{2\to2} \right)
.
\qedhere
\end{align*}

\end{proof}

\section{Analysis of constrained formulation} \label{section:opt1}

Throughout this section, we fix a target decomposition $(\bar{X}_S,\bar{X}_L)$ that
satisfies the constraints of~\eqref{eq:opt1}, and let $(\hat{X}_S,\hat{X}_L)$ be the
optimal solution to~\eqref{eq:opt1}.
Let ${\Delta_S} := \hat{X}_S - \bar{X}_S$ and ${\Delta_L} := \hat{X}_L - \bar{X}_L$.
We show that under the conditions of Theorem~\ref{theorem:dual-cert} with
$E=0$ and appropriately chosen $\lambda$, solving \eqref{eq:opt1}
accurately recovers the target decomposition $(\bar{X}_S,\bar{X}_L)$.

We decompose the errors into symmetric and antisymmetric parts $\Delta_{\operatorname{avg}} := ({\Delta_S}
+ {\Delta_L})/2$ and $\Delta_{\operatorname{mid}} := ({\Delta_S} - {\Delta_L}) / 2$.
The constraints allow us to easily bound $\Delta_{\operatorname{avg}}$, so most of the analysis
involves bounding $\Delta_{\operatorname{mid}}$ in terms of $\Delta_{\operatorname{avg}}$.
\begin{lemma} \label{lemma:opt1-avg}
$\|\Delta_{\operatorname{avg}}\|_\v1 \leq \epsilon_\v1$ and $\|\Delta_{\operatorname{avg}}\|_* \leq \epsilon_*$.
\end{lemma}
\begin{proof}
Since both $(\hat{X}_S,\hat{X}_L)$ and $(\bar{X}_S,\bar{X}_L)$ as feasible solutions
to~\eqref{eq:opt1}, we have for $\diamondsuit \in \{\v1, *\}$,
\begin{align*}
\|\Delta_{\operatorname{avg}}\|_\diamondsuit
& = \nicefrac12 \|{\Delta_S} + {\Delta_L}\|_\diamondsuit \\
& = \nicefrac12 \|(\hat{X}_S + \hat{X}_L - Y) - (\bar{X}_S + \bar{X}_L - Y)\|_\diamondsuit \\
& \leq \nicefrac12 \left( \|\hat{X}_S + \hat{X}_L - Y\|_\diamondsuit + \|\bar{X}_S + \bar{X}_L -
Y\|_\diamondsuit
\right) \\
& \leq \epsilon_\diamondsuit
.
\qedhere
\end{align*}
\end{proof}

\begin{lemma} \label{lemma:opt1-outside}
Assume the conditions of Theorem~\ref{theorem:dual-cert} hold with $E=0$.
We have
\[
\lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}})\|_\v1 + \|\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})\|_*
\leq (1-1/c)^{-1} \left( \lambda \|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{avg}}\|_* \right)
.
\]
\end{lemma}
\begin{proof}
Let $Q := Q_{\bar{\Omega}} + Q_{\bar{T}}$ be the dual certificate guaranteed by
Theorem~\ref{theorem:dual-cert}.
Note that $Q$ satisfies the conditions of Lemma~\ref{lemma:subgradient}, so
we have
\begin{multline*}
\lambda \|\bar{X}_S + \Delta_{\operatorname{mid}}\|_\v1 + \|\bar{X}_L - \Delta_{\operatorname{mid}}\|_* - \lambda  \|\bar{X}_S\|_\v1 -
\|\bar{X}_L\|_*
\\
\geq (1-1/c) \left( \lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}})\|_\v1 +
\|\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})\|_* \right)
.
\end{multline*}
Using the triangle inequality, we have
\begin{align*}
\lambda \|\hat{X}_S\|_\v1 + \|\hat{X}_L\|_*
& = \lambda \|\bar{X}_S + {\Delta_S}\|_\v1 + \|\bar{X}_L + {\Delta_L}\|_* \\
& = \lambda \|\bar{X}_S + \Delta_{\operatorname{mid}} + \Delta_{\operatorname{avg}}\|_\v1 + \|\bar{X}_L - \Delta_{\operatorname{mid}} + \Delta_{\operatorname{avg}}\|_* \\
& \geq
\lambda \|\bar{X}_S + \Delta_{\operatorname{mid}}\|_\v1 - \lambda \|\Delta_{\operatorname{avg}}\|_\v1
+ \|\bar{X}_L - \Delta_{\operatorname{mid}}\|_* - \|\Delta_{\operatorname{avg}}\|_*
.
\end{align*}
Now using the fact that $\lambda \|\hat{X}_S\|_\v1 + \|\hat{X}_L\|_* \leq \lambda
\|\bar{X}_S\|_\v1 + \|\bar{X}_L\|_*$ gives the claim.
\end{proof}

\begin{lemma} \label{lemma:opt1-inside}
Let $\bar{k} := |\supp(\bar{X}_S)|$.
Assume the conditions of Theorem~\ref{theorem:dual-cert} hold with $E = 0$.
We have
\[ \|\mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}})\|_\v1
 \leq \frac{(1-1/c)^{-1}}{1-\alpha(\rho)\beta(\rho)}
\cdot (\|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{avg}}\|_* / \lambda)
.
\]
\end{lemma}
\begin{proof}
Because $\Delta_{\operatorname{mid}} = \mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}}) + \mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}}) = \mathcal{P}_{{\bar{T}}}(\Delta_{\operatorname{mid}}) +
\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})$, we have the equation
\[ \mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}}) - \mathcal{P}_{{\bar{T}}}(\Delta_{\operatorname{mid}}) = - \mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}}) +
\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})
. \]
Separately applying $\mathcal{P}_{{\bar{\Omega}}}$ and $\mathcal{P}_{{\bar{T}}}$ to both sides gives
\[
\left[ \begin{array}{cc}
\mathcal{I} & \mathcal{P}_{{\bar{\Omega}}} \\
\mathcal{P}_{{\bar{T}}} & \mathcal{I}
\end{array} \right]
\left[ \begin{array}{r}
\mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}}) \\
-\mathcal{P}_{{\bar{T}}}(\Delta_{\operatorname{mid}})
\end{array} \right]
=
\left[ \begin{array}{r}
(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(\Delta_{\operatorname{mid}}) \\
-(\mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(\Delta_{\operatorname{mid}})
\end{array} \right]
.
\]
Under the condition $\alpha(\rho) \beta(\rho) < 1$,
Lemma~\ref{lemma:dual-composition-bound} and
Lemma~\ref{lemma:block-inverse} imply that
\[ \|(\mathcal{I} - \mathcal{P}_{{\bar{\Omega}}} \circ
\mathcal{P}_{{\bar{T}}})^{-1}\|_{\v1\to\v1} \leq
\frac1{1-\alpha(\rho) \beta(\rho)}
\]
and that
\begin{align*}
\mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}})
& = (\mathcal{I} - \mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})^{-1}
\left(
(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(\Delta_{\operatorname{mid}})
- (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(\Delta_{\operatorname{mid}})
\right)
.
\end{align*}
Therefore
\begin{align*}
\lefteqn{\|\mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}})\|_\v1} \\
& \leq \frac1{1-\alpha(\rho)\beta(\rho)}
\cdot \left(
\|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(\Delta_{\operatorname{mid}})\|_\v1
+ \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})(\Delta_{\operatorname{mid}})\|_\v1
\right)
\\
& \leq \frac1{1-\alpha(\rho)\beta(\rho)}
\cdot \left(
\sqrt{\bar{k}} \cdot \|\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})\|_\v2
+ \alpha(\rho) \beta(\rho) \cdot \|\mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}})\|_\v1
\right)
\quad \text{(Lemma~\ref{lemma:dual-composition-bound})}
\\
& \leq \frac1{1-\alpha(\rho)\beta(\rho)}
\cdot \left(
\sqrt{\bar{k}} \cdot \|\mathcal{P}_{{\bar{T}}^\perp}(\Delta_{\operatorname{mid}})\|_*
+ \alpha(\rho) \beta(\rho) \cdot \|\mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}})\|_\v1
\right)
\\
& \leq \frac{(1-1/c)^{-1}}{1-\alpha(\rho)\beta(\rho)}
\cdot \max\left\{ \sqrt{\bar{k}}, \ \alpha(\rho)\beta(\rho) / \lambda \right\}
\cdot (\lambda \|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{avg}}\|_*)
\quad \text{(Lemma~\ref{lemma:opt1-outside})}
\\
& \leq \frac{(1-1/c)^{-1}}{1-\alpha(\rho)\beta(\rho)}
\cdot (\|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{avg}}\|_* / \lambda)
\end{align*}
where the last inequality uses the facts $\bar{k} \leq \alpha(\rho)^2$,
$\alpha(\rho)\beta(\rho) < 1$, and $\lambda \alpha(\rho) \leq 1$.
\end{proof}

We now prove Theorem~\ref{theorem:opt1}, which we restate here for
convenience.
\begin{theorem}[Theorem~\ref{theorem:opt1} restated] \label{theorem:opt1-again}
Assume the conditions of Theorem~\ref{theorem:dual-cert} hold with $E = 0$.
We have
\begin{multline*}
\max\{ \|{\Delta_S}\|_\v1, \ \|{\Delta_L}\|_\v1 \}
\\
\leq
\left(
1 +
(1-1/c)^{-1} \cdot
\frac{2-\alpha(\rho)\beta(\rho)}{1-\alpha(\rho)\beta(\rho)}
\right)
\cdot \epsilon_\v1
+ (1-1/c)^{-1} \cdot
\frac{2-\alpha(\rho)\beta(\rho)}{1-\alpha(\rho)\beta(\rho)}
\cdot
\epsilon_* / \lambda
.
\end{multline*}
If, in addition for some $b \geq \|\bar{X}_L\|_\v\infty$, either:
\begin{itemize}
\item the optimization problem~\eqref{eq:opt1} is augmented with the
constraint $\|X_L\|_\v\infty \leq b$, or

\item $\hat{X}_L$ is post-processed by replacing $[\hat{X}_L]_{i,j}$ with
$\min\{ \max\{ [\hat{X}_L]_{i,j}, -b\}, b \}$ for all $i,j$,

\end{itemize}
then we also have
\[ \|{\Delta_L}\|_\v2 \leq \min\left\{ \|{\Delta_L}\|_\v1, \ \sqrt{2b \|{\Delta_L}\|_\v1}
\right\} . \]
\end{theorem}
\begin{proof}
First note that since ${\Delta_S} = \Delta_{\operatorname{avg}} + \Delta_{\operatorname{mid}}$ and ${\Delta_L} = \Delta_{\operatorname{avg}} - \Delta_{\operatorname{mid}}$, we have
$\max\{\|{\Delta_S}\|_\v1,\|{\Delta_L}\|_\v1\} \leq \|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{mid}}\|_\v1$.
We can bound $\|\Delta_{\operatorname{mid}}\|_\v1$ as
\begin{align*}
\|\Delta_{\operatorname{mid}}\|_\v1
& \leq \|\mathcal{P}_{{\bar{\Omega}}^\perp}(\Delta_{\operatorname{mid}})\|_\v1 + \|\mathcal{P}_{{\bar{\Omega}}}(\Delta_{\operatorname{mid}})\|_\v1 \\
& \leq
(1-1/c)^{-1} \cdot \left(
1 + \frac{1}{1-\alpha(\rho)\beta(\rho)}
\right)
\cdot ( \|\Delta_{\operatorname{avg}}\|_\v1 + \|\Delta_{\operatorname{avg}}\|_* / \lambda)
\end{align*}
by Lemma~\ref{lemma:opt1-outside} and Lemma~\ref{lemma:opt1-inside}.
The bounds on $\|{\Delta_S}\|_\v1$ and $\|{\Delta_L}\|_\v1$ follow from the bounds on
$\|\Delta_{\operatorname{mid}}\|_\v1$, $\|\Delta_{\operatorname{avg}}\|_\v1$, and $\|\Delta_{\operatorname{avg}}\|_*$ (from
Lemma~\ref{lemma:opt1-avg}).

If the constraint $\|X_L\|_\v\infty \leq b$ is added, then we can use the
facts $\|{\Delta_L}\|_\v\infty \leq \|\hat{X}_L\|_\v\infty + \|\bar{X}_L\|_\v\infty \leq 2b$
and $\|{\Delta_L}\|_\v2 \sqrt{\|{\Delta_L}\|_\v\infty \|{\Delta_L}\|_\v1} \leq
\sqrt{2b\|{\Delta_L}\|_\v1}$.
If $\hat{X}_L$ is post-processed, then (letting $\clip(\hat{X}_L)$ be the result of
the post-processing) $|\clip(\hat{X}_L)_{i,j} - [\bar{X}_L]_{i,j}| \leq |[\hat{X}_L]_{i,j}
- [\bar{X}_L]_{i,j}|$ for all $i,j$, so $\|\clip(\hat{X}_L) - \bar{X}_L\|_\v1 \leq
\|{\Delta_L}\|_\v1$ and $\|\clip(\hat{X}_L)-\bar{X}_L\|_\v2 \leq \sqrt{2b
\|\clip(\hat{X}_L)-\bar{X}_L\|_\v1}$.
\end{proof}

\section{Analysis of regularized formulation} \label{section:opt2}

Throughout this section, we fix a target decomposition $(\bar{X}_S,\bar{X}_L)$ that
satisfies $\|\bar{X}_S-Y\|_\v\infty \leq b$, and let $(\hat{X}_S, \hat{X}_L)$ be the
optimal solution to~\eqref{eq:opt2} augmented with the constraint
$\|X_S-Y\|_\v\infty \leq b$ for some $b \geq \|\bar{X}_S-Y\|_\v\infty$ ($b =
\infty$ is allowed).
Let ${\Delta_S} := \hat{X}_S-\bar{X}_S$ and ${\Delta_L} := \hat{X}_L-\bar{X}_L$.
We show that under the conditions of Theorem~\ref{theorem:dual-cert} with
$E=Y-(\bar{X}_S+\bar{X}_L)$ and appropriately chosen $\lambda$ and $\mu$, solving
\eqref{eq:opt2} accurately recovers the target decomposition $(\bar{X}_S,\bar{X}_L)$.

\begin{lemma} \label{lemma:opt2-kkt}
There exists $G_S, G_L, H_S \in \mathbb{R}^{m \times n}$ such that
\begin{enumerate}
\item $\mu^{-1} ( \hat{X}_S + \hat{X}_L - Y ) + \lambda G_S + H = 0$;
$\|G_S\|_\v\infty \leq 1$;

\item $\mu^{-1} ( \hat{X}_S + \hat{X}_L - Y ) + \lambda G_L = 0$;
$\|G_L\|_{2\to2} \leq 1$;

\item $[H_S]_{i,j} [{\Delta_S}]_{i,j} \geq 0 \ \forall i,j$ .

\end{enumerate}
\end{lemma}
\begin{proof}
We express the constraint $\|X_S-Y\|_\v\infty \leq b$ in~\eqref{eq:opt2} as
$2mn$ constraints $[X_S]_{i,j} - Y_{i,j} - b \leq 0$ and $-[X_S]_{i,j} +
Y_{i,j} - b \leq 0$ for all $i,j$.
Now the corresponding Lagrangian is
\[
\frac1{2\mu} \|X_S+X_L-Y\|_\v2^2 + \lambda \|X_S\|_\v1 + \|X_L\|_*
+ \ang{\Lambda^+,X_S-Y-b 1_{m,n}}
+ \ang{\Lambda^-,-X_S+Y-b 1_{m,n}}
\]
where $\Lambda^+, \Lambda^- \geq 0$ and $1_{m,n}$ is the all-ones $m \times
n$ matrix.
First-order optimality conditions imply that there exists a subgradient
$G_S$ of $\|X_S\|_\v1$ at $X_S=\hat{X}_S$ and a subgradient $G_L$ of $\|X_L\|_*$
at $X_L=\hat{X}_L$ such that
\[
\mu^{-1} (\hat{X}_S + \hat{X}_L - Y) + \lambda G_S + (\Lambda^+ - \Lambda^-) = 0
\quad \text{and} \quad
\mu^{-1} (\hat{X}_S + \hat{X}_L - Y) + G_L = 0
.
\]
Now since $\|\bar{X}_S-Y\|_\v\infty \leq b$, we have
$[\bar{X}_S]_{i,j} \leq Y_{i,j} + b$
and
$-[\bar{X}_S]_{i,j} \leq -Y_{i,j} + b$.
By complementary slackness, if $\Lambda^+_{i,j} > 0$, then $[\hat{X}_S]_{i,j} -
Y_{i,j} - b = 0$, which means $[\hat{X}_S]_{i,j} - [\bar{X}_S]_{i,j} \geq
[\hat{X}_S]_{i,j} - (Y_{i,j} + b) = 0$.
So $\Lambda^+_{i,j} [{\Delta_S}]_{i,j} \geq 0$.
Similarly, if $\Lambda^-_{i,j} > 0$, then $[\hat{X}_S]_{i,j} - [\bar{X}_S]_{i,j} \leq
0$.
So $\Lambda^-_{i,j} [{\Delta_S}]_{i,j} \leq 0$.
Therefore $H := \Lambda^+ - \Lambda^-$ satisfies $H_{i,j} [{\Delta_S}]_{i,j} \geq
0$.
\end{proof}

\begin{lemma} \label{lemma:opt2-outside}
Assume the conditions of Theorem~\ref{theorem:dual-cert} hold with $E = Y -
(\bar{X}_S + \bar{X}_L)$, and let $(Q_{\bar{\Omega}},Q_{\bar{T}})$ be the dual certificate from the
conclusion.
We have
\[
\lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp} ({\Delta_S})\|_{\v1} + \|\mathcal{P}_{{\bar{T}}^\perp} ({\Delta_L})\|_*
\leq (1-1/c)^{-1} \|Q_{\bar{\Omega}} + Q_{\bar{T}}\|_\v2^2 \mu/2
.
\]
\end{lemma}
\begin{proof}
Let $Q := Q_{\bar{\Omega}} + Q_{\bar{T}}$ and $\Delta := {\Delta_S} + {\Delta_L}$.
Since $Q + \mu^{-1} E$ satisfies the conditions of
Lemma~\ref{lemma:subgradient},
\begin{multline*}
(1-1/c) \left( \lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp} ({\Delta_S})\|_{\v1} + \|\mathcal{P}_{{\bar{T}}^\perp}
({\Delta_L})\|_* \right)
\\
\leq
( \lambda \|\hat{X}_S\|_\v1 + \|\hat{X}_L\|_* )
- ( \lambda \|\bar{X}_S\|_\v1 + \|\bar{X}_L\|_* )
- \ang{Q + \mu^{-1} E, {\Delta_S}+{\Delta_L}}
.
\end{multline*}
Furthermore, by the optimality of $(\hat{X}_S,\hat{X}_L)$,
\begin{align*}
( \lambda \|\hat{X}_S\|_\v1 + \|\hat{X}_L\|_* )
- ( \lambda \|\bar{X}_S\|_\v1 + \|\bar{X}_L\|_* )
& \leq
\frac1{2\mu} \|\bar{X}_S + \bar{X}_L - Y\|_\v2^2
- \frac1{2\mu} \|\hat{X}_S + \hat{X}_L - Y\|_\v2^2
\\
& =
\frac1{2\mu} \|E\|_\v2^2
- \frac1{2\mu} \|{\Delta_S}+{\Delta_L}-E\|_\v2^2
\\
& =
\frac{1}{2\mu} (2\ang{E,\Delta} - \ang{\Delta,\Delta})
.
\end{align*}
Combining the inequalities gives
\begin{align*}
(1-1/c) \left( \lambda \|\mathcal{P}_{{\bar{\Omega}}^\perp} ({\Delta_S})\|_{\v1} + \|\mathcal{P}_{{\bar{T}}^\perp}
({\Delta_L})\|_* \right)
& \leq -\ang{Q,\Delta} -\frac1{2\mu} \ang{\Delta,\Delta}
 \leq \|Q\|_\v2^2 \mu/2
\end{align*}
where the last inequality follows by taking the maximum value over $\Delta$
at $\Delta = -\mu Q$.
\end{proof}

Now we prove Theorem~\ref{theorem:opt2}, restated below (with an additional result for $\|\Delta_L\|_{\flat(\rho)}$).
\begin{theorem}[Theorem~\ref{theorem:opt2} restated] \label{theorem:opt2-again}
Let $\bar{k} := |\supp(\bar{X}_S)|$ and $\bar{r} := \rank(\bar{X}_L)$.
Assume the conditions of Theorem~\ref{theorem:dual-cert} hold with $E = Y -
(\bar{X}_S + \bar{X}_L)$, and let $(Q_{\bar{\Omega}},Q_{\bar{T}})$ be the dual certificate from the
conclusion.
We have
\begin{align*}
\|{\Delta_S}\|_\v1
& \leq
\frac
{
\lambda^{-1}
(1-1/c)^{-1}
\|Q_{\bar{\Omega}}+Q_{\bar{T}}\|_\v2^2
\mu
+ \lambda \bar{k} \mu
+ 2\sqrt{\bar{k}\bar{r}} \mu
+ \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
}
{1-\alpha(\rho)\beta(\rho)}
\\
\|{\Delta_S}\|_\v2 & \leq \min\left\{ \|{\Delta_S}\|_\v1, \ \sqrt{2b\|{\Delta_S}\|_\v1} \right\}
\\
\|{\Delta_L}\|_{\flat(\rho)}
& \leq (1-1/c)^{-1} \|Q_{\bar{\Omega}}+Q_{\bar{T}}\|_\v2^2 \mu / 2
+ \min\left\{ \beta(\rho) \|{\Delta_S}\|_\v1, \ \sqrt{2\bar{r}} \|{\Delta_S}\|_\v2 \right\}
+ \|\mathcal{P}_{\bar{T}}(E)\|_* + 2\bar{r}\mu
\\
\|{\Delta_L}\|_*
& \leq (1-1/c)^{-1} \|Q_{\bar{\Omega}}+Q_{\bar{T}}\|_\v2^2 \mu / 2
+ \sqrt{2\bar{r}} \|{\Delta_S}\|_\v2 + \|\mathcal{P}_{\bar{T}}(E)\|_* + 2\bar{r}\mu
.
\end{align*}
\end{theorem}
\begin{proof}
From Lemma~\ref{lemma:opt2-kkt}, we obtain $G_S, G_L, H_S \in \mathbb{R}^{m \times
n}$ and the following equations:
\begin{align}
& \mu^{-1} (\mathcal{P}_{\bar{\Omega}}({\Delta_S}) + \mathcal{P}_{\bar{\Omega}}({\Delta_L}) - \mathcal{P}_{\bar{\Omega}}(E)) + \mathcal{P}_{\bar{\Omega}}(H_S)
= -\lambda \mathcal{P}_{\bar{\Omega}}(G_S)
\label{eq:kkt1} \\
& \mu^{-1} (\mathcal{P}_{\bar{T}}({\Delta_S}) + \mathcal{P}_{\bar{T}}({\Delta_L}) - \mathcal{P}_{\bar{T}}(E)) = -\mathcal{P}_{\bar{T}}(G_L)
\label{eq:kkt2} \\
& \mu^{-1} ((\mathcal{P}_{\bar{\Omega}}\circ\mathcal{P}_{\bar{T}})({\Delta_S}) + (\mathcal{P}_{\bar{\Omega}}\circ\mathcal{P}_{\bar{T}})({\Delta_L})
- (\mathcal{P}_{\bar{\Omega}}\circ\mathcal{P}_{\bar{T}})(E))
= -(\mathcal{P}_{\bar{\Omega}}\circ\mathcal{P}_{\bar{T}})(G_L)
\label{eq:kkt3}
.
\end{align}
Subtracting~\eqref{eq:kkt3} from~\eqref{eq:kkt1} gives
\begin{multline*}
\mu^{-1} (
\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})
- (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}})({\Delta_S})
- (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})({\Delta_S})
- (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})({\Delta_L})
)
+ \mathcal{P}_{{\bar{\Omega}}}(H_S)
\\
 =
-\lambda \mathcal{P}_{{\bar{\Omega}}}(G_S)
+ (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})(G_L)
+ \mu^{-1} (\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)
.
\end{multline*}
Moreover, we have
$\ang{\sign({\Delta_S}),\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})} = \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1$
and
$\ang{\sign({\Delta_S}),\mathcal{P}_{{\bar{\Omega}}}(H_S)} = \|\mathcal{P}_{{\bar{\Omega}}}(H_S)\|_\v1$,
so taking inner products with $\sign({\Delta_S})$ on both sides of the equation
gives
\begin{align*}
\lefteqn{
\mu^{-1} \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1 + \|\mathcal{P}_{{\bar{\Omega}}}(H_S)\|_\v1
} \\
& \leq
\mu^{-1} \|(\mathcal{P}_{{\bar{\Omega}}}\circ\mathcal{P}_{{\bar{T}}}\circ\mathcal{P}_{{\bar{\Omega}}})({\Delta_S})\|_\v1
+ \mu^{-1} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}} \circ \mathcal{P}_{{\bar{\Omega}}^\perp})({\Delta_S})\|_\v1
+ \mu^{-1} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})({\Delta_L})\|_\v1
\\
& \qquad{}
+ \lambda \|\mathcal{P}_{{\bar{\Omega}}}(G_S)\|_\v1
+ \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}})(G_L)\|_\v1
+ \mu^{-1} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v1
\\
& \leq
\mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1
+ \mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
+ \mu^{-1} \sqrt{\bar{k}} \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_\v2
\\
& \qquad{}
+ \lambda \bar{k}
+ \sqrt{\bar{k}} \|\mathcal{P}_{{\bar{T}}}(G_L)\|_\v2
+ \mu^{-1} \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
\\
& \leq
\mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1
+ \mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
+ \mu^{-1} \sqrt{\bar{k}} \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_\v2
\\
& \qquad{}
+ \lambda \bar{k}
+ 2\sqrt{\bar{k}\bar{r}} \|G_L\|_{2\to2}
+ \mu^{-1} \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
\\
& \leq
\mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1
+ \mu^{-1} \alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
+ \mu^{-1} \sqrt{\bar{k}} \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_\v2
\\
& \qquad{}
+ \lambda \bar{k}
+ 2\sqrt{\bar{k}\bar{r}}
+ \mu^{-1} \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
.
\end{align*}
The second and third inequalities above follow from
Lemma~\ref{lemma:projections}
and
Lemma~\ref{lemma:dual-composition-bound},
and the fourth inequality uses the fact that $\|G_L\|_{2\to2} \leq 1$.
Rearranging the inequality and applying Lemma~\ref{lemma:opt2-outside}
gives
\begin{align*}
\lefteqn{
(1-\alpha(\rho)\beta(\rho)) \|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1
} \\
& \leq
\alpha(\rho)\beta(\rho) \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1
+ \sqrt{\bar{k}} \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_\v2
+ \lambda \bar{k} \mu
+ 2\sqrt{\bar{k}\bar{r}} \mu
+ \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
\\
& \leq
\max\{\alpha(\rho)\beta(\rho)/\lambda,\ \sqrt{\bar{k}}\}
(1-1/c)^{-1}
\|Q_{\bar{\Omega}}+Q_{\bar{T}}\|_\v2^2
\mu / 2
+ \lambda \bar{k} \mu
+ 2\sqrt{\bar{k}\bar{r}} \mu
+ \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
\\
& \leq
\lambda^{-1}
(1-1/c)^{-1}
\|Q_{\bar{\Omega}}+Q_{\bar{T}}\|_\v2^2
\mu / 2
+ \lambda \bar{k} \mu
+ 2\sqrt{\bar{k}\bar{r}} \mu
+ \bar{k} \|(\mathcal{P}_{{\bar{\Omega}}} \circ \mathcal{P}_{{\bar{T}}^\perp})(E)\|_\v\infty
\end{align*}
since $\bar{k} \leq \alpha(\rho)^2$, $\alpha(\rho)\beta(\rho) < 1$, and
$\lambda \alpha(\rho) \leq 1$.
Now we combine this with $\|{\Delta_S}\|_\v1 \leq \|\mathcal{P}_{{\bar{\Omega}}^\perp}({\Delta_S})\|_\v1 +
\|\mathcal{P}_{{\bar{\Omega}}}({\Delta_S})\|_\v1$ and Lemma~\ref{lemma:opt2-outside} to get the first
bound.

For the second bound, we use the facts
$\|{\Delta_S}\|_\v\infty \leq \|\hat{X}_S-Y\|_\v\infty + \|\bar{X}_S-Y\|_\v\infty \leq 2b$
and
$\|{\Delta_S}\|_\v2 \leq \sqrt{\|{\Delta_S}\|_\v1\|{\Delta_S}\|_\v\infty} \leq
\sqrt{2b\|{\Delta_S}\|_\v1}$.

For the third and fourth bounds, we obtain from~\eqref{eq:kkt2}
\begin{align*}
\|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_{\flat(\rho)}
& \leq \|\mathcal{P}_{\bar{T}}({\Delta_S})\|_{\flat(\rho)}
+ \|\mathcal{P}_{\bar{T}}(E)\|_{\flat(\rho)}
+ \mu\|\mathcal{P}_{\bar{T}}(G_L)\|_{\flat(\rho)}
\\
& \leq \|\mathcal{P}_{\bar{T}}\|_{\v1\to\flat(\rho)} \|{\Delta_S}\|_\v1
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ \mu\|\mathcal{P}_{\bar{T}}(G_L)\|_*
\quad \text{(Lemma~\ref{lemma:trace-bound})}
\\
& = \|\mathcal{P}_{\bar{T}}^*\|_{\sharp(\rho)\to\v\infty} \|{\Delta_S}\|_\v1
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ \mu\|\mathcal{P}_{\bar{T}}(G_L)\|_*
\quad \text{(Proposition~\ref{proposition:operator-dual})}
\\
& \leq \beta(\rho) \|{\Delta_S}\|_\v1
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ \mu\|\mathcal{P}_{\bar{T}}(G_L)\|_*
\quad \text{(Lemma~\ref{lemma:lowrank-bound})}
\\
& \leq \beta(\rho) \|{\Delta_S}\|_\v1
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ 2\bar{r}\mu
\quad \text{(Lemma~\ref{lemma:projections} and $\|G_L\|_{2\to2} \leq 1$)}
\end{align*}
and
\begin{align*}
\|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_*
& \leq \|\mathcal{P}_{\bar{T}}({\Delta_S})\|_*
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ \mu\|\mathcal{P}_{\bar{T}}(G_L)\|_*
\\
& \leq \sqrt{2\bar{r}} \|{\Delta_S}\|_\v2
+ \|\mathcal{P}_{\bar{T}}(E)\|_*
+ 2\bar{r}\mu
\quad \text{(Lemma~\ref{lemma:projections} and $\|G_L\|_{2\to2} \leq 1$)}
.
\end{align*}
Now we combine these with
\begin{align*}
\|{\Delta_L}\|_{\flat(\rho)}
& \leq \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_{\flat(\rho)} +
\|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_{\flat(\rho)}
\\
& \leq \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_* +
\min\{\|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_*,\|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_{\flat(\rho)}\}
\quad \text{(Lemma~\ref{lemma:trace-bound})}
\\
\|{\Delta_L}\|_*
& \leq \|\mathcal{P}_{{\bar{T}}^\perp}({\Delta_L})\|_* + \|\mathcal{P}_{{\bar{T}}}({\Delta_L})\|_*
\end{align*}
and Lemma~\ref{lemma:opt2-outside}.
\end{proof}
Note that we have an error bound for ${\Delta_L}$ in $\|\cdot\|_{\flat(\rho)}$
norm, which can be significantly smaller than the bound for the trace norm
of ${\Delta_L}$.

\subsubsection*{Acknowledgements}

We thank Emmanuel Cand\`es for clarifications about the results
in~\citep{CLMW09}.

redpajama_set_name: RedPajamaArXiv


text:
Q: I know my root password, so where do i type it to open this file? I have my root password, and just installed a keylogger for myself and after losing a long chunk of text i worked really hard on to a program crash. The keylogger installed just fine, using my root password in the terminal worked fine to, set the output file and started it.
Now how do i look at the output file? Under permissions, it say's that only root can read/write. How do i log in as root?

A: I wouldn't start a file browser instance with gksu to open a file.  I would use:
gksudo gedit /the/full/path/to/the/file

Or any other text editor it's easy to copy paste multi-page text from for that matter.

A: Enable open as administrator in nautilus!
To get started, press Ctrl – Alt – T on your keyboard to open Terminal. When it opens, run the commands below:
enter code here
sudo apt-get install nautilus-gksu

After installing that application run copy and paste the line below and press enter.
sudo cp /usr/lib/nautilus/extensions-2.0/libnautilus-gksu.so /usr/lib/nautilus/extensions-3.0/

Finally, log out and back in then go and test it, by clicking your right mouse click on the file you want to run as Admin and your see a popup menu with the words: open as administrater.

Visit: http://www.liberiangeek.net/2011/12/add-open-as-administrator-to-nautilus-context-menu-in-ubuntu-11-10-oneiric-ocelot/ for help and from here.
Enjoy!

A: First, Open Terminal
Type:
gksu nautilus <location>

will help to navigate as root.
sudo gedit <location>

will help to open / edit too.

redpajama_set_name: RedPajamaStackExchange


Are you willing to do what it takes to make your business thrive? It's not something that can be accomplished by doing things halfway or taking shortcuts. You can't be lazy about it, you have to put 100% into it.
What this suggests to me is there is a just a lot of plain laziness out there in the marketplace and very few people are talking about this using this word. For to do so would be judgmental and unkind even though profits are being drained away.
Laziness is so prevalent in our society (U.S.), I am surprised that anything gets done. The majority of people are born both mentally and physically fit. However, due to a variety of reasons, laziness takes over.
With the prevalent entitlement mentality, productivity suffers while other costs such as health care to the price of retail goods continue to spiral upward. The U.S. and even Britain's obesity rates confirm this change in behavior and the additional costs.
Just look at the parking lot of any grocery or retail store. How many carts are left stranded in parking places because someone was just too darn lazy to return the cart to one of those cart holding stands?
This laziness also has a much deeper meaning and that is the total 100% disrespect for all those other shoppers who have to weave around those unintended shopping carts. (Think ethics and beliefs) Heaven forbid if it is a windy day and a sudden gust takes the cart and slams it into your vehicle or worse yet, your child! My sense is many of those lazy people would be the first to complain if their car was damaged, or their child was harmed by a stray unattended shopping cart.
When people are lazy in sales, in business and in life, their behaviors affect everyone else because of their poor business ethics. This is why it is important to focus on what you can control and have an action plan to support that focus. Additionally, it is critical to have a unified and shared positive core values throughout your organization.
As one final observation if you choose to be lazy, then do not expect others to pick up your slack. You have 100% control of the actions you take from picking up that phone to call a potential customer to what food you place into your mouth. Personal responsibility and accountability are key attributes or talents not only for professional sales people but everyone else as well.


text:
Have a news? Write to us.
The Amazing eBook
COVID-19-Learn Freelancing & Online Work
Freelancing questions
Ratan Tata
BitcoinInternet
Bitcoin is trying to make a comeback
by Hisham Sarwar Twitter | Facebook January 6, 2017, 8:18 pm 114 Views
On Thursday Bitcoin reached to the lowest levels in two years. The currency earlier fell by 20% but this time it went down 13% to $985.68 per coin as of 11:10 a.m. ET. But on the first trading day of the New Year, for the first time since 2013 the crypto curruncy crossed the $1,000 mark. But now it has dropped down from that level.
Just before the fall Bitcoin almost gained 100%. The reason for its surge was the renewed interest from China. Bitcoin in China became a strong currency whereas its own currency Yuan continued to fall. Since record keeping began in 2010, Yuan experienced its biggest two-day surge on Thursday. It happened because the Chinese government made all efforts to stop the outflows from the country. The overnight borrowing costs in Hong Kong went up to 100%. Yuan's rise has pressed the investors who were expecting further fall in Chinese currency. US dollar, which fell against other currencies is under pressure because of Yuan's rise.
Via: Business Insider
Previous article World's biggest Freelance marketplaces for online work
Next article Retina VR
Written by Hisham Sarwar
https://www.youtube.com/watch?v=OAi5HVJbixQ
That is all you ever need to know about me but let me warn you, freelancing for me is a journey, certainly not a destination :)
6 Startups that you can begin on your own January 28, 2023
A Fundamental Mistake Freelancers Make January 27, 2023
5 Things needed to become a successful freelancer January 27, 2023
96% of workers are looking for a new job in 2023 January 27, 2023
The Amazing Benefits of Work From Home January 25, 2023
Upwork releases most-in-demand Freelance skills of 2023 January 25, 2023
6 Startups that you can begin on your own
by Hina Javed Malik January 28, 2023, 2:52 pm
A Fundamental Mistake Freelancers Make
by Laiba Shahzad January 27, 2023, 10:37 am
5 Things needed to become a successful freelancer
by Ali Younus January 27, 2023, 9:40 am
The Amazing Benefits of Work From Home
Upwork releases most-in-demand Freelance skills of 2023
by Madiha Yaqoob January 25, 2023, 2:05 pm
About Being Guru
BeingGuru is a Freelancing, motivation and technology blog. The website covers latest technology news, showcases videos to teach freelancing and writes about motivation…
© 2023 BeingGuru.com - All rights reserved

redpajama_set_name: RedPajamaCommonCrawl


Neu-Dorf was a khutor (farmstead) located 42 kilometers north of Fedorovka, on the right bank of the Mius River. All of its inhabitants were Volga German Lutherans who had relocated from the daughter colony of Gnadenflur.
Nothing remains of the khutor. The geographic coordinates are approximate, based on Soviet maps from the 1930s.
There was no known religious structure in Neu-Dorf.