Non-convex Robust PCA

Keywords:

Robust PCA, matrix decomposition, non-convex methods, alternating projections.

Introduction

Principal component analysis (PCA) is a common procedure for preprocessing and denoising, where a low rank approximation to the input matrix (such as the covariance matrix) is carried out. Although PCA is simple to implement via eigen-decomposition, it is sensitive to the presence of outliers, since it attempts to “force fit” the outliers to the low rank approximation. To overcome this, the notion of robust PCA is employed, where the goal is to remove sparse corruptions from an input matrix and obtain a low rank approximation. Robust PCA has been employed in a wide range of applications, including background modeling [LHGT04], 3d reconstruction [MZYM11], robust topic modeling [Shi13], and community detection [CSX12], and so on.

Concretely, robust PCA refers to the following problem: given an input matrix $M=L^{*}+S^{*}$, the goal is to decompose it into sparse $S^{*}$ and low rank $L^{*}$ matrices. The seminal works of [CSPW11, CLMW11] showed that this problem can be provably solved via convex relaxation methods, under some natural conditions on the low rank and sparse components. While the theory is elegant, in practice, convex techniques are expensive to run on a large scale and have poor convergence rates. Concretely, for decomposing an $m\times n$ matrix, say with $m\leq n$, the best specialized implementations (typically first-order methods) have a per-iteration complexity of $O\left({m^{2}n}\right)$, and require $O(1/\epsilon)$ number of iterations to achieve an error of $\epsilon$. In contrast, the usual PCA, which carries out a rank-$r$ approximation of the input matrix, has $O(rmn)$ complexity per iteration – drastically smaller when $r$ is much smaller than $m,n$. Moreover, PCA requires exponentially fewer iterations for convergence: an $\epsilon$ accuracy is achieved with only $O\left({\log(1/\epsilon)}\right)$ iterations (assuming constant gap in singular values).

In this paper, we design a non-convex algorithm which is “best of both the worlds” and bridges the gap between (the usual) PCA and convex methods for robust PCA. Our method has low computational complexity similar to PCA (i.e. scaling costs and convergence rates), and at the same time, has provable global convergence guarantees, similar to the convex methods. Proving global convergence for non-convex methods is an exciting recent development in machine learning. Non-convex alternating minimization techniques have recently shown success in many settings such as matrix completion [Kes12, JNS13, Har13], phase retrieval [NJS13], dictionary learning [AAJ+13], tensor decompositions for unsupervised learning [AGH+12], and so on. Our current work on the analysis of non-convex methods for robust PCA is an important addition to this growing list.

We propose a simple intuitive algorithm for robust PCA with low per-iteration cost and a fast convergence rate. We prove tight guarantees for recovery of sparse and low rank components, which match those for the convex methods. In the process, we derive novel matrix perturbation bounds, when subject to sparse perturbations. Our experiments reveal significant gains in terms of speed-ups over the convex relaxation techniques, especially as we scale the size of the input matrices.

Our method consists of simple alternating (non-convex) projections onto low-rank and sparse matrices. For an $m\times n$ matrix, our method has a running time of $O(r^{2}mn\log(1/\epsilon))$, where $r$ is the rank of the low rank component. Thus, our method has a linear convergence rate, i.e. it requires $O(\log(1/\epsilon))$ iterations to achieve an error of $\epsilon$, where $r$ is the rank of the low rank component $L^{*}$. When the rank $r$ is small, this nearly matches the complexity of PCA, (which is $O(rmn\log(1/\epsilon))$).

We prove recovery of the sparse and low rank components under a set of requirements which are tight and match those for the convex techniques (up to constant factors). In particular, under the deterministic sparsity model, where each row and each column of the sparse matrix $S^{*}$ has at most $\alpha$ fraction of non-zeros, we require that $\alpha=O\left({1/(\mu^{2}r)}\right)$, where $\mu$ is the incoherence factor (see Section 3).

In addition to strong theoretical guarantees, in practice, our method enjoys significant advantages over the state-of-art solver for (1), viz., the inexact augmented Lagrange multiplier (IALM) method [CLMW11]. Our method outperforms IALM in all instances, as we vary the sparsity levels, incoherence, and rank, in terms of running time to achieve a fixed level of accuracy. In addition, on a real dataset involving the standard task of foreground-background separation [CLMW11], our method is significantly faster and provides visually better separation.

2 Related Work

Guaranteed methods for robust PCA have received a lot of attention in the past few years, starting from the seminal works of [CSPW11, CLMW11], where they showed recovery of an incoherent low rank matrix $L^{*}$ through the following convex relaxation method:

[CSPW11] and [CLMW11] consider two different models of sparsity for $S^{*}$. Chandrasekaran et al. [CSPW11] consider a deterministic sparsity model, where each row and column of the $m\times n$ matrix, $S$, has at most $\alpha$ fraction of non-zero entries. For guaranteed recovery, they require $\alpha=O\left({1/(\mu^{2}r\sqrt{n})}\right)$, where $\mu$ is the incoherence level of $L^{*}$, and $r$ is its rank. Hsu et al. [HKZ11] improve upon this result to obtain guarantees for an optimal sparsity level of $\alpha=O\left({1/(\mu^{2}r)}\right)$. This matches the requirements of our non-convex method for exact recovery. Note that when the rank $r=O(1)$, this allows for a constant fraction of corrupted entries. Candès et al. [CLMW11] consider a different model with random sparsity and additional incoherence constraints, viz., they require $\|UV^{\top}\|_{\infty}<\mu\sqrt{r}/n$. Note that our assumption of incoherence, viz., $\|U^{(i)}\|<\mu\sqrt{r/n}$, only yields $\|UV^{\top}\|_{\infty}<\mu^{2}r/n$. The additional assumption enables [CLMW11] to prove exact recovery with a constant fraction of corrupted entries, even when $L^{*}$ is nearly full-rank. We note that removing the $\|UV^{\top}\|_{\infty}$ condition for robust PCA would imply solving the planted clique problem when the clique size is less than $\sqrt{n}$ [Che13]. Thus, our recovery guarantees are tight upto constants without these additional assumptions.

