Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time

Introduction

Under these assumptions, a variety of algorithms based on convex relaxation have been derived . These algorithms relax the problem as a trace-norm minimization problem that can be solved with semidefinite programs (SDP). Unfortunately, solving SDP is inherently slow and rarely used in practice: even the state-of-the-art SDP solver would require $O(n^{\omega})$ time$\omega$ is the exponent of matrix multiplication. Currently, $\omega\approx 2.37$ . to solve the program . Heuristics such as alternating minimization and gradient descent are much preferred due to their efficiency. first showed that under the standard low rank and incoherent settings, as long as we are allowed to observe $\widetilde{O}(\kappa^{4}nk^{4.5}\log(1/\epsilon))$ entriesIn this paper, we assume $n\geq m$ and we use $\widetilde{O}(\cdot)$ to hide polylogarithmic factors in $n$ and $k$. (where $\kappa$ is the condition number of matrix $M$) , then alternating minimization provably recovers the matrix $M$. Subsequent works further unify different approaches by treating matrix completion as a non-convex optimization problem and improve the sample complexity . A remarkable advantage of alternating minimization is its efficiency, as each iteration, the two alternating updates can be implemented in $O(|\Omega|k^{2})$ time.

Despite various advantages, the series of theoretical papers analyzing alternating minimization fail to capture a crucial component of many practical implementations as the updates are usually computed approximately to further speed up the process. In contrast, the analysis pioneered in and followups crucially relies on the exact formulation of the updates, making it difficult to adapt and generalize to the approximate updates setting. On the other hand, developing an alternating minimization framework would also enable us to utilize faster, approximate solvers to implement updates that leads to theoretical speedup of the algorithm.

In Section 2, we introduce the related works which include matrix completion and applying sketching matrices to solve optimization problems. In Section 3, we present the notations, definitions, and lemmas that we use for the later sections. In Section 4, we present the significant findings and discuss the techniques utilized. In Section 5, we provide some concluding remarks and future directions.

Related Work

Low rank matrix completion is a fundamental problem in machine learning. Practical applications including recommender systems, with the most notable one being collaborative filtering and the Netflix Challenge . It also has a wide range of applications in computer visions and signal processing . For more comprehensive surveys, we refer readers to . Algorithms for matrix completion can be roughly divided into two categories — convex relaxation and non-convex heuristics. Candes and Recht prove the first sample complexity for low rank matrix completion under convex relaxation and the bound is subsequently improved by . In practice, heuristic methods based on non-convex optimizations are often preferred due to their simplicity and efficiency. One notable approach is gradient descent . Alternating minimization is also a popular alternative that is widely applied in practice. provides a provable guarantee on the convergence of alternating minimization when the matrix-to-recover is low rank and incoherent. Subsequently, there have been a long line of works analyzing the performance of non-convex heuristics under standard matrix completion setting and under the noise or corrupted-entries setting . Recently, the work provides an algorithm with improved sample complexity and runtime when stronger subspace regularity assumptions are imposed, utilizing techniques from sparse recovery in the semi-random setting .

A recent trend in sketching community is to apply them as a means to reduce the iteration cost of optimization algorithms. Applications such as linear programming , empirical risk minimization , approximating the John ellipsoid , Frank-Wolfe algorithm and linear MDPs .

Preliminary

In this section, we provide necessary background on matrix completion and assumptions.

Given a rank-$k$, $m\times n$ real matrix $A$, we use $\kappa(A)$ to denote its condition number: $\kappa(A)=\frac{\sigma_{1}(A)}{\sigma_{k}(A)}$ where $\sigma_{1}(A),\ldots,\sigma_{k}(A)$ are singular values of $A$ sorted in magnitude. When $A$ is clear from context, we often use $\kappa$ directly.

1 Angles and Distances Between Subspaces

A key quantity that captures the closeness of the subspaces by two matrices is the distance, defined as follows:

One can further quantify the geometry of two subspaces by their principal angles:

For any matrix $U$, and for orthogonal matrix $V$ ($V^{\top}V=I_{k}$) we define

$\tan\theta(V,U):=\|V_{\bot}^{\top}U(V^{\top}U)^{-1}\|$.

For orthogonal matrices $V$ and $U$ ($V^{\top}V=I_{k}$ and $U^{\top}U=I_{k}$), we define

$\cos\theta(V,U):=\sigma_{\min}(V^{\top}U)$.

$\cos\theta(V,U)=1/\|(V^{\top}U)^{-1}\|$ and $\cos\theta(V,U)\leq 1$.

$\sin\theta(V,U)=\|V_{\bot}V_{\bot}^{\top}U\|=\|V_{\bot}^{\top}U\|$ and $\sin\theta(V,U)\leq 1$.

Standard trigonometry equalities and inequalities hold for above definitions, see, e.g., .

2 Background on Matrix Completion

We introduce necessary definitions and assumptions for low rank matrix completion. Given a set of of indices $\Omega$, we define a linear operator that selects the corresponding entries:

A crucial assumption for low rank matrix completion is incoherence. We start by defining the notion below.

Here $u_{i}$ is the $i$-th row of $U$, for all $i\in[m]$.

We say a general rank-$k$ matrix is incoherent if both its row and column spans are incoherent:

$\|u_{i}\|_{2}\leq\frac{\sqrt{k}}{\sqrt{m}}\cdot\mu$, $\forall i\in[m]$

$\|v_{j}\|_{2}\leq\frac{\sqrt{k}}{\sqrt{n}}\cdot\mu$, $\forall j\in[n]$

where $M=U\Sigma V^{\top}$ is the SVD of M and $u_{i}$, $v_{j}$ denote the $i$-th row of $U$ and the $j$-th row of $V$ respectively.

We are now in the position to state the set of assumptions for low rank matrix completion problem.

Each entry of $M$ is sampled independently with equal probability. In other words, the set $\Omega\sim[m]\times[n]$ is formed by sampling each entry independently according to certain distribution.

We note that the above assumptions are all standard in the literature.

Now we are ready to state the low rank matrix completion problem.

Technique Overview

Before diving into the details of our algorithm and analysis, let us review the alternating minimization proposed in . The algorithm can be described pretty succinctly: given the sampled indices $\Omega$, the algorithm starts by partitioning $\Omega$ into $2T+1$ groups, denoted by $\Omega_{0},\ldots,\Omega_{2T}$. The algorithm first computes a top-$k$ SVD of the matrix $\frac{1}{p}P_{\Omega_{0}}(M)$ where $p$ is the sampling probability. It then proceeds to trim all rows of the left singular matrix $U$ with large row norms (this step is often referred as clipping). It then optimizes the factors $U$ and $V$ alternatively. At iteration $t$, the algorithm first fixes $U$ and solves for $V$ with a multiple response regression using entries in $\Omega_{t+1}$, then it fixes the newly obtained $V$ and solves for $U$ with entries in $\Omega_{T+t+1}$. After iterating over all groups in the partition, the algorithm outputs the final factors $U$ and $V$ as its output.

