Fast Algorithms for Robust PCA via Gradient Descent

Introduction

While there have been recent results developing provably robust algorithms for PCA (e.g., ), the running times range from $\mathcal{O}(r^{2}d^{2})$ to $\mathcal{O}(d^{3})$For precise dependence on error and other factors, please see details below. and hence are significantly worse than SVD. Meanwhile, the literature developing sub-quadratic algorithms for PCA (e.g., ) seems unable to guarantee robustness to outliers or missing data.

Our contribution lies precisely in this area: provably robust algorithms for PCA with improved run-time. Specifically, we provide an efficient algorithm with running time that matches SVD while nearly matching the best-known robustness guarantees. In the case where rank is small compared to dimension, we develop an algorithm with running time that is nearly linear in the dimension. This last algorithm works by subsampling the data, and therefore we also show that our algorithm solves the Robust PCA problem with partial observations (a generalization of matrix completion and Robust PCA).

Provable solutions for this model are first provided in the works of and . They propose to solve this problem by convex relaxation:

where $|\!|\!|M|\!|\!|_{{\mbox{\tiny{nuc}}}}$ denotes the nuclear norm of $M$. Despite analyzing the same method, the corruption models in and differ. In , the authors consider the setting where the entries of $M^{*}$ are corrupted at random with probability $\alpha$. They show their method succeeds in exact recovery with $\alpha$ as large as $0.1$, which indicates they can tolerate a constant fraction of corruptions. Work in considers a deterministic corruption model, where nonzero entries of $S^{*}$ can have arbitrary position, but the sparsity of each row and column does not exceed $\alpha d$. They prove that for exact recovery, it can allow $\alpha=\mathcal{O}(1/(\mu r\sqrt{d}))$. This was subsequently further improved to $\alpha=\mathcal{O}(1/(\mu r))$, which is in fact optimal . Here, $\mu$ represents the incoherence of $M^{*}$ (see Section 2 for details). In this paper, we follow this latter line and focus on the deterministic corruption model.

The state-of-the-art solver for (1) has time complexity $\mathcal{O}(d^{3}/\varepsilon)$ to achieve error $\varepsilon$, and is thus much slower than SVD, and prohibitive for even modest values of $d$. Work in considers the deterministic corruption model, and improves this running time without sacrificing the robustness guarantee on $\alpha$. They propose an alternating projection (AltProj) method to estimate the low rank and sparse structures iteratively and simultaneously, and show their algorithm has complexity $\mathcal{O}(r^{2}d^{2}\log(1/\varepsilon))$, which is faster than the convex approach but still slower than SVD.

After the initial post of our paper on arxiv, Cherapanamjeri et al. posted their paper on solving robust PCA with partial observations by a method modified from AltProj. Their approach is shown to have optimal robustness. The sample complexity they established is $\mathcal{O}(\mu^{2}r^{2}d\log^{2}d\log^{2}(1/\varepsilon))$, which depends on the estimation error $\varepsilon$, since the analysis of AltProj under partial observations requires sampling splitting. In contrast, the sample complexity $\mathcal{O}(\mu^{2}r^{2}d\log d)$ of our approach (see Corollary 2) does not have such dependence. Moreover, their method requires computing rank-$r$ SVD of the observed matrices in every round of iterations. Our algorithm only needs to compute rank-$r$ SVD (approximately) once in the initialization step.

It is worth mentioning other works that obtain provable guarantees of non-convex algorithms or problems including phase retrieval , EM algorithms , tensor decompositions and second order method . It might be interesting to bring robust considerations to these works.

2 Our Contributions

In this paper, we develop efficient non-convex algorithms for robust PCA. We propose a novel algorithm based on the projected gradient method on the factorized space. We also extend it to solve robust PCA in the setting with partial observations, i.e., in addition to gross corruptions, the data matrix has a large number of missing values. Our main contributions are summarized as follows.To ease presentation, the discussion here assumes $M^{*}$ has constant condition number, whereas our results below show the dependence on condition number explicitly.

We propose a novel sparse estimator for the setting of deterministic corruptions. For the low-rank structure to be identifiable, it is natural to assume that deterministic corruptions are “spread out” (no more than some number in each row/column). We leverage this information in a simple but critical algorithmic idea, that is tied to the ultimate complexity advantages our algorithm delivers.

Based on the proposed sparse estimator, we propose a projected gradient method on the matrix factorized space. While non-convex, the algorithm is shown to enjoy linear convergence under proper initialization. Along with a new initialization method, we show that robust PCA can be solved within complexity $\mathcal{O}(rd^{2}\log(1/\varepsilon))$ while ensuring robustness $\alpha=\mathcal{O}(1/(\mu r^{1.5}))$. Our algorithm is thus faster than the best previous known algorithm by a factor of $r$, and enjoys superior empirical performance as well.

Algorithms for Robust PCA with partial observations still rely on a computationally expensive convex approach, as apparently this problem has evaded treatment by non-convex methods. We consider precisely this problem. In a nutshell, we show that our gradient method succeeds (it is guaranteed to produce the subspace of $M^{*}$) even when run on no more than $\mathcal{O}(\mu^{2}r^{2}d\log d)$ random entries of $Y$. The computational cost is $\mathcal{O}(\mu^{3}r^{4}d\log d\log(1/\varepsilon))$. When rank $r$ is small compared to the dimension $d$, in fact this dramatically improves on our bound above, as our cost becomes nearly linear in $d$. We show, moreover, that this savings and robustness to erasures comes at no cost in the robustness guarantee for the deterministic (gross) corruptions. While this demonstrates our algorithm is robust to both outliers and erasures, it also provides a way to reduce computational costs even in the fully observed setting, when $r$ is small.

An immediate corollary of the above result provides a guarantee for exact matrix completion, with general rectangular matrices, using $\mathcal{O}(\mu^{2}r^{2}d\log d)$ observed entries and $\mathcal{O}(\mu^{3}r^{4}d\log d\log(1/\varepsilon))$ time, thereby improving on existing results in .

3 Organization and Notation