A number of works have considered modified models under the robust PCA framework, e.g. [ANW12, XCS12]. For instance, Agarwal et al. [ANW12] relax the incoherence assumption to a weaker “diffusivity” assumption, which bounds the magnitude of the entries in the low rank part, but incurs an additional approximation error. Xu et al.[XCS12] impose special sparsity structure where a column can either be non-zero or fully zero.

In terms of state-of-art specialized solvers, [CLMW11] implements the in-exact augmented Lagrangian multipliers (IALM) method and provides guidelines for parameter tuning. Other related methods such as multi-block alternating directions method of multipliers (ADMM) have also been considered for robust PCA, e.g. [WHML13]. Recently, a multi-step multi-block stochastic ADMM method was analyzed for this problem [SAJ14], and this requires $1/\epsilon$ iterations to achieve an error of $\epsilon$. In addition, the convergence rate is tight in terms of scaling with respect to problem size $(m,n)$ and sparsity and rank parameters, under random noise models.

There is only one other work which considers a non-convex method for robust PCA [KC12]. However, their result holds only for significantly more restrictive settings and does not cover the deterministic sparsity assumption that we study. Moreover, the projection step in their method can have an arbitrarily large rank, so the running time is still $O(m^{2}n)$, which is the same as the convex methods. In contrast, we have an improved running time of $O(r^{2}mn)$.

Algorithm

In this section, we present our algorithm for the robust PCA problem. The robust PCA problem can be formulated as the following optimization problem: find $L,S$ s.t. $\|M-L-S\|_{F}\leq\epsilon$$\epsilon$ is the desired reconstruction error and

$L$ lies in the set of low-rank matrices,

A natural algorithm for the above problem is to iteratively project $M-L$ onto the set of sparse matrices to update $S$, and then to project $M-S$ onto the set of low-rank matrices to update $L$. Alternatively, one can view the problem as that of finding a matrix $L$ in the intersection of the following two sets: a) $\mathcal{L}=\{$ set of rank-$r$ matrices$\}$, b) \mathcal{S}_{M}=\{M-S,\ where $S$ is a sparse matrix$\}$. Note that these projections can be done efficiently, even though the sets are non-convex. Hard thresholding (HT) is employed for projections on to sparse matrices, and singular value decomposition (SVD) is used for projections on to low rank matrices. Rank-$1$ case: We first describe our algorithm for the special case when $L^{*}$ is rank 1. Our algorithm performs an initial hard thresholding to remove very large entries from input $M$. Note that if we performed the projection on to rank-$1$ matrices without the initial hard thresholding, we would not make any progress since it is subject to large perturbations. We alternate between computing the rank-$1$ projection of $M-S$, and performing hard thresholding on $M-L$ to remove entries exceeding a certain threshold. This threshold is gradually decreased as the iterations proceed, and the algorithm is run for a certain number of iterations (which depends on the desired reconstruction error). General rank case: When $L^{*}$ has rank $r>1$, a naive extension of our algorithm consists of alternating projections on to rank-$r$ matrices and sparse matrices. However, such a method has poor performance on ill-conditioned matrices. This is because after the initial thresholding of the input matrix $M$, the sparse corruptions in the residual are of the order of the top singular value (with the choice of threshold as specified in the algorithm). When the lower singular values are much smaller, the corresponding singular vectors are subject to relatively large perturbations and thus, we cannot make progress in improving the reconstruction error. To alleviate the dependence on the condition number, we propose an algorithm that proceeds in stages. In the $k^{{\mbox{\tiny th}}}$ stage, the algorithm alternates between rank-$k$ projections and hard thresholding for a certain number of iterations. We run the algorithm for $r$ stages, where $r$ is the rank of $L^{*}$. Intuitively, through this procedure, we recover the lower singular values only after the input matrix is sufficiently denoised, i.e. sparse corruptions at the desired level have been removed. Figure 1 shows a pictorial representation of the alternating projections in different stages.

Parameters: As can be seen, the only real parameter to the algorithm is $\beta$, used in thresholding, which represents “spikiness” of $L^{*}$. That is if the user expects $L^{*}$ to be “spiky” and the sparse part to be heavily diffused, then higher value of $\beta$ can be provided. In our implementation, we found that selecting $\beta$ aggressively helped speed up recovery of our algorithm. In particular, we selected $\beta=1/\sqrt{n}$.

Complexity: The complexity of each iteration within a single stage is $O(kmn)$, since it involves calculating the rank-$k$ approximationNote that we only require a rank-$k$ approximation of the matrix rather than the actual singular vectors. Thus, the computational complexity has no dependence on the gap between the singular values. of an $m\times n$ matrix (done e.g. via vanilla PCA). The number of iterations in each stage is $O\left({\log\left(1/\epsilon\right)}\right)$ and there are at most $r$ stages. Thus the overall complexity of the entire algorithm is then $O(r^{2}mn\log(1/\epsilon))$. This is drastically lower than the best known bound of $O\left({m^{2}n/\epsilon}\right)$ on the number of iterations required by convex methods, and just a factor $r$ away from the complexity of vanilla PCA.

Analysis

In this section, we present our main result on the correctness of AltProj. We assume the following conditions:

