Low-rank Matrix Completion using Alternating Minimization

Introduction

Due to the above two reasons, in several applications, the target matrix $X$ is parameterized by $X=UV^{\dagger}$. For example, clustering , sparse PCA etc.

Using the bi-linear parametrization of the target matrix $X$, the task of estimating $X$ now reduces to finding $U$ and $V$ that, for example, minimize an error metric. The resulting problem is typically non-convex due to bi-linearity. Correspondingly, a popular approach has been to use alternating minimization: iteratively keep one of $U,V$ fixed and optimize over the other, then switch and repeat, see e.g. . While the overall problem is non-convex, each sub-problem is typically convex and can be solved efficiently.

Despite wide usage of bi-linear representation and alternating minimization, there has been to date almost no theoretical understanding of when such a formulation works. Motivated by this disconnect between theory and practice in the estimation of low-rank matrices, in this paper we provide the first guarantees for performance of alternating minimization, for two low-rank matrix recovery problems: matrix completion, and matrix sensing.

Matrix completion involves completing a low-rank matrix, by observing only a few of its elements. Its recent popularity, and primary motivation, comes from recommendation systems , where the task is to complete a user-item ratings matrix using only a small number of ratings. As elaborated in Section 2, alternating minimization becomes particularly appealing for this problem as it provides a fast, distributed algorithm that can exploit both sparsity of ratings as well as the low-rank bi-linear parametrization of $X$.

Our Results

In this section, we will first define the matrix sensing problem, and present our results for it. Subsequently, we will do the same for matrix completion. The matrix sensing setting – i.e. recovery of any low-rank matrix from linear measurements that satisfy matrix RIP – represents an easier analytical setting than matrix completion, but still captures several key properties of the problem that helps us in developing an analysis for matrix completion.We note that for either problem, ours represent the first global optimality guarantees for alternating minimization based algorithms.

As in the existing work on this problem, we are interested in the under-determined case, where $d<mn$. Note that this problem is a strict generalization of the popular compressed sensing problem ; compressed sensing represents the case when $M$ is restricted to be a diagonal matrix.

As mentioned earlier, alternating minimization algorithm for matrix sensing now alternately solves for $U$ and $V$ while fixing the other factor. See Algorithm 1 for a pseudo-code of AltMinSense algorithm that we analyze.

We note two key properties of AltMinSense : a) Each minimization – over $U$ with $V$ fixed, and vice versa – is a simple least-squares problem, which can be solved in time $O(dn^{2}k^{2}+n^{3}k^{3})$Throughout this paper, we assume $m\leq n$., b) We initialize $U^{0}$ to be the top-$k$ left singular vectors of $\sum_{i}A_{i}b_{i}$ (step 2 of Algorithm 1). As we will see later in Section 4, this provides a good initialization point for the sensing problem which is crucial; if the first iterate $\widehat{U}^{0}$ is orthogonal, or almost orthogonal, to the true $U^{*}$ subspace, AltMinSense may never converge to the true space (this is easy to see in the simplest case, when the map is identity, i.e. ${\mathcal{A}}(X)=X$ – in which case AltMinSense just becomes the power method).

In general, since $d<mn$, problem (LRMS) is not well posed as there can be multiple rank-$k$ solutions that satisfy $\mathcal{A}(X)=b$. However, inspired by a similar condition in compressed sensing , Recht et al. showed that if the linear map ${\mathcal{A}}$ satisfies a (matrix) restricted isometry property (RIP), then a trace-norm based convex relaxation of (LRMS) leads to exact recovery. This property is defined below.

Several random matrix ensembles with sufficiently many measurements ($d$) satisfy matrix RIP . For example, if $d=\Omega(\frac{1}{\delta_{k}^{2}}kn\log n)$ and each entry of $A_{i}$ is sampled i.i.d. from a -mean sub-Gaussian distribution then $k$-RIP is satisfied with RIP constant $\delta_{k}$.

We now present our main result for AltMinSense.

The above theorem establishes geometric convergence (in $O(\log(1/\epsilon))$ steps) of AltMinSense to the optimal solution of (LRMS) under standard RIP assumptions. This is in contrast to existing iterative methods for trace-norm minimization all of which require at least $O(\frac{1}{\sqrt{\epsilon}})$ steps; interior point methods for trace-norm minimization converge to the optimum in $O(\log(1/\epsilon))$ steps but require storage of the full $m\times n$ matrix and require $O(n^{5})$ time per step, which makes it infeasible for even moderate sized problems.

Recently, several projected gradient based methods have been developed for matrix sensing that also guarantee convergence to the optimum in $O(\log(1/\epsilon))$ steps. But each iteration in these algorithms requires computation of the top $k$ singular components of an $m\times n$ matrix, which is typically significantly slower than solving a least squares problem (as required by each iteration of AltMinSense). Stagewise AltMinSense Algorithm: A drawback of our analysis for AltMinSense is the dependence of $\delta_{2k}$ on the condition number ($\kappa=\frac{\sigma^{*}_{1}}{\sigma^{*}_{k}}$) of $M$, which implies that the number of measurements $d$ required by AltMinSense grows quadratically with $\kappa$. We address this issue by using a stagewise version of AltMinSense (Algorithm 3) for which we are able to obtain near optimal measurement requirement.

The key idea behind our stagewise algorithm is that if one of the singular vectors of $M$ is very dominant, then we can treat the underlying matrix as a rank-$1$ matrix plus noise and approximately recover the top singular vector. Once we remove this singular vector from the measurements, we will have a relatively well-conditioned problem. Hence, at each stage of Algorithm 3, we seek to remove the remaining most dominant singular vector of $M$. See Section 6 for more details; here we state the corresponding theorem regarding the performance of Stage-AltMin.

where $T=\Omega\left(\log(\|M\|_{F}^{2}/\epsilon)\right)$. That is, the $T$-th step iterates of the $k$-th stage, satisfy: $\|M-\widehat{U}^{T}_{1:k}\left(V^{T}_{1:k}\right)^{{\dagger}}\|_{F}^{2}\leq\epsilon.$

The above theorem guarantees exact recovery using $O(k^{4}n\log n)$ measurements which is only $O(k^{3})$ worse than the information theoretic lower bound. We also note that for simplicity of analysis, we did not optimize the constant factors in $\delta_{2k}$.

Matrix Completion via Alternating Minimization

Nevertheless, like matrix sensing, matrix completion has been shown to be possible once additional conditions are applied to the low-rank matrix $M$ and the observation set $\Omega$. Starting with the first work , the typical assumption has been to have $\Omega$ generated uniformly at random, and $M$ to satisfy a particular incoherence property that, loosely speaking, makes it very far from a sparse matrix. In this paper, we show that once such assumptions are made, alternating minimization also succeeds. We now restate, and subsequently use, this incoherence definition.

where $M=U\Sigma V^{T}$ is the SVD of $M$ and $u^{(i)}$, $v^{(j)}$ denote the $i^{\textrm{th}}$ row of $U$ and the $j^{\textrm{th}}$ row of $V$ respectively.