The remainder of this paper is organized as follows. In Section 2, we formally describe our problem and assumptions. In Section 3, we present and describe our algorithms for fully (Algorithm 1) and partially (Algorithm 2) observed settings. In Section 4.1, we establish theoretical guarantees of Algorithm 1. The theory for partially observed setting are presented in Section 4.2. The numerical results are collected in Section 5. Sections 6, 7 and Appendix A contain all the proofs and technical lemmas.

Problem Setup

(ii) The entries of $S^{*}$ are “spread out” – for $\alpha\in[0,1)$, we assume $S^{*}\in\mathcal{S}_{\alpha}$, where

In other words, $S^{*}$ contains at most $\alpha$-fraction nonzero entries per row and column.

Algorithms

For both the full and partial observation settings, our method proceeds in two phases. In the first phase, we use a new sorting-based sparse estimator to produce a rough estimate $S_{\text{init}}$ for $S^{*}$ based on the observed matrix $Y$, and then find a rank $r$ matrix factorized as $U_{0}V_{0}^{\top}$ that is a rough estimate of $M^{*}$ by performing SVD on ($Y-S_{\text{init}}$). In the second phase, given $(U_{0},V_{0})$, we perform an iterative method to produce series $\{(U_{t},V_{t})\}_{t=0}^{\infty}$. In each step $t$, we first apply our sparse estimator to produce a sparse matrix $S_{t}$ based on $(U_{t},V_{t})$, and then perform a projected gradient descent step on the low-rank factorized space to produce $(U_{t+1},V_{t+1})$. This flow is the same for full and partial observations, though a few details differ. Algorithm 1 gives the full observation algorithm, and Algorithm 2 gives the partial observation algorithm. We now describe the key details of each algorithm.

where $A_{(i,\cdot)}^{(k)}$ and $A_{(\cdot,j)}^{(k)}$ denote the elements of $A_{(i,\cdot)}$ and $A_{(\cdot,j)}$ that have the $k$-th largest magnitude respectively. In other words, we choose to keep those elements that are simultaneously among the largest $\alpha$-fraction entries in the corresponding row and column. In the case of entries having identical magnitude, we break ties arbitrarily. It is thus guaranteed that $\mathcal{T}_{\alpha}\left[A\right]\in\mathcal{S}_{\alpha}$.

Initialization.

In the fully observed setting, we compute $S_{\text{init}}$ based on $Y$ as $S_{\text{init}}=\mathcal{T}_{\alpha}\left[Y\right]$. In the partially observed setting with sampling rate $p$, we let $S_{\text{init}}=\mathcal{T}_{2p\alpha}\left[Y\right]$. In both cases, we then set $U_{0}=L\Sigma^{1/2}$ and $V_{0}=R\Sigma^{1/2}$, where $L\Sigma R^{\top}$ is an SVD of the best rank $r$ approximation of $Y-S_{\text{init}}$.

Gradient Method on Factorized Space.

After initialization, we proceed by projected gradient descent. To do this, we define loss functions explicitly in the factored space, i.e., in terms of $U,V$ and $S$:

Recall that our goal is to recover $M^{*}$ that satisfies the $\mu$-incoherent condition. Given an SVD $M^{*}=L^{*}\Sigma R^{*\top}$, we expect that the solution $(U,V)$ is close to $(L^{*}\Sigma^{1/2},R^{*}\Sigma^{1/2})$ up to some rotation. In order to serve such $\mu$-incoherent structure, it is natural to put constraints on the row norms of $U,V$ based on $|\!|\!|M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$. As $|\!|\!|M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$ is unavailable, given $U_{0},V_{0}$ computed in the first phase, we rely on the sets $\mathcal{U}$, $\mathcal{V}$ defined as

Now we consider the following optimization problems with constraints:

The regularization term in the objectives above is used to encourage that $U$ and $V$ have the same scale. Given $(U_{0},V_{0})$, we propose the following iterative method to produce series $\{(U_{t},V_{t})\}_{t=0}^{\infty}$ and $\{S_{t}\}_{t=0}^{\infty}$. We give the details for the fully observed case – the partially observed case is similar. For $t=0,1,\ldots$, we update $S_{t}$ using the sparse estimator $S_{t}=\mathcal{T}_{\gamma\alpha}\left[Y-U_{t}V_{t}^{\top}\right]$, followed by a projected gradient update on $U_{t}$ and $V_{t}$

Here $\alpha$ is the model parameter that characterizes the corruption fraction, $\gamma$ and $\eta$ are algorithmic tunning parameters, which we specify in our analysis. Essentially, the above algorithm corresponds to applying projected gradient method to optimize (8), where $S$ is replaced by the aforementioned sparse estimator in each step.

Main Results

In this section, we establish theoretical guarantees for Algorithm 1 in the fully observed setting and for Algorithm 2 in the partially observed setting.

We begin with some definitions and notation. It is important to define a proper error metric because the optimal solution corresponds to a manifold and there are many distinguished pairs $(U,V)$ that minimize (8). Given the SVD of the true low-rank matrix $M^{*}=L^{*}\Sigma^{*}R^{*\top}$, we let $U^{*}:=L^{*}\Sigma^{*1/2}$ and $V^{*}:=R^{*}\Sigma^{*1/2}$. We also let $\sigma_{1}^{*}\geq\sigma_{2}^{*}\geq\ldots\geq\sigma_{r}^{*}$ be sorted nonzero singular values of $M^{*}$, and denote the condition number of $M^{*}$ by $\kappa$, i.e., $\kappa:=\sigma_{1}^{*}/\sigma_{r}^{*}$. We define estimation error $d(U,V;U^{*},V^{*})$ as the minimal Frobenius norm between $(U,V)$ and $(U^{*},V^{*})$ with respect to the optimal rotation, namely

when $d(U,V;U^{*},V^{*})\leq\sqrt{\sigma_{1}^{*}}$. We denote the local region around the optimum $(U^{*},V^{*})$ with radius $\omega$ as

The next two theorems provide guarantees for the initialization phase and gradient iterations, respectively, of Algorithm 1. The proofs are given in Sections 6.1 and 6.2.

Consider the paired $(U_{0},V_{0})$ produced in the first phase of Algorithm 1. If $\alpha\leq 1/(16\kappa\mu r)$, we have