$L^{*}$ is $\mu$-incoherent, i.e., if $L^{*}=U^{*}\Sigma^{*}(V^{*})^{\top}$ is the SVD of $L^{*}$, then $\|(U^{*})^{i}\|_{2}\leq\frac{\mu\sqrt{r}}{\sqrt{m}},$ $\forall 1\leq i\leq m$ and $\|(V^{*})^{i}\|_{2}\leq\frac{\mu\sqrt{r}}{\sqrt{n}}$, $\forall 1\leq i\leq n$, where $(U^{*})^{i}$ and $(V^{*})^{i}$ denote the $i^{\textrm{th}}$ rows of $U^{*}$ and $V^{*}$ respectively.

Each row and column of $S$ have at most $\alpha$ fraction of non-zero entries such that $\alpha\leq\frac{1}{512\mu^{2}r}$.

Note that in general, it is not possible to have a unique recovery of low-rank and sparse components. For example, if the input matrix $M$ is both sparse and low rank, then there is no unique decomposition (e.g. $M=\bm{e}_{1}\bm{e}_{1}^{\top}$). The above conditions ensure uniqueness of the matrix decomposition problem.

Additionally, we set the parameter $\beta$ in Algorithm 1 be set as $\beta=\frac{4\mu^{2}r}{\sqrt{mn}}$.

We now establish that our proposed algorithm recovers the low rank and sparse components under the above conditions.

Under conditions $(L1)$, $(L2)$ and $S^{*}$, and choice of $\beta$ as above, the outputs $\widehat{L}$ and $\widehat{S}$ of Algorithm 1 satisfy:

Remark (tight recovery conditions): Our result is tight up to constants, in terms of allowable sparsity level under the deterministic sparsity model. In other words, if we exceed the sparsity limit imposed in S1, it is possible to construct instances where there is no unique decompositionFor instance, consider the $n\times n$ matrix which has $r$ copies of the all ones matrix, each of size $\frac{n}{r}$, placed across the diagonal. We see that this matrix has rank $r$ and is incoherent with parameter $\mu=1$. Note that a fraction of $\alpha=O\left({1/r}\right)$ sparse perturbations suffice to erase one of these blocks making it impossible to recover the matrix.. Our conditions L1, L2 and S1 also match the conditions required by the convex method for recovery, as established in [HKZ11]. Remark (convergence rate): Our method has a linear rate of convergence, i.e. $O(\log(1/\epsilon))$ to achieve an error of $\epsilon$, and hence we provide a strongly polynomial method for robust PCA. In contrast, the best known bound for convex methods for robust PCA is $O(1/\epsilon)$ iterations to converge to an $\epsilon$-approximate solution.

Under conditions $(L1)$, $(L2)$ and $S^{*}$, and choice of $\beta$ as in Theorem 1, when the noise $\left\lVert N^{*}\right\rVert_{\infty}\leq\frac{\sigma_{r}(L^{*})}{100n}$,the outputs $\widehat{L},\widehat{S}$ of Algorithm 1 satisfy:

We now present the key steps in the proof of Theorem 1. A detailed proof is provided in the appendix.

Step I: Reduce to the symmetric case, while maintaining incoherence of $\bm{L^{*}}$ and sparsity of $\bm{S^{*}}$. Using standard symmetrization arguments, we can reduce the problem to the symmetric case, where all the matrices involved are symmetric. See appendix for details on this step.

Step II: Show decay in $\|L-L^{*}\|_{\infty}$ after projection onto the set of rank-$k$ matrices. The $t$-th iterate $L^{(t+1)}$ of the $k$-th stage is given by $L^{(t+1)}=P_{k}(L^{*}+S^{*}-S^{(t)})$. Hence, $L^{(t+1)}$ is obtained by using the top principal components of a perturbation of $L^{*}$ given by $L^{*}+(S^{*}-S^{(t)})$. The key step in our analysis is to show that when an incoherent and low-rank $L^{*}$ is perturbed by a sparse matrix $S^{*}-S^{(t)}$, then $\|L^{(t+1)}-L^{*}\|_{\infty}$ is small and is much smaller than $|S^{*}-S^{(t)}|_{\infty}$. The following lemma formalizes the intuition; see the appendix for a detailed proof.

Let $L^{*},S^{*}$ be symmetric and satisfy the assumptions of Theorem 1 and let $S^{(t)}$ and $L^{(t)}$ be the $t^{\textrm{th}}$ iterates of the $k^{\textrm{th}}$ stage of Algorithm 1. Let $\sigma_{1}^{*},\dots,\sigma_{n}^{*}$ be the eigenvalues of $L^{*}$, s.t., $|\sigma_{1}^{*}|\geq\dots\geq|\sigma_{r}^{*}|$. Then, the following holds:

Moreover, the outputs $\widehat{L}$ and $\widehat{S}$ of Algorithm 1 satisfy:

Step III: Show decay in $\|S-S^{*}\|_{\infty}$ after projection onto the set of sparse matrices. We next show that if $\|L^{(t+1)}-L^{*}\|_{\infty}$ is much smaller than $\|S^{(t)}-S^{*}\|_{\infty}$ then the iterate $S^{(t+1)}$ also has a much smaller error (w.r.t. $S^{*}$) than $S^{(t)}$. The above given lemma formally provides the error bound.

Experiments

We now present an empirical study of our AltProj method. The goal of this study is two-fold: a) establish that our method indeed recovers the low-rank and sparse part exactly, without significant parameter tuning, b) demonstrate that AltProj is significantly faster than Conv-RPCA (see (1)); we solve Conv-RPCA using the IALM method [CLMW11], a state-of-the-art solver [LCM10]. We implemented our method in Matlab and used a Matlab implementation of the IALM method by [LCM10].

