Nearly-optimal Robust Matrix Completion

Introduction

In this paper, we study the Robust Matrix Completion (RMC) problem where the goal is to recover an underlying low-rank matrix by observing a small number of sparsely corrupted entries from the matrix. Formally,

RMC is an important problem with several applications such as recommendation systems with outliers. Similarly, the problem is also heavily used to model PCA under gross outliers as well as erasures [JRVS11]. Finally, as we show later, an efficient solution to RMC enables faster solution for the robust PCA (RPCA) problem as well. The goal in RPCA is to find a low-rank matrix $L^{*}$ and sparse matrix $\widetilde{S}^{*}$ by observing their sum, i.e., $M=L^{*}+\widetilde{S}^{*}$. State-of-the-art results for RPCA shows exact recovery of a rank-$r$, $\mu$-incoherent $L^{*}$ (see Assumption 1, Section 3) if at most $\rho=\frac{1}{\mu^{2}r}$ fraction of the entries in each row/column of $\widetilde{S}^{*}$ are corrupted [HKZ11, NUNS+14].

However, the existing state-of-the-art results for RMC with optimal $\rho=\frac{1}{\mu^{2}r}$ fraction of corrupted entries, either require at least a constant fraction of the entries of $L^{*}$ to be observed [CJSC11, CLMW11] or require restrictive assumptions like support of corruptions $\widetilde{S}^{*}$ being uniformly random [Li13]. [KLT14] also considers RMC problem but studies the noisy setting and do not provide exact recovery bounds. Moreover, most of the existing methods for RMC use convex relaxation for both low-rank and sparse components, and in general exhibit large time complexity ($O(m^{2}n)$).

In this work, we attempt to answer the following open question (assuming $m\leq n$): Can RMC be solved exactly by using $|\Omega|=O(rn\log n)$ observations out of which $O(\frac{1}{\mu^{2}r})$ fraction of the observed entries in each row/column are corrupted. Note that both $|\Omega|$ (for uniformly random $\Omega$) and $\rho$ values mentioned in the question above denote the information theoretic limits. Hence, the goal is to solve RMC for nearly-optimal number of samples and nearly-optimal fraction of corruptions.

Under standard assumptions on $L^{*},\ S^{*},\ \Omega$ and for $n=O(m)$, we answer the above question in affirmative albeit with $|\Omega|$ which is $O(r)$ (ignoring log factors) larger than the optimal sample complexity (see Theorem 1). In particular, we propose a simple projected gradient (PGD) style method for RMC that alternately cleans up corrupted entries by hard-thresholding; our method’s computational complexity is also nearly optimal ($O(|\Omega|r+(m+n)r^{2}+r^{3})$). Our algorithm is based on projected gradient descent for estimating $L^{*}$ and alternating projection on set of sparse matrices for estimating $S^{*}$. Note that projection is onto non-convex sets of low-rank matrices (for $L^{*}$) and sparse matrices (for $S^{*}$), hence standard convex analysis techniques cannot be used for our algorithm.

In a concurrent and independent work, [YPCC16] also studied the RMC problem and obtained similar results. They study an alternating minimization style algorithm while our algorithm is based on low-rank projected gradient descent. Moreover, our sample complexity, corruption complexity as well as time complexity differs along certain critical parameters: a) Sample complexity: Our sample complexity bound is dependent only logarithmically on $\kappa$, the condition number of the matrix $L^{*}$ (see Table 1). On the other hand, result of [YPCC16] depends quadratically on $\kappa$, which can be significantly large. However, our sample complexity bound depends logarithmically on the final error $\epsilon$ (defined as $\epsilon=\left\lVert L-L^{*}\right\rVert_{2}$); this implies that for typical finite precision computation, our sample complexity bound can be worse by a constant factor. b) Our result allows the fraction of corrupted entries to be information theoretic optimal (up to a constant) $O(\frac{1}{\mu^{2}r})$, while the result of [YPCC16] allows only $O\left(\min\left(\frac{1}{\mu^{2}r\sqrt{r\kappa}},\frac{1}{\mu^{2}\kappa^{2}r}\right)\right)$ fraction of corrupted entries. c) As a consequence of the sample complexity bounds, running time of the method by [YPCC16] depends quintically on $\kappa$. On the other hand, our algorithm has optimal sparsity (up to a constant factor) independent of $\kappa$ and polylogarithmic dependence on $\kappa$ for sample and running time complexities.

Several recent results [JN15, NUNS+14, JTK14, HW14, Blu11] show that under certain assumptions, projection onto non-convex sets indeed lead to provable algorithms with fast convergence to the global optima. However, as explained in Section 3, RMC presents unique set of challenges as we have to perform error analysis with the errors arising due to missing entries as well as sparse corruptions, both of which interact among themselves as well. In fact, our careful error analysis also enables us to improve results for the matrix completion as well as the RPCA problem.

Matrix Completion (MC): The goal of MC is to find rank-$r$ $L^{*}$ using $\mathcal{P}_{\Omega}(L^{*})$. State-of-the-art result for MC uses nuclear norm minimization and requires $|\Omega|\geq\mu^{2}nr^{2}\log^{2}n$ under standard $\mu$-incoherence assumption (see Section 3), but the method requires $O(m^{2}n)$ time in general. The best sample complexity result for a non-convex iterative method (with at most logarithmic dependence on the condition number of $L^{*}$) achieve exact recovery when $|\Omega|\geq\mu^{6}nr^{5}\log^{2}n$ and needs $O(|\Omega|r)$ computational steps. In contrast, assuming $n=O(m)$, our method achieves nearly the same sample complexity of trace-norm but with nearly linear time algorithm ($O(|\Omega|r)$). See Table 1 for a detailed comparison of our result with the existing methods.

RPCA: Several recent results show that RPCA can be solved if $\rho=O(\frac{1}{\mu^{2}r})$-fraction of entries in each row and column of $L^{*}$ are corrupted [NUNS+14, HKZ11] where $L^{*}$ is assumed to be $\mu$-incoherent. Moreover, St-NcRPCA algorithm [NUNS+14] can solve the problem in time $O(mnr^{2})$. Corollary 2 shows that by sampling $\Omega$ uniformly at random, we can solve the problem in time $O(nr^{3})$ only. That is, we can recover $L^{*}$ without even observing the entire input matrix. Moreover, if the goal is to recover the sparse corruption as well, then we can obtain a two-pass (over the input matrix) algorithm that solves the RPCA problem exactly. St-NcRPCA algorithm requires $r^{2}\log(1/\epsilon)$ passes over the data. Our method has significantly smaller space complexity as well.