Therefore, using proper initialization and step size, the gradient iteration converges at a linear rate with a constant contraction factor $1-\mathcal{O}(1/\kappa)$. To obtain relative precision $\varepsilon$ compared to the initial error, it suffices to perform $O(\kappa\log(1/\varepsilon))$ iterations. Note that the step size is chosen according to $1/\sigma_{1}^{*}$. When $\alpha\lesssim 1/(\mu\sqrt{\kappa r^{3}})$, Theorem 1 and the inequality (11) together imply that $|\!|\!|U_{0}V_{0}^{\top}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}\leq\frac{1}{2}\sigma_{1}^{*}$. Hence we can set the step size as $\eta=\mathcal{O}(1/\sigma_{1}(U_{0}V_{0}^{\top}))$ using being the top singular value $\sigma_{1}(U_{0}V_{0}^{\top})$ of the matrix $U_{0}V_{0}^{\top}$

Combining Theorems 1 and 2 implies the following result, proved in Section 6.3, that provides an overall guarantee for Algorithm 1.

for some constant $c$. Then for any $\varepsilon\in(0,1)$, Algorithm 1 with $T=\mathcal{O}(\kappa\log(1/\varepsilon))$ outputs a pair $(U_{T},V_{T})$ that satisfies

For simplicity we assume $d_{1}=d_{2}=d$. Our sparse estimator (4) can be implemented by finding the top $\alpha d$ elements of each row and column via partial quick sort, which has running time $\mathcal{O}({d^{2}\log(\alpha d)})$. Performing rank-$r$ SVD in the first phase and computing the gradient in each iteration both have complexity $\mathcal{O}(rd^{2})$.In fact, it suffices to compute the best rank-$r$ approximation with running time independent of the eigen gap. Algorithm 1 thus has total running time $\mathcal{O}(\kappa rd^{2}\log(1/\varepsilon))$ for achieving an $\epsilon$ accuracy as in (12). We note that when $\kappa=\mathcal{O}(1)$, our algorithm is orderwise faster than the AltProj algorithm in , which has running time $\mathcal{O}(r^{2}d^{2}\log(1/\varepsilon))$. Moreover, our algorithm only requires computing one singular value decomposition.

Assuming $\kappa=\mathcal{O}(1)$, our algorithm can tolerate corruption at a sparsity level up to $\alpha=\mathcal{O}(1/(\mu r\sqrt{r}))$. This is worse by a factor $\sqrt{r}$ compared to the optimal statistical guarantee $1/(\mu r)$ obtained in . This looseness is a consequence of the condition for $(U_{0},V_{0})$ in Theorem 2. Nevertheless, when $\mu r=\mathcal{O}(1)$, our algorithm can tolerate a constant $\alpha$ fraction of corruptions.

Notably, we show that gradient descent works in the case of $\alpha=\mathcal{O}(1/(\mu r))$ if initialization is sufficiently close. Accordingly, to provide an algorithm with optimal robustness, it is straightforward to use a more complicated initial method such as AltProj that can tolerate $1/(\mu r)$ fraction of corruptions while satisfying our initial condition. As gradient descent provides a simple and efficient way to successively refine the estimation, such combination still gives a better running time than prior arts.

2 Analysis of Algorithm 2

We now move to the guarantees of Algorithm 2. We show here that not only can we handle partial observations, but in fact subsampling the data in the fully observed case can significantly reduce the time complexity from the guarantees given in the previous section without sacrificing robustness. In particular, for smaller values of $r$, the complexity of Algorithm 2 has near linear dependence on the dimension $d$, instead of quadratic.

In the following discussion, we let $d:=\max\{d_{1},d_{2}\}$. The next two results, proved in Sections 6.4 and 6.5, control the quality of the initialization step, and then the gradient iterations.

Suppose the observed indices $\Phi$ follow the Bernoulli model given in (2). Consider the pair $(U_{0},V_{0})$ produced in the first phase of Algorithm 2. There exist constants $\{c_{i}\}_{i=1}^{3}$ such that for any $\epsilon\in(0,\sqrt{r}/(8c_{1}\kappa))$, if

with probability at least $1-c_{3}d^{-1}$.

Suppose the observed indices $\Phi$ follow the Bernoulli model given in (2). Consider the second phase of Algorithm 2. Suppose we choose $\gamma=3$, and $\eta=c/(\mu r\sigma_{1}^{*})$ for a sufficiently small constant $c$. There exist constants $\{c_{i}\}_{i=1}^{4}$ such that if

then with probability at least $1-c_{3}d^{-1}$, the iterates $\{(U_{t},V_{t})\}_{t=0}^{\infty}$ satisfy

The above result ensures linear convergence to $(U^{*},V^{*})$ (up to rotation) even when the gradient iterations are computed using partial observations. Note that setting $p=1$ recovers Theorem 2 up to an additional factor $\mu r$ in the contraction factor. For achieving $\varepsilon$ relative accuracy, now we need $\mathcal{O}(\mu r\kappa\log(1/\varepsilon))$ iterations.

Putting Theorems 3 and 4 together, we have the following overall guarantee, proved in Section 6.6, for Algorithm 2.

for some constants $c,c^{\prime}$. With probability at least $1-\mathcal{O}(d^{-1})$, for any $\varepsilon\in(0,1)$, Algorithm 2 with $T=\mathcal{O}(\mu r\kappa\log(1/\varepsilon))$ outputs a pair $(U_{T},V_{T})$ that satisfies

This result shows that partial observations do not compromise robustness to sparse corruptions: as long as the observation probability $p$ satisfies the condition in Corollary 2, Algorithm 2 enjoys the same robustness guarantees as the method using all entries. Below we provide two remarks on the sample and time complexity. For simplicity, we assume $d_{1}=d_{2}=d$, $\kappa=\mathcal{O}(1)$.

Using the lower bound on $p$, it is sufficient to have $\mathcal{O}(\mu^{2}r^{2}d\log d)$ observed entries. In the special case $S^{*}=0$, our partial observation model is equivalent to the model of exact matrix completion (see, e.g., ). We note that our sample complexity (i.e., observations needed) matches that of completing a positive semidefinite (PSD) matrix by gradient descent as shown in , and is better than the non-convex matrix completion algorithms in and . Accordingly, our result reveals the important fact that we can obtain robustness in matrix completion without deterioration of our statistical guarantees. It is known that that any algorithm for solving exact matrix completion must have sample size $\Omega(\mu rd\log d)$ , and a nearly tight upper bound $O(\mu rd\log^{2}d)$ is obtained in by convex relaxation. While sub-optimal by a factor $\mu r$, our algorithm is much faster than convex relaxation as shown below.