We consider both synthetic experiments and experiments on real data involving the problem of foreground-background separation in a video. Each of our results for synthetic datasets is averaged over $5$ runs.

Parameter Setting: Our pseudo-code (Algorithm 1) prescribes the threshold $\zeta$ in Step 4, which depends on the knowledge of the singular values of the low rank component $L^{*}$. Instead, in the experiments, we set the threshold at the $(t+1)$-th step of $k$-th stage as $\zeta=\frac{\mu\sigma_{k+1}(M-S^{(t)})}{\sqrt{n}}$. For synthetic experiments, we employ the $\mu$ used for data generation, and for real-world datasets, we tune $\mu$ through cross-validation. We found that the above thresholding provides exact recovery while speeding up the computation significantly. We would also like to note that [CLMW11] sets the regularization parameter $\lambda$ in Conv-RPCA (1) as $1/\sqrt{n}$ (assuming $m\leq n$). However, we found that for problems with large incoherence such a parameter setting does not provide exact recovery. Instead, we set $\lambda=\mu/\sqrt{n}$ in our experiments.

There are three key problem parameters for RPCA with a fixed matrix size: a) sparsity of $S^{*}$, b) incoherence of $L^{*}$, c) rank of $L^{*}$. We investigate performance of both AltProj and IALM by varying each of the three parameters while fixing the others. In our plots (see Figure 2), we report computational time required by each of the two methods for decomposing $M$ into $L+S$ up to a relative error ($\|M-L-S\|_{F}/\|M\|_{F}$) of $10^{-3}$. Figure 2 shows that AltProj scales significantly better than IALM for increasingly dense $S^{*}$. We attribute this observation to the fact that as $\|S^{*}\|_{0}$ increases, the problem is “harder” and the intermediate iterates of IALM have ranks significantly larger than $r$. Our intuition is confirmed by Figure 2 (b), which shows that when density ($\alpha$) of $S^{*}$ is $0.4$ then the intermediate iterates of IALM can be of rank over $500$ while the rank of $L^{*}$ is only $5$. We observe a similar trend for the other parameters, i.e., AltProj scales significantly better than IALM with increasing incoherence parameter $\mu$ (Figure 2 (c)) and increasing rank (Figure 2 (d)). See Appendix C for additional plots.

Real-world datasets: Next, we apply our method to the problem of foreground-background (F-B) separation in a video [LHGT04]. The observed matrix $M$ is formed by vectorizing each frame and stacking them column-wise. Intuitively, the background in a video is the static part and hence forms a low-rank component while the foreground is a dynamic but sparse perturbation.

Here, we used two benchmark datasets named Escalator and Restaurant dataset. The Escalator dataset has $3417$ frames at a resolution of $160\times 130$. We first applied the standard PCA method for extracting low-rank part. Figure 3 (b) shows the extracted background from the video. There are several artifacts (shadows of people near the escalator) that are not desirable. In contrast, both IALM and AltProj obtain significantly better F-B separation (see Figure 3(c), (d)). Interestingly, AltProj removes the steps of the escalator which are moving and arguably are part of the dynamic foreground, while IALM keeps the steps in the background part. Also, our method is significantly faster, i.e., our method, which takes $63.2s$ is about $26$ times faster than IALM, which takes $1688.9s$.

Restaurant dataset: Figure 4 shows the comparison of AltProj and IALM on a subset of the “Restaurant” dataset where we consider the last $2055$ frames at a resolution of $120\times 160$. AltProj was around $19$ times faster than IALM. Moreover, visually, the background extraction seems to be of better quality (for example, notice the blur near top corner counter in the IALM solution). Plot(b) shows the PCA solution and that also suffers from a similar blur at the top corner of the image, while the background frame extracted by AltProj does not have any noticeable artifacts.

Conclusion

In this work, we proposed a non-convex method for robust PCA, which consists of alternating projections on to low rank and sparse matrices. We established global convergence of our method under conditions which match those for convex methods. At the same time, our method has much faster running times, and has superior experimental performance. This work opens up a number of interesting questions for future investigation. While we match the convex methods, under the deterministic sparsity model, studying the random sparsity model is of interest. Our noisy recovery results assume deterministic noise; improving the results under random noise needs to be investigated. There are many decomposition problems beyond the robust PCA setting, e.g. structured sparsity models, robust tensor PCA problem, and so on. It is interesting to see if we can establish global convergence for non-convex methods in these settings.

Acknowledgements

AA and UN would like to acknowledge NSF grant CCF-1219234, ONR N00014-14-1-0665, and Microsoft faculty fellowship. SS would like to acknowledge NSF grants 1302435, 0954059, 1017525 and DTRA grant HDTRA1-13-1-0024. PJ would like to acknowledge Nikhil Srivastava and Deeparnab Chakrabarty for several insightful discussions during the course of the project.

References

Appendix A Proof of Theorem 1

We will start with some preliminary lemmas. The first lemma is the well known Weyl’s inequality in the matrix setting[Bha97].

Suppose $B=A+E$ be an $n\times n$ matrix. Let $\lambda_{1},\cdots,\lambda_{n}$ and $\sigma_{1},\cdots,\sigma_{n}$ be the eigenvalues of $B$ and $A$ respectively such that $\lambda_{1}\geq\cdots\geq\lambda_{n}$ and $\sigma_{1}\geq\cdots\geq{\sigma_{n}}$. Then we have:

The following lemma is the Davis-Kahan theorem[Bha97], specialized for rank-$1$ matrices.