The alternating minimization algorithm can be viewed as an approximate way to solve the following non-convex problem:

Similar to AltMinSense, the altmin procedure proceeds by alternatively solving for $U$ and $V$. As noted earlier, this approach has been popular in practice and has seen several variants and extensions being used in practice . However, for ease of analysis, our algorithm further modifies the standard alternating minimization method. In particular, we introduce partitioning of the observed set $\Omega$, so that we use different partitions of $\Omega$ in each iteration. See Algorithm 2 for a pseudo-code of our variant of the alternating minimization approach.

We now present our main result for (LRMC):

where $\delta_{2k}\leq\frac{\sigma^{*}_{k}}{12k\sigma^{*}_{1}}$ and $C>0$ is a global constant. Then w.h.p. for $T=C^{\prime}\log\frac{\left\|{M}\right\|_{\text{F}}}{\epsilon}$, the outputs $\widehat{U}^{T}$ and $V^{T}$ of Algorithm 2, with input $(\Omega,P_{\Omega}(M))$ (see Equation (2)) satisfy: $\left\|{M-\widehat{U}^{T}\left(V^{T}\right)^{{\dagger}}}\right\|_{\text{F}}\leq\epsilon.$

The above theorem implies that by observing $\left|\Omega\right|=O\left((\frac{\sigma^{*}_{1}}{\sigma^{*}_{k}})^{4}k^{4.5}n\log n\log(k\|M\|_{F}/\epsilon)\right)$ random entries of an incoherent $M$, AltMinComplete can recover $M$ in $O(\log(1/\epsilon))$ steps. In terms of sample complexity ($|\Omega|$), our results show alternating minimization may require a bigger $\Omega$ than convex optimization, as our result has $|\Omega|$ depend on the condition number, required accuracy ($\epsilon$) and worse dependence on $k$ than known bounds. In contrast, trace-norm minimization based methods require $O(kn\log n)$ samples only.

Empirically however, this is not seen to be the case and we leave further tightening of the sample complexity bounds for matrix completion as an open problem.

In terms of time complexity, we show that AltMinComplete needs time $O(|\Omega|k^{2}\log(1/\epsilon))$. This is in contrast to popular trace-norm minimization based methods that need $O(1/\sqrt{\epsilon})$ steps and total time complexity of $O(|\Omega|n/\sqrt{\epsilon})$; note that the latter can be potentially quadratic in $n$. Furthermore, each step of such methods requires computation of the SVD of an $m\times n$ matrix. As mentioned earlier, interior point methods for trace-norm minimization also converge in $O(\log(1/\epsilon))$ steps but each iteration requires $O(n^{5})$ steps and need storage of the entire $m\times n$ matrix $X$.

Related Work

Alternating Minimization: Alternating minimization and its variants have been applied to several low-rank matrix estimation problems. For example, clustering , sparse PCA , non-negative matrix factorization , signed network prediction etc. There are three main reasons for such wide applicability of this approach: a) low-memory footprint and fast iterations, b) flexible modeling, c) amenable to parallelization. However, despite such empirical success, this approach has largely been used as a heuristic and has had no theoretical analysis other than the guarantees of convergence to the local minima . Ours is the first analysis of this approach for two practically important problems: a) matrix completion, b) matrix sensing.

Matrix Completion: This is the problem of completing a low-rank matrix from a few sampled entries. Candes and Recht provided the first results on this problem, showing that under the random sampling and incoherence conditions (detailed above), $O(kn^{1.2}\log n)$ samples allow for recovery via convex trace-norm minimization; this was improved to $O(kn\log n)$ in . For large matrices, this approach is not very attractive due to the need to store and update the entire matrix, and because iterative methods for trace norm minimization require $O(\frac{1}{\sqrt{\epsilon}})$ steps to achieve additive error of $\epsilon$. Moreover, each such step needs to compute an SVD.

Another approach, in , involved taking a single SVD, followed by gradient descent on a Grassmanian manifold. However, (a) this is more expensive than alternating minimization as it needs to compute gradient over Grassmanian manifold which in general is a computationally intensive step, and (b) the analysis of the algorithm only guarantees asymptotic convergence, and in the worst case might take exponential time in the problem size.

Recently, several other matrix completion type of problems have been studied in the literature. For example, robust PCA , spectral clustering etc. Here again, under additional assumptions, convex relaxation based methods have rigorous analysis but alternating minimization based algorithms continue to be algorithms of choice in practice.