Our empirical results on synthetic data demonstrates effectiveness of our method. We also apply our method to the foreground background separation problem; our method is an order of magnitude faster than the state-of-the-art method (St-NcRPCA) while achieving similar accuracy.

In summary, this paper’s main contributions are: (a) RMC: We propose a nearly linear time method that solves RMC with $|\Omega|=O(nr^{2}\log^{2}n\log^{2}\|M\|_{2}/\epsilon)$ random entries and with optimal fraction of corruptions ($\rho=\frac{1}{\mu^{2}r}$). (b) Matrix Completion: Our result improves upon the existing linear time algorithm’s sample complexity by an $O(r^{3})$ factor, and time complexity by $O(r^{4})$ factor, although with an extra $O(\log\|L^{*}\|/\epsilon)$ factor in both time and sample complexity. (c) RPCA: We present a nearly linear time ($O(nr^{3})$) algorithm for RPCA under optimal fraction of corruptions, improving upon $O(mnr^{2})$ time complexity of the existing methods.

Paper Organization: We present our main algorithm in Section 2 and our main results in Section 3. We also present an overview of the proof in Section 3. Section 4 presents our empirical result. Due to lack of space, we present most of the proofs and useful lemmas in Appendix.

Algorithm

For the above problem, we propose a simple iterative algorithm that combines projected gradient descent (for $L$) with alternating projections (for $S$). In particular, we maintain iterates $L^{(t)}$ (with rank $k\leq r$) and sparse $S^{(t)}$. $L^{(t+1)}$ is computed using gradient descent step for objective (3) and then projecting back onto the set of rank $k$ matrices. That is,

where $P_{k}(A)$ denotes projection of $A$ onto the set of rank-$k$ matrices and can be computed efficiently using SVD of $A$, $p=\frac{|\Omega|}{mn}$. $S^{(t+1)}$ is computed by projecting the residual ${\mathcal{P}}_{\Omega}(M-L^{(t+1)})$ onto set of sparse matrices using a hard-thresholding operator, i.e.,

Unfortunately, just the above two simple iterations cannot handle problems where $L^{*}$ has poor condition number, as the intermediate errors can be significantly larger than the smallest singular values of $L^{*}$, making recovery of the corresponding singular vectors challenging. To alleviate this issue, we propose an algorithm that proceeds in stages. In the $q$-th stage, we project $L^{(t)}$ onto set of rank-$k_{q}$ matrices. Rank $k_{q}$ is monotonic w.r.t. $q$. Under standard assumptions, we show that we can increase $k_{q}$ in a manner such that after each stage $\left\lVert L^{(t)}-L^{*}\right\rVert_{\infty}$ decreased by at least a constant factor. Hence, the number of stages is only logarithmic in the condition number of $L^{*}$.

See Algorithm 1 (PG-RMC ) for a pseudo-code of the algorithm. We require an upper bound of the first singular value for our algorithm to work. Specifically, we require $\sigma=O\left({\sigma^{*}_{1}}\right)$. Alternatively, we can also obtain an estimate of $\sigma^{*}_{1}$ by using the thresholding technique from [YPCC16] although this requires an estimate of the number of corruptions in each row and column. We also use a simplified version of Algorithm 5 from [HW14] to form independent sets of samples for each iteration which is required for our theoretical analysis. Our algorithm has an “outer loop” (see Line 6) which sets rank $k_{q}$ of iterates $L^{(t)}$ appropriately (see Line 7). We then update $L^{(t)}$ and $S^{(t)}$ in the “inner loop” using (4), (5). We set threshold for the hard-thresholding operator using singular values of current gradient descent update (see Line 12). Note that, we divide $\Omega$ uniformly into $Q\cdot T$ sets, where $Q$ is an upper bound on the number of outer iterations and $T$ is the number of inner iterations. This division ensures independence across iterates that is critical to application of standard concentration bounds; such division is a standard technique in the matrix completion related literature [JN15, HW14, Rec11]. Also, $\eta$ is a tunable parameter which should be less than one and is smaller for “easier” problems.

Note that updating $S^{(t)}$ requires $O(|\Omega|\cdot r+(m+n)\cdot r)$ computational steps. Computation of $L^{(t+1)}$ requires computing SVD for projection $P_{r}$, which can be computed in time $O(|\Omega|\cdot r+(m+n)\cdot r^{2}+r^{3})$ time (ignoring $\log$ factors); see [JMD10] for more details. Hence, the computational complexity of each step of the algorithm is linear in $|\Omega|\cdot r$ (assuming $|\Omega|\geq r\cdot(m+n)$). As we show in the next section, the algorithm exhibits geometric convergence rate under standard assumptions and hence the overall complexity is still nearly linear in $|\Omega|$ (assuming $r$ is just a constant).

Rank based Stagewise algorithm: We also provide a rank-based stagewise algorithm (R-RMC) where the outer loop increments $k_{q}$ by one at each stage, i.e., the rank is $q$ in the $q$-th stage. Our analysis extends for this algorithm as well, however, its time and sample complexity trades off a factor of $O(\log(\sigma_{1}/\epsilon))$ from the complexity of PG-RMC with a factor of $r$ (rank of $L^{*}$). We provide the detailed algorithm in Appendix 5.3 due to lack of space (see Algorithm 3).

Analysis

We now present our analysis for both of our algorithms PG-RMC (Algorithm 1) and R-RMC (Algorithm 3). In general the problem of Robust PCA with Missing Entries (3) is harder than the standard Matrix Completion problem and hence is NP-hard [HMRW14]. Hence, we need to impose certain (by now standard) assumptions on $L^{*}$, $\widetilde{S}^{*}$, and $\Omega$ to ensure tractability of the problem:

Sparsity of $\widetilde{S}^{*}$, $S^{*}$: We assume that at most $\rho\leq\frac{c}{\mu^{2}r}$ fraction of the elements in each row and column of $\widetilde{S}^{*}$ are non-zero for a small enough constant $c$. Moreover, we assume that $\Omega$ is independent of $\widetilde{S}^{*}$. Hence, $S^{*}=\mathcal{P}_{\Omega}(\widetilde{S}^{*})$ also has at most $p\cdot\rho$ fraction of the entries in expectation.