Suppose ${B}={A}+{E}$. Let ${A}=\bm{u}^{*}{(\bm{u}^{*})}^{\top}$ be a rank-$1$ matrix with unit spectral norm. Suppose further that $\left\lVert{E}\right\rVert_{2}<\frac{1}{2}$. Then, we have:

where $\lambda$ and $\bm{u}$ are the top eigenvalue eigenvector pair of ${B}$.

As outlined in Section 3.1 (and formalized in the proof of Theorem 1), it is sufficient to prove the correctness of Algorithm 1 for the case of symmetric matrices. So, most of the lemmas we prove in this section assume that the matrices are symmetric.

Let $x,y$ be unit vectors such that $\|S\|_{2}=x^{T}Sy=\sum_{ij}x_{i}y_{j}S_{ij}$. Then, using $a\cdot b\leq(a^{2}+b^{2})/2$, we have:

where the last inequality follows from the fact that $S$ has at most $\alpha n$ non-zeros per row and per column. ∎

We prove the lemma using mathematical induction.

Base Case ($p=0$): This is just a restatement of the incoherence of $U$.

In what follows, we prove a number of lemmas concerning the structure of $L^{(t)}$ and ${E}^{(t)}:=S^{*}-S^{(t)}$. The following lemma shows that the threshold in (2) is close to that with $M-S^{(t)}$ replaced by $L^{*}$.

Let $L^{*},S^{*}$ be symmetric and satisfy the assumptions of Theorem 1 and let $S^{(t)}$ be the $t^{\textrm{th}}$ iterate of the $k^{\textrm{th}}$ stage of Algorithm 1. Let $\sigma_{1}^{*},\dots,\sigma_{r}^{*}$ be the eigenvalues of $L^{*}$, such that $|\sigma_{1}^{*}|\geq\dots\geq|\sigma_{r}^{*}|$ and $\lambda_{1},\cdots,\lambda_{n}$ be the eigenvalues of $M-S^{(t)}$ such that $\left\lvert\lambda_{1}\right\rvert\geq\cdots\geq\left\lvert\lambda_{n}\right\rvert$. Recall that ${E}^{(t)}:=S^{*}-S^{(t)}$. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|\right)$, and

$\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Note that $M-S^{(t)}=L^{*}+{E}^{(t)}$. Now, using Lemmas 2 and 4, we have:

where $\gamma_{t}:=\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|\right)$. That is, $\left\lvert|\lambda_{k+1}|-|\sigma_{k+1}^{*}|\right\rvert\leq 8\mu^{2}r\alpha\gamma_{t}$. Similarly, $\left\lvert|\lambda_{k}|-|\sigma_{k}^{*}|\right\rvert\leq 8\mu^{2}r\alpha\gamma_{t}$. So we have:

where the last inequality follows from the bound $\alpha\leq\frac{1}{512\mu^{2}r}$. ∎

Assume the notation of Lemma 6. Also, let $L^{(t)},S^{(t)}$ be the $t^{\textrm{th}}$ iterates of $k^{\textrm{th}}$ stage of Algorithm 1 and $L^{(t+1)},S^{(t+1)}$ be the $(t+1)^{\textrm{th}}$ iterates of the same stage. Also, recall that ${E}^{(t)}:=S^{*}-S^{(t)}$ and ${E}^{(t+1)}:=S^{*}-S^{(t+1)}$. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|\right)$, and

$\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Let $L^{(t+1)}=P_{k}(M-S^{(t)})=U\Lambda{U}^{\top}$ be the eigenvalue decomposition of $L^{(t+1)}$. Also, recall that $M-S^{(t)}=L^{*}+{E}^{(t)}$. Then, for every eigenvector $\bm{u}_{i}$ of $L^{(t+1)}$, we have

Note that we used Lemmas 2 and 4 to guarantee the existence of ${\left(I-\frac{{E}^{(t)}}{\lambda_{i}}\right)}^{-1}$. Hence,

We now bound the two terms on the right hand side above.

where we denote $U^{*}\Sigma^{*}{(U^{*})}^{\top}$ to be the SVD of $L^{*}$. Let $L^{*}+{E}^{(t)}=U\Lambda{U}^{\top}+\widetilde{U}\widetilde{\Lambda}{\widetilde{U}}^{\top}$ be the eigenvalue decomposition of $L^{*}+{E}^{(t)}$. Note that ${\widetilde{U}}^{\top}U=0$. Recall that, $U\Lambda{U}^{\top}=P_{k}(M-S^{(t)})=P_{k}(L^{*}+{E}^{(t)})=L^{(t+1)}$. Also note that,

Now, we will bound the $(p,q)^{\textrm{th}}$ term of $\sum_{p+q\geq 1}\left\lVert\left({E}^{(t)}\right)^{p}L^{*}U\Lambda^{-(p+q+1)}{U}^{\top}L^{*}\left({E}^{(t)}\right)^{q}\right\rVert_{\infty}$:

where $\zeta_{1}$ follows from Lemma 5 and the incoherence of $L^{*}$. Now, similar to (8), we have:

Using the above bound, and the assumption on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$:

where we used Lemma 4 and the assumption on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$. ∎

We used the following technical lemma in the proof of Lemma 7.

Assume the notation of Lemma 7. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|\right)$, and

$\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

The result follows by using the bound on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$. ∎

The following lemma bounds the support of ${E}^{(t+1)}$ and $\left\lVert{E}^{(t+1)}\right\rVert_{\infty}$, using an assumption on $\left\lVert L^{(t+1)}-L^{*}\right\rVert_{\infty}$.