Matrix Sensing: The general problem of matrix sensing was first proposed by . They established recovery via trace norm minimization, assuming the sensing operator satisfies “restricted isometry” conditions. Subsequently, several other methods were proposed for this problem that also recovers the underlying matrix with optimal number of measurements and can give an $\epsilon$-additive approximation in time $O(\log(1/\epsilon)$. But, similar to matrix completion, most of these methods require computing SVD of a large matrix at each step and hence have poor scalability to large problems.

We show that AltMinSense and AltMin-Completion provide more scalable algorithms for their respective problems. We demonstrate that these algorithms have geometric convergence to the optima, while each iteration is relatively cheap. For this, we assume conditions similar to those required by existing algorithms; albeit, with one drawback: number of samples required by our analysis depend on the condition number of the underlying matrix $M$. For the matrix sensing problem, we remove this requirement by using a stagewise algorithm; we leave similar analysis for matrix completion as an open problem.

Matrix Sensing

In this section, we study the matrix sensing problem (LRMS) and prove that if the measurement operator, ${\mathcal{A}}$, satisfies RIP then AltMinSense (Algorithm 1) recovers the underlying low-rank matrix exactly (see Theorem 2.2).

At a high level, we prove Theorem 2.2 by showing that the “distance” between subspaces spanned by $\widehat{V}^{t}$ (iterate at time $t$) and $V^{*}$ decreases exponentially with $t$. This done based on the observation that once the (standard) matrix RIP condition (Definition 2.1) holds, alternating minimization can be viewed, and analyzed, as a perturbed version of the power method. This is easiest to see for the rank-1 case below; we detail this proof, and then the more general rank-$k$ case.

In this paper, we use the following definition of distance between subspaces:

where $U$ and $W$ are orthonormal bases of the spaces $\textrm{Span}\left(\widehat{U}\right)$ and $\textrm{Span}\left(\widehat{W}\right)$, respectively. Similarly, $U_{\perp}$ and $W_{\perp}$ are any orthonormal bases of the perpendicular spaces $\textrm{Span}\left(U\right)^{\perp}$ and $\textrm{Span}\left(W\right)^{\perp}$, respectively.

We now present a theorem that bounds the distance between the subspaces spanned by $\widehat{V}^{t}$ and $V^{*}$ and show that it decreases exponentially with $t$.

Let $b={\mathcal{A}}(M)$ where $M$ and ${\mathcal{A}}$ satisfy assumptions given in Theorem 2.2. Then, the $(t+1)$-th iterates $\widehat{U}^{t+1}$, $\widehat{V}^{t+1}$ of AltMinSense satisfy:

Using Theorem 4.2, we are now ready to prove Theorem 2.2.

Assuming correctness of Theorem 4.2, Theorem 2.2 follows by using the following set of inequalities:

To complete the proof of Theorem 2.2, we now need to prove Theorem 4.2. In the next section, we illustrate the main ideas of the proof of Theorem 4.2 by applying it to a rank-$1$ matrix i.e., when $k=1$. We then provide a proof of Theorem 4.2 for arbitrary $k$ in Section 4.2.

Consider the $t$-th update step in the AltMinSense procedure. As $\widehat{v}^{t+1}=$ $\operatorname*{argmin}_{\widehat{v}}\sum_{i=1}^{d}\left(\widehat{u}^{t{\dagger}}A_{i}^{\dagger}\widehat{v}-\sigma^{*}u^{*^{\dagger}}A_{i}^{\dagger}v^{*}\right)^{2}$, setting the gradient of the above objective function to , we obtain:

where $u^{t}=\widehat{u}^{t}/\|\widehat{u}^{t}\|_{2}$. Now, let $B=\sum_{i=1}^{d}A_{i}u^{t}(u^{t})^{\dagger}A_{i}^{\dagger}$ and $C=\sum_{i=1}^{d}A_{i}u^{t}(u^{*})^{\dagger}A_{i}^{\dagger}$. Then,

Note that the first term in the above expression is the power method iterate (i.e., $M^{{\dagger}}u^{t}$). The second term is an error term and the goal is to show that it becomes smaller as $u^{t}$ gets closer to $u^{*}$. Note that when $u^{t}=u^{*}$, the error term is irrespective of the measurement operator ${\mathcal{A}}$.

Below, we provide a precise bound on the error term:

Consider the error term defined in (4) and let ${\mathcal{A}}$ satisfy $2$-RIP with constant $\delta_{2}$. Then,

See Appendix B.1 for a detailed proof of the above lemma.

Using the above lemma, we now finish the proof of Theorem 4.2:

Let $v^{t+1}=\widehat{v}^{t+1}/\|\widehat{v}^{t+1}\|_{2}$. Now, using (4) and Lemma 4.3:,

where $\widehat{\delta}_{2}=\frac{3\delta_{2}}{1-3\delta_{2}}$. That is,

Therefore, $\langle u^{0},u^{*}\rangle\geq\sqrt{1-2\delta_{2}}\geq 5\widehat{\delta}_{2}$ assuming $\delta_{2}\leq\frac{1}{100}$. ∎

2 Rank-k𝑘k Case

In this section, we present the proof of Theorem 4.2 for arbitrary $k$, i.e., when $M$ is a rank-$k$ matrix (with SVD $U^{*}\Sigma^{*}\left(V^{*}\right)^{{\dagger}})$.

Similar to the analysis for the rank-$1$ case (Section 4.1), we show that even for arbitrary $k$, the updates of AltMinSense are essentially power-method type updates but with a bounded error term whose magnitude decreases with each iteration.

However, directly analyzing iterates of AltMinSense is a bit tedious due to non-orthonormality of intermediate iterates $\widehat{U}$. Instead, for analysis only we consider the iterates of a modified version of AltMinSense, where we explicitly orthonormalize each iterate using the QR-decompositionThe QR decomposition factorizes a matrix into an orthonormal matrix (a basis of its column space) and an upper triangular matrix; that is given $\widehat{S}$ it computes $\widehat{S}=SR$ where $S$ has orthonormal columns and $R$ is upper triangular. If $\widehat{S}$ is full-rank, so are $S$ and $R$.. In particular, suppose we replace steps 4 and 5 of AltMinSensewith the following

Let $\widehat{U}^{t}$ be the $t^{th}$ iterate of our AltMinSense algorithm, and $\widetilde{U}^{t}$ of the modified version stated above. Suppose also that both $\widehat{U}^{t},\widetilde{U}^{t}$ are full-rank, and span the same subspace. Then the same will be true for the subsequent iterates for the two algorithms, i.e. $Span(\widehat{V}^{t+1})=Span(\widetilde{V}^{t+1})$, $Span(\widehat{U}^{t+1})=Span(\widetilde{U}^{t+1})$, and all matrices at iterate $t+1$ will be full-rank.

The proof of the above lemma can be found in Appendix B.2. In light of this, we will now prove Theorem 4.2 with the new QR-based iterates (5).

Let $\widehat{U}^{t}$ be the $t$-th step iterate of AltMinSense and let $U^{t},\widehat{V}^{t+1}$ and $V^{t+1}$ be obtained by Update (5). Then,

where $F$ is an error matrix defined in (18) and $R^{(t+1)}$ is a triangular matrix obtained using QR-decomposition of $\widehat{V}^{t+1}$.

See Appendix B for a detailed proof of the above lemma.

Note that the notation above should have been $B^{t},C^{t}$ and so on. We suppress the dependence on $t$ for notational simplicity. Now, from Update (6), we have

where $V_{\perp}^{*}$ is an orthonormal basis of $\textrm{Span}\left(v_{1}^{*},v_{2}^{*},\cdots,v_{k}^{*}\right)^{\perp}$. Therefore,

Now, we break down the proof of Theorem 4.2 into the following two steps:

show that $\left\|{F(\Sigma^{*})^{-1}}\right\|_{2}$ is small (Lemma 4.6) and

show that $\|\Sigma^{*}{R^{(t+1)}}^{-1}\|_{2}$ is small(Lemma 4.7).

We will now state the two corresponding lemmas. Complete proofs can be found in Appendix B.2 The first lemma bounds the spectral norm of $F(\Sigma^{*})^{-1}$.

The following lemma bounds the spectral norm of $\Sigma^{*}R^{(t+1)^{-1}}$.

With the above two lemmas, we now prove Theorem 4.2.

Using (19), (20) and (21), we obtain the following:

Matrix Completion

In this section, we study the Matrix Completion problem (LRMC) and show that, assuming $k$ and $\frac{\sigma^{*}_{1}}{\sigma^{*}_{k}}$ are constant, AltMinComplete (Algorithm 2) recovers the underlying matrix $M$ using only $O(n\log n)$ measurements (i.e., we prove Theorem 2.5).

As mentioned, while observing elements in $\Omega$ constitutes a linear map, matrix completion is different from matrix sensing because the map does not satisfy RIP. The (now standard) approach is to assume incoherence of the true matrix $M$, as done in Definition 2.4. With this, and the random sampling of $\Omega$, matrix completion exhibits similarities to matrix sensing. For our analysis, we can again use the fact that incoherence allows us to view alternating minimization as a perturbed power method, whose error we can control.

However, there are important differences between the two problems, which make the analysis of completion more complicated. Chief among them is the fact that we need to establish the incoherence of each iterate. For the first initialization $\widehat{U}^{0}$, this necessitates the “clipping” procedure (described in step 4 of the algorithm). For the subsequent steps, this requires the partitioning of the observed $\Omega$ into $2T+1$ sets (as described in step 2 of the algorithm).

As in the case of matrix sensing, we prove our main result for matrix completion (Theorem 2.5) by first establishing a geometric decay of the distance between the subspaces spanned by $\widehat{U}^{t},\widehat{V}^{t}$ and $U^{*},V^{*}$ respectively.

Under the assumptions of Theorem 2.5, the $(t+1)^{\textrm{th}}$ iterates $\widehat{U}^{t+1}$ and $\widehat{V}^{t+1}$ satisfy the following property w.h.p.:

We use the above result along with incoherence of $M$ to prove Theorem 2.5. See Appendix C for a detailed proof.

Now, similar to the matrix sensing case, alternating minimization needs an initial iterate that is close enough to $U^{*}$ and $V^{*}$, from where it will then converge. To this end, Steps $3-4$ of Algorithm 2 use SVD of $P_{\Omega}(M)$ followed by clipping to initialize $\widehat{U}^{0}$. While the SVD step guarantees that $\widehat{U}^{0}$ is close enough to $U^{*}$, it might not remain incoherent. To maintain incoherence, we introduce an extra clipping step which guarantees incoherence of $\widehat{U}^{0}$ while also ensuring that $\widehat{U}^{0}$ is close enough to $U^{*}$ (see Lemma 5.2)

Let $M,\Omega,p$ be as defined in Theorem 2.5. Also, let $U^{0}$ be the initial iterate obtained by step $4$ of Algorithm 2. Then, w.h.p. we have

$U^{0}$ is incoherent with parameter $4\mu\sqrt{k}$.

The above lemma guarantees a “good” starting point for alternating minimization. Using this, we now present a proof of Theorem 5.1. Similar to the sensing section, we first explain key ideas of our proof using rank-$1$ example. Then in Section 5.2 we extend our proof to general rank-$k$ matrices.

Consider the rank-$1$ matrix completion problem where $M=\sigma^{*}u^{*}(v^{*})^{\dagger}$. Now, the $t$-th step iterates $\widehat{v}^{t+1}$ of Algorithm 2 are given by:

Let $u^{t}=\widehat{u}^{t}/\|\widehat{u}^{t}\|_{2}$. Then, $\forall j$:

Note the similarities between the update (25) and the rank-$1$ update (4) for the sensing case. Here again, it is essentially a power-method update (first term) along with a bounded error term (see Lemma 5.3). Using this insight, we now prove Theorem 5.1 for the special case of rank-$1$ matrices. Our proof can be divided in three major steps:

Base Case: Show that $u^{0}=\widehat{u}^{0}/\|\widehat{u}^{0}\|_{2}$ is incoherent and have small distance to $u^{*}$ (see Lemma 5.2).

Induction Step (distance): Assuming $u^{t}=\widehat{u}^{t}/\|\widehat{u}^{t}\|_{2}$ to be incoherent and that $u^{t}$ has a small distance to $u^{*}$, $v^{t+1}$ decreases distances to $v^{*}$ by at least a constant factor.

Induction Step (incoherence): Show incoherence of $v^{t+1}$, while assuming incoherence of $u^{t}$ (see Lemma 5.4)

We first prove the second step of our proof. To this end, we provide the following lemma that bounds the error term. See Appendix C.2 for a proof of the below given lemma.

Let $M$, $p$, $\Omega$, $u^{t}$ be as defined in Theorem 2.5. Also, let $u^{t}$ be a unit vector with incoherence parameter $\mu_{1}=\frac{6(1+\delta_{2})\mu}{1-\delta_{2}}$.Then, w.p. at least $1-\frac{1}{n^{3}}$:

Multiplying (25) with $v^{*}$ and using Lemma 5.3, we get:

where $\delta_{2}<\frac{1}{12}$ is a constant defined in the Theorem statement and is similar to the RIP constant in Section 4.

Similarly, by multiplying (25) with $v_{\perp}$ (where $\langle v_{\perp}^{*},v^{*}\rangle=0$ and $\|v_{\perp}^{*}\|_{2}=1$) and using Lemma 5.3:

Assuming, $\langle v^{t+1},v^{*}\rangle\geq 6\delta_{2}$,

We now provide the following lemma to prove the third step. We stress that $v^{t+1}$ does not increase the incoherence parameter ($\mu_{1}$) when compared to that of $u^{t}$.

Let $M$, $p$, $\Omega$ be as defined in Theorem 2.5. Also, let $u^{t}$ be a unit vector with incoherence parameter $\mu_{1}=\frac{6(1+\delta_{2})\mu}{1-\delta_{2}}$. Then, w.p. at least $1-\frac{1}{n^{3}}$, $v^{t+1}$ is also $\mu_{1}$ incoherent.

See Appendix C.2 for a detailed proof of the lemma.

Finally, for the base case we need that $u^{0}$ is $\mu_{1}$ incoherent and also $\langle u^{0},u^{*}\rangle\geq 6\delta_{2}$. This follows directly by using Lemma 5.2 and the fact that $\delta_{2}\leq 1/12$.

Note that, to obtain an error of $\epsilon$, AltMinComplete needs to run for $O\left(\log\frac{\|M\|_{F}}{\epsilon}\right)$ iterations. Also, we need to sample a fresh $\Omega$ at each iteration of AltMinComplete. Hence, the total number of samples needed by AltMinComplete is $O\left(\log\frac{\|M\|_{F}}{\epsilon}\right)$ larger than the number of samples required per step.

2 Rank-k𝑘k case

We now extend our proof of Theorem 5.1 to matrices with arbitrary rank. Here again, we show that the AltMinComplete algorithm reduces to power method with bounded perturbation at each step.

Similar to the matrix sensing case, we analyze the following QR decomposition based update instead of directly analyzing the updates of Algorithm 2:

Here again, we would stress that the updates output exactly the same matrices at the end of each iteration and we prefer QR-based updates due to notational ease.

Now, as matrix completion is a special case of matrix sensing, Lemma 4.5 characterizes the updates of the AltMinComplete algorithm (see Algorithm 2). That is,

where $F$ is the error matrix defined in (18) and $R^{(t+1)}$ is a upper-triangular matrix obtained using QR-decomposition of $\widehat{V}^{t+1}$. See (13) for the definition of $B,C$, $D$, and $S$.

Also, note that for the special case of matrix completion, $B_{pq},C_{pq},1\leq p,q\leq k$ are diagonal matrices with

and $D^{j}=(U^{t})^{\dagger}U^{*}$. Using the above notation, (29) decouples into $n$ equations of the form ($1\leq j\leq n$):

where $(V^{t+1})^{(j)}$ and $(V^{*})^{(j)}$ denote the $j^{\textrm{th}}$ rows of $V^{t+1}$ and $V^{*}$ respectively.

Using the above notation, we now provide a proof of Theorem 5.1 for the general rank-$k$ case.

Multiplying the update equation (29) on the left by $\left(V^{*}_{\perp}\right)^{{\dagger}}$, we get: $(V^{*}_{\perp})^{{\dagger}}\widehat{V}^{t+1}=-(V^{*}_{\perp})^{{\dagger}}F(R^{(t+1)})^{-1}.$ That is,

Now, similar to the sensing case (see Section 4.2) we break down our proof into the following two steps:

Bound $\left\|{F(\Sigma^{*})^{-1}}\right\|_{2}$ (Lemma 5.6) and

Bound $\|\Sigma^{*}{R^{(t+1)}}^{-1}\|_{2}$, i.e., the minimum singular value of $\left(\Sigma^{*}\right)^{-1}R^{(t+1)}$ (Lemma 5.7).

Using Lemma 5.6 and Lemma 5.7, w.p. at least $1-1/n^{3}$,

We now provide lemmas required by our above given proof. See Appendix C.3 for detailed proof of each of the lemmas.

We first provide a lemma to bound incoherence of $V^{t+1}$, assuming incoherence of $U^{t}$.

Let $M,\Omega,p$ be as defined in Theorem 2.5. Also, let $U^{t}$ be the $t$-th step iterate obtained by (28). Let $U^{t}$ be $\mu_{1}=\frac{16\sigma_{1}^{*}\mu\sqrt{k}}{\sigma_{k}^{*}}$ incoherent. Then, w.p. at least $1-1/n^{3}$, iterate $V^{(t+1)}$ is also $\mu_{1}$ incoherent.

We now bound the error term ($F$) in AltMin update (29).

Let $F$ be the error matrix defined by (18) (also see (29)) and let $U^{t}$ be a $\mu_{1}$-incoherent orthonormal matrix obtained after $(t-1)^{\textrm{th}}$ update. Also, let $M$, $\Omega$, and $p$ satisfy assumptions of Theorem 2.5. Then, w.p. at least $1-1/n^{3}$:

Next, we present a lemma to bound $\|(R^{(t+1)})^{-1}\|_{2}$.

Let $R^{(t+1)}$ be the lower-triangular matrix obtained by QR decomposition of $\widehat{V}^{t+1}$ ( see (29)) and let $U^{t}$ be a $\mu_{1}$-incoherent orthonormal matrix obtained after $(t-1)^{\textrm{th}}$ update. Also, let $M$ and $\Omega$ satisfy assumptions of Theorem 2.5. Then,

Lemma follows by exactly the same proof as that of Lemma 4.7 for the matrix sensing case. ∎

Stagewise AltMin Algorithm

In Section 4, we showed that if $\delta_{2k}\leq\frac{(\sigma^{*}_{k})^{2}}{(\sigma^{*}_{1})^{2}k}$ then AltMinSense (Algorithm 1) recovers the underlying matrix. This means that, $d=\frac{(\sigma^{*}_{1})^{4}}{(\sigma^{*}_{k})^{4}}k^{2}n\log n$ random Gaussian measurements (assume $m\leq n$) are required to recover $M$. For matrices with large condition number ($\sigma^{*}_{1}/\sigma^{*}_{k}$), this would be significantly larger than the information theoretic bound of $O(kn\log n/k)$ measurements.

To alleviate this problem, we present a modified version of AltMinSense called Stage-AltMin. Stage-AltMin proceeds in $k$ stages where in the $i$-th stage, a rank-$i$ problem is solved. The goal of the $i$-th stage is to recover top $i$-singular vectors of $M$, up to $O(\sigma^{*}_{i+1})$ error.

Recall that, the main problem with our analysis of AltMinSense is that if $\sigma_{i}\gg\sigma_{i+1}$ (for some $i$) then $\delta_{2k}\leq\frac{(\sigma^{*}_{i+1})^{2}}{(\sigma^{*}_{i})^{2}k}$ would need to be small. However, in such a scenario, the $i$-th stage of Algorithm 3 can be thought of as solving a noisy sensing problem where the goal is to recover $M_{i}\stackrel{{\scriptstyle\textrm{def}}}{{=}}U^{*}_{1:i}\Sigma^{*}_{1:i}(V^{*}_{1:i})^{\dagger}$ using noisy measurements $b={\mathcal{A}}(U^{*}_{1:i}\Sigma^{*}_{1:i}(V^{*}_{1:i})^{\dagger}+N)$ where noise matrix $N\stackrel{{\scriptstyle\textrm{def}}}{{=}}U^{*}_{i+1:k}\Sigma^{*}_{i+1:k}(V^{*}_{i+1:k})^{\dagger}$. Here $M_{i}$ and $N$ represent the top $i$ singular components and last $k-i$ singular components of $M$ respectively. Hence, using noisy-case type analysis (see Section B.3) we show that the error $\|M-\widehat{U}^{t}(\widehat{V}^{t})^{\dagger}\|_{F}$ decreases to $O(\sigma^{*}_{i+1})$.

We now formally present the proof of our main result (see Theorem 2.3).

We prove the theorem using mathematical induction.

Base Case: After the -th step, error is: $\|M\|_{F}^{2}\leq\sum_{j=1}^{k}\sigma_{j}^{2}\leq k\sigma_{1}^{2}$. Hence, base case holds.

Induction Step: Here, assuming that the error bound holds for $(i-1)$-th stage, we prove the error bound for the $i$-th stage.

Our proof proceeds in two steps. First, we show that the initial point $\widehat{U}^{0}_{1:i}$, $\widehat{V}^{0}_{1:i}$ of the $i$-th stage, obtained using Step 4, has $c(\sigma^{*}_{i})^{2}+O\left(k(\sigma^{*}_{i+1})^{2}\right)$ error, with $c<1$. In the second step, we show that using the initial points $\widehat{U}^{0}_{1:i}$, $\widehat{V}^{0}_{1:i}$, the AltMin algorithm iterations in the $i$-th stage (Steps 6, 7) reduces the error to $\max(\epsilon,16k\sigma_{i+1}^{2})$.

We formalize the above mentioned first step in Lemma 6.1 and then prove the second step in Lemma 6.2. ∎

We now present two lemmas used by the above given proof. See Appendix B.4 for a proof of each of the lemmas.

Let assumptions of Theorem 2.3 be satisfied. Also, let $\widehat{U}^{0}_{1:i}$, $\widehat{V}^{0}_{1:i}$ be the output of Step 4 of Algorithm 3. Then, assuming that $\|M-\widehat{U}^{T}_{1:i-1}\widehat{V}^{T}_{1:i-1}\|_{F}^{2}\leq 16k(\sigma^{*}_{i})^{2}$, we obtain:

Let assumptions of Theorem 2.3 be satisfied. Also, let $\widehat{U}^{T}_{1:i}$, $\widehat{V}^{T}_{1:i}$ be the $T$-th step iterates of the $i$-th stage of Algorithm 3. Then, assuming that $\|M-\widehat{U}^{0}_{1:i}V^{0}_{1:i}\|_{F}^{2}\leq\sum_{j=i+1}^{k}(\sigma^{*}_{j})^{2}+\frac{1}{100}(\sigma^{*}_{i})^{2}$, we obtain:

where $T=\Omega(\log(\|M\|_{F}/\epsilon))$.

Summary and Discussion

Alternating minimization provides an empirically appealing and popular approach to solving several different low-rank matrix recovery problems. The main motivation, and result, of this paper was to provide the first theoretical guarantees on the global optimality of alternating minimization, for matrix completion and the related problem of matrix sensing. We would like to note the following aspects of our results and proofs:

For both the problems, we show that alternating minimization recovers the true matrix under similar problem conditions (RIP, incoherence) to those used by existing algorithms (based on convex optimization or iterated SVDs); computationally, our results show faster convergence to the global optima, but with possibly higher statistical (i.e. sample) complexity.

We develop a new framework for analyzing alternating minimization for low-rank problems. Key observation of our framework is that for some problems (under standard problem conditions) alternating minimization can be viewed as a perturbed version of the power method. In our case, we can control the perturbation error based on the extent of RIP / incoherence demonstrated by the problem. This idea is likely to have applications to other similar problems where trace-norm based convex relaxation techniques have rigorous theoretical results but alternating minimization has enjoyed more empirical success. For example, robust PCA , spectral clustering etc.

Our analysis also sheds light on two key aspects of the alternating minimization approach: Initialization: Due to its connection to power method, it is now easy to see that for alternating minimization to succeed, the initial iterate should not be orthogonal to the target vector. Our results indeed show that alternating minimization succeeds if the initial iterate is not “almost orthogonal” to the target subspace. This suggests that, selecting initial iterate smartly is preferable to random initialization. Dependence on the condition number: Our results for the alternating minimization algorithm depend on the condition number. However, using a stagewise adaptation of alternating minimization, we can remove this dependence for the matrix sensing problem. This suggests that (problem specific) modifications of the basic alternating minimization algorithm may in fact perform better than the original one, while (mostly) retaining the computational / implementational simplicity of the underlying method.

References

Appendix A Preliminaries

Let $b={\mathcal{A}}(M)+e$, where $e$ is a bounded error vector, $M$ is a rank-$k$ matrix and ${\mathcal{A}}$ is a linear measurement operator that satisfies $2k$-RIP with constant $\delta_{2k}$ (assume $\delta_{2k}<1/3$). Let $X^{t+1}$ be the $t+1$-th step iterate of SVP, then the following holds:

In our analysis, we heavily use the following two results. The first result is the well-known Bernstein’s inequality.

The second result is a restatement of Theorem 3.1 from .

(Restatement of Theorem 3.1 from ) Suppose $M$ is an incoherent rank-$k$ matrix and let $p,\Omega$ be as in Theorem 2.5. Further, let $M_{k}$ be the best rank-$k$ approximation of $\frac{1}{p}P_{\Omega}\left(M\right)$. Then, w.h.p. we have:

Remark: Note that Theorem 3.1 from holds only for $T_{r}\left(P_{\Omega}(M)\right)$ where $T_{r}\left(P_{\Omega}(M)\right)$ is a trimmed version of $P_{\Omega}(M)$ obtained by setting all rows and columns of $P_{\Omega}(M)$ with too many observed entries to zero. However, using standard Chernoff bound we can argue that for our choice of $p$, none of the rows and columns of $P_{\Omega}(M)$ have too many observed entries and hence $T_{r}\left(P_{\Omega}(M)\right)=P_{\Omega}(M)$, whp.

Appendix B Matrix Sensing: Proofs

The following is an alternate characterization of RIP that we use heavily in our proofs. At a conceptual level, it says that if ${\mathcal{A}}$ satisfies RIP, then it also preserves inner-product between any two rank-$k$ matrices (upto some additive error).

Consider the matrices $X_{1}\stackrel{{\scriptstyle\textrm{def}}}{{=}}U_{1}V_{1}^{T}$, $X_{2}\stackrel{{\scriptstyle\textrm{def}}}{{=}}U_{2}V_{2}^{T}$ and $X=X_{1}+X_{2}$. Since the rank of $X$ is at most $2k$, we obtain the following using the RIP of $\mathcal{A}$:

Concentrating on the second inequality, we obtain

A similar argument proves the other side of the inequality. This proves the lemma. ∎

We first show that the update (6) reduces to:

Let $Err(V)\stackrel{{\scriptstyle\textrm{def}}}{{=}}\sum_{i}\left(\operatorname{Tr}\left(A_{i}M\right)-\operatorname{Tr}\left(A_{i}U^{(t)}V^{\dagger}\right)\right)^{2}$. Since $\widehat{V}^{(t+1)}$ minimizes $E(V)$, we have $\nabla_{V}E(\widehat{V}^{(t+1)})=0$.

where inverting $B$ is valid since the minimum singular value of $B$ is strictly positive (please refer Lemma B.2). Considering the $p^{\textrm{th}}$ block of $\widehat{v}^{(t)}$, we obtain

This gives us the following equation for $\widehat{V}^{(t)}$:

where F=\left[\begin{array}[]{cccc}\left(B^{-1}\left(BD-C\right)Sv^{*}\right)_{1}&\left(B^{-1}\left(BD-C\right)Sv^{*}\right)_{2}&\cdots&\left(B^{-1}\left(BD-C\right)Sv^{*}\right)_{k}\end{array}\right].

Consider $B=\sum_{i}A_{i}u^{t}(u^{t})^{\dagger}A_{i}^{\dagger}$. Now, smallest eigenvalue of $B$, i.e., $\lambda_{min}(B)$ is given by:

where the last inequality follows using Lemma B.1. Using (38),

Now, consider $G=\langle u^{*},u^{t}\rangle B-C=\sum_{i}A_{i}\left(\langle u^{*},u^{t}\rangle u^{t}(u^{t})^{\dagger}-u^{t}(u^{*})^{\dagger}\right)A_{i}^{\dagger}=\sum_{i}A_{i}u^{t}\left(\langle u^{*},u^{t}\rangle u^{t}-u^{*}\right)^{\dagger}A_{i}^{\dagger}$. Using definition of the spectral norm:

where the last inequality follows by using Lemma B.1 and the fact that $\langle u^{t},\left(\langle u^{*},u^{t}\rangle u^{t}-u^{*}\right)\rangle=0$.

Lemma now follows using (37), (39), (40). ∎

B.2 Rank-k𝑘k Matrix Sensing

Since $\widehat{U}^{t}$ and $\widetilde{U}^{t}$ have full rank and span the same subspace, there exists a $k\times k$, full rank matrix $R$ such that $\widehat{U}^{t}=\widetilde{U}^{t}R=U^{t}R_{U}^{t}R$. We have:

Now, using RIP (see Definition 2.1) along with the above equation, we get:

Since $w$ was arbitrary, this proves the lemma. ∎

We calculate $\left(BD-C\right)_{pq}$ as follows:

Since $w$ and $z$ were arbitrary unit vectors, we can conclude that $\left\|{BD-C}\right\|_{2}\leq\delta_{2k}\sqrt{k}\cdot dist(U^{t},U^{*})$. Plugging this bound in (42) proves the lemma. ∎

Note that $\|\Sigma^{*}(R^{(t+1)})^{-1}\|_{2}\leq\frac{\sigma^{*}_{1}}{\sigma_{\text{min}}(R^{(t+1)})}$. Now,

Lemma now follows using above inequality with Lemma 4.6.

B.3 Noisy Matrix Sensing: Proofs

We now consider an extension of the matrix sensing problem where measurements can be corrupted arbitrarily using a bounded noise. That is, we observe $b={\mathcal{A}}\left(M+N\right)$, where $N$ is the noise matrix. For this noisy case as well, we show that AltMinSense recovers $M$ upto an additive approximation depending on the Frobenius norm of $N$.

Let $M$ and $\mathcal{A}(\cdot)$ be as defined in Theorem 2.2. Suppose, AltMinSense algorithm (Algorithm 1) is supplied inputs ${\mathcal{A}}$, $b={\mathcal{A}}(M+N)$, where $N$ is the noise matrix s.t. $\left\|N\right\|_{F}<\frac{1}{100}\sigma^{*}_{k}$. Then, after $T=4\log(2/\epsilon)$ steps, iterates $\widehat{U}^{T}$, $\widehat{V}^{T}$ of AltMinSense satisfy:

At a high level, our proof for noisy case follows closely, the exact case proof given in Section 4. That is, we show that the update of AltMinSense algorithm is similar to power-method type update but with two errors terms: one due to incomplete measurements and another due to the noise matrix.

Similar to our proof for sensing problem (Section 4), we analyze QR-decomposition based updates. That is,

Similar to Lemma 4.5, we can re-write the above given update equation as:

where, $F$ is the error matrix and is as defined in (18) and $G$ is the error matrix due to noise and is given by:

where $B$, $C$ and $D$ defined in the previous section (See (13)) and $C^{N}$ and $D^{N}$ are defined below:

Now, multiplying (44) with $V^{*}_{\perp}$, we get:

where the last inequality follows using Lemma 4.6.

Now, we break down the proof in the following two steps:

Bound $\left\|{G}\right\|_{2}$ (Lemma B.4, analogous to Lemma 4.6)

Bound $\|({R^{(t+1)}})^{-1}\|_{2}$ (Lemma B.5, similar to Lemma 4.7)

Later in this section, we provide the above mentioned lemmas and their detailed proof.

As, $U^{0}$ is obtained using SVD of $\sum_{i}A_{i}b_{i}$. Hence, using Lemma A.1, we have:

where last inequality follows using $\frac{\|N\|_{F}}{\sigma^{*}_{k}}<1/100$.

Theorem now follows using above equation with (47). ∎

Assuming conditions of Lemma B.4, we have the following bound on the minimum singular value of $R^{(t)}$:

Similar to the proof of Lemma 4.7, we have the following set of inequalities:

B.4 Stagewise Alternating Minimization for Matrix Sensing: Proofs

As the initial point of the $i$-th stage is obtained by one step of SVP , using Lemma A.1, we obtain:

Now, by assumption over the $(i-1)$-th stage error (this assumption follows from the inductive hypothesis in proof of Theorem 2.3),

Lemma now follows by setting $\delta_{2k}\leq\frac{1}{3200k}$. ∎

For our proof, we consider two cases: a) $\frac{\sigma^{*}_{i}}{\sigma^{*}_{i+1}}<5\sqrt{k}$, b) $\frac{\sigma^{*}_{i}}{\sigma^{*}_{i+1}}\geq 5\sqrt{k}$. Case (a): In this case, using monotonicity of the AltMin algorithm directly gives error bound. That is, $\|M-\widehat{U}^{T}_{1:i}(\widehat{V}_{1:i}^{T})^{{\dagger}}\|_{F}^{2}\leq\|M-\widehat{U}^{0}_{1:i}V^{0}_{1:i}\|_{F}^{2}\leq k(\sigma^{*}_{i+1})^{2}+\frac{25k}{100}(\sigma^{*}_{i+1})^{2}.$ Case (b): At a high level, if $\frac{\sigma^{*}_{i}}{\sigma^{*}_{i+1}}\geq 5\sqrt{k}$ then $U^{0}_{1:i}$ is “close” to $U^{*}_{1:i}$ and hence the error bound follows by using an analysis similar to the noisy case. Note that $\sigma^{*}_{i+1}$ being small implies that the “noise” is small. See Lemma B.6 for a formal proof of this case. ∎