Assumptions 1, 2 are standard assumptions in the provable matrix completion literature [CR09, Rec11, JN15], while Assumptions 1, 3 are standard assumptions in the robust PCA (low-rank+sparse matrix recovery) literature [CSPW11, CLMW11, HKZ11]. Hence, our setting is a generalization of both the standard and popular problems and as we show later in the section, our result can be used to meaningfully improve the state-of-the-art for both these problems.

We first present our main result for Algorithm 1 under the assumptions given above.

Let Assumptions 1, 2 and 3 on $L^{*}$, $\widetilde{S}^{*}$ and $\Omega$ hold respectively. Let $m\leq n$, $n=O(m)$, and let the number of samples $|\Omega|$ satisfy:

where $C$ is a global constant. Then, with probability at least $1-n^{-\log\frac{\alpha}{2}}$, Algorithm 1 with $\eta=\frac{4\mu^{2}r}{m}$, at most $O(\log(\|M\|_{2}/\epsilon)))$ outer iterations and $O(\log(\frac{\mu^{2}r\|M\|_{2}}{\epsilon}))$ inner iterations, outputs a matrix $\hat{L}$ such that:

Note that our number of samples increase with the desired accuracy $\epsilon$. However, using argument similar to that of [JN15], we should be able to replace $\epsilon$ by $\sigma_{\min}^{*}$ which should modify the $\epsilon$ term to be $\log^{2}\kappa$ where $\kappa=\sigma_{1}(L^{*})/\sigma_{r}(L^{*})$. We leave ironing out the details for future work.

Note that the number of samples matches information theoretic bound upto $O(r\log n\log^{2}\sigma_{1}^{*}/\epsilon)$ factor. Also, the number of allowed corruptions in $\widetilde{S}^{*}$ also matches the known lower bounds (up to a constant factor) and cannot be improved upon information theoretically.

We now present our result for the rank based stagewise algorithm (Algorithm 3).

Under Assumptions 1, 2 and 3 on $L^{*}$, $\widetilde{S}^{*}$ and $\Omega$ respectively and $\Omega$ satisfying:

for a large enough constant $C$, then Algorithm 3 with $\eta$ set to $\frac{4\mu^{2}r}{m}$ outputs a matrix $\hat{L}$ such that: $\left\lVert\hat{L}-L^{*}\right\rVert_{F}\leq\epsilon,$ w.p. $\geq 1-n^{-\log\frac{\alpha}{2}}$.

Notice that the sample complexity of Algorithm 3 has an additional multiplicative factor of $O(r)$ when compared to that of Algorithm 1, but shaves off a factor of $O(\log(\kappa))$. Similarly, computational complexity of Algorithm 3 also trades off a $O(\log\kappa)$ factor for $O(r)$ factor from the computational complexity of Algorithm 1.

Result for Matrix Completion: Note that for $\widetilde{S}^{*}=0$, the RMC problem with Assumptions 1,2 is exactly the same as the standard matrix completion problem and hence, we get the following result as a corollary of Theorem 1:

Suppose we observe $\Omega$ and $P_{\Omega}(L^{*})$ where Assumptions 1,2 hold for $L^{*}$ and $\Omega$. Also, let $E[|\Omega|]\geq C\alpha^{2}\mu^{4}r^{2}n\log^{2}n\log^{2}\sigma_{1}/\epsilon$ and $m\leq n$. Then, w.p. $\geq 1-n^{-\log\frac{\alpha}{2}}$, Algorithm 1 outputs $\hat{L}$ s.t. $\|\hat{L}-L^{*}\|_{2}\leq\epsilon$.

Table 1 compares our sample and time complexity bounds for low-rank MC. Note that our sample complexity is nearly the same as that of nuclear-norm methods while the running time of our algorithm is significantly better than the existing results that have at most logarithmic dependence on the condition number of $L^{*}$.

Result for Robust PCA: Consider the standard Robust PCA problem (RPCA), where the goal is to recover $L^{*}$ from $M=L^{*}+\widetilde{S}^{*}$. For RPCA as well, we can randomly sample $|\Omega|$ entries from $M$, where $\Omega$ satisfies the assumption required by Theorem 1. This leads us to the following corollary:

Suppose we observe $M=L^{*}+\widetilde{S}^{*}$, where Assumptions 1, 3 hold for $L^{*}$ and $\widetilde{S}^{*}$. Generate $\Omega\in[m]\times[n]$ by sampling each entry uniformly at random with probability $p$, s.t., $E[|\Omega|]\geq C\alpha^{2}\mu^{4}r^{2}n\log^{2}n\log^{2}\sigma_{1}/\epsilon$. Let $m\leq n$. Then, w.p. $\geq 1-n^{-\log\frac{\alpha}{2}}$, Algorithm 1 outputs $\hat{L}$ s.t. $\|\hat{L}-L^{*}\|_{2}\leq\epsilon$.

Hence, using Theorem 1, we will still be able to recover $L^{*}$ but using only the sampled entries. Moreover, the running time of the algorithm is only $O(\mu^{2}nr^{3}\log^{2}n\log^{2}(\sigma_{1}/\epsilon))$, i.e., we are able to solve RPCA problem in time linear in $n$. To the best of our knowledge, the existing state-of-the-art methods for RPCA require at least $O(n^{2}r)$ time to perform the same task [NUNS+14, GWL16]. Similarly, we don’t need to load the entire data matrix in memory, but we can just sample the matrix and work with the obtained sparse matrix with at most linear number of entries. Hence, our method significantly reduces both time and space complexity, and as demonstrated empirically in Section 4 can help scale our algorithm to very large data sets without losing accuracy.

We now provide an outline of our proof for Theorem 1 and motivate some of our proof techniques; the proof of Theorem 2 follows similarly. Recall that we assume that $M=L^{*}+\widetilde{S}^{*}$ and define $S^{*}=\mathcal{P}_{\Omega}(\widetilde{S}^{*})$. Similarly, we define $\widetilde{S}^{(t)}=\mathcal{HT}_{\zeta}(M-L^{(t)})$. Critically, $S^{(t)}=\mathcal{P}_{\Omega}(\widetilde{S}^{(t)})$ (see Line 9 of Algorithm 1), i.e., $\widetilde{S}^{(t)}$ is the set of iterates that we “could” obtain if entire $M$ was observed. Note that we cannot compute $\widetilde{S}^{(t)}$, it is introduced only to simplify our analysis.