Our sparse estimator on the sparse matrix with support $\Phi$ can be implemented via partial quick sort with running time $\mathcal{O}({pd^{2}\log(\alpha pd)})$. Computing the gradient in each step involves the two terms in the objective function (9). Computing the gradient of the first term $\widetilde{\mathcal{L}}$ takes time $\mathcal{O}(r|\Phi|)$, whereas the second term takes time $\mathcal{O}(r^{2}d)$. In the initialization phase, performing rank-$r$ SVD on a sparse matrix with support $\Phi$ can be done in time $\mathcal{O}(r|\Phi|)$. We conclude that when $|\Phi|=\mathcal{O}(\mu^{2}r^{2}d\log d)$, Algorithm 2 achieves the error bound (15) with running time $\mathcal{O}(\mu^{3}r^{4}d\log d\log(1/\varepsilon))$. Therefore, in the small rank setting with $r\ll d^{1/3}$, even when full observations are given, it is better to use Algorithm 2 by subsampling the entries of $Y$.

Numerical Results

In this section, we provide numerical results and compare the proposed algorithms with existing methods, including the inexact augmented lagrange multiplier (IALM) approach for solving the convex relaxation (1) and the alternating projection (AltProj) algorithm proposed in . All algorithms are implemented in MATLAB Our code is available at https://www.yixinyang.org/code/RPCA_GD.zip., and the codes for existing algorithms are obtained from their authors. SVD computation in all algorithms uses the PROPACK library.http://sun.stanford.edu/~rmunk/PROPACK/ We ran all simulations on a machine with Intel 32-core Xeon (E5-2699) 2.3GHz with 240GB RAM.

The results are summarized in Figure 1. Figure 1(a) shows the convergence of our algorithms for different random instances with different sub-sampling rate $p$ (note that $p=1$ corresponds to the fully observed setting). As predicted by Theorems 2 and 4, our gradient method converges geometrically with a contraction factor nearly independent of $p$. Figure 1(b) shows the running time of our algorithm with partially observed data. We see that the running time scales linearly with $d$, again consistent with the theory. We note that our algorithm is memory-efficient: in the large scale setting with $d=2\times 10^{5}$, using approximately $0.1\%$ entries is sufficient for the successful recovery. In contrast, AltProj and IALM are designed to manipulate the entire matrix with $d^{2}=4\times 10^{10}$ entries, which is prohibitive on a single machine. Figure 1(c) compares our algorithms with AltProj and IALM by showing reconstruction error versus real running time. Our algorithm requires significantly less computation to achieve the same accuracy level, and using only a subset of the entries provides additional speed-up.

2 Foreground-background Separation

We apply our method to the task of foreground-background (FB) separation in a video. We use two public benchmarks, the Restaurant and ShoppingMall datasets.http://perception.i2r.a-star.edu.sg/bk_model/bk_index.html Each dataset contains a video with static background. By vectorizing and stacking the frames as columns of a matrix $Y$, the FB separation problem can be cast as RPCA, where the static background corresponds to a low rank matrix $M^{*}$ with identical columns, and the moving objects in the video can be modeled as sparse corruptions $S^{*}$. Figure 2 shows the output of different algorithms on two frames from the dataset. Our algorithms require significantly less running time than both AltProj and IALM. Moreover, even with 20% sub-sampling, our methods still appear to achieve better separation quality (note that in each of the frames our algorithms remove a person that is not identified by the other algorithms).

Figure 3 shows recovery results for several more frames. Again, our algorithms enjoy better running time and outperform AltProj and IALM in separating persons from the background images. In Appendix B, we describe the detailed parameter settings for our algorithm.

Proofs

In this section we provide the proofs for our main theoretical results in Theorems 1–4 and Corollaries 1–2.

Let $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}:=Y-S_{\text{init}}$. As $Y=M^{*}+S^{*}$, we have $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}=S^{*}-S_{\text{init}}$. We obtain $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}\in\mathcal{S}_{2\alpha}$ because $S^{*},S_{\text{init}}\in\mathcal{S}_{\alpha}$.

We claim that $\|\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}\|_{\infty}\leq 2\|M^{*}\|_{\infty}$. Denote the support of $S^{*},S_{\text{init}}$ by $\Omega^{*}$ and $\Omega$ respectively. Since $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}$ is supported on $\Omega\cup\Omega^{*}$, to prove the claim it suffices to consider the following three cases.

For $(i,j)\in\Omega^{*}\cap\Omega$, due to rule of sparse estimation, we have $=0$.

For $(i,j)\in\Omega^{*}\setminus\Omega$, we must have $||\leq 2\|M^{*}\|_{\infty}$. Otherwise, we have $||=||>\|M^{*}\|_{\infty}$. So $||$ is larger than any uncorrupted entries in its row and column. Since there are at most $\alpha$ fraction corruptions per row and column, we have $\in\Omega$, which violates the prior condition $(i,j)\in\Omega^{*}\setminus\Omega$.

For the last case $(i,j)\in\Omega\setminus\Omega^{*}$, since $=$, trivially we have $||\leq\|M^{*}\|_{\infty}$.

The following result, proved in Section 7.1, relates the operator norm of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}$ to its infinite norm.

In the last step, we use the fact that $M^{*}$ satisfies the $\mu$-incoherent condition, which leads to

We denote the $i$-th largest singular value of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}$ by $\sigma_{i}$. By Weyl’s theorem, we have $|\sigma_{i}^{*}-\sigma_{i}|\leq|\!|\!|\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$ for all $i\in[d_{1}\wedge d_{2}]$. Since $\sigma_{r+1}^{*}=0$, we have $\sigma_{r+1}\leq|\!|\!|\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$. Recall that $U_{0}V_{0}^{\top}$ is the best rank $r$ approximation of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}$. Accordingly, we have