$\textrm{Supp}\left({E}^{(t+1)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

$\left\lVert{E}^{(t+1)}\right\rVert_{\infty}\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)$, and

We first prove the first conclusion. Recall that,

where $\zeta=\frac{4\mu^{2}r}{n}\left(|\lambda_{k+1}|+\left(\frac{1}{2}\right)^{t}|\lambda_{k}|\right)$ is as defined in Algorithm 1 and $\lambda_{1},\cdots,\lambda_{n}$ are the eigenvalues of $M-S^{(t)}$ such that $\left\lvert\lambda_{1}\right\rvert\geq\cdots\geq\left\lvert\lambda_{n}\right\rvert$.

We now prove the second conclusion. We consider the following two cases:

$\left\lvert M_{ij}-L^{(t+1)}_{ij}\right\rvert>\zeta$: Here, $S^{(t+1)}_{ij}=S^{*}_{ij}+L^{*}_{ij}-L^{(t+1)}_{ij}$. Hence, $|S^{(t+1)}_{ij}-S^{*}_{ij}|\leq|L^{*}_{ij}-L^{(t+1)}_{ij}|\leq\frac{2\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)$.

$\left\lvert M_{ij}-L^{(t+1)}_{ij}\right\rvert\leq\zeta$: In this case, $S^{(t+1)}_{ij}=0$ and $\left\lvert S^{*}_{ij}+L^{*}_{ij}-L^{(t+1)}_{ij}\right\rvert\leq\zeta$. So we have, $\left\lvert{E}^{(t+1)}_{ij}\right\rvert=\left\lvert S^{*}_{ij}\right\rvert\leq\zeta+\left\lvert L^{*}_{ij}-L^{(t+1)}_{ij}\right\rvert\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)$. The last inequality above follows from Lemma 6.

We are now ready to prove Lemma 1. In fact, we prove the following stronger version.

Recall that in the $k^{\textrm{th}}$ stage, the update $L^{(t+1)}$ is given by: $L^{(t+1)}=P_{k}(M-S^{(t)})$ and $S^{(t+1)}$ is given by: $S^{(t+1)}=H_{\zeta}(M-L^{(t+1)})$. Also, recall that ${E}^{(t)}:=S^{*}-S^{(t)}$ and ${E}^{(t+1)}:=S^{*}-S^{(t+1)}$.

We prove the lemma by induction on both $k$ and $t$. For the base case ($k=1$ and $t=-1$), we first note that the first inequality on $\left\lVert L^{(0)}-L^{*}\right\rVert_{\infty}$ is trivially satisfied. Due to the thresholding step (step $3$ in Algorithm 1) and the incoherence assumption on $L^{*}$, we have:

So the base case of induction is satisfied.

We first do the inductive step over $t$ (for a fixed $k$). By inductive hypothesis we assume that: a) $\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|\right)$, b) $\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$. Then by Lemma 7, we have:

$\left\lVert{E}^{(t+1)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)$, and