From a runtime complexity perspective, the most expensive steps are solving two multiple response regressions per iteration, which would take a total of $O(|\Omega|k^{2})$ time. On the other hand, we observe that the total instance size for the multiple response regressions is only $O(|\Omega|k)$, inspiring us to consider efficient, randomized solvers that can solve the regression in time nearly linear in the instance size.We note that our solver would incur an extra total cost of $\widetilde{O}(nk^{3})$. Under the standard low rank and incoherent assumptions, the state-of-the-art non-convex optimization-based approach would require $\widetilde{O}(nk^{2+o(1)})$ samples and the $\widetilde{O}(nk^{3})$ time is subsumed by the $\widetilde{O}(|\Omega|k)$ portion. This term is hence ignored. This in turn produces an algorithm with a nearly linear runtime in terms of verifying all entries in $\Omega$.

Two problems remain to complete our algorithm: 1). What kind of multiple response regression solvers will run in nearly linear time and produce high accuracy solutions and 2). How to prove the convergence of the alternating minimization in the presence of the errors caused by approximate solvers. While the second question seems rather intuitive that the algorithm should tolerate moderate amount of errors, the analysis becomes highly nontrivial when one examines the argument in and followups, as all of them crucially rely on the fact that the factors $U$ and $V$ are solved exactly and hence admit closed form. This motivates us to develop an analytical framework for alternating minimization, that admits approximate solves each iteration.

It remains to develop a perturbation theory for alternating minimization and our key innovation is a perturbation argument on the incoherence bound under small row norm perturbation. Let $A_{i}$ denote the $i$-th row of $A$. We show that if two matrices $A$ and $B$ satisfying $\|(A-B)_{i}\|_{2}\leq\epsilon$ and $\epsilon\leq\sigma_{\min}(A)$, then the change of incoherence between $A$ and $B$ is also very small. Our main strategy involves reducing incoherence to statistical leverage score, a critical numerical quantity that measures the importance of rows . The problem then reduces to showing that if two matrices have similar rows, their leverage scores are also similar. By utilizing the leverage score formulation and a perturbation result from , we prove that it is indeed the case they have similar leverage scores. This concludes the perturbation argument on matrix incoherence.

However, this alone is insufficient for our inductive argument to progress, as we must also quantify the proximity between the approximate and exact solutions. To accomplish this, we employ a novel approach based on the condition number of the matrices. Specifically, given the exact matrix $A$ and the approximate matrix $B$, we demonstrate that the distance between $A$ and $B$ is relatively small as long as $\kappa(B)$ is bounded by $\kappa(A)$. To obtain a good bound on $\kappa(B)$, we need to solve the approximate regression to high precision (inverse proportionally to $\kappa(A)$). We achieve this objective through a sketching-based preconditioner, which is the first problem we would like to address.

Sketching-based preconditioning is a widely-used and lightweight approach to solving regression problems with high accuracy. The fundamental concept involves reducing the dimensionality of the regression problem by utilizing a sketching matrix and creating an approximate preconditioner based on the sketch. This preconditioner accelerates the convergence of an iterative solver, such as the conjugate gradient or Generalized Minimal RESidual method (GMRES), employed in the reduced system. With this preconditioner, we obtain an $O(\log(1/\epsilon))$ convergence for an $\epsilon$-approximate solution. Beyond its theoretical soundness and efficiency, these preconditioners also exhibit good performances when used in practice .

An important feature of our robust alternating minimization framework coupled with the fast regression solvers is that we preserve the sample complexity of : by picking the sampling probability $p=O(\kappa^{4}\mu^{2}k^{4.5}\log n\log(1/\epsilon)/m)$, we are required to sample $|\Omega|=O(\kappa^{4}\mu^{2}nk^{4.5}\log n\log(1/\epsilon))$ entries. By a clever thresholding approach, further improves the sample complexity to $O(\kappa^{2}\mu^{2}nk^{4}\log(1/\epsilon))$. As their algorithm is alternating minimization in nature, our robust framework and nearly linear regression solvers can be adapted and hence obtain an improved sample complexity and runtime by a factor of $O(\kappa^{2}k^{0.5}\log n)$.

In the rest of this section, we will review our approaches and clarify how we employ various strategies to achieve our goal.

In Section 4.1, we illustrate the major means to prove the convergence of alternating minimization through a subspace approaching argument.

In Section 4.2, we describe a perturbation theory that handles the incoherence of approximate updates.

In Section 4.3, we present the main algorithmic tool to realize the speedup, a sketching-based high accuracy regression solver.

In Section 4.4, we deliver the main result of this paper.

The basis of the analysis of both and ours is an inductive argument that shows the low rank factors obtained in each iteration approaches the optimum as their distance shrinks by a constant factor and we call this subspace approaching argument, as we iteratively refine subspaces that approach the optimum. The major difference is that the induction of can be based on the exact solutions solely — they inductively prove the distances shrink by a constant factor, and the low rank factors are $\mu_{2}$-incoherent for $\mu_{2}$ to be specified. It is tempting to replace these exact solutions with the approximate solutions we obtain. Unfortunately, the heavily exploits the closed-form formulation of the solutions so that they can easily decompose the matrices into terms whose spectral norms can be bounded in a straightforward manner. Our approximate solutions on the other hand cannot be factored in such a fashion.