Under condition $\alpha\mu r\leq\frac{1}{16\kappa}$, we obtain $|\!|\!|U_{0}V_{0}^{\top}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}\leq\frac{1}{2}\sigma_{r}^{*}$. Applying Lemma 5.14 in (we provide it as Lemma 15 for the sake of completeness), we obtain

Plugging the upper bound of $|\!|\!|U_{0}V_{0}^{\top}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$ into the above inequality completes the proof.

2 Proof of Theorem 2

We essentially follow the general framework developed in for analyzing the behaviors of gradient descent in factorized low-rank optimization. But it is worth to note that only studies the symmetric and positive semidefinite setting, while we avoid such constraint on $M^{*}$. The techniques for analyzing general asymmetric matrix in factorized space is inspired by the recent work on solving low-rank matrix equations. In our setting, the technical challenge is to verify the local descent condition of the loss function (8), which not only has a bilinear dependence on $U$ and $V$, but also involves our sparse estimator (4).

We begin with some notations. Define the equivalent set of optimal solution as

As a result, for $\mathcal{U},\mathcal{V}$ constructed according to (7), we have

For $\mathcal{L}(U,V;S)$, we denote the gradient with respect to $M$ by $\nabla_{M}\mathcal{L}(U,V;S)$, i.e. $\nabla_{M}\mathcal{L}(U,V;S)=UV^{\top}+S-Y$.

The local descent property is implied by combining the following two results, which are proved in Section 6.7 and 6.8 respectively.

Here $\Delta_{U}:=U-U_{\pi^{*}}$, $\Delta_{V}:=V-V_{\pi^{*}}$, $\delta:=|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}+|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$, and $\nu:=9(\beta+6)\alpha\mu r+5\beta^{-1}$.

where $\delta$ is defined according to Lemma 2.

As another key ingredient, we establish the following smoothness condition, proved in Section 6.9, which indicates that the Frobenius norm of gradient decreases as $(U,V)$ approaches the optimal manifold.

With the above results in hand, we are ready to prove Theorem 2.

For $(U_{t},V_{t})$, let $(U_{\pi^{*}}^{t},V_{\pi^{*}}^{t}):=\arg\!\min_{(A,B)\in\mathcal{E}(M^{*})}|\!|\!|U_{t}-A|\!|\!|_{{\mbox{\tiny{F}}}}^{2}+|\!|\!|V_{t}-B|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. Define $\Delta_{U}^{t}:=U_{t}-U_{\pi^{*}}^{t}$, $\Delta_{V}^{t}:=V_{t}-V_{\pi^{*}}^{t}$.

where the second step follows from the non-expansion property of projection onto $\mathcal{U},\mathcal{V}$, which is implied by $\mathcal{E}(M^{*})\subseteq\mathcal{U}\times\mathcal{V}$ shown in (19). Since $\nabla_{U}\mathcal{L}_{t}=\left[\nabla_{M}\mathcal{L}_{t}\right]V$ and $\nabla_{V}\mathcal{L}_{t}=\left[\nabla_{M}\mathcal{L}_{t}\right]^{\top}U$, we have

Combining Lemma 2 and 3, under condition $\delta_{t}<\sigma_{r}^{*}$, we have that

By the assumption $\eta=c/\sigma_{1}^{*}$ for any constant $c\leq 1/36$, we thus have

In Lemma 2, choosing $\beta=320\kappa$ and assuming $\alpha\lesssim 1/(\kappa^{2}\mu r)$, we can have $\nu\leq 1/(32\kappa)$. Assuming $\delta_{t}\lesssim\sigma_{r}^{*}/\kappa$ leads to $14\sqrt{\sigma_{1}^{*}\delta_{t}^{3}}\leq\frac{1}{16}\sigma_{r}^{*}\delta_{t}$. We thus obtain

Under initial condition $\delta_{0}\lesssim\sigma_{r}^{*}/\kappa$, we obtain that such condition holds for all $t$ since estimation error decays geometrically after each iteration. Then applying (25) for all iterations, we conclude that for all $t=0,1,\ldots$,

3 Proof of Corollary 1

We need $\alpha\lesssim\frac{1}{\kappa^{2}\mu r}$ due to the condition of Theorem 2. In order to ensure the linear convergence happens, it suffices to let the initial error shown in Theorem 1 be less than the corresponding condition in Theorem 2. Accordingly, we need

which leads to $\alpha\lesssim\frac{1}{\mu\sqrt{r\kappa}^{3}}$.

Using the conclusion that gradient descent has linear convergence, choosing $T=\mathcal{O}(\kappa\log(1/\varepsilon))$, we have

Finally, applying the relationship between $d(U_{T},V_{T};U^{*},V^{*})$ and $|\!|\!|U_{T}V_{T}^{\top}-M^{*}|\!|\!|_{{\mbox{\tiny{F}}}}$ shown in (11), we complete the proof.

4 Proof of Theorem 3

Let $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}:=\frac{1}{p}(Y-S_{\text{init}})$. Similar to the proof of Theorem 1, we first establish an upper bound on $|\!|\!|\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-M^{*}|\!|\!|_{{\mbox{\tiny{op}}}}$. We have that

For the first term, we have $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}-\frac{1}{p}\Pi_{\Phi}M^{*}=\frac{1}{p}(\Pi_{\Phi}(S^{*})-S_{\text{init}})$ because $Y=\Pi_{\Phi}(M^{*}+S^{*})$. Lemma 10 shows that under condition $p\gtrsim\frac{\log d}{\alpha(d_{1}\wedge d_{2})}$, there are at most $\frac{3}{2}p\alpha$-fraction nonzero entries in each row and column of $\Pi_{\Phi}(S^{*})$ with high probability. Since $S_{\text{init}}\in\mathcal{S}_{2p\alpha}$, we have