Assume conditions given in Theorem 2.3 are satisfied and let $\frac{\sigma^{*}_{i}}{\sigma^{*}_{i+1}}\geq 5\sqrt{k}$. Also, let

Then, $U^{T}_{1:i}$, $V^{T}_{1:i}$ satisfy:

We first show that if $\sigma_{i}$ and $\sigma_{i+1}$ have large gap then $\forall\;t$, the $t^{\textrm{th}}$ iterate of the $i$-th stage, $\widehat{U}^{t}_{1:i}$ is close to $U^{*}_{1:i}$. Let $U_{\perp}^{t}$ be a basis of the subspace orthogonal to $\widehat{U}^{t}_{1:i}$.

where $(\zeta_{1})$ follows from the fact that lines $5-8$ of Algorithm 3 never increases $\left\|{{\mathcal{A}}\left(M-\widehat{U}^{t}_{1:i}(\widehat{V}^{t}_{1:i})^{\dagger}\right)}\right\|_{2}$. Using (50), (51), and $\frac{\sigma^{*}_{i}}{\sigma^{*}_{i+1}}\geq 5\sqrt{k}$, we obtain the following bound:

Now, we consider the update equation for $\widehat{V}^{t+1}$:

Note that, the update is same as noisy case with noise matrix $N=U^{*}_{i+1:k}\Sigma^{*}_{i+1:k}(V^{*}_{i+1:k})^{\dagger}$ from (44):