To circumvent this issue, we instead keeping the exact solutions $U_{t},V_{t}$ as a sequence of references and inductively bound the incoherence of these exact solutions. More specifically, for any $t\in[T]$, we assume $U_{t}$ is $\mu_{2}$-incoherent and $\operatorname{dist}(\widehat{U}_{t},U^{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{V}_{t},V^{*})\leq 1/10$, then we show that

$\operatorname{dist}(\widehat{V}_{t+1},V^{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{U}_{t},U^{*})\leq 1/10$ and

We can then proceed to show similar conditions hold for $\widehat{U}_{t+1}$ and $U_{t+1}$, therefore advance the induction. Note that we only show the exact solutions are incoherent, but to conclude the desired guarantee on the output, we also need to show that the approximate solutions $\widehat{U},\widehat{V}$ are also incoherent. This motivates us to develop a perturbation theory of matrix incoherence under the presence of row perturbations.

2 A Perturbation Theory for Matrix Incoherence

Our main goal is to understand how perturbations to rows of a matrix change the incoherence.

With all pieces in hand, we can readily prove that indeed, the row norms after isotropic transformation is indeed small:

For more details, we refer readers to Appendix G. We can then instantiate the perturbation result with matrices $\widehat{U}_{t}$ and $U_{t}$, $\widehat{V}_{t}$ and $V_{t}$ respectively.

3 Nearly Linear Time Solve via Sketching

Sum over all $T$ iterations, the total size of the multiple response regression is $O(\sum_{i=1}^{n}|{\cal K}_{i}|k)=O(|\Omega|k)$, and our regression solver takes $\widetilde{O}(|\Omega|k+nk^{3})=\widetilde{O}(|\Omega|k)$ time, as desired.

We summarize the result in the following lemma.

4 Putting Things Together

Given our fast regression solver and robust analytical framework that effectively handles the perturbation error caused by approximate solve, we are in the position of delivering our main result.

It samples $|\Omega|=O(\kappa^{4}\mu^{2}nk^{4.5}\log n\log(k\|M\|_{F}/\epsilon)$ entries;

It runs in $\widetilde{O}(|\Omega|k)$ time.

Let us pause and make some remarks regarding the above result. On the sample complexity front, we attain the result achieved in , but we would also like to point out that it can be further improved using the approach developed in . Our robust alternating minimization framework indicates that as long as the error caused by the approximate solver can be polynomially bounded, then the convergence of the algorithm is preserved (up to $\log(1/\epsilon)$ factors). Thus, our framework can be safely integrated into any alternating minimization-based algorithm for matrix completion.

Moreover, the runtime of algorithm is nearly linear in the verification time — given a set of sampled entries $\Omega$, it takes $O(k)$ time to compute an entry of $P_{\Omega}(\widehat{U}\widehat{V}^{\top})$ therefore a total of $O(|\Omega|k)$ time. achieves similar runtime guarantee with a sample complexity of $|\Omega|=\widetilde{O}(nk^{2+o(1)})$, but their approach is based on generalizing sparse recovery to low rank matrix setting and is much more complicated than ours. As alternating minimization is among the most popular practical implementations for matrix completion, we believe our algorithm not only bridges the gap between theory and practice in terms of robust analysis, but also obtains an improved practical runtime, as the fast regression solver has been widely adapted in practice .

Conclusion

In this paper, we develop a nearly linear time algorithm for low rank matrix completion via two ingredients: a sketching-based preconditioner for solving multiple response regressions, and a robust framework for alternating minimization.

Our robust alternating minimization framework effectively bridges the gap between theory and practice — as all prior theoretical analysis of alternating minimization requires exact solve of the multiple response regressions, but in practice, fast and cheap approximate solvers are preferred. Our algorithm also has the feature that it runs in time nearly linear in verifying the solution, as given a set of entries $\Omega$, it takes $O(|\Omega|k)$ time to compute the corresponding entries.

One natural next step is to improve the sample complexity for alternating minimization-based matrix completion algorithms, as it would lead to direct sample complexity and runtime improvement to our approach. It is also interesting to develop an algorithm that runs in nearly linear time of the output size, i.e., an algorithm with runtime $\widetilde{O}(mk+nk)$.

Acknowledgement

The authors would like to thank Jonathan Kelner for helpful discussions and pointing out many references. Lichen Zhang is supported by NSF grant No. 1955217 and NSF grant No. 2022448.

References

Appendix

In Section A, we introduce more fundamental lemmas and facts. In Section B, we provide more details about our sketching-based solver. In Section C, we support the main init by giving and explaining more definitions and lemmas. In Section D, we explain our main induction hypothesis. In Section E, we analyze the general case of the update rules and notations. In Section F, we give the lemmas for distance shrinking and their proofs: we upper bound different terms by distance. In Section G, we analyze the distance and incoherence under row perturbations.

Appendix A More Preliminary

In this section, we display more fundamental concepts. In Section A.1, we introduce algebraic properties for matrices. In Section A.2, we analyze the properties of angles and distances. In Section A.3, we provide the tools which are used in previous works. In Section A.4, we state several well-known probability tools.

We state several standard norm inequalities here.

Part 2. $\|AB\|\geq\|A\|\cdot\sigma_{\min}(B)$.

Part 4. if $B^{\top}A=0$, $\|A+B\|\geq\|A\|$ .

Part 5. $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$.

Part 7. $\|A\|_{F}\leq\sqrt{k}\|A\|$ if $A$ is rank-$k$.

Part 8. If $A$ is invertible, we have $\|A\|=\sigma_{\min}(A^{-1})$.

Part 9. For vector $x$ with $\|x\|_{2}=1$, we have $\|Ax\|_{2}=\max_{y:\|y\|_{2}=1}y^{\top}Ax$.

For any matrix $A$, square invertible matrix $B$

Part 10. $\|A\|\leq\sigma_{\max}(B)\cdot\|AB^{-1}\|$.

For any matrix $A$, and square diagonal invertible matrix $B$

Part 11. $\sigma_{\min}(BA)\geq\sigma_{\min}(B)\cdot\sigma_{\min}(A)$.

We omit their proofs, as they are quite standard.

The next fact bounds the spectral norm of a matrix after applying a unitary transformation.

Part 1. By the property of $U$, we know that $UU^{\top}\preceq I_{m}$.

Part 2. By property of $U$, we have $U^{\top}U=I_{k}$.

The following is a collection of simple algebraic facts.

Part 1. If $x\in(0,1/2)$, then $\sqrt{1-x^{2}}-yx\geq 1/2$.

Part 2. If $x\geq 1/2$, then $x-y\sqrt{1-x^{2}}\geq\frac{1}{2}x$.

Part 3. If $x\in$, then $1-\sqrt{1-x^{2}}\leq x^{2}$.

where the first step follows from $y\in(0,0.1)$, the second step follows from $\sqrt{1-x^{2}}\geq 1-\frac{1}{2}x$ for all $x\in[0,4/3]$, and the last step follows from $x\leq 1/2$.

where the first step follows from $0\leq\sqrt{1-x^{2}}\leq 1$, the second step follows from $y\in(0,0.1)$, and the last step follows from $x\geq 1/2$.

where the first step follows from Eq. (1) and the second step follows from simple algebra.

for all $x$ in the domain of $\sqrt{1-x^{2}}$.

A.2 Properties of Angles and Distances

We explore some more relations for angles and distances between subspaces.

The next lemma is a simple application of fundamental subspaces decomposition.

We know that the column space of $A$ is orthogonal to the null space of $A^{\top}$, and the null space of $A^{\top}$ has dimension $n-k$.

Let $A_{\perp}$ be an orthonormal basis of the null space of $A^{\top}$.

We know that $z$ either in the column space of $A$ or the null space of $A^{\top}$.

Case 1: $z$ in the column space of $A$. In this case, we can write $z=Ay$.

where the first step follows from $z=Ay$, the second step follows from $A$ is orthogonal that $A^{\top}=A^{-1}$, the third step follows from $(AB)^{\top}=B^{\top}A^{\top}$ for all matrices $A$ and $B$, the fourth step follows from Eq. (2), and the last step follows from $z=Ay$.

Case 2: $z$ in the null space of $A^{\top}$. In this case, we know that $A^{\top}z=0$ and $z=A_{\perp}y$, so

where the first step follows from $A^{\top}z=0$ and $z=A_{\perp}y$, the second step follows from $A_{\bot}^{\top}A_{\bot}=I$, and the third step follows from $z=Ay$.

Thus, we have shown $AA^{\top}+A_{\perp}A_{\perp}^{\top}=I_{n}$. ∎

The following lemma presents a simple inequality for orthogonal complements.

Let us first compute the Gram matrix of $V^{\top}U$, which is

where the first step follows from $V_{\bot}V_{\bot}^{\top}+VV^{\top}=I$, the second step follows from simple algebra, and the last step follows from $U$ has orthonormal columns.

This means that $(V^{\top}U)_{\bot}=V_{\bot}^{\top}U$. ∎

The singular vectors can be parametrized by orthogonal complement and inverse, solely.

Part 1. $A_{\bot}$ and $A^{-1}$ have the same set of singular vectors.

Part 2. Let $u$ be a singular vector of $A$, if $u$ corresponds to $\sigma_{i}(A)$, then it corresponds to $\sigma_{k-i}(A_{\bot})$.

Part 3. $\|A_{\bot}A^{-1}\|=\|A_{\bot}\|\|A^{-1}\|$.

we argue that $x$ corresponds to the smallest singular value of $A_{\bot}$ via contradiction. Suppose there exists some unit vector $y$ with

and it contradicts the definition of spectral norm.

Similarly, if $z$ is the unit vector that realizes the spectral norm of $A_{\bot}$, then it is also a singular vector corresponds to the smallest singular value of $A$, or equivalently, the spectral norm of $A^{-1}$. Our above argument essentially implies that $A_{\bot}$ and $A^{-1}$ have the same set of singular vectors.

Our above argument is choosing $x$ to the eigenvector corresponding to the largest singular values. Similarly, we can choose to 2nd, 3rd, and then prove entire sets.

let $\sigma_{1}(A),\ldots,\sigma_{k}(A)$ be the singular values of $A$ and $u_{1},\ldots,u_{k}$ be corresponding singular vectors.

which means that $A_{\perp}u_{i}=\sqrt{1-\sigma_{i}^{2}(A)}u_{i}$. Note that all singular values of $A_{\perp}$ are in this form, i.e., we have its singular values being

as $\sigma_{1}(A)\geq\ldots\geq\sigma_{k}(A)$, and the above singular values are in ascending order.

Proof of Part 3. The proof is then straightforward.

Suppose that $(\lambda,z)$ is largest singular value and singular vector (e.g. $\|A_{\bot}\|=\lambda$). Then, we have

Using Part 2 (by choosing $i=1$), we know that $z$ is also the largest singular vector for $A^{-1}$. Assume that $A^{-1}$ largest singular value is $\mu$ (e.g. $\|A^{-1}\|=\mu$). Then we have

where the first step follows from Eq. (4), the second step follows from $\mu$ is a real number and a real number multiplying a matrix is commutative and follows from the associative property, and the third step follows from Eq. (3).

Combining the lower bound and upper bound, we have

We prove several fundamental trigonometry equalities for subspace angles.

where the first step follows from the definition of $\tan\theta(V,U)$ (see Definition 3.2), the second step follows from Lemma A.5, the third step follows from the part 3 of Lemma A.6, the fourth step follows from simple algebra, the fifth step follows from Lemma A.5, and the last step follows from the definition of $\sin\theta(V,U)$ and $\cos\theta(V,U)$ (see Definition 3.2). ∎

Recall that $\cos\theta(V,U)=\frac{1}{\|(V^{\top}U)^{-1}\|}$ and $\sin\theta(V,U)=\|V_{\bot}^{\top}U\|$.

so by the definition of $\sin\theta(V,U)$ (see Definition 3.2), we have

By part 1 of Lemma A.6, we know that $A_{\bot}$ and $A^{-1}$ have the same set of singular vectors.

Note that $A_{\bot}$ and $A^{-1}$ have the same singular vectors implies that the singular vector realizing $\|A_{\bot}\|$ corresponds to the smallest singular value of $A$, i.e.,

where the first step follows from $\|z\|_{2}^{2}=1$, the second step follows from $A^{\top}A+A_{\bot}^{\top}A_{\bot}=I$, the third step follows from simple algebra, the fourth step follows from $x^{\top}B^{\top}Bx=\|Bx\|_{2}^{2}$, the fifth step follows from Eq. (7), and the sixth step follows from Eq. (8).

where the first step follows from Eq. (6), the second step follows from Lemma A.5, the third step follows from definitions of $\sin\theta$ and $\cos\theta$ (see Def. 3.2).

Therefore, by Eq. (A.2), we have $\sin^{2}\theta(V,U)+\cos^{2}\theta(V,U)=1$. This completes the proof. ∎

The next lemma demonstrates relationship between several trigonometry definitions.

Part 1. $\sin\theta(V,U)\leq\tan\theta(V,U)$.

Part 2. $\frac{1-\cos\theta(V,U)}{\cos\theta(V,U)}\leq\tan\theta(V,U)$.

Part 3. $\sin\theta(V,U)\leq\operatorname{dist}_{c}(V,U)$.

Part 4. $\operatorname{dist}_{c}(V,U)\leq\sin\theta(V,U)+\frac{1-\cos\theta(V,U)}{\cos\theta(V,U)}$.

Part 5. $\operatorname{dist}_{c}(V,U)\leq 2\tan\theta(V,U)$.

where the first step follows from the definition of

the second step follows from $U=VQ^{*}+R$ (see Eq. (10)), the third step follows from simple algebra, the fourth step follows from $V_{\bot}^{\top}V=(V^{\top}V_{\bot})^{\top}=0$ (see Lemma A.4), the fifth step follows from $\|AB\|\leq\|A\|\|B\|$, and the last step follows from $\|V_{\bot}^{\top}\|\leq 1$.

where the first step follows from Lemma A.7, the last step follows from $\cos\theta(V,U)\leq 1$.

Proof of Part 2. For simplicity, we use $\theta$ to represent $\theta(V,U)$.

Using Lemma A.8, the above equation is further equivalent to

This is true forever, since $\cos\theta\in$.

Proof of Part 3. Given $\operatorname{dist}_{c}(V,U)=\|R\|$ (Eq. (11)) and $\sin\theta(V,U)\leq\|R\|$ (Eq. (A.2)), we have

Proof of Part 4. We define $A,D,B$ as the SVD of matrix $V^{\top}U$ as follows

where the first step follows from $(AB)^{\top}=B^{\top}A^{\top}$ for all matrices $A$ and $B$, the second step follows from the simple property of matrix, the third step follows from the fact that $B$ is orthogonal, and the last step follows from simple algebra, i.e., $AB^{\top}\in O^{k\times k}$.

For $\operatorname{dist}_{c}(V,U)$, we have

where the first step follows from $AB^{\top}$ can not provide a better cost than minimizer, the second step follows from Eq. (13), the third step follows from simple algebra, and the last step follows from the triangle inequality.

For the second term of Eq. (A.2), namely $\|VV^{\top}U-U\|$, we have

where the first step follows from simple algebra and the second step follows from the definition of $\sin\theta(V,U)$ (see Definition 3.2).

For the first term of Eq. (A.2), namely $\|VV^{\top}UBD^{-1}B^{\top}-VV^{\top}U\|$, we have

where the first step follows from simple algebra, the second step follows from $\|VV^{\top}U\|\leq 1$, the third step follows from $B$ is orthonormal basis, and the last step follows from $\|D^{-1}-I\|=|\frac{1}{\sigma_{\min}(D)}-1|=|\frac{1}{\cos\theta}-1|=\frac{1-\cos\theta}{\cos\theta}$.

where the first step follows from Part 4, the second step follows from Part 2, and the last step follows from Part 1. ∎

A.3 Tools from Prior Works

The previous paper assumes the entries of $M$ are sampled independently with the following probability. Note that the choice of $p$ also determines the sample complexity of the algorithm.

Let $C\geq 10$ denote a sufficiently large constant. We define sample probability to be

Then, we sample $\Omega\sim[m]\times[n]$ each coordinately independently according to that probability.

The parameter $\delta_{2k}$ is a tuning parameter for sampling probability.

It is obvious that $\delta_{2k}\in(0,0.01)$.

Given the set of indices, we denote the row and column selection operator as follows.

For each $j\in[n]$, we define set $\Omega_{*,j}\subset[m]$

For each $i\in[m]$, we define set $\Omega_{i,*}\subset[m]$,

The next structural lemma bounds the inner product between vectors inside set $\Omega$.

Let $\Omega\subset[m]\times[n]$ be a set f indices sampled uniformly at random from $[m]\times[n]$ with each element of $[m]\times[n]$ sampled independently with probability $p\geq C(\log n)/m$. Let $C>1$ be a sufficiently large constant.

The following lemma bounds the spectral gap between two matrix inverses in terms of the larger of their spectral norm squared, times the spectral norm of their differences.

For two conforming real matrices $A$ and $B$,

The next claim bounds the inner product between any unit vector and rows of incoherent matrix.

Suppose $U_{t}$ is $\mu_{2}$ incoherent, and $U_{*}$ is $\mu$ incoherent. For any unit vectors $x,y$ we have

Part 1. $\sum_{i\in[m]}\langle x,U_{t,i}\rangle^{4}\leq\mu_{2}^{2}k/m$

Part 2. $\sum_{i\in[m]}\langle y,U_{*,i}\rangle^{2}\cdot\langle x,U_{t,i}\rangle^{2}\leq\mu^{2}k/m$.

Proof of Part 1. Note that $\|U_{t,i}\|_{2}\leq 1$, so

where the second step follows from the inner product between two unit vectors is at most 1.

where the last step follows from $U_{t}$ is $\mu_{2}$ incoherent.

where the first step follows from $\sum_{i\in[m]}a_{i}b_{i}\leq\max_{i\in[m]}a_{i}\sum_{i\in[m]}b_{i}$, the second step follows from Eq. (A.3), the third step follows from $U_{t}^{\top}U_{t}=\sum_{i=1}^{m}U_{t,i}^{\top}U_{t,i}$, the fourth step follows from $U_{t}^{\top}U_{t}=I_{k}$, and the last step follows from the Lemma statement that $x$ is a unit vector.

Proof of Part 2. Similarly as the proof of part 1. We know that

where the first step follows from $\sum_{i\in[m]}a_{i}b_{i}\leq\max_{i\in[m]}a_{i}\sum_{i\in[m]}b_{i}$, the second step follows from Eq. (17), the third step follows from $U_{t}^{\top}U_{t}=\sum_{i=1}^{m}U_{t,i}^{\top}U_{t,i}$, and the last step follows from $U_{t}U_{t}=I_{k}$. ∎

A.4 Probability Tools

We introduce several well-known probability inequalities.

$\Pr[X\geq(1+\delta)\mu]\leq\exp(-\delta^{2}\mu/3)$, $\forall\delta>0$;

$\Pr[X\leq(1-\delta)\mu]\leq\exp(-\delta^{2}\mu/2)$, $\forall\delta\in(0,1)$.

Appendix B High Accuracy Weighted Regression Solver

We demonstrate our high accuracy, iterative solver for weighted multiple response regression in this section.

Here, we mainly focus on the SRHT matrix, the algorithm that processes it, and its properties. We start by introducing the definition of the SRHT matrix .

For an $n\times d$ matrix $A$, $SA$ can be computed in time $O(nd\log n)$.

The following lemma states that a suitable chosen SRHT provides the so-called subspace embedding property.

SRHT can be further utilized for a high accuracy regression solver, as presented by the following lemma.

The above result also extends to weighted regression, measured in terms of the $\|v\|_{w}^{2}=\sum_{i=1}^{n}w_{i}v_{i}^{2}$ norm. For the sake of completeness, we include the algorithm and a proof here.

Let us analyze Algorithm 2, first on its convergence then on its runtime.

where the first step follows from the definition of $x_{t+1}$ from Algorithm 2, the second step follows from simple algebra, the third step follows from $b=ARx^{*}$, the fourth step follows from simple algebra, the last step follows from the SVD, $AR=U\Sigma V^{\top}$.

and recall for initial solution $x_{0}$, we have

B.2 Forward Error of Regression

Let $x_{\operatorname{OPT}}$ denote the exact solution to the regression problem, then it holds that

so we can perform the following decomposition:

where the first step follows from simple algebra, the second step follows from the Pythagorean theorem, the third step follows from the assumption of Lemma B.5, and the fourth step follows from simple algebra.

Assuming $A$ has full column rank, then $A^{\dagger}A=I$.

where the first step follows from $A^{\dagger}A=I$, the second step follows from $\|ABx\|_{2}\leq\|Ax\|_{2}\|B\|$, the third step follows from Eq. (B.2), and the last step follows from $\|A^{\dagger}\|=\|A^{-1}\|=\frac{1}{\sigma_{\min}(A)}$. ∎

B.3 Reducing Weighted Linear Regression to Linear Regression

Solving the regression in matrix completion involves computing the Hadamard product with a binary matrix, we further generalize it to a nonnegative weight matrix, and show it’s equivalent up to a rescaling.

Let $\epsilon_{1}\in(0,0.1)$ and $\delta_{1}\in(0,0.1)$.

with probability at least $1-\delta_{1}$, then there is an algorithm that runs in

where the first step follows from the definition of $\|\cdot\|_{2}^{2}$, the second step follows from the definition of $\widetilde{A}_{i,:}$ and $\widetilde{b}_{i}$, the third step follows from simple algebra, the fourth step follows from $(xy)^{2}=x^{2}y^{2}$, and the last step follows from the definition of $\|Ay-b\|_{w}^{2}$. This finishes the proof. ∎

B.4 Solving Weighted Multiple Response Regression in Weight Sparsity Time

The main result of this section is an algorithm, together with a weighted multiple response analysis that runs in time proportional to the sparsity of weight matrix $W$.

We can rewrite multiple regression into $n$ linear regression in the following way,

Consider the $i$-th linear regression. We define

Let $C>1$ be a sufficiently large constant (The running time of the algorithm is linear in $C$). Using forward error Lemma B.5, we know that

where the second step follows from $\|M_{:,i}\|_{2}\leq\sigma_{\max}(M)$, the third step follows from the definition of $\kappa_{0}$ (see Lemma B.7), and the last step follows from simple algebra.

Using Lemma B.6 $n$ times, we can obtain the running time. ∎

Appendix C Initialization Conditions

In this section, we deal with init conditions. In Section C.1, we provide the lemma which bound the distance between $U_{\phi}$ and $U_{*}$. In Section C.2, we show that if $U_{\phi}$ is close to $U_{*}$, then $U_{0}$ is close to $U_{*}$. In Section C.3, we give the formal definition of $U_{0}$, $U_{\tau}$, and $U_{\phi}$. In Section C.4, we combine the previous lemmas to form a new result.

We prove our init condition lemma. This can be viewed as a variation of Lemma C.1 in .

holds with probability at least $1-1/\operatorname{poly}(n)$.

Let $M_{\phi}:=U_{\phi}\Sigma V^{\top}$. Let $C>1$ be some constant decided by Theorem 3.1 .

where the first step follows from Theorem 3.1 in , the second step follows from $\|M\|_{F}\leq\sqrt{k}\sigma_{1}^{*}$, the third step follows from simple algebra, namely $k^{\frac{1}{2}}\cdot k^{\frac{1}{2}}=k$, the fourth step follows from $n\geq m$, the last step follows from

where the first step follows from the SVD of $M$ (see Definition 3.5) and $M_{k}$, the second step follows from adding and subtracting the same thing, the third step follows from simple algebra, the fourth step follows from $\|A+B\|\geq\|A\|$ if $B^{\top}A=0$ (Fact A.1), the fifth step follows from $U_{\phi}U_{\phi}^{\top}+U_{\phi,\bot}U_{\phi,\bot}^{\top}=I$, the sixth step follows from applying Part 2 of Fact A.2 twice (one for $U_{\phi,\bot}$ and one for $V_{*}$), the seventh step follows from $\|AB\|\geq\|A\|\cdot\sigma_{\min}(B)$ (Fact A.1), and the last step follows from $\sigma_{\min}(\Sigma_{*})=\sigma_{k}^{*}$.

Combining Eq. (C.1) and Eq. (C.1), we get:

We first define $\tau$, and then provide a lemma to show that whenever $U_{\phi}$ is close to $U_{*}$, $U_{0}$ is close to $U_{*}$.

The initialization condition proof is very standard in literature, we follows from .

Let $U_{\phi}$ be an orthonormal column matrix such that

Let $U_{0}$ be an orthonormal basis of $U_{\tau}$.

Part 1. $\operatorname{dist}(U_{0},U_{*})\leq 1/2$

Part 2. $U_{0}$ is incoherent with parameter $4\mu\sqrt{k}$.

For the convenience of matching later induction proof, when we use this lemma for the base in induction, we write $\widehat{U}_{0}$ to denote $U_{\tau}$.

Proof of Part 1. For simplicity, in the proof, we use $\epsilon$ to denote $\epsilon_{\phi}$.

By definition of $U_{\phi}$, we know that

Then, for each $j\in[m]$ with $|(u_{i})_{j}|>\tau$,

where the first step follows from truncation at $\tau$, the second step follows from simple algebra, the third step follows from Eq. (27), the fourth step follows from simple algebra, the fifth step follows from the definition of $|(u_{i})_{j}|$ and $|(z_{i})_{j}|$, and the last step follows from the triangle inequality.

For each $j\in[m]$ with $|(u_{i})_{j}|\leq\tau$, we know that

where the first step follows from $(u_{\tau,i})_{j}=(u_{i})_{j}$ in this case.

Combining Eq. (C.2) and Eq. (31), we know for all $j\in[m]$

where the first step follows from taking the summation of square of Eq. (C.2), and the second step follows from simple algebra, the third step follows from Eq. (25), the fourth step follows from $u_{i}$ and $z_{i}$ are unit vectors, and the last step follows Part 3 of Fact A.3.

where the first step follows from triangle inequality, the second step follows from Eq. (C.2), and the third step follows from Eq. (26).

where the first step follows from Eq. (29), the second step follows from triangle inequality, the third step follows from Eq. (28), the fourth step follows from Eq. (C.2), and the last step follows from simple algebra.

where the first step follows from $\|\cdot\|\leq\|\cdot\|_{F}$, the second step follows from taking the summation of square of Eq. (C.2).

where the first step follows from Eq. (36) and the second step follows from $\|AB\|\leq\|A\|\cdot\|B\|$ (Fact A.1).

where the first step follows from triangle inequality, the second step follows from $\|u_{*,\bot}^{\top}\|_{2}\leq d$, the third step follows from the definition of $\|\cdot\|$, the fourth step follows from Eq. (C.2), and the last step follows from $k\geq 1$.

where the first step follows from Fact A.1, the second step follows from the fact that $U_{0}$ forms an orthonormal basis (see Part 2 of Fact A.2), the third step follows from the QR decomposition of $U_{\tau}$ (Eq. (36)), the fourth step follows from $\cos^{2}\theta+\sin^{2}\theta=1$ (see Lemma A.8), the fifth step follows from Eq. (C.2), and the last step follows from using the fact that $\epsilon<\frac{1}{100k}$.

where the first step follows from Eq. (C.2), the second step follows from Eq. (C.2), the third step follows from Eq. (C.2), the fourth step follows from simple algebra, and the last step follows from the fact that $\epsilon\leq\frac{1}{10^{4}k}$.

Proof of Part 2. The incoherence of $U_{0}$ is

where the first step follows from the definition of incoherence, the second step follows from Eq. (36), the third step follows from $\|AB\|\leq\|A\|\|B\|$, the fourth step follows from Eq (C.2), the fifth step follows from $U_{\tau}$ is truncating at $\tau$, the sixth step follows from $\tau=2\mu\sqrt{k}/\sqrt{n}$, and the last step follows from $n\geq m$. ∎

We provide the definitions for $U_{0}$, $U_{\tau}$, and $U_{\phi}$. We also include a procedure that clips rows with large norm then perform Gram-Schmidt.

Let $\tau:=\frac{2\mu\sqrt{k}}{\sqrt{n}}$.

To make convenient of base case of induction proof, we call $U_{\tau}$ to be $\widehat{U}_{0}$.

C.4 Initialization Condition: Main Result

We provide a Lemma which bounds $\operatorname{dist}(U_{0},U_{*})$ and shows that $U_{0}$ is incoherent with parameter $4\mu\sqrt{k}$.

Let $\Omega\subset[m]\times[n]$ and $p\in(0,1)$ be defined as Definition A.10.

$\operatorname{dist}(U_{0},U_{*})\leq\frac{1}{2}$ and

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

holds with probability at least $1-1/\operatorname{poly}(n)$.

From Lemma C.1, we see that $U_{0}$ satisfy that

Appendix D Main Induction Hypothesis

In this section, we provide our main induction hypothesis: we inductively bound $\operatorname{dist}(\widehat{V}_{t+1},V^{*}),\operatorname{dist}(\widehat{U}_{t+1},U^{*})$ and the incoherence of $U_{t+1},V_{t+1}$. We start by presenting our formal algorithm.

Let $M=U_{*}\Sigma_{*}V_{*}^{\top}$ be defined as Definition 3.5. Define $\epsilon_{d}:=1/10$. For all $t\in[T]$, we have the following results.

Part 1. If $U_{t}$ is $\mu_{2}$ incoherent and $\operatorname{dist}(\widehat{U}_{t},U_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{V}_{t},V_{*})\leq\epsilon_{d}$, then we have

$\operatorname{dist}(\widehat{V}_{t+1},V_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{U}_{t},U^{*})\leq\epsilon_{d}$

Part 2. If $U_{t}$ is $\mu_{2}$ incoherent and $\operatorname{dist}(\widehat{U}_{t},U_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{V}_{t},V_{*})\leq\epsilon_{d}$, then we have

Part 3. If $V_{t+1}$ is $\mu_{2}$ incoherent and $\operatorname{dist}(\widehat{V}_{t+1},V_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{U}_{t},U_{*})\leq\epsilon_{d}$, then we have

$\operatorname{dist}(\widehat{U}_{t+1},U_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{V}_{t+1},V_{*})\leq\epsilon_{d}$

Part 4. If $V_{t+1}$ is $\mu_{2}$ incoherent and $\operatorname{dist}(\widehat{V}_{t+1},V_{*})\leq\frac{1}{4}\operatorname{dist}(\widehat{U}_{t},U_{*})\leq\epsilon_{d}$, then we have

The above results hold with high probability.

Proof of Part 1. To prove this part, we need to use Lemma F.1, and Lemma F.3. To use Lemma F.1, we need the condition that $U_{t}$ is $\mu_{2}$ incoherent. To use Lemma F.3, we need two conditions: one is that $U_{t}$ be a $\mu_{2}$-incoherent and the other is $\operatorname{dist}(U_{t},U_{*})\leq 1/2$.

where the first step follows from the definition of distance (Definition 3.1), the second step follows from the definition of $V_{t+1}$ ($V_{t+1}=(V_{*}\Sigma_{*}U_{*}^{\top}U_{t}+F)\cdot R_{t+1}^{-1}$, see Definition E.6), the third step follows from simple algebra, the fourth step follows from $V_{*,\bot}^{\top}V_{*}=0$, the fifth step follows from Fact A.2, the sixth step follows from $\Sigma_{*}^{-1}\Sigma_{*}=I$, and the seventh step follows from $\|A\cdot B\|\leq\|A\|\cdot\|B\|$ (Fact A.1).

where the second step follows from Lemma F.1, the third step follows from Lemma F.3, the last step follows from Definition A.11.

Proof of Part 2. In this proof, we need to use Lemma F.3, Lemma F.4, Lemma F.5. To use Lemma F.3, we need the condition that $U_{t}$ is $\mu_{2}$ incoherent and the other is $\operatorname{dist}(U_{t},U_{*})\leq 1/2$. To use Lemma F.4, we need the condition that $U_{t}$ is $\mu_{2}$ incoherent. To use Lemma F.5, we need the condition that $U_{t}$ is $\mu_{2}$ incoherent.

For each $j\in[n]$, according to Definition E.6, we have

where it follows from Part 2 of Lemma F.3.

where the first step follows from $\|AB\|\leq\|A\|\cdot\|B\|$, the second step follows from $\|D_{j}\|\leq 1$, the third step follows from Lemma F.4, the fourth step follows from $\|A+B\|\leq\|A\|+\|B\|$, the fifth step follows from Lemma F.5 (for $\|C_{j}\|\leq 2$), and the last step follows from simple algebra.

Combining Eq. (41), Eq. (42), Eq. (43), and Eq. (D), we have

Proof of Part 3 and Part 4. By a symmetric argument, we can also prove

We are now ready to prove the main theorem of this paper (Theorem 4.2)

For the correctness part, it follows from combining the Init condition (Lemma C.6), perturbation lemma (Lemma G.5) Induction lemmas (Lemma D.1).

For the running time part, it follows from using Lemma B.7 for $2T$ times. For each iteration, we use twice, and there are $T$ iterations. ∎

Appendix E General Case Update Rules and Notations

In this section, we review various properties of rank-$k$ updates due to our algorithm. In Section E.1, we provide the formal definition of the updated rule. In Section E.2, we give the definition of the error matrix and analyze its properties. In Section E.3, we focus on providing the definition for the update rule for $V$.

To begin with, we formally define the updated rule as follows.

We note that the update rule does not directly reflect our algorithm. Nevertheless, we start by analyzing this QR-based update and later connecting it to our algorithm.

E.2 Error Matrix

Next, we provide several definitions related to error matrix $F$. For most of notations, we follow (Note that those definitions are implicitly presented at page 16 in ). Note that we use $U_{*},V_{*}$ to denote the optimal low rank factor instead of $U^{*},V^{*}$ to ease notations.

Let $B,D,C$ be diagonal block matrices (where each block has size $k\times k$).

Let $S$ be block rescaled identity matrix (where each block has size $n\times n$).

Without loss of generality, we can assume that $n/k$ is an integer. Then, $S$ can also be viewed as a diagonal block matrix with size $k\times k$.

where the first step follows from all matrices are diagonal block matrix, the second step follows from $S_{j}$ is an identiy matrix with resacling ($AI=IA$), and the third step follows from all matrices ar diagonal block matrix.

where the first step follows from the definition of $\|\cdot\|_{F}^{2}$ the second step follows from Claim E.4, the third step follows from that fact that $S$ is a diagonal matrix, the fourth step follows from $S_{n(i-1)+j,n(i-1)+j}=\sigma_{i}^{*}$, the fifth step follows from $(\sigma_{i}^{*})^{2}$ and $(\sigma_{i}^{*})^{-2}$ canceling out, and the last step follows from the definition of $\|\cdot\|_{2}^{2}$. ∎

E.3 Update Rule for V𝑉V

Appendix F Technical Lemmas for Distance Shrinkage

In this section, we prove a collection of technical lemmas that will facilitate us to eventually conclude our induction.

In Section F.1, we bound $\|F\Sigma_{*}^{-1}\|$ by distance. In Section F.2, we bound $\|(BD-C)v_{*}\|_{2}$ by distance. In Section F.3, we upper bound $\|\Sigma^{*}R_{t+1}^{-1}\|$. In Section F.4, we upper bound $\|B^{-1}\|$. In Section F.5, we upper bound $\|C_{j}\|$.

In this section, we upper bound $\|F\Sigma_{*}^{-1}\|$ by distance between $U_{t}$ and $U_{*}$. We generally follow the approach of .

Let $F$ be the error matrix defined by Definition E.6. Let $U_{t}$ be a $\mu_{2}$-incoherent matrix and $\operatorname{dist}(U_{t},U_{*})\leq 1/2$. Let $M$ be a $(\mu,k)$-incoherent matrix (see Definition 3.5). Let $\Omega\subset[m]\times[n]$ and $p\in(0,1)$ be defined as Definition A.10. Let $\delta_{2k}\in(0,0.1)$ be defined as Definition A.11.

holds with probability least $1-1/\operatorname{poly}(n)$.

where the first step follows from $\|\cdot\|\leq\|\cdot\|_{F}$ (Fact A.1), the second step follows from Claim E.5, the third step follows from $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$, the fourth step follows from Lemma F.4, and the fifth step follows from Lemma F.2. ∎

Now, we upper bound $\|(BD-C)v_{*}\|_{2}$. We follow similar ideas in literature .

holds with probability at least $1-1/\operatorname{poly}(n)$.

where the first step follows from $j$ being defined as the $j$-th row of matrices and the second step follows from the definition of $B_{j},C_{j},D$ (see Definition E.3).

Also, using Eq. (46), we have $\forall(p,q)\in[k]\times[k]$:

Hence, we get with probability at least $1-\frac{1}{n^{3}}$:

where the first step follows from $j$ being defined as the $j$-th row of matrices and the second step follows from Lemma A.13.

where the first step follows from Eq. (45), the second step follows from $\sum_{i}a_{i}b_{i}\leq\max_{i}a_{i}\sum_{i}b_{i}$, the third step follows from simple algebra, the fourth step follows from $u_{t}$ is $\mu_{2}$ incoherent, the fifth step follows from spectral norm definition, the last step follows from the definition of distance.

where the last step follows from $\sum_{p=1}^{k}\|x_{p}\|_{2}\leq\sqrt{k}\|x\|_{2}=\sqrt{k}$.

where the first step follows from Fact A.1 and the second step follows from Eq. (F.2). ∎

𝑡11\|\Sigma^{*}R_{t+1}^{-1}\| by Condition Number To bound $\|\Sigma^{*}R_{t+1}^{-1}\|$, we show that $\|\Sigma^{*}R_{t+1}^{-1}\|\leq 2\cdot\sigma_{1}^{*}/\sigma_{k}^{*}$. Similarly, we also bound $\frac{\sigma_{1}^{*}}{\sigma_{\min}(R_{t+1})}$ by showing $\frac{\sigma_{1}^{*}}{\sigma_{\min}(R_{t+1})}\leq 2\cdot\sigma_{1}^{*}/\sigma_{k}^{*}$.

Let $R_{t+1}$ be the lower-triangular matrix obtained by QR decomposition of $\widehat{V}_{t+1}$ (see Definition E.6). Let $U_{t}$ be a $\mu_{2}$-incoherent and $\operatorname{dist}(U_{t},U_{*})\leq 1/2$. Let $M$ be a $(\mu,k)$-incoherent matrix (see Definition 3.5). Let $\Omega$ be defined as Definition A.10. Let $\delta_{2k}\in(0,0.01)$ be defined as Definition A.11.

where the first step follows from $\Sigma_{*}^{-1}\Sigma_{*}=I$, the second step follows from $\|AB\|\leq\|A\|\cdot\|B\|$, and the third step follows from $\|\Sigma_{*}\|\leq\sigma_{1}^{*}$.

where the first step follows from Part 2 of Fact A.2 that $V$ is a matrix of SVD that has an orthonormal basis, the second step follows from definition of $\sigma_{\min}$, the third step follows from Fact A.1, the fourth step follows from $\sigma_{\min}(\Sigma_{*})=\sigma_{k}^{*}$, and the last step follows from $\cos^{2}\theta+\sin^{2}\theta=1$ (see Lemma A.8).

where the first step follows from the definition of $\sigma_{\min}$, the second step follows from Part 2 of Fact A.2, the third step follows from Definition E.6, the fourth step follows from triangle inequality, the fifth step follows from the definition of $\|\cdot\|$, the sixth step follows from Eq. (F.3), the seventh step follows from the definition of $\operatorname{dist}(U_{*},U_{t})$ (see Definition 3.1), and the last step follows from Lemma F.1.

For convenient, we define $x:=\operatorname{dist}(U_{t},U_{*})$.

We define $y:=2(\sigma_{1}^{*}/\sigma_{k}^{*})\delta_{2k}k$.

Then we now $x\in[0,1/2]$ and $y\in(0,0.1)$.

We analyze $\|B_{j}^{-1}\|$, for all $j\in[n]$, and $\|B^{-1}\|$ and show both of them are bounded by 2. We prove a variation of Lemma C.6 in .