Denote the support of $\Pi_{\Phi}(S^{*})$ and $S_{\text{init}}$ by $\Omega_{o}^{*}$ and $\Omega$. For $(i,j)\in\Omega_{o}^{*}\cap\Omega$ and $(i,j)\in\Omega\setminus\Omega_{o}^{*}$, we have $=0$ and $=-$, respectively. To prove the claim, it remains to show that for $(i,j)\in\Omega_{o}^{*}\setminus\Omega$, $||<2\|M^{*}\|_{\infty}$. If this is not true, then we must have $||>\|M^{*}\|_{\infty}$. Accordingly, $||$ is larger than the magnitude of any uncorrupted entries in its row and column. Note that on the support $\Phi$, there are at most $\frac{3}{2}p\alpha$ corruptions per row and column, we have $(i,j)\in\Omega$, which violates our prior condition $(i,j)\in\Omega_{o}^{*}\setminus\Omega$.

Using these two properties (27), (28) and applying Lemma 1, we have

For the second term in (26), we use the following lemma proved in .

Given the SVD $M^{*}=L^{*}\Sigma R^{*\top}$, for any $i\in[d_{1}]$, we have

We can bound $|\!|\!|M^{*\top}|\!|\!|_{{2,\infty}}$ similarly. Lemma 5 leads to

under condition $p\geq\frac{4\mu r^{2}\log d}{\epsilon^{2}(d_{1}\wedge d_{2})}$.

Putting (29) and (30) together, we obtain

Then using the fact that $U_{0}V_{0}^{\top}$ is the best rank $r$ approximation of $\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.67886pt}{0.43057pt}}{Y}$ and applying Wely’s theorem (see the proof of Theorem 1 for a detailed argument), we have

Under our assumptions, we have $16\alpha\mu r\sigma_{1}^{*}+2c^{\prime}\epsilon\sigma_{1}^{*}/\sqrt{r}\leq\frac{1}{2}\sigma_{r}^{*}$. Accordingly, Lemma 15 gives

We complete the proof by combining the above two inequalities.

5 Proof of Theorem 4

In this section, we turn to prove Theorem 4. Similar to the proof of Theorem 2, we rely on establishing the local descent and smoothness conditions. Compared to the full observation setting, we replace $\mathcal{L}$ by $\widetilde{\mathcal{L}}$ given in (6), while the regularization term $\widetilde{\mathcal{G}}(U,V):=\frac{1}{64}|\!|\!|U^{\top}U-V^{\top}V|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$ merely differs from $\mathcal{G}(U,V)$ given in (20) by a constant factor. It is thus sufficient to analyze the properties of $\widetilde{\mathcal{L}}$.

Define $\mathcal{E}(M^{*})$ according to (18). Under the initial condition, we still have

We prove the next two lemmas in Section 6.10 and 6.11 respectively. In both lemmas, for any $(U,V)\in\mathcal{U}\times\mathcal{V}$, we use shorthands

$\Delta_{U}:=U-U_{\pi^{*}}$, $\Delta_{V}:=V-V_{\pi^{*}}$, and $\delta:=|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}+|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. Recall that $d:=\max\{d_{1},d_{2}\}$.

Suppose $\mathcal{U},\mathcal{V}$ satisfy (31). Suppose we let

where we choose $\gamma=3$. For any $\beta>0$ and $\epsilon\in(0,\frac{1}{4})$, we define $\nu:=(14\beta+81)\alpha\mu r+26\sqrt{\epsilon}+18\beta^{-1}$. There exist constants $\{c_{i}\}_{i=1}^{2}$ such that if

then with probability at least $1-c_{2}d^{-1}$,

In the remainder of this section, we condition on the events in Lemma 6 and 7. Now we are ready to prove Theorem 4.

We essentially follow the process for proving Theorem 2. Let the following shorthands be defined in the same fashion: $\delta_{t}$, $(U_{\pi^{*}}^{t},V_{\pi^{*}}^{t})$, $(\Delta_{U}^{t},\Delta_{V}^{t})$, $\widetilde{\mathcal{L}}_{t}$, $\widetilde{\mathcal{G}}_{t}$.

Here we show error decays in one step of iteration. The induction process is the same as the proof of Theorem 2, and is thus omitted. For any $t\geq 0$, similar to (24) we have that

which can be lower bounded by Lemma 6. Note that $\widetilde{\mathcal{G}}$ differs from $\mathcal{G}$ by a constant, we can still leverage Lemma 3. Hence, we obtain that

where $c$ is a constant, and the last step is implied by Lemma 4 and Lemma 7.

By the assumption $\eta=c^{\prime}/[\mu r\sigma_{1}^{*}]$ for sufficiently small constant $c^{\prime}$, we thus have

Recall that $\nu:=(14\beta+81)\alpha\mu r+26\sqrt{\epsilon}+18\beta^{-1}$. By letting $\beta=c_{1}\kappa$, $\epsilon=c_{2}/\kappa^{2}$ and assuming $\alpha\leq c_{3}/(\mu r\kappa^{2})$ and $\delta_{t}\leq c_{4}\sigma_{r}^{*}/\kappa$ for some sufficiently small constants $\{c_{i}\}_{i=1}^{4}$, we can have $-2\eta(W_{1}+W_{2})+\eta^{2}(W_{3}+W_{4})\leq-\frac{1}{64}\eta\sigma_{r}^{*}\delta_{t}$, which implies that

6 Proof of Corollary 2

We need $\alpha\lesssim\frac{1}{\mu\kappa^{2}r}$ due to the condition of Theorem 4. Letting the initial error provided in Theorem 3 be less than the corresponding condition in Theorem 4, we have

Plugging the above two upper bounds into the second term in (13), it suffices to have

Comparing the above bound with the second term in (14) completes the proof.

7 Proof of Lemma 2

Plugging it back into the left hand side of (21), we obtain

Next we derive upper bounds of $T_{1}$ and $T_{2}$ respectively.

We denote the support of $S$, $S^{*}$ by $\Omega$ and $\Omega^{*}$ respectively. Since $S-S^{*}$ is supported on $\Omega^{*}\cup\Omega$, we have

Recall that for any $(i,j)\in\Omega$, we have $=$. Accordingly, we have

Now we turn to bound $W_{2}$. Since $S_{(i,j)}=0$ for any $(i,j)\in\Omega^{*}\setminus\Omega$, we have