where $F$ and $G$ are given by (18), (45). Multiplying (53) from the left by $V_{\perp}^{{\dagger}}=I-V^{t+1}(V^{t+1})^{\dagger}$, we obtain:

where the last inequality follows using the fact that $\sigma_{\min}(A)\|B\|_{F}\leq\|AB\|_{F}$. Using Lemma B.4, and a modification of Lemma 4.6, we get:

Using (54), (55), and the fact that $\sigma_{\min}(U_{\perp}^{\dagger}U^{*}_{1:i})=\sqrt{1-\|U_{\perp}^{\dagger}U^{*}_{1:i}\|_{2}^{2}}$,

Assuming $\left\|{U_{\perp}^{{\dagger}}U^{*}_{1:i}\Sigma^{*}_{1:i}}\right\|_{\text{F}}>2\sqrt{\sum_{j=i+1}^{k}\sigma_{j}^{2}}$, we obtain:

Using similar analysis, we can show that,

So after $T\geq 8\log(k\sigma^{*}_{i})$ iterations, we have:

Using the above inequality, we now bound the error after $T\geq 8\log(k\sigma^{*}_{i})$ iterations of the $i$-th stage:

where $(\zeta_{1})$ follows from (53) and $(\zeta_{2})$ follows from (55). Using (57) and (58), we obtain the following bound:

Appendix C Matrix Completion: Proofs

Using Theorem 5.1, after $O(\log(1/\epsilon))$ iterations, we get:

Now, using (29), the residual after $t$-th step is given by:

where $\zeta_{1}$ follows by Lemma 5.6 and setting $\delta_{2k}$ appropriately. Theorem 2.5 now follows by setting $\epsilon^{\prime}=2\sqrt{k}\|M\|_{F}\epsilon$. ∎

We now provide the two results used in the above lemma.

After step $3$ in Algorithm 2, whp we have:

From Theorem 3.1 in , we have the following result:

Let $U^{(0)}\Sigma V^{{\dagger}}$ be the top $k$ singular components of $M_{k}$. We also have:

where $(\zeta_{1})$ follows from the fact that the column space of the first two terms in the equation is $U_{\perp}^{(0)}$ where as the column space of the last two terms is $U^{(0)}$. Using the above two inequalities, we get:

if $p>\frac{C^{\prime}k^{4}\log n}{m}\cdot\frac{(\sigma^{*}_{1})^{2}}{(\sigma^{*}_{k})^{2}}$ for a large enough constant $C^{\prime}$. ∎

$\widetilde{U}$ is incoherent with parameter $4\mu\sqrt{k}$.

Let $u_{i}^{c}$ be the vector obtained by setting all the elements of $u_{i}$ with magnitude greater than $\frac{2\mu\sqrt{k}}{\sqrt{m}}$ to zero and let $u_{i}^{\overline{c}}\stackrel{{\scriptstyle\textrm{def}}}{{=}}u_{i}-u_{i}^{c}$. Now, note that if for element $j$ of $u_{i}$ we have $\left|u_{i}^{j}\right|>\frac{2\mu\sqrt{k}}{\sqrt{m}}$, then, $|(u_{i}^{c})^{j}-\breve{u}_{i}^{j}|=\left|\breve{u}_{i}^{j}\right|\leq\frac{\mu\sqrt{k}}{\sqrt{m}}\leq\left|u_{i}^{j}-\breve{u}_{i}^{j}\right|$. Hence,