We first re-write the projected gradient descent step for $L^{(t+1)}$ as described in (4):

That is, $L^{(t+1)}$ is obtained by rank-$k_{q}$ SVD of a perturbed version of $L^{*}$: $L^{*}+E_{1}+E_{3}$. As we perform entrywise thresholding to reduce $\|\widetilde{S}^{*}-\widetilde{S}^{(t)}\|_{\infty}$, we need to bound $\|L^{(t+1)}-L^{*}\|_{\infty}$. To this end, we use techniques from [JN15], [NUNS+14] that explicitly model singular vectors of $L^{(t+1)}$ and argue about the infinity norm error using a Taylor series expansion. However, in our case, such an error analysis requires analyzing the following key quantities ($H=E_{1}+E_{3}$):

Note that $E_{1}=0$ in the case of standard RPCA which was analyzed in [NUNS+14], while $E_{3}=0$ in the case of standard MC which was considered in [JN15]. In contrast, in our case both $E_{1}$ and $E_{3}$ are non-zero. Moreover, $E_{3}$ is dependent on random variable $\Omega$. Hence, for $j\geq 2$, we will get cross terms between $E_{3}$ and $E_{1}$ that will also have dependent random variables which precludes application of standard Bernstein-style tail bounds. To this end, we use a technique similar to that of [EKYY13, JN15] to provide a careful combinatorial-style argument to bound the above given quantity. That is, we can provide the following key lemma:

Let $L^{*}$, $\Omega$, and $\widetilde{S}^{*}$ satisfy Assumptions 1, 2 and 3 respectively. Let $L^{*}=U^{*}\Sigma^{*}(V^{*})^{\top}$ be the singular value decomposition of $L^{*}$. Furthermore, suppose that in the $t^{\textrm{th}}$ iteration of the $q^{\textrm{th}}$ stage, $\widetilde{S}^{(t)}$ defined as $HT_{\zeta}(M-L^{(t)})$ satisfies $Supp(\widetilde{S}^{(t)})\subseteq Supp(\widetilde{S}^{*})$, then we have:

$\forall c>0$ w.p $\geq 1-n^{-2\log\frac{c}{4}+4}$, where $E_{1},E_{2}\text{ and }E_{3}$ are defined in (6), $A_{a},B_{a},C_{a},D_{a}$ are defined in (3.1).

Remark: We would like to note that even for the standard MC setting, i.e., when $E_{1}=0$, we obtain better bound than that of [JN15] as we can bound $\max_{i}\|e_{i}^{T}(E_{3})^{q}U\|_{2}$ directly rather than the weaker $\sqrt{r}\max_{i}\|e_{i}^{T}(E_{3})^{q}u_{j}\|$ bound that [JN15] uses.

Now, using Lemmas 1 and 7 and by using a hard-thresholding argument we can bound $\|L^{(t+1)}-L^{*}\|_{\infty}\leq\frac{2\mu^{2}r}{m}(\sigma^{*}_{k_{q}+1}+\left(\frac{1}{2}\right)^{t}\sigma^{*}_{k_{q}})$ (see Lemma 9) in the $q$-th stage. Hence, after $O(\log(\sigma^{*}_{1}/\epsilon))$ “inner” iterations, we can guarantee in the $q$-th stage:

Moreover, by using sparsity of $\widetilde{S}^{*}$ and the special structure of $E_{3}$ (See Lemma 7), we have: ${\|E_{1}+E_{3}\|_{2}}\leq c\cdot\sigma^{*}_{k_{q}+1}$, where $c$ is a small constant.

Now, the outer iteration sets the next stage’s rank $k_{q+1}$ as: $k_{q+1}=|\{i:\sigma_{i}(L^{*}+E_{1}+E_{3})\geq 0.5\cdot\sigma_{k_{q}+1}(L^{*}+E_{1}+E_{3})\}|$. Hence, using bound on $\|E_{1}+E_{3}\|_{2}$ and Weyl’s eigenvalue perturbation bound (Lemma 2), we have: $\sigma^{*}_{k_{q+1}}\geq 0.6\,\sigma^{*}_{k_{q}+1}$ and $\sigma^{*}_{k_{q}+1}\leq\sigma^{*}_{k_{q}}$. Hence, after $Q=O(\log(\sigma_{1}^{*}/\epsilon))$ “outer” iterations, Algorithm 1 converges to an $\epsilon$-approximate solution to $L^{*}$.

Experiments

In this section we discuss the performance of Algorithm 1 on synthetic data and its use in foreground background separation. The goal of the section is two-fold: a) to demonstrate practicality and effectiveness of Algorithm 1 for the RMC problem, b) to show that Algorithm 1 indeed solves RPCA problem in significantly smaller time than that required by the existing state-of-the-art algorithm (St-NcRPCA [NUNS+14]). To this end, we use synthetic data as well as video datasets where the goal is to perform foreground-background separation [CLMW11].

We implemented our algorithm in MATLAB and the results for the synthetic data set were obtained by averaging over 20 runs. We obtained a matlab implementation of St-NcRPCA [NUNS+14] from the authors of [NUNS+14]. Note that if the sampling probability is $p=1$, then our method is similar to St-NcRPCA; the key difference being how rank is selected in each stage. We also implemented the Alternating Minimzation based algorithm from [GWL16]. However, we found it to be an order of magnitude slower than Algorithm 1 on the foreground-background separation task. For example, on the escalator video, the algorithm did not converge in less than 150 seconds despite discounting for the expensive sorting operation in the truncation step. On the other hand, our algorithm finds the foreground in about 8 seconds.

Parameters. The algorithm has three main parameters: 1) threshold $\eta$, 2) incoherence $\mu$ and 3) sampling probability $p$ ($E[|\Omega|]=p\cdot mn$). In the experiments on synthetic data we observed that keeping $\lambda\sim\mu\left\lVert M-S^{(t)}\right\rVert_{2}/{\sqrt{n}}$ speeds up the recovery while for background extraction keeping $\lambda\sim\mu\left\lVert M-S^{(t)}\right\rVert_{2}/{n}$ gives a better quality output. The value of $\mu$ for real world data sets was figured out using cross validation while for the synthetic data the same value was used as used in data generation. The sampling probability for the synthetic data could be kept as low as $2r\log^{2}(n)/{n}$ while for the real world data set we got good results for $p=0.05$. Also, rather than splitting samples, we use entire set of observed entries to perform our updates (see Algorithm 1).