Let $u_{i}$ be the $i$-th row of $M-M^{*}$, and $v_{j}$ be the $j$-th column of $M-M^{*}$. For any $k\in[d_{2}]$, we let $u_{i}^{(k)}$ denote the element of $u_{i}$ that has the $k$-th largest magnitude. Similarly, for any $k\in[d_{1}]$, we let $v_{j}^{(k)}$ denote the element of $v_{j}$ that has the $k$-th largest magnitude.

From the design of sparse estimator (4), we have that for any $(i,j)\in\Omega^{*}\setminus\Omega$, $||$ is either smaller than the $\gamma\alpha d_{2}$-th largest entry of the $i$-th row of $M^{*}+S^{*}-M$ or smaller than the $\gamma\alpha d_{1}$-th largest entry of the $j$-th column of $M^{*}+S^{*}-M$. Note that $S^{*}$ only contains at most $\alpha$-fraction nonzero entries per row and column. As a result, $||$ has to be less than the magnitude of $u_{i}^{(\gamma\alpha d_{2}-\alpha d_{2})}$ or $v_{j}^{(\gamma\alpha d_{1}-\alpha d_{1})}$. Formally, we have for $(i,j)\in\Omega^{*}\setminus\Omega$,

Meanwhile, for any $(i,j)\in\Omega^{*}\setminus\Omega$, we have

where $\beta$ in the last step can be any positive number. Combining (38) and (39) leads to

We introduce shorthand $\delta:=|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}+|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. We prove the following inequality in the end of this section.

where the last step follows from Lemma 14 by noticing that $\Pi_{\Omega}(M-M^{*})$ has at most $\gamma\alpha$-fraction nonzero entries per row and column.

To ease notation, we let $C:=M+S-M^{*}-S^{*}$. We observe that $C$ is supported on $\Omega^{c}$, we have

where the last step follows from (42) and $|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}}|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}\leq\delta/2$.

It remains to bound $W_{4}$. By Cauchy-Swartz inequality, we have

where step $(a)$ is from (37), step $(b)$ follows from (38), and step $(c)$ follows from (6.7). Combining the upper bounds of $W_{3}$ and $W_{4}$, we obtain

Combining pieces.

Now we choose $\gamma=2$. Then inequality (43) implies that

Plugging the above two inequalities into (35) completes the proof.

where the first step follows from the upper bound of $|\!|\!|M-M^{*}|\!|\!|_{{\mbox{\tiny{F}}}}$ shown in Lemma 12, and the second step follows from the assumption $|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}},|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}\leq\sqrt{\sigma_{1}^{*}}$.

8 Proof of Lemma 3

where the last step follows from $\Delta_{U}^{\top}U_{\pi^{*}}-\Delta_{V}^{\top}V_{\pi^{*}}=U^{\top}U_{\pi^{*}}-V^{\top}V_{\pi^{*}}$ since $U_{\pi^{*}}^{\top}U_{\pi^{*}}=V_{\pi^{*}}^{\top}V_{\pi^{*}}$. Note that

where we use $U_{\pi^{*}}^{\top}U_{\pi^{*}}=V_{\pi^{*}}^{\top}V_{\pi^{*}}$ again in the last step. Furthermore, since $U^{\top}U-V^{\top}V$ is symmetric, we have

Using these arguments, for the second term in (45), denoted by $T_{2}$, we have

It remains to find a lower bound of $|\!|\!|U^{\top}U-V^{\top}V|\!|\!|_{{\mbox{\tiny{F}}}}$. The following inequality, which we turn to prove later, is true:

Proceeding with the first term in (45) by using (47), we get

Introduce $\Delta_{F}:=F-F_{\pi^{*}}$. Recall that $\delta:=|\!|\!|\Delta_{U}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}+|\!|\!|\Delta_{V}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. Equivalently $\delta=|\!|\!|\Delta_{F}|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. We have

For the cross term, by the following result, proved in (we also provide a proof in Section 7.5 for the sake of completeness), we have $\langle\!\langle{\Delta_{F}F^{\top}_{\pi*}},\;{F_{\pi^{*}}\Delta_{F}^{\top}}\rangle\!\rangle\geq 0$.

When $|\!|\!|F-F_{\pi^{*}}|\!|\!|_{{\mbox{\tiny{op}}}}<\sqrt{2\sigma_{r}^{*}}$, we have that $\Delta_{F}^{\top}F_{\pi^{*}}$ is symmetric.

Accordingly, we have $|\!|\!|FF^{\top}-F_{\pi^{*}}F^{\top}_{\pi^{*}}|\!|\!|_{{\mbox{\tiny{F}}}}\geq 2\sqrt{\sigma_{r}^{*}\delta}-\delta\geq\sqrt{\sigma_{r}^{*}\delta}$ under condition $\delta\leq\sigma_{r}^{*}$. Plugging this lower bound into (48), we obtain

Putting (45), (46) and the above inequality together completes the proof.

Proof of inequality (47). For the term on the left hand side of (47), it is easy to check that

The property $U_{\pi^{*}}^{\top}U_{\pi^{*}}=V_{\pi^{*}}^{\top}V_{\pi^{*}}$ implies that $|\!|\!|U_{\pi^{*}}U_{\pi^{*}}^{\top}|\!|\!|_{{\mbox{\tiny{F}}}}=|\!|\!|V_{\pi^{*}}V_{\pi^{*}}^{\top}|\!|\!|_{{\mbox{\tiny{F}}}}=|\!|\!|U_{\pi^{*}}V_{\pi^{*}}^{\top}|\!|\!|_{{\mbox{\tiny{F}}}}$. Therefore, expanding those quadratic terms on the right hand side of (47), one can show that it is equal to

Comparing inequalities (49) and (50), it thus remains to show that

Equivalently, we always have $|\!|\!|U_{\pi^{*}}^{\top}U-V_{\pi^{*}}^{\top}V|\!|\!|_{{\mbox{\tiny{F}}}}^{2}\geq 0$, and thus prove (47).

9 Proof of Lemma 4

Now we turn to prove (22). We observe that

where we let $M:=UV^{\top}$. We denote the support of $S,S^{*}$ by $\Omega$ and $\Omega^{*}$ respectively. Based on the sparse estimator (4) for computing $S$, $\nabla_{M}\mathcal{L}(U,V;S)$ is only supported on $\Omega^{c}$. We thus have