Let $U^{c}=\widetilde{U}\Lambda^{-1}$ (QR decomposition). Then, for any $u_{\perp}^{*}\in\textrm{Span}(U_{\perp}^{*})$ we have:

We now bound $\left\|{\Lambda}\right\|_{2}$ as follows:

where we used the fact that $d<\frac{1}{16k}$. So we have:

Incoherence of $\widetilde{U}$ follows using the following set of inequalities:

C.2 Rank-111 Matrix Completion: Proofs

As $B$ is a diagonal matrix, $\|B^{-1}\|_{2}=\frac{1}{\min_{i}B_{ii}}\leq\frac{1}{1-\delta_{2}}$, where the last inequality follows using Lemma C.3. The lemma now follows using the above observation and Lemma C.4.∎

Let $M=\sigma^{*}u^{*}(v^{*})^{\dagger}$, $p$, $\Omega$, $u^{t}$ be as defined in Lemma 5.3. Then, w.p. at least $1-\frac{1}{n^{3}}$,

Using union bound (for all $j$) and for $p\geq\frac{9\mu_{1}^{2}\log n}{m\delta_{2}^{2}}$, w.p. $1-\frac{1}{n^{3}}$: $\forall j,\langle u^{t},u^{*}\rangle-\delta_{2}\leq Z_{j}\leq\langle u^{t},u^{*}\rangle+\delta_{2}$. ∎