$\textrm{Supp}\left({E}^{(t+1)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

This finishes the induction over $t$. Note that we show a stronger bound than necessary on $\left\lVert{E}^{(t+1)}\right\rVert_{\infty}$.

We now do the induction over $k$. Suppose the hypothesis holds for stage $k$. Let $T$ denote the number of iterations in each stage. We first obtain a lower bound on $T$. Since

we see that $T\geq 10\log\left(3\mu^{2}r\left\lvert\sigma_{1}^{*}\right\rvert/\epsilon\right)$. So, at the end of stage $k$, we have:

$\left\lVert{E}^{(T)}\right\rVert_{\infty}\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{T}|\sigma_{k}^{*}|\right)\leq\frac{7\mu^{2}r\left\lvert\sigma_{k+1}^{*}\right\rvert}{n}+\frac{\epsilon}{10n}$, and

$\textrm{Supp}\left({E}^{(T)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Lemmas 4 and 2 tell us that $\left\lvert\sigma_{k+1}\left(M-S^{(T)}\right)-\left\lvert\sigma_{k+1}^{*}\right\rvert\right\rvert\leq\left\lVert{E}^{(T)}\right\rVert_{2}\leq\alpha\left(7\mu^{2}r\left\lvert\sigma_{k+1}^{*}\right\rvert+\epsilon\right)$. We will now consider two cases:

Algorithm 1 terminates: This means that $\beta\sigma_{k+1}\left(M-S^{(T)}\right)<\frac{\epsilon}{2n}$ which then implies that $\left\lvert\sigma_{k+1}^{*}\right\rvert<\frac{\epsilon}{6\mu^{2}r}$. So we have:

This proves the statement about $\widehat{L}$. A similar argument proves the claim on $\left\lVert\widehat{S}-S^{*}\right\rVert_{\infty}$. The claim on $\textrm{Supp}\left(\widehat{S}\right)$ follows since $\textrm{Supp}\left({E}^{(T)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Algorithm 1 continues to stage $\bm{\left(k+1\right)}$: This means that $\beta\sigma_{k+1}\left(L^{(T)}\right)\geq\frac{\epsilon}{2n}$ which then implies that $\left\lvert\sigma_{k+1}^{*}\right\rvert>\frac{\epsilon}{8\mu^{2}r}$. So we have:

Similarly for $\left\lVert L^{(T)}-L^{*}\right\rVert_{\infty}$.

Using Lemma 1, it suffices to show that the general case can be reduced to the case of symmetric matrices. We will now outline this reduction.

Recall that we are given an $m\times n$ matrix $M=L^{*}+S^{*}$ where $L^{*}$ is the true low-rank matrix and $S^{*}$ the sparse error matrix. Wlog, let $m\leq n$ and suppose $\beta m\leq n<(\beta+1)m$, for some $\beta\geq 1$. We then consider the symmetric matrices

and $\widetilde{S}=\widetilde{M}-\widetilde{L}$. A simple calculation shows that $\widetilde{L}$ is incoherent with parameter $\sqrt{3}\mu$ and $\widetilde{S}$ satisfies the sparsity condition (S1) with parameter $\frac{\alpha}{\sqrt{2}}$. Moreover the iterates of AltProj with input $\widetilde{M}$ have similar expressions as in (41) in terms of the corresponding iterates with input $M$. This means that it suffices to obtain the same guarantees for Algorithm 1 for the symmetric case. Lemma 1 does precisely this, proving the theorem. ∎

Appendix B Proof of Theorem 2

In this section, we prove Theorem 2. The roadmap of the proofs in this section is essentially the same as that in Appendix A.

In what follows, we prove a number of lemmas concerning the structure of $L^{(t)}$ and ${E}^{(t)}:=S^{*}-S^{(t)}$. The first lemma is a generalization of Lemma 6 and shows that the threshold in (2) is close to that with $M^{(t)}$ replaced by $L^{*}$.

Let $L^{*},S^{*},N^{*}$ be symmetric and satisfy the assumptions of Theorem 2 and let $S^{(t)}$ be the $t^{\textrm{th}}$ iterate of the $k^{\textrm{th}}$ stage of Algorithm 1. Let $\sigma_{1}^{*},\dots,\sigma_{r}^{*}$ be the eigenvalues of $L^{*}$, such that $|\sigma_{1}^{*}|\geq\dots\geq|\sigma_{r}^{*}|$ and $\lambda_{1},\cdots,\lambda_{n}$ be the eigenvalues of $M-S^{(t)}$ such that $\left\lvert\lambda_{1}\right\rvert\geq\cdots\geq\left\lvert\lambda_{n}\right\rvert$. Recall that ${E}^{(t)}:=S^{*}-S^{(t)}$. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, and

$\textrm{Supp}\left(S^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Note that $M-S^{(t)}=L^{*}+N^{*}+{E}^{(t)}$. Now, using Lemmas 2 and 4, we have:

where $\gamma_{t}=\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$. That is, $\left\lvert|\lambda_{k+1}|-|\sigma_{k+1}^{*}|\right\rvert\leq 8\mu^{2}r\alpha\gamma_{t}$. Similarly, $\left\lvert|\lambda_{k}|-|\sigma_{k}^{*}|\right\rvert\leq 8\mu^{2}r\alpha\gamma_{t}$. So we have:

where the last inequality follows from the bound $\alpha\leq\frac{1}{512\mu^{2}r}$ and the assumption on $\left\lVert N^{*}\right\rVert_{\infty}$. ∎

Assume the notation of Lemma 6. Also, let $L^{(t)},S^{(t)}$ be the $t^{\textrm{th}}$ iterates of $k^{\textrm{th}}$ stage of Algorithm 1 and $L^{(t+1)},S^{(t+1)}$ be the $(t+1)^{\textrm{th}}$ iterates of the same stage. Also, recall that ${E}^{(t)}:=S^{*}-S^{(t)}$ and ${E}^{(t+1)}:=S^{*}-S^{(t+1)}$. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, and

$\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Let $L^{(t+1)}=P_{k}(M-S^{(t)})=U\Lambda{U}^{\top}$ be the eigenvalue decomposition of $L^{(t+1)}$. Also, recall that $M-S^{(t)}=L^{*}+N^{*}+{E}^{(t)}$. Then, for every eigenvector $\bm{u}_{i}$ of $L^{(t+1)}$, we have

Note that we used Lemmas 2 and 4 to guarantee the existence of ${\left(I-\frac{{E}^{(t)}}{\lambda_{i}}\right)}^{-1}$. Hence,

We now bound the two terms on the right hand side above.

For the first term, we again use triangle inequality to obtain

where we denote $U^{*}\Sigma^{*}{(U^{*})}^{\top}$ to be the SVD of $L^{*}$. Let $L^{*}+N^{*}+{E}^{(t)}=U\Lambda{U}^{\top}+\widetilde{U}\widetilde{\Lambda}{\widetilde{U}}^{\top}$ be the eigenvalue decomposition of $L^{*}+N^{*}+{E}^{(t)}$. Note that ${\widetilde{U}}^{\top}U=0$. Recall that, $U\Lambda{U}^{\top}=P_{k}(M^{(t)})=L^{(t)}$. Also note that,

Coming to the second term of (44), we have:

Using an expansion along the lines of (46), we see that

A similar argument as in (49) gives us the following bound on the last term in (44):

Next, we analyze $\sum_{p+q\geq 1}\left\lVert({E}^{(t)})^{p}(L^{*}+N^{*})U\Lambda^{-(p+q+1)}{U}^{\top}(L^{*}+N^{*})({E}^{(t)})^{q}\right\rVert_{\infty}$. This can again be bounded by four quantities:

where $(\zeta_{1})$ follows from Lemma 5 and the incoherence of $L^{*}$. Now, similar to (46), we have:

where $(\zeta_{1})$ follows from Lemma 12 and the bound on $\left\lVert N^{*}\right\rVert_{\infty}$.

Coming to the second term of (54), we have

where $(\zeta_{1})$ follows from Lemma 5 and incoherence of $U^{*}$. Proceeding along the lines of (56), we obtain:

Plugging the above inequality along with (57) and (59) into (54) gives us:

Using the above bound, and the assumption on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$:

where $(\zeta_{1})$ follows from Lemma 4, and $(\zeta_{2})$ follows from the assumption on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$. ∎

We used the following technical lemma in the proof of Lemma 11.

Assume the notation of Lemma 11. Suppose further that

$\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, and

$\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

Using the bound on $\left\lVert{E}^{(t)}\right\rVert_{\infty}$ and recalling the assumption that

The following lemma bounds the support of ${E}^{(t+1)}$ and $\left\lVert{E}^{(t+1)}\right\rVert_{\infty}$, using an assumption on $\left\lVert L^{(t+1)}-L^{*}\right\rVert_{\infty}$.

$\textrm{Supp}\left({E}^{(t+1)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

$\left\lVert{E}^{(t+1)}\right\rVert_{\infty}\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, and

We first prove the first conclusion. Recall that,

where $\zeta=\frac{4\mu^{2}r}{n}\left(|\lambda_{k+1}|+\left(\frac{1}{2}\right)^{t}|\lambda_{k}|\right)$ is as defined in Algorithm 1 and $\lambda_{1},\cdots,\lambda_{n}$ are the eigenvalues of $M-S^{(t)}$ such that $\left\lvert\lambda_{1}\right\rvert\geq\cdots\geq\left\lvert\lambda_{n}\right\rvert$.

We now prove the second conclusion. We consider the following two cases:

$\left\lvert M_{ij}-L^{(t+1)}_{ij}\right\rvert>\zeta$: Here, $S^{(t+1)}_{ij}=S^{*}_{ij}+L^{*}_{ij}-L^{(t+1)}_{ij}+N^{*}_{ij}$. Hence, $|S^{(t+1)}_{ij}-S^{*}_{ij}|\leq|L^{*}_{ij}-L^{(t+1)}_{ij}|+\left\lvert N^{*}_{ij}\right\rvert\leq\frac{2\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)+\left\lVert N^{*}\right\rVert_{\infty}$.

$\left\lvert M_{ij}-L^{(t+1)}_{ij}\right\rvert\leq\zeta$: In this case, $S^{(t+1)}_{ij}=0$ and $\left\lvert S^{*}_{ij}+L^{*}_{ij}-L^{(t+1)}_{ij}+N^{*}_{ij}\right\rvert\leq\zeta$. So we have, $\left\lvert{E}^{(t+1)}_{ij}\right\rvert=\left\lvert S^{*}_{ij}\right\rvert\leq\zeta+\left\lvert L^{*}_{ij}-L^{(t+1)}_{ij}\right\rvert+\left\lvert N^{*}_{ij}\right\rvert\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|\right)+\left\lVert N^{*}\right\rVert_{\infty}$. The last inequality above follows from Lemma 6.

The following lemma is a generalization of Lemma 1.

Let $L^{*},S^{*},N^{*}$ be symmetric and satisfy the assumptions of Theorem 2 and let $M^{(t)}$ and $L^{(t)}$ be the $t^{\textrm{th}}$ iterates of the $k^{\textrm{th}}$ stage of Algorithm 1. Let $\sigma_{1}^{*},\dots,\sigma_{n}^{*}$ be the eigenvalues of $L^{*}$, s.t., $|\sigma_{1}^{*}|\geq\dots\geq|\sigma_{r}^{*}|$. Then, the following holds:

Moreover, the outputs $\widehat{L}$ and $\widehat{S}$ of Algorithm 1 satisfy:

Recall that in the $k^{\textrm{th}}$ stage, the update $L^{(t+1)}$ is given by: $L^{(t+1)}=P_{k}(M-S^{(t)})$ and $S^{(t+1)}$ is given by: $S^{(t+1)}=H_{\zeta}(M-L^{(t+1)})$. Also, recall that ${E}^{(t)}:=S^{*}-S^{(t)}$ and ${E}^{(t+1)}:=S^{*}-S^{(t+1)}$.

We prove the lemma by induction on both $k$ and $t$. For the base case ($k=1$ and $t=-1$), we first note that the first inequality on $\left\lVert L^{(0)}-L^{*}\right\rVert_{\infty}$ is trivially satisfied. Due to the thresholding step (step $3$ in Algorithm 1) and the incoherence assumption on $L^{*}$, we have:

So the base case of induction is satisfied.

We first do the inductive step over $t$ (for a fixed $k$). By inductive hypothesis we assume that: a) $\left\lVert{E}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t-1}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, b) $\textrm{Supp}\left({E}^{(t)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$. Then by Lemma 11, we have:

$\left\lVert{E}^{(t+1)}\right\rVert_{\infty}\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{t}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)$, and

$\textrm{Supp}\left({E}^{(t+1)}\right)\subseteq\textrm{Supp}\left(S^{*}\right)$.

This finishes the induction over $t$. Note that we show a stronger bound than necessary on $\left\lVert{E}^{(t+1)}\right\rVert_{\infty}$.

We now do the induction over $k$. Suppose the hypothesis holds for stage $k$. Let $T$ denote the number of iterations in each stage. We first obtain a lower bound on $T$. Since

we see that $T\geq 10\log\left(3\mu^{2}r\left\lvert\sigma_{1}^{*}\right\rvert/\epsilon\right)$. So, at the end of stage $k$, we have:

$\left\lVert{E}^{(T)}\right\rVert_{\infty}\leq\frac{7\mu^{2}r}{n}\left(|\sigma_{k+1}^{*}|+\left(\frac{1}{2}\right)^{T}|\sigma_{k}^{*}|+7\left\lVert N^{*}\right\rVert_{2}+\frac{8n}{\sqrt{r}}\left\lVert N^{*}\right\rVert_{\infty}\right)\leq\frac{7\mu^{2}r\left\lvert\sigma_{k+1}^{*}\right\rvert}{n}+\frac{\epsilon}{10n}$, and