It remains to upper bound the second term on the right hand side. Following (37) and (38), we have

where the last step is proved in (6.7). By choosing $\gamma=2$, we thus conclude that

10 Proof of Lemma 6

We denote the support of $\Pi_{\Phi}(S^{*})$, $S$ by $\Omega^{*}_{o}$ and $\Omega$. We always have $\Omega^{*}_{o}\subseteq\Phi$ and $\Omega\subseteq\Phi$.

In the sequel, we establish several results that characterize the properties of $\Phi$. The first result, proved in Section 7.2, shows that the Frobenius norm of any incoherent matrix whose row (or column) space are equal to $L^{*}$ (or $R^{*}$) is well preserved under partial observations supported on $\Phi$.

We need the next result, proved in Section 7.3, to control the number of nonzero entries per row and column in $\Omega^{*}_{o}$ and $\Phi$.

If $p\geq\frac{56}{3}\frac{\log d}{\alpha(d_{1}\wedge d_{2})}$, then with probability at least $1-6d^{-1}$, we have

The next lemma, proved in Section 7.4, can be used to control the projection of small matrices to $\Phi$.

In the remainder of this section, we condition on the events in Lemmas 9, 10 and 11. Now we are ready to prove Lemma 6.

Plugging it back into the left hand side of (21), we obtain

Next we derive lower bounds of $T_{1}$, upper bounds of $T_{2}$ and $T_{3}$ respectively.

We observe that $M-M^{*}=U_{\pi^{*}}^{*}\Delta_{V}^{\top}+\Delta_{U}V_{\pi^{*}}^{\top}+\Delta_{U}\Delta_{V}^{\top}$. By triangle inequality, we have

Note that when $c\geq a-b$ for $a,b\geq 0$, we always have $c^{2}\geq\frac{1}{2}a^{2}-b^{2}$. We thus have

where the second step is implied by Lemma 9, the third step follows from (51) in Lemma 11 by noticing that $|\!|\!|\Delta_{U}|\!|\!|_{{2,\infty}}\leq 3\sqrt{\mu r\sigma_{1}^{*}/d_{1}}$ and $|\!|\!|\Delta_{V}|\!|\!|_{{2,\infty}}\leq 3\sqrt{\mu r\sigma_{1}^{*}/d_{1}}$, which is further implied by (31).

Since $S-S^{*}$ is supported on $\Omega^{*}_{0}\cup\Omega$, we have

For any $(i,j)\in\Omega$, we have $(S-S^{*})_{(i,j)}=(M^{*}-M)_{(i,j)}$. Therefore, for the second term on the right hand side, we have

where the last inequality follows from Lemma 14 and the fact that $|\Omega_{(i,\cdot)}|\leq\gamma p\alpha d_{2}$, $|\Omega_{(\cdot,j)}|\leq\gamma p\alpha d_{1}$ for all $i\in[d_{1}]$, $j\in[d_{2}]$.

We denote the $i$-th row of $\Pi_{\Phi}(M-M^{*})$ by $u_{i}$, and we denote the $j$-th column of $\Pi_{\Phi}(M-M^{*})$ by $v_{j}$. We let $u_{i}^{(k)}$ denote the element of $u_{i}$ that has the $k$-th largest magnitude. We let $v_{j}^{(k)}$ denote the element of $v_{j}$ that has the $k$-th largest magnitude.

For the first term on the right hand side of (55), we first observe that for $(i,j)\in\Omega^{*}_{o}\setminus\Omega$, $|(M^{*}+S^{*}-M)_{(i,j)}|$ is either less than the $\gamma p\alpha d_{2}$-th largest element in the $i$-th row of $\Pi_{\Phi}(M^{*}+S^{*}-M)$, or less than $\gamma p\alpha d_{1}$-th largest element in the $j$-th row of $\Pi_{\Phi}(M^{*}+S^{*}-M)$. Based on Lemma 10, $\Pi_{\Phi}(S^{*})$ has at most $3p\alpha d_{2}/2$ nonzero entries per row and at most $3p\alpha d_{1}/2$ nonzero entries per column. Therefore, we have

where the second step holds for any $\beta>0$ and the last step follows from Lemma 14 under the size constraints of $\Omega^{*}_{o}$ shown in Lemma 10. For the second term in (58), using (57), we have

where the second step follows from Lemma 9 and inequality (51) in Lemma 11. Putting (55)-(60) together, we obtain

where we use (51) in Lemma 11 in the second step.

We observe that $\Pi_{\Phi}(M-M^{*}+S-S^{*})$ is supported on $\Phi\setminus\Omega$. Therefore, we have

where the third step follows from (6.10), and the last step is from (60). Under assumptions $\gamma=3$, $\epsilon\leq 1/4$ and $\delta\leq\sigma_{1}^{*}$, we have

Combining pieces.

Under the aforementioned assumptions, putting all pieces together leads to

11 Proof of Lemma 7

Conditioning on the event in Lemma 11, since $(U,V)\in\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.17749pt}{0.43057pt}}{\mathcal{U}}\times\makebox[0.0pt][l]{\hskip 2.05pt\rule[8.12498pt]{5.17749pt}{0.43057pt}}{\mathcal{V}}$, inequalities (52) and (53) imply that

It remains to bound the term $|\!|\!|\Pi_{\Phi}\left(M+S-M^{*}-S^{*}\right)|\!|\!|_{{\mbox{\tiny{F}}}}^{2}$. Let $\Omega^{*}_{o}$ and $\Omega$ be the support of $\Pi_{\Phi}(S^{*})$ and $S$ respectively. We observe that

In the proof of Lemma 6, it is shown in (6.10) that

We thus finish proving our conclusion by combining all pieces and noticing that $\gamma=3$ and $\epsilon\leq 1/4$.

Proofs for Technical Lemmas

In this section, we prove several technical lemmas that are used in the proofs of our main theorems.

It is thus implied that $|\!|\!|A|\!|\!|_{{\mbox{\tiny{op}}}}\leq\frac{1}{2}\alpha(\beta^{-1}d_{2}+\beta d_{1})\|A\|_{\infty}$. Choosing $\beta=\sqrt{d_{2}/d_{1}}$ completes the proof.