Let $M=\sigma^{*}u^{*}(v^{*})^{\dagger}$, $p$, $\Omega$, $u^{t}$ be as defined in Lemma 5.3. Then, w.p. at least $1-\frac{1}{n^{3}}$,

where $C>0$ is a global constant and $(\zeta_{1})$ follows by using a modified version of Lemma 6.1 by (see Lemma C.5) and $(\zeta_{2})$ follows by using incoherence of $v^{*}$ and $u^{t}$. Lemma now follows by observing that $\max_{x,\|x\|_{2}=1}x^{\dagger}(\langle u^{*},u^{t}\rangle B-C)v^{*}=\|(\langle u^{*},u^{t}\rangle B-C)v^{*}\|_{2}$ and $p>\frac{C\mu_{1}^{2}\log n}{m\delta_{2}^{2}}$. ∎

Using (25) and using the fact that $B,C$ are diagonal matrices:

We bound the largest magnitude of elements in $\widehat{v}^{t+1}$ as follows. For every $j\in[n]$, we have:

where $(\zeta_{1})$ follows from the fact that $1-\delta_{2}\leq B_{jj}\leq 1+\delta_{2}$ and $\left|C_{jj}\right|\leq\left(\left|\langle u^{t},u^{*}\rangle\right|+\delta_{2}\right)$ (please refer Lemma C.3).

C.3 General Rank-k𝑘k Matrix Completion: Proofs

From the decoupled update equation, (30), we obtain:

We bound the two norm of the $(V^{t+1})^{(j)}$ as follows:

where we used the following inequalities in $(\zeta_{1})$:

where (62) follows from the incoherence of $V^{*}$, (63) follows from from an analysis similar to the proof of Lemma 4.7, (64) follows from (the proof of) Lemma C.6, (65) follows from Lemma C.7 and finally (66) follows from the fact that $D^{j}=\left(U^{t}\right)^{{\dagger}}U^{*}$ with $U^{t}$ and $U^{*}$ being orthonormal column matrices. ∎

where the last inequality follows using Lemma C.6 and Lemma C.8. ∎

We now bound $\|B^{-1}\|_{2}$ and $\|C^{j}\|_{2}$, which is required by our bound for $F$ as well as for our incoherence proof.

Let $M,\Omega,p,$ and $U^{t}$ be as defined in Theorem 2.5 and Lemma 5.6. Then, w.p. at least $1-\frac{1}{n^{3}}$:

Lemma would follow using the bound on $\sigma_{min}(B^{j}),\forall j$ that we show below.

That is, by using $p$ as in the statement of the lemma with the above equation and using union bound, we get (w.p. $>1-1/n^{3}$): $\forall w,j\ \ w^{\dagger}B^{j}w\geq 1-\delta_{2k}$. That is, $\forall j,\sigma_{min}(B^{j})\geq(1-\delta_{2k})$. ∎

Finally, we provide a lemma to bound the second part of the error term ($F$).

Let $M,\Omega,p,$ and $U^{t}$ be as defined in Theorem 2.5 and Lemma 5.6. Then, w.p. at least $1-\frac{1}{n^{3}}$:

where $v^{*}=vec(V^{*})$, i.e. $v^{*}=\left[\begin{matrix}V^{*}_{1}\\ \vdots\\ V^{*}_{k}\end{matrix}\right]$.