Figure 1 (a) plots recovery error ($\|L-L^{*}\|_{F}$) vs computational time for our PG-RMC method (with different sampling probabilities) as well as the St-NcRPCA algorithm. Note that even for very small values of sampling $p$, we can achieve same recovery error using significantly small values. For example, our method with $p=0.1$ achieve $0.01$ error ($\|L-L^{*}\|_{F}$) in $\approx 2.5s$ while St-NcRPCA method requires $\approx 10s$ to achieve the same accuracy. Note that we do not compare against the convex relaxation based methods like IALM from [CLMW11], as [NUNS+14] shows that St-NcRPCA is significantly faster than IALM and several other convex relaxation solvers.

Figure 1 (b) plots time required to achieve different recovery errors ($\|L-L^{*}\|_{F}$) as the sampling probability $p$ increases. As expected, we observe a linear increase in the run-time with $p$. Interestingly, for very small values of $p$, we observe an increase in running time. In this regime, $\frac{\|\mathcal{P}_{\Omega}(M)\|_{2}}{p}$ becomes very large (as $p$ doesn’t satisfy the sampling requirements). Hence, increase in the number of iterations ($T\approx\log\frac{\|\mathcal{P}_{\Omega}(M)\|_{2}}{p\epsilon}$) dominates the decrease in per iteration time complexity.

Figure 1 (c), (d) plots computation time required by our method (PG-RMC , Algorithm 1) versus rank and incoherence, respectively. As expected, as these two problem parameters increase, our method requires more time. Note that our run-time dependence on rank seems to be linear, while our existing results require $O(r^{3})$ time. This hints at the possibility of further improving the computational complexity analysis of our algorithm.

We also study phase transition for different values of sampling probability $p$. Figure 3 (a) in Appendix 5.5 show a phase transition phenomenon where beyond $p>.06$ the probability of recovery is almost $1$ while below it, it is almost .

Foreground-background separation. We also applied our technique to the problem of foreground-background separation. We use the usual method of stacking up the vectorized video frames to construct a matrix. The background, being static, will form the low rank component while the foreground can be considered to be the noise.

We applied our PG-RMC method (with varying $p$) to several videos. Figure 2 (a), (d) shows one frame each from two videos (a shopping center video, a restaurant video). Figure 2 (b), (d) shows the extracted background from the two videos by using our method (PG-RMC , Algorithm 1) with probability of sampling $p=0.05$. Figure 2 (c), (f) compares objective function value for different $p$ values. Clearly, PG-RMC can recover the true background with $p$ as small as $0.05$. We also observe an order of magnitude speedup ($\approx 5$x) over St-NcRPCA [NUNS+14]. We present results on the video Escalator in Appendix 5.5.

Conclusion. In this work, we studied the Robust Matrix Completion problem. For this problem, we provide exact recovery of the low-rank matrix $L^{*}$ using nearly optimal number of observations as well as nearly optimal fraction of corruptions in the observed entries. Our RMC result is based on a simple and efficient PGD algorithm that has nearly linear time complexity as well. Our result improves state-of-the-art for the related Matrix Completion as well as Robust PCA problem. For Robust PCA, we provide first nearly linear time algorithm under standard assumptions.

Our sample complexity depends on $\epsilon$, the desired accuracy in $L^{*}$. Moreover, improving dependence of sample complexity on $r$ (from $r^{2}$ to $r$) also represents an important direction. Finally, similar to foreground background separation, we would like to explore more applications of RMC/RPCA.

References

Appendix

We divide this section into five parts. In the first part we prove some common lemmas. In the second part we give the convergence guarantee for PG-RMC . In the third part we give another algorithm which has a sample complexity of $O(\mu^{4}r^{3}n\log^{2}{n}\log{\frac{\mu^{2}r\sigma_{1}^{*}}{\epsilon}})$ and prove its convergence guarantees. In the fourth part we prove a generalized form of lemma 1. In the fifth part we present some additional experiments.

For the sake of convenience in the following proofs, we will define some notations here.

We define $p=\frac{\left\lvert\Omega_{k,t}\right\rvert}{mn}$ and we consider the following equivalent update step for $L^{(t+1)}$ in the analysis:

The singular values of $L^{*}$ are denoted by $\sigma^{*}_{1},\ldots,\sigma^{*}_{r}$ where $\left\lvert\sigma^{*}_{1}\right\rvert\geq\ldots\geq\left\lvert\sigma^{*}_{r}\right\rvert$ and we will let $\lambda_{1},\ldots,\lambda_{n}$ denote the singular values of $M^{(t)}$ where $\left\lvert\lambda_{1}\right\rvert\geq\ldots\geq\left\lvert\lambda_{n}\right\rvert$.

We will begin by restating some lemmas from previous work that we will use in our proofs.

First, we restate Weyl’s perturbation lemma from [Bha97], a key tool in our analysis:

This lemma establishes a bound on the spectral norm of a sparse matrix.

For any pair of unit vectors $u$ and $v$, we have:

Lemma now follows by using $\|S\|_{2}=\max_{u,v,\|u\|_{2}=1,\|v\|_{2}=1}u^{T}Sv$. ∎

Now, we define a -mean random matrix with small higher moments values.

$H$ is a random matrix of size $m\times n$ with each of its entries drawn independently satisfying the following moment conditions:

for $i,j\in[n]$ and $2\leq k\leq 2\log n$.

We now restate two useful lemmas from [JN15]:

Suppose $H$ satisfies Definition 1. Then, w.p. $\geq 1-1/n^{10+\log\alpha}$, we have: $\left\lVert H\right\rVert_{2}\leq 3\sqrt{\alpha}.$

Let $A$ be a $m\times n$ matrix with $n\geq m$. Suppose $\Omega\subseteq[m]\times[n]$ is obtained by sampling each element with probability $p\in\left[\frac{1}{4n},0.5\right]$. Then, the following matrix $H$ satisfies Defintion 1:

$\left\lVert A-AU\Lambda^{-1}U^{\top}A\right\rVert_{2}\leq\left\lvert\sigma_{k}\right\rvert+5\left\lVert C\right\rVert_{2}$,

$\left\lVert AU\Lambda^{-a}U^{\top}A\right\rVert_{2}\leq 4\left(\frac{\left\lvert\sigma_{k}\right\rvert}{2}\right)^{-a+2}\quad\forall a\geq 2$.

We now provide a lemma that bounds $\|\cdot\|_{\infty}$ norm of an incoherent matrix with its operator norm.

Let $A=U\Sigma V^{\top}$. Then, $ACA=UU^{\top}ACAVV^{\top}$. The lemma now follows by using definition of incoherence with the fact that $\|U^{\top}ACAV\|_{2}\leq\|ACA\|_{2}$. ∎

We now present a lemma that shows improvement in the error $\|L-L^{*}\|_{\infty}$ by using gradient descent on $L^{(t)}$.

Let $L^{*}$, $\Omega$, $\widetilde{S}^{*}$ satisfy Assumptions 1,2,3 respectively. Also, let the following hold for the $t$-th inner-iteration of any stage $q$:

$\left\lVert L^{*}-L^{(t)}\right\rVert_{\infty}\leq\frac{2\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

$\left\lVert\widetilde{S}^{*}-\widetilde{S}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

$Supp(\widetilde{S}^{(t)})\subseteq Supp(\widetilde{S}^{*})$

where $z\geq-3$ and $\sigma_{k}^{*}$ and $\sigma_{k+1}^{*}$ are the $k$ and $(k+1)^{\textit{th}}$ singular values of $L^{*}$. Also, let $E_{1}=\widetilde{S}^{(t)}-\widetilde{S}^{*}$ and $E_{3}=\left(\mathcal{I}-\frac{\mathcal{P}_{\Omega_{q,t}}}{p}\right)\left(L^{(t)}-L^{*}+\widetilde{S}^{(t)}-\widetilde{S}^{*}\right)$ be the error terms defined also in (6). Then, the following holds w.p $\geq 1-n^{-(10+\log\alpha)}$:

satisfies definition 1 with $\beta=\frac{2\sqrt{n}}{\sqrt{p}}\cdot\|L^{(t)}-L^{*}+\widetilde{S}^{(t)}-\widetilde{S}^{*}\|_{\infty}$.

We now bound the spectral norm of $E_{1}+E_{3}$ as follows:

where $(\zeta_{1})$ follows from Lemma 3 and 4. $(\zeta_{2})$ follows by our assumptions on $\rho$, $\left\lVert L^{(t)}-L^{*}\right\rVert_{\infty}$, and $\left\lVert\widetilde{S}^{(t)}-\widetilde{S}^{*}\right\rVert_{\infty}$. $(\zeta_{3})$ follows from our assumption on $p$. ∎

In the following lemma, we prove that the value of the threshold computed using $\sigma_{k}(M^{(t)})=\sigma_{k}(L^{*}+E_{1}+E_{3})$, where $E_{1},E_{3}$ are defined in (6), closely tracks the threshold that we would have gotten had we had access to the true eigenvalues of $L^{*}$, $\sigma^{*}_{k}$.

Let $L^{*}$, $\Omega$, $\widetilde{S}^{*}$ satisfy Assumptions 1,2,3 respectively. Also, let the following hold for the $t$-th inner-iteration of any stage $q$:

$\left\lVert L^{*}-L^{(t)}\right\rVert_{\infty}\leq\frac{2\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

$\left\lVert\widetilde{S}^{*}-\widetilde{S}^{(t)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

$Supp(\widetilde{S}^{(t)})\subseteq Supp(\widetilde{S}^{*})$

where $z\geq-3$ and $\sigma_{k}^{*}$ and $\sigma_{k+1}^{*}$ are the $k$ and $(k+1)^{\textit{th}}$ singular values of $L^{*}$. Also, let $E_{1}=\widetilde{S}^{(t)}-\widetilde{S}^{*}$ and $E_{3}=\left(\mathcal{I}-\frac{\mathcal{P}_{\Omega_{q,t}}}{p}\right)\left(L^{(t)}-L^{*}+\widetilde{S}^{(t)}-\widetilde{S}^{*}\right)$ be the error terms defined also in (6). Then, the following holds $\forall z>-3$ w.p $\geq 1-n^{-(10+\log\alpha)}$:

where $\lambda_{k}:=\sigma_{k}(M^{(t)})=\sigma_{k}(L^{*}+E_{1}+E_{3})$ and $E_{1},E_{3}$ are defined in (6).

Using Weyl’s inequality (Lemma 2), we have: : $\left\lvert\lambda_{k}-\sigma^{*}_{k}\right\rvert\leq\|E_{1}+E_{3}\|_{2}$ and $\left\lvert\lambda_{k+1}-\sigma^{*}_{k+1}\right\rvert\leq\|E_{1}+E_{3}\|_{2}$ We now proceed to prove the lemma as follows:

where $(\zeta)$ follows from Lemma 7 and the last inequality follows from the assumption that $z\geq-3$. ∎

Next, we show that the projected gradient descent update (6) leads to a better estimate of $L^{*}$, i.e., we bound $\|L^{(t+1)}-L^{*}\|_{\infty}$. Under the assumptions of the below given Lemma, the proof follows arguments similar to [NUNS+14] with additional challenge arises due to more involved error terms $E_{1}$, $E_{3}$.

Our proof proceeds by first symmetrizing our matrices by rectangular dilation. We first begin by noting some properties of symmetrized matrices used in the proof of the following lemma.

Let $A$ be a $m\times n$ dimensional matrix with singular value decomposition $U\Sigma V^{\top}$. We denote its symmetrized version be $A_{s}\coloneqq\begin{bmatrix}0&A^{\top}\\ A&0\end{bmatrix}$. Then:

The eigenvalue decomposition of $A_{s}$ is given by $A_{s}=U_{s}\Sigma_{s}U_{s}^{\top}$ where

$\mathcal{P}_{2k}\left(A_{s}\right)=\begin{bmatrix}0&\mathcal{P}_{k}(A^{\top})\\ \mathcal{P}_{k}(A)&0\end{bmatrix}$

We have $A_{s}^{2j}=\begin{bmatrix}(A^{\top}A)^{j}&0\\ 0&(AA^{\top})^{j}\end{bmatrix}$ $A_{s}^{2j+1}=\begin{bmatrix}0&(A^{\top}A)^{j}A^{\top}\\ (AA^{\top})^{j}A&0\end{bmatrix}$

Let $L^{(t)}=P_{k}(L^{*}+H)$, where $H$ is any perturbation matrix that satisfies the following:

$\left\lVert H\right\rVert_{2}\leq\frac{\displaystyle\sigma^{*}_{k}}{\displaystyle 4}$

$\forall i\in[n],\ a\in\lceil\frac{\log n}{2}\rceil$ with $\upsilon\leq\frac{\displaystyle\sigma^{*}_{k}}{\displaystyle 4}$

where $\sigma_{k}^{*}$ is the $k^{\textit{th}}$ singular value of $L^{*}$. Also, let $L^{*}$ satisfy Assumption 1. Then, the following holds:

where $\mu$ and $r$ are the rank and incoherence of the matrix $L^{*}$ respectively.

Let $l=m+n$. Let $\lambda_{1},\cdots,\lambda_{l}$ be the eigenvalues of $M^{(t)}_{s}=L^{*}_{s}+H_{s}$ with $\left\lvert\lambda_{1}\right\rvert\geq\left\lvert\lambda_{2}\right\rvert\cdots\geq\left\lvert\lambda_{l}\right\rvert$. Let $u_{1},u_{2},\cdots,u_{l}$ be the corresponding eigenvectors of $M^{(t)}_{s}$. Using Lemma 2 along with the assumption on $\left\lVert H_{s}\right\rVert_{2}$, we have: $|\lambda_{2k}|\geq\frac{3\sigma^{*}_{k}}{4}$.

Let $U\Lambda V$ be the eigen vector decomposition of $L^{(t+1)}$. Let $U_{s}\Lambda_{s}U_{s}^{\top}$ to be the eigen vector decomposition of $L^{(t+1)}_{s}$. Then, using Remark 1 we have $\forall\ i\in[2k]$:

As $\left\lvert\lambda_{2k}\right\rvert\geq\frac{3\sigma^{*}_{k}}{4}$ and $\left\lVert H_{s}\right\rVert_{2}\leq\frac{1}{4}\sigma_{k}^{*}$, we can apply the Taylor’s series expansion to get the following expression for $u_{i}$:

Subtracting $L^{*}_{s}$ on both sides and taking operator norm, we get:

We separately bound the first and the second term of RHS. The first term can be bounded as follows:

where $(\zeta_{1})$ follows Remark 1, $(\zeta_{2})$ from Lemma 6 and $(\zeta_{3})$ follows from Claim 1 of Lemma 5.

We now bound second term of RHS of (10) which we again split in two parts. We first bound the terms with $s+t>\log n$:

where $(\zeta_{1})$ follows from the second claim of Lemma 5 and noting that $\left\lVert H_{s}\right\rVert_{2}=\left\lVert H\right\rVert_{2}$ and $(\zeta_{2})$ follows from assumption on $\left\lVert H\right\rVert_{2}$ and using the fact that $s+t\geq\log n$.

Summing up over all terms with $s+t>\log n$, we get from 13 and 12:

Now, for terms corresponding to $1\leq s+t\leq\log n$, we have:

where $(\zeta_{1})$ follows from assumption on $H$ in the lemma statement, $(\zeta_{2})$ follows from Claim 2 of Lemma 5.

It now remains to bound the terms, $\max\limits_{q_{1}\in[m+n]}\left\lVert e_{q_{1}}^{\top}H_{s}^{s}U_{s}^{*}\right\rVert_{2}$. Note from Remark 1.1 that $U_{s}^{*}=\frac{1}{\sqrt{2}}\begin{bmatrix}V^{*}&V^{*}\\ U^{*}&-U^{*}\end{bmatrix}$. Now, we have the following cases for $H^{s}_{s}$:

This leads to the following 4 cases for $\max\limits_{q_{1}\in[m+n]}\left\lVert e_{q_{1}}^{\top}H_{s}^{s}U_{s}^{*}\right\rVert_{2}$:

we get the bound on these terms in Lemma 15. Also, note from the Remark 1.2 that $\left\lVert L^{*}_{s}-L^{(t+1)}_{s}\right\rVert_{\infty}=\left\lVert L^{*}-L^{(t+1)}\right\rVert_{\infty}$.

Now, summing up 15 over all $1\leq s+t\leq\log n$ and combining with 14 we get the required result. ∎

In the next lemma, we show that with the threshold chosen in the algorithm, we show an improvement in the estimation of $\widetilde{S}^{*}$ by $\widetilde{S}^{(t+1)}$.

In the $t^{\textit{th}}$ iterate of the $q^{\textit{th}}$ stage, assume the following holds:

$\left\lVert L^{*}-L^{(t)}\right\rVert_{\infty}\leq\frac{2\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

$\frac{\displaystyle 7}{\displaystyle 8}\left(\sigma^{*}_{k+1}+\left(\frac{\displaystyle 1}{\displaystyle 2}\right)^{z}\sigma^{*}_{k}\right)\leq\left(\lambda_{k+1}+\left(\frac{\displaystyle 1}{\displaystyle 2}\right)^{z}\lambda_{k}\right)\leq\frac{\displaystyle 9}{\displaystyle 8}\left(\sigma^{*}_{k+1}+\left(\frac{\displaystyle 1}{\displaystyle 2}\right)^{z}\sigma^{*}_{k}\right)$

where $\sigma_{k}^{*}$ and $\sigma_{k+1}^{*}$ are the $k$ and $(k+1)^{\textit{th}}$ singular values of $L^{*}$, $\lambda_{k}$ and $\lambda_{k+1}$ are the $k$ and $(k+1)^{\textit{th}}$ singular values of $M^{(t)}$ and, $r$ and $\mu$ are the rank and incoherence of the $m\times n$ matrix $L^{*}$ respectively. Then we have

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

$\left\lVert\widetilde{S}^{(t)}-\widetilde{S}^{*}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{m}\left(\sigma^{*}_{k+1}+\left(\frac{1}{2}\right)^{z}\sigma^{*}_{k}\right)$

We first prove the first claim of the lemma. Consider an index pair $(i,j)\notin Supp(\widetilde{S}^{*})$.

where $(\zeta_{1})$ follows from the second assumption. Hence, we do not threshold any entry that is not corrupted by $\widetilde{S}^{*}$.

Now, we prove the second claim of the lemma. Consider an index entry $(i,j)\in Supp(\widetilde{S}^{*})$. Here, we consider two cases:

The entry $(i,j)\in Supp(\widetilde{S}^{(t)})$: Here the entry $(i,j)$ is thresholded. We know that $L^{(t)}_{ij}+\widetilde{S}^{(t)}_{ij}=L^{*}_{ij}+\widetilde{S}^{*}_{ij}$ from which we get

The entry $(i,j)\notin Supp(\widetilde{S}^{(t)})$: Here the entry $(i,j)$ is not thresholded. We know that $\left\lvert L^{*}_{ij}+\widetilde{S}^{*}_{ij}-L^{(t)}_{ij}\right\rvert\leq\zeta$ from which we get

where $(\zeta_{2})$ follows from the second assumption along with the assumption about $\eta=\frac{\mu^{2}r}{m}$.

The above two cases prove the second statement of the lemma. ∎

The number of iteration $T$ in the inner loop of Algorithm 1 and Algorithm 3 satisfy:

w.p $\geq 1-n^{-(10+\log\alpha)}$. Here $\sigma_{1}^{*}$ is the highest singular value of $L^{*}$, $r$ is it’s rank and $\mu$ is it’s incoherence.

where $(\zeta_{1})$ follows from Lemma 7. ∎

We will now prove Lemma 1 Proof of Lemma 1: Recall the definitions of $E_{1}=\left(\widetilde{S}^{*}-\widetilde{S}^{(t)}\right)$ , $E_{2}=\left(L^{(t)}-L^{*}\right)$ , $E_{3}=\left(\mathcal{I}-\frac{\mathcal{P}_{\Omega_{q,t}}}{p}\right)\left(E_{2}-E_{1}\right)$ and $\beta=2\sqrt{\frac{n}{p}}\left\lVert E_{2}-E_{1}\right\rVert_{\infty}$. Recall that $H\coloneqq E_{1}+E_{3}$ From Lemma 4, we have that $\frac{1}{\beta}E_{3}$ satisfies Definition 1. This implies that the matrix $\frac{1}{\beta}\left(E_{1}+E_{3}\right)$ satisfies the conditions of Lemma 15. Now, we have $\forall 1\leq a\leq\lceil\log n\rceil$ and $\forall i\in[n]$:

where $(\zeta)$ follows from the application of Lemma 15 along with the incoherence assumption on $U^{*}$. The other statements of the lemma can be proved in a similar manner by invocations of the different claims of Lemma 15. $\Box$

2 Algorithm PG-RMC

Proof of Theorem 1: From Lemma 11 we know that $T\geq\log(\frac{3\mu^{2}r\sigma_{1}^{*}}{\epsilon})$. Consider the stage $q$ reached at the termination of the algorithm. We know from Lemma 12 that:

$\left\lVert E^{(T)}\right\rVert_{\infty}\leq\frac{8\mu^{2}r}{m}\left(\sigma^{*}_{k_{q}+1}+\left(\frac{1}{2}\right)^{T}\sigma^{*}_{k_{q}}\right)\leq\frac{8\mu^{2}r}{m}\sigma^{*}_{k_{q}+1}+\frac{\epsilon}{10n}$

$\left\lVert L^{(T)}-L^{*}\right\rVert_{\infty}\leq\frac{2\mu^{2}r}{m}\left(\sigma^{*}_{k_{q}+1}+\left(\frac{1}{2}\right)^{T}\left\lvert\sigma^{*}_{k_{q}}\right\rvert\right)\leq\frac{2\mu^{2}r}{m}\sigma^{*}_{k_{q}+1}+\frac{\epsilon}{10n}$

Combining this with Lemmas 2 and 7, we get:

When the while loop terminates, $\eta\sigma_{k_{q}+1}\left(M^{(T)}\right)<\frac{\epsilon}{2n}$, which from 16, implies that $\sigma_{k_{q}+1}^{*}<\frac{m\epsilon}{7n\mu^{2}r}$. So we have:

We will now bound the number of iterations required for the PG-RMC to converge.

From claim 2 of Lemma 13, we have $\sigma^{*}_{k_{q}+1}\leq\frac{17}{32}\sigma^{*}_{k_{q-1}+1}\quad\forall q\geq 1$. By recursively applying this inequality, we get $\sigma^{*}_{k_{q}+1}\leq\left(\frac{17}{32}\right)^{q}\sigma^{*}_{1}$. We know that when the algorithm terminates, $\sigma_{k_{q}+1}^{*}<\frac{\epsilon}{7\mu^{2}r}$. Since, $\left(\frac{17}{32}\right)^{q}\sigma^{*}_{1}$ is an upper bound for $\sigma_{k_{q}+1}^{*}$, an upper bound for the number of iterations is $5\log\left(\frac{7\mu^{2}r\sigma_{1}^{*}}{\epsilon}\right)$. Also, note that an upper bound to this quantity is used to partition the samples provided to the algorithm. This happens with probability $\geq 1-T^{2}n^{-(10+\log\alpha)}\geq 1-n^{-\log\alpha}$. This concludes the proof. $\Box$

In the following lemma, we show that we make progress simultaneously in the estimation of both $\widetilde{S}^{*}$ and $L^{*}$ by $\widetilde{S}^{(t)}$ and $L^{(t)}$. We make use of Lemmas 9 and 10 to show progress in the estimation of one affects the other alternatively. We also emphasize the roles of the following quantities in enabling us to prove our convergence result:

$\left\lVert H\right\rVert_{2}$ - We use Lemma 7 to bound this quanitity

The analysis of the following 4 quanitities is crucial to obtaining error bounds in $\lVert\rVert_{\infty}$ norm

Let $L^{*}$, $\Omega$, $\widetilde{S}^{*}$ and $\widetilde{S}^{(t)}$ satisfy Assumptions 1,2,3 respectively. Then, in the $t^{\textrm{th}}$ iteration of the $q^{\textrm{th}}$ stage of Algorithm 1, $\widetilde{S}^{(t)}$ and $L^{(t)}$ satisfy: