Low Rank Matrix Completion via Robust Alternating Minimization in Nearly Linear Time
Authors: Yuzhou Gu
Zhao Song
Junze Yin
Lichen Zhang
Venue: ICLR 2024 poster (2024)
Keywords: matrix completion
Primary area: optimization
TL;DR: We provide a framework for matrix completion using fast alternating minimization that runs in nearly linear time in terms of verifying the solution

Abstract: Given a matrix $M\in \mathbb{R}^{m\times n}$, the low rank matrix completion problem asks us to find a rank-$k$ approximation of $M$ as $UV^\top$ for $U\in \mathbb{R}^{m\times k}$ and $V\in \mathbb{R}^{n\times k}$ by only observing a few entries specified by a set of entries $\Omega\subseteq [m]\times [n]$. In particular, we examine an approach that is widely used in practice --- the alternating minimization framework. Jain, Netrapalli and Sanghavi showed that if $M$ has incoherent rows and columns, then alternating minimization provably recovers the matrix $M$ by observing a nearly linear in $n$ number of entries. While the sample complexity has been subsequently improved, alternating minimization steps are required to be computed exactly. This hinders the development of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed approximately in favor of efficiency.

In this paper, we take a major step towards a more efficient and error-robust alternating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate a moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time $\widetilde O(|\Omega| k)$, which is nearly linear in the time to verify the solution while preserving the sample complexity. This improves upon all prior known alternating minimization approaches which require $\widetilde O(|\Omega| k^2)$ time.

Published as a conference paper at ICLR 2024
Low RANK MATRIX COMPLETION VIA ROBUST AL- TERNATING MINIMIZATION IN NEARLY LINEAR TIME
Yuzhou Gu
Zhao Song
Junze Yin
Institute of Advanced Study yuzhouguê a edu
Adobe Research
Boston University
z com
junze@bu. edu
Lichen Zhang
MIT CSAIL
1 lichenzecsail mit edu
ABSTRACT
Given matrix M E Rmx", the low rank matrix completion problem asks us to find rank-k approximation of as UVT for U E Rm and V E Bank by only observing a few entries specified by set of entries Ω C [m/] x [n]. In particular, we examine an approach that is widely used in practice - the alternating minimization framework. Jain, Netrapalli, and Sanghavi Jain et al. (2013) showed that if .M has incoherent rows and columns, then alternating minimization provably recovers the matrix MM by observing nearly linear in number of entries. While the sample complexity has been subsequently improved Gamarnik et al. (2017), alternating minimization steps are required be computed exactly. This hinders the develop- ment of more efficient algorithms and fails to depict the practical implementation of alternating minimization, where the updates are usually performed upproximately in favor of efficiency.
In this paper, we take a major step towards more efficient and error-robust alter- nating minimization framework. To this end, we develop an analytical framework for alternating minimization that can tolerate moderate amount of errors caused by approximate updates. Moreover, our algorithm runs in time Ö([S(()), which is nearly linear in the time to verify the solution while preserving the sample com- plexity. This improves upon all prior known alternating minimization approaches which require (( 2:2) time.
INTRODUCTION
Matrix completion is a well-studied problem both in theory and practice of computer science and machine learning. Given matrix M E Rmxx, the matrix completion problem asks recover the matrix by observing only a few (random) entries of M. This problem originally appears in the context of collaborative filtering Rennie & Srebro (2005) with the most notable example being the Netflix Challenge. Since then, it has found various applications in signal processing Linial al. (1994); So & Ye (2005) and traffic engineering Gürsun & Crovella (2012). In theory, one requires additional structural assumptions on the matrix M in order to obtain provable guarantees, with the most natural and practical assumption being the matrix M a rank-k low rank matrix. In tasks such as collaborative filtering, the matrix one faces is often low rank Candès & Recht (2012). Another popular assumption is the M has incoherent rows and columns. This intuitively eliminates the degenerate case where M only has few large entries, making it imperative to observe them. Matrices in practice are usually incoherent as well Avron et al. (2010); Mohri & Talwalkar (2011); Kumar et al. (2012).
Under these assumptions, a variety of algorithms based on convex relaxation have been derived Candès & Tao (2010); Recht (201 1); Candès & Recht (2012). These algorithms relax the problem 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

---

Published as a conference paper at ICLR 2024
require On))) time' to solve the program Jiang et al. (2020); Huang et al. (2022). Heuristics such as alternating minimization and gradient descent are much preferred due to their efficiency. Jain et al. (2013) first showed that under the standard low rank and incoherent settings, as long as allowed to observe Ö(*5nk4.5 log(1/e)) entries² (where K is the condition number of matrix M), then alternating minimization provably recovers the matrix M up to error in terms of Frobenius norm. Subsequent works further unify different approaches by treating matrix completion as a non-convex optimization problem Zhao et al. (2015) and improve the sample complexity Gamarnik et al. (2017). A remarkable advantage of alternating minimization its efficiency, as each iteration, the two alternating updates can be implemented in (( time.
Despite various advantages, the series of theoretical papers analyzing alternating minimization fail to capture 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 Jain et al. (2013) and followups Zhao et al. (2015); Gamarnik et al. (2017); Li et al. (2016) crucially relies 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 this paper, we take the first major step towards an error-robust analysis for alternating minimization. Specifically, we show that the alternating updates can be formulated as two multiple response regressions and fast, high accuracy solvers can be utilized to solve them in nearly linear time. Coupling our robust alternating minimization framework with our faster multiple response regression solver, we derive an algorithm that solves the matrix completion problem in time O k). We note that this runtime is nearly linear in terms of the time to verify the solution: Given matrices U E Rm and V E Ro*k it takes (k) time to verify a single entry and a total of O([ kk) time to verify all entries in Ω. To the best of our knowledge, this is the first algorithm based alternating minimization, that achieves a nearly linear time in verification. We remark that a recent work Kelner et al. (2023b) achieves a similar runtime behavior of (({2)k): their algorithm has an improved sample complexity of [S2] = ((nk2+((1) and runtime of (no)))) However, their algorithm heavily relies on the tools developed in Kelner et al. (2023a) and mainly serves as a proof-of proof-of-coneee oo-ccneept for matrix completion rather than efficient practical implementation." 4 In contrast, our algorithm adopts an off the shelf regression solver that is fast and high accuracy with good practical performances Avron al. (2010) 0); Meng al. (2014).
We state an informal version of our main result as follows:
Theorem 1.1 (Informal version of Theorem 4.2). Let M E RuXXn be a matrix that is rank-k, has incoherent rows and columns and entries can be sampled independently. Then, there exists randomzied algorithm that samples [S2] Ö(n poly(k)) entries, and with high probability, oulputs pair of matrices Ü IR m V Raak such that
IM - 10
and the algorithm runs in time [(())A).
Roadmap. 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. Section 4, we present the significant findings and discuss the techniques utilized. In Section 5, we provide some concluding remarks and future directions.
'w is the exponent of matrix multiplication. Currently, w 2 2.37 Duan et al. (2023).
II this paper. we assume 2 m and we use (-) to hide polylogarithmic factors in & and L/c. We note that in the context matrix completion. robustness is often used with respect to noise - i.e., we observe a noisy, higher rank matrix M = M + N. where M is the low rank ground truth and N is the higher rank noise matrix. In this paper, we focus on the setting where the ground truth is noiscless, and we use robust referring robustness against the errors caused by computing updates approximately.
'We note another work that also claims to obtain a runtime of Ö((2)k) Cherapanamjeri et al. (2017), but as pointed out in Kelner et al. (2023b) their runtime is only achievable if certain linear algehraic operations can be performed exactly in sublinear time, which is unknown this day.
2

---

Published as a conference paper at ICLR 2024
2
RELATED WORK
Low rank matrix completion is fundamental problem in machine learning. Practical applications including recommender systems, with the most notable one being collaborative filtering Rennie & Srebro (2005) and the Netflix Challenge Koren (2009); Koren et al. (2009). It also has wide range of applications in computer visions Candès & Recht (2012) and signal processing Linial et al. (1994); So & Ye (2005); Candès et al. (2011). For more comprehensive surveys, we refer readers to Johnson (1990); Nguyen et al. (2019). Algorithms for matrix completion can be roughly divided into two categories convex relaxation and non-convex heuristies. Candes and Recht Candès & Recht (2012) prove the first sample complexity for low rank matrix completion under convex relaxation and the bound subsequently improved by Candès & Tao (2010). In practice, heuristic methods based on non-convex optimizations often preferred due to their simplicity and efficiency. One notable approach is gradient descent Keshavan et al. (2009); Zhao et al. (2015). Alternating minimization also popular alternative that is widely applied in practice. Jain et al. (2013) provides provable guarantee on the convergence of alternating minimization when the and incoherent. Subsequently, there have been long line of works analyzing the performance of non-convex heuristics under standard matrix completion setting and under the noise or corrupted- entries setting Gunasekar et al. (2013); 3); Hardt (2014); Hardt et al. (2014); Hardt & Wootters (2014); Jain & Netrapalli (2015); Sun & Luo (2016); Gamarnik et al. (2017); Cherapanamjeri et al. (2017). Recently, the work Kelner et al. (2023b) provides an algorithm with improved sample complexity and runtime when stronger subspace regularity assumptions are imposed.
is low rank
In addition to the high accuracy randomized solver we utilize in this paper, sketching has a variety of applications in numerical linear algebra and machine learning, such as linear regression, low rank approximation Clarkson Woodruff (2013); Nelson & Nguyên (2013), matrix CUR decomposition Boutsidis & Woodruff (2014); Song et al. (2017: 2019c), weighted low rank approximation Razen- shteyn et al. (2016), entrywise l norm low-rank approximation Song et al. (2017; 2019b), general norm column subset selection Song et al. (2019a), tensor low-rank approximation Song al. (2019c), and tensor regression Diao et al. (2018; 2019); Reddy et al. (2022); Song et al. (2021).
A recent trend in the sketching community is to apply them as means to reduce the iteration cost of optimization algorithms. Applications such as linear programming Song & Yu (2021), empirical risk minimization Lee et al. (2019); Qin et al. (2023), approximating the John ellipsoid Cohen et al. (2019), Frank- Wolfe algorithm Xu et al. (2021) and linear MDPs Xu et al. (2023).
PRELIMINARY
In this section, we provide necessary background on matrix completion and assumptions.
Notations. We use [n] for a positive integer n to denote the set {1, 21. n). Given a vector x. use ||æ||| to denote its & norm. Given matrix A, use ||-A|| to denote its spectral norm and ||A|| to denote its Frobenious norm. Given a matrix A, we use A,, to denote its i-th row and A.,, denote its j-th column. We use ||Allo to denote the to semi-norm of A that measures the number of nonzero entries in A.
Given orthonormal basis A R A's orthogonal complement, such that AAT + AAAI=
A1 E (nn((n-)) to denote orthonormal basis to
Given rank-k, m real matrix A, use x(A) to denote its condition number: x(A) (.) where 01 (A)....,o (A) are singular values of A sorted in magnitude. When A is clear from context, we often directly.
(A(
3.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:
3

---

Published as a conference paper at ICLR 2024
Definition 3.1 (Distance between general matrices). Given matrices Ü,W W E R the (principal angle) distance between the subspaces spanned by the columns of U and W is given by:
dist(U, SR,,(,,,)) W) = [I = IIWTUl
where and W are orthonormal bases of the spaces span(U) and span(W) respectively. Simi- larly, U1 and 11 are any orthonormal bases of the orthogonal spaces span(U)* and span respectively.
One can further quantify the geometry of two subspaces by their principal angles:
Definition 3.2. Let U Bank and V E Rank
For any matrix U, for orthogonal matrix V (V Ig] we define
tan (V. == IVIU((TU)>'I
For orthogonal matrices V and U (V I and U -gh. we define
co, U) == min (V
cos (V. /1)/((/TT))/))) and cos ((V s
sin (V = [[ VVT)ull
- sin (VV = (0,,,)_l[Viii]] VTUI = ||VUU| and sin (V, 1
Standard trigonometry equalities and inequalities hold for above definitions, see, e.g. Zhu Knyazev (2013).
3.2 BACKGROUND ON MATRIX COMPLETION
We introduce necessary definitions and assumptions for low rank matrix completion. Given a set of indices Ω2 we define linear operator that selects the corresponding entries:
Definition 3.3. Let S E mR denote a matrix. Let Ω C [m]] x [n]. We define operator Pa as follows:
Pa(S) = [Sigh if (1,))) 10, otherwise.
A crucial assumption for low rank matrix completion is incoherence. We start by defining the notion below.
Definition 3.4. For orthonormal basis U RRix we say U is p-incoherent, if
Vk
|lu
S
μ.
m
Here u, is the i-th row of U, for all i e [m].
We say a general rank-k matrix incoherent if both its row and column spans are incoherent: Definition 3.5 (1,, kt) incooherentt.. A rank-k matrix M Rmxx is (j,, iincoheetttt if:
|uell2 < yk Vi E [m]
. 11yll22 <
V
J4, Vj
[m]
where T is the SVD of M and us Uj denote the i-th row of U and the j-th row of V respectively.
We now in the position state the set of assumptions for low rank matrix completion problem.
4

---

Published as a conference paper at ICLR 2024
Assumption 3.6. Let M R= and we assume M satisfies the following property:
M is a rank-k matrix;
M is (u, (u,k))-nnooil iiccoheeen:;
Each entry of M is sampled independently with equal probability. other words, the set
Ω S [m]] x [n]] is formed by sampling each entry independently according to certain distribution.
note that the above assumptions are standard in the literature.
Now we are ready to state the low rank matrix completion problem.
Problem 3.7. Let M IR Assumption 3.6. The low rank matrix completion problem asks to find a pair of matrices E Rink and V E Tg such that
|M UV Uv
TECHNIQUE OVERVIEW
Before diving into the details of our algorithm and analysis, let us review the alternating minimization proposed in Jain et al. (2013). The algorithm can be described pretty succinctly: given the sampled indices Ω the algorithm starts by partitioning 52 into 2T + 1 groups, denoted by Sn ........ .,, 2ty. The algorithm first computes top-k SVD of the matrix p Pa, (M) where p is the sampling probability. It then proceeds to trim all rows of the left singular matrix U with large often referred to as clipping). It then optimizes the factors and V alternatively. At iteration t, the algorithm first fixes U and solves for V with multiple response regression using entries in 8 then it fixes the newly obtained V and solves for U with entries in 4T After iterating over all groups in the partition, the algorithm outputs the final factors U and V as its output. Here, we use independent samples across different iterations to ensure that each iteration is independent of priors (in terms of randomness used). If one would like drop the uniform and independent samples across iterations (see, e.g., Liu et al. (2017)), the convergence has only been shown under additional assumptions and in terms of critical points to certain non-convex program.
norms (this step is
From a runtime complexity perspective, the most expensive steps are solving two multiple response regressions per iteration, which would take a total ( A2) time. On the other hand, if the sum of the size of all the regressions across 7 iterations is only O k)) inspiring us to consider efficient, randomized solvers that can solve the regression time nearly linear in the instance size. $ This in turn produces algorithm with nearly linear runtime in terms of verifying all entries in Ω.
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 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 Jain al. (2013) algorithm should tolerate moderate amount of errors, the analysis becomes highly nontrivial when one examines the argument in Jain et al. (2013) and followups, as all of them crucially rely 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 solutions for each iteration.
Our argument is inductive in nature. Let M = T be optimal rank-k factors, we build up induction by assuming the approximate regression solutions Ú,-1; Vi-1 close U* V and proving for Ü., Vz. The loss of structure due to solving the regressions approximately forces us to find alternatives to bound the closeness, as the argument of Jain et al. (2013) relies on the exact formulation of the closed-form solution. Our strategy is instead consider a sequence of imaginary, exact solutions to the multiple response regressions and prove that our approximate
'We note that our solver would incur extra total cost of Ō(nk"). Under the standard low rank and incoherent assumptions, the state-of-the-art non-convex optimization based approach Kelner al. (2023b) would require ((n&2+o(1) samples and the ((kk3) time is subsumed by the O([S)k)) portion. This term is hence ignored.
5

---

Published as a conference paper at ICLR 2024
solutions are close to those exact solutions. In particular, show that if U2 V2 are close to their exact counterpart in the le row norn sense, then it suffices to prove additional structural conditions on U2 and V2 to progress the induction. Specifically, we show that as long as - is incoherent and dist(U,-1, U* I 3 dist V*), we will have dist(V, V*) I dist(U,-1, UT) and the exacr solution at time t, Vi is incoherent. We can then progress the induction by using the small distance between 1 and V* in conjunction with the incoherence of Vi advance on dist(U,, U*) and the incoherence of Uz. As the gap decreases geometrically, this leads to an overall log(1/e) iterations to converge, as desired.
4
remains to develop a perturbation theory for alternating minimization and our key innovation is perturbation argument the incoherence bound under small row norm perturbation. Let A, denote the i-th row of A. We show that if two matrices A and B satisfying (I(A - B):ll2 S e and S Amin ( (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 Spielman & Srivastava (2011). The problem then reduces 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 Wedin (1973), we prove that it 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 x) is bounded by x(A). To obtain a good bound on x(B), we need to solve the approximate regression to high precision (inverse polynomial proportionally to x(A)), We achieve this objective through a sketching- based preconditioner, which is the first problem we would like to address.
Sketching- baaedd 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 (log(1/c) convergence for an c-approximate solution. Beyond its theoretical soundness and efficiency, these preconditioners also exhibit good performances when used in practice Avron et al. (2010); Meng et al. (2014).
An important feature of our robust alternating minimization framework coupled with the fast regression solvers is that we preserve the sample complexity of Jain et al. (2013): by pick- ing the sampling probability p O(K²p² g45 log n log(1/e)/m), we are required to sample [0]] = =O log n log(1/))) entries. By a clever thresholding approach, Gamarnik et al. (2017) further improves the sample complexity to O(x² p(*2 log(l/e)). As their algorithm is alter- nating minimization in nature, our robust framework and nearly linear time regression solvers can be adapted and hence obtain improved sample complexity and runtime by factor of 2 log n).
In the rest of this section, we will review our approaches and clarify how we employ various strategies to achieve our goal.
4.1 SUBSPACE APPROACHING ARGUMENT
The basis of the analysis of both Jain et al. (2013) and ours is an inductive argument that shows the low rank factors obtained in each iteration approach 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 Jain et al. (2013) can be based on the exact solutions solely - they inductively prove the distances shrink by a constant factor, and the low rank factors are juz-incoeerent for #22 to be specified. It is tempting to replace these exact solutions with the approximate solutions we obtain. Unfortunately, the Jain et al. (2013) heavily exploits the closed-form formulation of the solutions so that they easily decompose the matrices into terms whose spectral norms can be bounded in a straightforward manner. Our approximate solutions the other hand cannot be factored in such fashion.

---

Published as a conference paper at ICLR 2024
Algorithm Alternating minimization for matrix completion. The INIT procedure clips the rows with large norms, then performs a Gram-Schmidt process.
1: procedure FASTMATRIXCOMPLLTTONC c [m/] x [n], Pa(M) Partition ! into 27 + subsets Ro, Ω2r
D Theorem 4.2
2:
3:
b Each element of Ω belonging to one of the Q with equal probability (sampling with
replacement)
4: Us = SVD P.zo (M)
5:
Co + INIT(U
> Algorithm 4
6:
for t
do Obtain V4 with Lemma 4.1 by solving g P (0,VT -M)
7:
8:
Obtain U.41 with Lemma 4.1 by solving minggemxx [ (UT end for
1-1 M)
9:
10: return V.
11: end procedure
To circumvent this issue, we instead keep the exact solutions U., Vi as a sequence of references and inductively bound the incoherence of these exact solutions. More specifically, for any [T], assume Ug is pz-incoherent and düst(U,, U*) S dist(V, (Ve, V*) = 1/10, then we show that
* dist(Ve+1, V*) < dist U*) < 1/10 and
V441 is pp-inncherenn..
We can then proceed to show similar conditions hold for Ü:41 and UL+1, therefore advance the induction. At the first glance, our induction conditions seem rather far-off from what we want in order to prove Vi+1 and V* are close, one would need to show V2+1 has small incoherence. We alternatively adapt a perturbation argument on incoherence, specifically, note that V++1 can be treated as blending in small perturbation to V(+1 in terms of row & norms, if we can manage prove under such perturbations, the incoherence of V.+1 is still close to the incoherence of V 1, then our induction condition on the incoherence of V effectively translates to the incoherence V4+1- In next section, illustrate how develop such a perturbation theory.
4.2
A PERTURBATION THEORY FOR MATRIX INCOHERENCE
Our main goal is to understand how perturbations to rows of matrix change the incoherence, Let us consider two matrices A, B m that are close in the spectral norm: || A BB| S eo for some small етrоr Eg. as the closeness in spectral norm implies all row norms of the difference matrix A B are small. Our next step will be putting the rows of and B to isotropic position', by mapping ag ++ (AT A) A)-1/2a, and + (BT B) -1/2b, The main motivation the equivalence between matrix incoherence and statistical leverage score Spielman & Srivastava (2011), 1), which measures the l2 importance of rows by putting the matrix into isotropic position. This provides us with an alternative way to measure the matrix incoherence directly instead of working with the singular value decomposition. It remains to bound the difference (A A) ( -
[I( -) ll2/, without loss of generality, assume [[(AT -)-1/2a, a/2a,112 2 [IBB' B) 10-1//bx//2.. then we can equivalently express it using difference of squares formula:
AA A)-1/2a,112 - () = [1 -)
[T B)
[[A A)2a,,,
1/2a,112 BB -)
where the numerator is the difference between leverage scores, and we utilize tools that bound perturbation pseudo-inverses Wedin (1973) to provide an upper bound. For the denominator, we can derive lower bound rather straightforwardly.
Combining these bounds, we conclude that
[II(A 1) 1/2 1/22, - [I( B) 11/2b,1 < O(o (ol)()(A))).
We say collection of vectors (01.-.., Un C B are in isatropic position if 5 Vana Jt-

---

Published as a conference paper at ICLR 2024
To put this bound into perspective, we will set A to be the exact update matrix U and B to be the approximate update matrix U. In our induction framework, number of U is well-controlled, therefore we can safely suffer error up to poly(n(U)), as we can set our final precision
further make sure that the condition
be inverse polynomially in x(U)). Since our algorithm converges in log( (o/e))) iterations, and our regression solver has an enror dependence log(1/c), this only blows up the runtime by a factor of log(x/c), c), as desired.
4.3 NEARLY LINEAR TIME SOLVE VIA SKETCHING
Now that we have a framework that tolerates errors caused by approximate solves, we are ready to deploy regression solvers that can actually compute the factors in nearly linear time. A popular and standard approach is through the so-called sketch-and-solve paradigm - given an overconstrained regression problem min, ||-Az- bll2 with A E Rn*k and > k, one samples random sketching matrix 5 E Rm with m < n and instead solves the sketched regression ||SAx Sb112- As the new regression problem has much fewer row count, solving it would take nearly linear time long as S'A can be quickly applied. In addition to its simplicity, efficiency and good error guarantees, if one picks S to be a dense subsampled randomized Hadamard transform (SRHT) Lu et al. (2013), then the regression solution is also close to the exact solution in an ex sense Price et al. (2017). While appealing, sketch-and and-solve has the deficiency of low accuracy if one wants solution with regression cost at most (1 + <) times the optimal cost, then the algorithm would take time proportional to 6- As we would set the 6 to be polynomially small to incorporate the error blowups due to perturbations to incoherence and the error conversion from regression cost to solution, an inverse polynomial dependence on e would significantly slow down the algorithm and ultimately lead to an even slower runtime than solving the regressions exactly.
We resort to a sketching -baed approach that enjoys high accuracy as the algorithm converges in log(1 /e) iterations and each iteration can be implemented in Onk + 1-3) time. The idea is to pick sketching matrix that produces a subspace embedding of ([L)-distottion" and compute a QR decomposition of matrix SA = QR- The matrix R is then used as preconditioner and we solve the preconditioned regression min,- ||ARx - 6|l2 via gradient descent.
Even though the solver runs in nearly linear time in the instance size, we still need to make sure that the sparsity of Ω is utilized, as |S] < mn. To demonstrate how to achieve runtime of ((())))) instead of Ömmnk), let us consider the following multiple response regression: miny e | M]LF. Our strategy is to solve n least-square regression. Consider the i-th regression problem: Pa note that v only contributes to the i-th column of UV which correlates to the i-th column of the operator Pq. therefore we only need to solve a regression with the rows of U selected by the i-th column of Pn. Let K,, be the corresponding set of nonzero indices, we select the rows of U which is of size UK,, RlK[I* and the resulting regression is min,eR* [|Ux,,* Mx,,ill2- Sum over all T iterations, the total size of the multiple response regression is O (G]Ak) ((I and regression solver takes Ö( + nk*) (((())) time, as desired.
min. (UUv))
We summarize the result in the following lemma.
Lemma 4.1. Let Ω S [m] [n]. M Rm and U Ba Let c,8 8 10,1) be precision and failure probability, respectively. There exists an algorithm that takes
O log n + nk3 log2 (n/8)) loo(n/c))
time output a matrix V such that IIÀ V*Il I where V arg minve [|Pa(UVT) (l(M)]]r. r. The algorithm succeeds with probability at least 1 - 5.
4.4 PUTTING THINGS TOGETHER
Given our fast regression solver and robust analytical framework that effectively handles the perturba- tion error caused by approximate solve, we are in the position to deliver our main result.
We say a matrix S produces a subspace embedding of e-distotionn if for any fixed orthonormal basis U Roxk the singular values of SU lie in [1 e, + +c] with high probability.
8

---

Published as a conference paper at ICLR 2024
Theorem 4.2 (Main result, formal version of Theorem 1.1). Let M R be matrix satisfying Assumption 3.6. Let operator Pa be defined as in Definition 3.3. Then, there exists a randomized algorithm (Algorithm 1) with the following properties:
It samples [ Ox122122 log (l))) entries;
It runs in (((k time.
The algorithu outputs pair of matrices Ü E 12mx and V E guxk such that
| 1M-UV- 10-00 se
holds with high probability.
Let us pause and make some remarks regarding the above result. On the sample complexity front, we attain the result achieved in Jain et al. (2013), but we would also like to point out that it can be further improved using the approach developed in Gamarnik al. (2017). Our robust alternating minimization framework indicates that as long as the eтror caused by the approximate solver can be polynomially bounded, then the convergence of the algorithm preserved (up to log(1/e /e) factors). Thus, our framework can be safely integrated into any alternating minimization-basel algorithm for matrix completion.
Comparison with Kelner et al. (2023b). The runtime of our algorithm is nearly linear in the verification time given a set of observed entries Q it takes O(k) time to verify an entry of PR(ŪVT)) hence requires total of O(([k) time. Kelner al. (2023b) achieves a similar runtime behavior with an improved sample complexity of [S2] ((n)2+o(1)) It worth noting that most popular practical algorithms for matrix completion are based on either alternating minimization or gradient descent, since they are easy to implement and certain steps can be sped up via fast solvers. In contrary, the machinery of Kelner et al. (2023b) is much more complicated. In short, they need to decompose the update into a "short" progress matrix and a "flat" noise component whose singular values relatively close to each other. To achieve this goal, their algorithm requires complicated primitives, such as approximating singular values and spectral norms Musco & Musco (2015), Nesterov's accelerated gradient descent Nesterov (1983) (which is known to be hard to realize for practical applications) and a complicated post-process procedure. While it is totally possible that these subroutines can be made practically efficient, empirical studies seem to be necessary to justify its practical performance. In contrast, our algorithm could be interpreted as providing a theoretical foundation on why fast alternating minimization works so well in practice. As most of the fast alternating minimization implementations rely on quick, approximate solvers (for instance, Lai Varghese (2017); Liu et al. (2020)) but most of their analyses assume every step the algorithm is computed exactly. From this perspective, one can view our robust analytical framework as "completing the picture" for all these variants alternating minimization. Moreover, one can further sharpen the dependence on k and condition number in the sample complexity for alternating minimization, matching that of Kelner et al. (2023b), we automatically obtain an algorithm with the same (asymptotic) complexity of their algorithm. We leave improving the sample complexity of alternating minimization as a future direction.
5 CONCLUSION
In this paper, we develop a nearly linear time algorithm for low rank matrix completion via two ingredients: sketching-basee 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 preferred. Our algorithm also has the feature that it runs in time nearly linear in verifying the solution, as given a set of entries Q it takes ({ time to compute the corresponding entries.
9

---

Published as a conference paper at ICLR 2024
ACKNOWLEDGEMENT
We would like to thank Jonathan Kelner for helpful discussions and pointing out many references, as well as comments from anonymous reviewers that significantly improve the presentation of this paper. Yuzhou Gu is supported by the National Science Foundation under Grant No. DMS-1926686. Lichen Zhang supported by NSF CCF-1955217 and NSF DMS-202244
REFERENCES
Haim Avron, Petar Maymounkov, and Sivan Toledo. Blendenpik: Supercharging lapack's 's least- squares solver. SIAM J. Sci. Comput., 2010.
Christos Boutsidis and David P Woodruff. Optimal cur matrix decompositions. In Proceedings of the sorty-sixth annual ACM symposium on Theory of computing (STOC), pp. 353-362, 2014.
Emmanuel Candès and Benjamin Recht, Exact matrix completion via convex optimization. Commum. ACM, 2012.
Emmanuel J. Candès and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Trans. Inf. Theor, 2010.
Emmanuel J. Candès, Xiaodong Li, Yi Ma, and John Wright. Robust principal component analysis? ACM, 2011.
Yeshwanth Cherapanamjeri, Kartik Gupta, and Prateek Jain. Nearly optimal robust matrix completion. In Proceedings of the 34th International Conference Machine Learning Volume 70, ICML' pp. 797-805, 2017.
Kenneth L Clarkson and David Woodruff. Low-rank approximation and regression in input sparsity time. In STOC, 2013.
Michael B Cohen, Ben Cousins, Yin Tat Lee, and Xin Yang. A near-optimal algorithm for approxi- mating the john ellipsoid. In Conference on Learning Theory, pp. -49-873. PMLR, 2019.
Huaian Diao, Zhao Song, Wen Sun, and David Woodruff. Sketching for kronecker product regression and p-splines. In International Conference on Artificial Intelligence and Statistics, pp. 1299-1308.
PMLR, 2018.
Huaian Diao. Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems, 32, 2019.
Ran Duan, Hongxun Wu, and Renfei Zhou. Faster matrix multiplication via asymmetric hashing. In FOCS, 2023.
David Gamarnik, Quan Li, and Hongyi Zhang. Matrix completion from ((n) samples in linear time. In Satyen Kale and Ohad Shamir (eds.), Proceedings of the 2017 Conference on Learning Theory, volume 65 of Proceedings of Machine Learning Research, pp. 940-947. PMLR, 07-10 Jul 2017.
Suriya Gunasekar, Ayan Acharya, Neeraj Gaur, and Joydeep Ghosh. Noisy matrix completion using alternating minimization. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2013, Prague, Czech Republic, September 23-27, 2013, Proceedings, Pari I1 13, pp. 194-209. Springer, 2013.
Gonca Gürsuun and Mark Crovella. On traffic matrix completion in the internet. In Proceedings of the 2012 Internet Measurement Conference, IMC '1, pp. 412, New York, NY, USA, 2012. Association for Computing Machinery.
Moritz Hardt. Understanding alternating minimization for matrix completion. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 651-660. IEEE, 2014.
Moritz Hardt and Mary Wootters. Fast matrix completion without the condition number. In Conference learning theory, pp. 638-677 PMLR, 2014.
10

---

Published as a conference paper at ICLR 2024
Moritz Hardt, Raghu Meka, Prasad Raghavendra, and Benjamin Weitz. Computational limits for matrix completion. In Conference on Learning Theory, pp. 703-725. PMLR, 2014.
Baihe Huang, Shunhua Jiang. Zhao Song, Runzhou Tao, and Ruizhe Zhang. Solving sdp faster: A robust ipm framework and efficient implementation. In FOCS, 2022.
Prateck Jain and Pranceth Netrapalli. Fast exact matrix completion with finite samples. In Peter Grünwald, Elad Hazan, and Satyen Kale (eds.), Proceedings of The 28th Conference on Learning Theory, volume 40 of Proceedings of Machine Learning Research, pp. 1007-1034, Paris, France, 03-06 Jul 2015. PMLR.
Prateek Jain, Pranecth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating minimization. In Proceedings of the forty-fifth anmual ACM symposium Theory of computing, pp. 665-674, 2013.
Haotian Jiang, Tarun Kathuria, Yin Tat Lee, Swati Padmanabhan, and Zhao Song. A faster interior point method for semidefinite programming. In FOCS, 2020.
Charles R Johnson. Matrix completion problems: survey. In Matrix theory and applications, volume 40, pp. 171-198, 1990.
Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Semi-random sparse recovery in nearly linear time. In Conference Learming Theory, COLT'23, 2023a.
Jonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford. and Kevin Tian. Matrix completion in almost- verification time. In 2023 IEEE 64th Anmual Symposium on Foundations of Computer Science, FOCS'23, 23, 2023b.
Raghunandan H. Keshavan, Sewoong Oh, and Andrea Montanari. Matrix completion from a few entries. In 2009 IEEE International Symposium on Information Theory, 2009.
Ychuda Koren. The bellkor solution to the netflix grand prize. Netflix prize documentation, 81(2009): 1-10, 2009.
Ychuda Koren, Robert Bell, and Chris Volinsky. Matrix factorization techniques for recommender systems. Computer, 42(8):30-37, 2009.
Sanjiv Kumar, Mehryar Mohri, and Ameet Talwalkar. Sampling methods for the nystrom method. Journal of Machine Learning Research, 2012.
Ming Jun Lai and Abraham Varghese. On convergence of the alternating projection method for matrix completion and sparse recovery problems, 2017.
Yin Tat Lee, Zhao Song, and Qiuyi Zhang. Solving empirical risk minimization the current matrix multiplication time. In Conference on Learning Theory, pp. 2140-2157 PMLR, 2019.
Yuanzhi Li, Yingyu Liang, and Andrej Risteski. Recovery guarantee of weighted low-rank approx- imation via alternating minimization. In International Conference on Machine Learning, pp. 2358-2367. PMLR, 2016.
N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. In Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994.
Guangcan Liu, Qingshan Liu, and Xiaotong Yuan. A new theory for matrix completion. In Guyon, U. Von Luxburg, S. Bengio. H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
Yajing Liu, April Sagan, Andrey Bernstein, Rui Yang. Xinyang Zhou, and Yingchen Zhang. Matrix completion using alternating minimization for distribution system state estimation. In 2020 IEEE International Conference on Communications, Control, and Computing Technologies for Smart Grids (SmanGrriCommmm, 2020.
Yichao Lu, Paramveer Dhillon, Dean P Foster, and Lyle Ungar. Faster ridge regression via the subsampled randomized hadamard transform. In Advances in neural information processing systems (NIPS), pp. 369-377, 2013.
11

---

Published as a conference paper at ICLR 2024
Lingsheng Meng and Bing Zheng. The optimal perturbation bounds of the moore penrose inverse under the frobenius nomn. Linear algebra and its applications, 432(():956- 963,,996,3 2010.
Xiangrui Meng, Michael A. Saunders, and Michael W. Mahoney. Lsmn: A parallel iterative solver for strongly over- or underdetermined systems. SIAM Journal on Scientific Computing, 36(2): C95-C118 18, 2014.
Mehryar Mohri and Ameet Talwalkar. Can matrix coherence be efficiently and accurately estimated? In Proceedings of the Fourteenth International Conference on Artificial Intelligence and Statistics, Proceedings of Machine Learning Research, 2011.
Cameron Musco and Christopher Musco. Randomized block krylov methods for stronger and faster approximate singular value decomposition. In Advances in Neural Information Processing Systems, volume 2015 5-Janurry, pp. 1396-1404, 2015.
Jelani Nelson and Huy L Nguyên. Osnap: Faster numerical linear algebra algorithms via sparser subspace embeddings. In 2013 ieee 54th annual symposium on foundations of computer science, pp. 117-126. IEEE, 2013.
Yu Nesterov. method for solving the convex programming problem with convergence rate ( ((z In Dokl. akad. nauk Sssr, volume 269, pp. 543-547, 1983.
Luong Trung Nguyen, Junhan Kim, and Byonghyo Shim. Low-rank matrix completion: contempo- rary survey, IEEE Access, 7:94215-94233 2019.
Eric Price, Zhao Song, and David P Woodruff. Fast regression with an foo guarantee. ICALP, 2017.
Lianke Qin, Zhao Song, Lichen Zhang, and Danyang Zhuo An online and unified algorithm for projection matrix vector multiplication with application to empirical risk minimization. In AISTATS, 2023.
Ilya Razenshteyn, Zhao Song, and David P Woodruff. Weighted low rank approximations with provable guarantees. In Proceedings of the forty-eighth anmual ACM symposium on Theory of Computing, pp. 250-263, 2016.
Benjamin Recht. A simpler approach to matrix completion. J. Mach. Learn. Res., 12:3413-3430, dec 2011.
Aravind Reddy, Zhao Song, and Lichen Zhang. Dynamic tensor product regression. In NeurIPS, 2022.
Jasson D. M. Rennie and Nathan Srebro. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference on Machine Learning. ICML '05, pp. 713-719, New York, NY, USA, 2005. Association for Computing Machinery.
Anthony Man-Cho So and Yinyu Ye. Theory of semidefinite programming for sensor network local- ization. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium Discrete Algorithms, SODA '05, pp. 405-414, USA, 2005. Society for Industrial and Applied Mathematics.
Zhao Song and Zheng Yu. Oblivious sketching-based based central path method for linear programming. In International Conference on Machine Learning, pp. 9835-9847. PMLR, 2021.
Zhao Song, David P Woodruff, and Peilin Zhong. Low rank approximation with entrywise 11-norm error. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 688-701, 2017.
Zhao Song, David Woodruff, and Peilin Zhong. Towards a zero-one law for column subset selection. Advances in Neural Information Processing Systems, 32, 2019a.
Zhao Song, David Woodruff, and Peilin Zhong. Average case column subset selection for entrywise L -oorm loss. Advances in Neural Information Processing Systems, 32, 2019b.
12

---

Published as a conference paper at ICLR 2024
Zhao Song, David P Woodruff, and Peilin Zhong. Relative enror tensor low rank approximation. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp- 2772-2789. SIAM, 2019c.
Zhao Song, David Woodruff, Zheng Yu, and Lichen Zhang. Fast sketching of polynomial kernels of polynomial degree. In International Conference on Machine Learning, pp. 9812-9823. PMLR, 2021.
Daniel Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal Computing, 40(6):1913-1926 2011.
Ruoyu Sun and Zhi- Zhi-Quan Luo. Guaranteed matrix completion via non-convex factorization. IEEE 6579, 2016.
Transactions on Information Theory,
Joel A. Tropp. Improved analysis of the subsampled randomized hadamard transform. Adv. Data Sci. Adapt. Anal., 2011.
Per-Åke Wedin. Perturbation theory for pseudo-inverses. BIT Numerical Mathematics, 13(2): 217-232, 1973.
H. Weyl. Das asymptotische verteilungsgesetz der eigenwerte linearer partieller differentialgleichhn- gen (mit einer anwendung auf die theorie der hohlraumstrablung) Mathematische Annalen, 71: 441-479, 1912.
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava. Breaking the linear iteration cost barrier for some well-known conditional gradient methods using maxip data-structures. Advances in Neural Information Processing Systems, 34:5576-5589 2021.
Zhaozhuo Xu, Zhao Song, and Anshumali Shrivastava. A tale of two efficient value iteration algorithms for solving linear mdps with large action space. In AISTATS, 2023.
Tuo Zhao, Zhaoran Wang, and Han Liu. nonconvex optimization framework for low rank matrix estimation. C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Peizhen Zhu and Andrew Knyazev. Angles between subspaces and their tangents. Journal of Numerical Mathematics, 21(4)3325-340, 2013.
13

---

Published as a conference paper at ICLR 2024
APPENDIX
Roadmap. Section A, we introduce more fundamental lemmas and facts. In Section B, we provide more details about sketching-basse solver. In Section C, 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, analyze the distance and incoherence under row perturbations.
A MORE PRELIMINARY
In this section, we display more fundamental concepts. In Section A. 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.
A. BASIC MATRIX ALGEBRA
We state several standard norm inequalities here.
Fact A.1 (Norm inequalities). For any matrix A, B
Part ||AB|| I ||||| BI]-
Part 2. ||A||] 2 ||||| 0min (B)
3. ||A+ B|| < ||||| ||||
Part 4. BT A 0, ||A+ + B|| 2 ||||
For any matrix A and vector æ
Part 5. ||Ax||2 < |||||| ||a|||2
Part 6. ||||| |
Part 7. ||||E & A|| if A is rank-k.
For any square matrix A
Part 8. If A is invertible, we have ||A|| 1/ouinnAA 1A
Part 9, For vector with ||]|| 1, we have ||Ax|12 = maxx:1lvla==1 v" Ax.
For any matrix A, square invertible matrix
Part 10. ||A|| & mmax(B) ||AB-''! [
For any matrix A, and square diagonal invertible matrix B
Part 11. Jmin (BA) 2 Omin(() -min (A).
We omit their proofs, they quite standard. We also state Weyl's inequality for singular values: Lemma A.2 (Weyl (1912)). Let A, B E Baxk where n 2 k, then we have for any i E [k).
(o,(A) - (B) < A A Bl}. Bl].
The next fact bounds the spectral norm of matrix after applying a unitary transformation.
Fact A.3. Let m 2 Let U Rmnk denote matrix that has an orthonormal basis.
Part For any matrix A E Rmxx we have
I A S |||]-
14

---

Published as a conference paper at ICLR 2024
Part 2. For any matrix B e Rexd we have
[UB] = |B||
Proof. Part 1. By the property of U, we know that UUT Im.
Thus, for any vector we have
xT A UU Ax S IxTAT A Ar.
Thus, - All & ||
Part By property of U, we have U = lt.
Thus, for any vector we have
BB TB BB. Br.
Thus, ||BB]| |BB].
The following is a collection of simple algebraic facts.
Fact A.4. Let y E (0, 0.1). We have
yz 1/2. Part If (0,1/2). then v1 -1-1" x2
Part 2. If 1/2, then yv1 - 12 222 1
v1 - x2 x² 3. If [0, 1). then
Proof. Proof of Part 1. We have
V1 x²
v1 x²
4x 2
T
5
1
1
2
5
2'
where the first step follows from y E (0, 0.1.. the second step follows from v1 -1-28 x² 21- f for
all E [0, 4/3], and the last step follows from I $ 1/2.
Proof of Part 2. We know that
v - x² 5 0.1 x/2,
(1)
and where the first step follows from 0 < v1 - x² < 1, the second step follows from (0, and the last step follows from æ 2 1/2.
Thus.
x² 2 x 2/2 x - y
x x//2,
where the first step follows from Eq. (1) and the second step follows from simple algebra.
Proof of Part 3. We know that
- x² S V1 - x2
for all x in the domain of VT- xZ
Then, the statement true.
15

---

Published as a conference paper at ICLR 2024
A.2 PROPERTIES OF ANGLES AND DISTANCES
We explore some more relations for angles and distances between subspaces.
Let U,V RRa* be two matrices with orthonormal columns, dVst,.(V denote the following minimization problem:
(Vst.(VUU)) = min IVQ - U|,
QEO,
where O₂ Rxo is the set of k orthogonal matrices.
The next lemma is simple application of fundamental subspace decomposition.
Lemma A.5. Let A E B2 be an orthonormal basis, then there exists a matrix A1 E (n-(n with AA
A A
In.
Proof. We know that the column space of orthogonal to the null space of A and the null space of A has dimension k.
Let _1 be an orthonormal basis of the null space of AT.
We have
A A1 0.
remains to show that
AA + AAAA = In.
Let E RR be any vector.
We know that z either in the column space of or the null space of AT. Case 1: in the column space of A. In this case, write Ay. Then,
AA ALAI= = AAT Ay + A_ A_AJAg Ay
Ay + ALAT Ay
Ay A1 A -Ay+0
2,
where the first step follows from z Ay. the second step follows from A is orthogonal that AT A-1, the third step follows from (AB) BB AT for all matrices A and B, the fourth step follows from Eq. (2), and the last step follows from z = Ay.
Case 2: in the null space of A In this case, we know that A and A
AAT = A, A 0 A 4 A1y
Aiy 2,
where the first step follows from AT = 0 and z = ALW. the second step follows from A A[A, and the third step follows from : Ayy.
=T,
Thus, we have shown AAT + A = I
L
The following lemma presents a simple inequality for orthogonal complements. Lemma A.6 (Structural lemma for matrices with orthonormal columns). Let U, V E paxk be matrices with orthonormll columns. Then
(TU)=== = VV...
16

---

Published as a conference paper at ICLR 2024
Proof. Let first compute the Gram matrix of VTU, which is
UVVV U- (T V
- - VIVV
= 4 U where the first step follows from VIVI + VVT I, the second step follows from simple algebra, and the last step follows from has orthonormal columns.
This means that (VTU) V.
The singular vectors can be parametrized by orthogonal complement and inverse, solely.
Lemma A.7 (Orthogonal and inverse share singular vectors). Let A E B be non-singular such that there exists A1 E (n-x))xk with A A + A I, then the following holds:
Part 1. A1 and A-1 have the same set of singular vectors.
Part 2. Let u be singular vector of A, if corresponds to oz(A), then it corresponds to ok-i(A1)-
Part || AA ||
Proof. Proof of Part 1. Let E R be the unit eigenvector of A that realizes the spectral norm.
Note that
=
argue that corresponds to the smallest singular value of A via contradiction. Suppose there exists some unit vector with
| < ||A 2/|22
By definition, we know that
|| + ||Ayyl = 1,
which means
|Ayll2 ||Az||2 ||A||]
and it contradicts the definition of spectral norm.
Similarly, if is the unit vector that realizes the spectral norm of A 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 implics that A and A A- 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.
Proof of Part The key of the proof is that for any unit vector u E RR*, we have
|ull + || 2 1,
let 01 (A),..., (A) be the singular values of A and ui,.... un be corresponding singular vectors.
By above definition, we know
|Au (AA))
Then, know
(2( + || u. 1,
which means that A u; = /1 o7 (A)u,, Note that all singular values of A, are this form, i.e. have its singular values being
- of(A)
(2)
17

---

Published as a conference paper at ICLR 2024
(A) ... (A), and the above singular values are in ascending order.
Thus, we have
Th -
Proof of Part 3. The proof is then straightforward.
Suppose that (A, 2) is largest singular value and singular vector (e.g. ||A1]| = X). Then, we have
A1 X=
Using Part (by choosing i = 1). we know that is also the largest singular vector for A-1 Assume that A- largest singular value is j (e.g. ||- μi). Then we have
A- = μzz
(4)
Then, have
A = ALuz
((A12)
Auz,
(5)
where the first step follows from Eq. (4). the second step follows from is a real number and a real number multiplying matrix is commutative and follows from the associative property, and the third step follows from Eq. (3).
From Eq. (5), we know that
|AIA-12 Apr ||A -|A
Using norm inequality, we have
| S || - -
Combining the lower bound and upper bound, we have
|ALA~11 || ||-I|||-
and have proved the assertion.
We prove several fundamental trigonometry equalities for subspace angles. Lemma A.8. Let U, V e x be orthonormal matrices, then
sin (V U) tan O(V cos (V,
Proof. We have,
(an O(VUV) I
-I(VTU) (V
I((TT)LL
1/I(CTT))
INTUII
sin ((V,U)
cos 0(V,0)'
where the first step follows from the definition of tan A(V.U) U) (see Definition 3.2), the second step follows from Lemma A.6, the third step follows from the part of Lemma A.7, the fourth step follows from simple algebra, the fifth step follows from Lemma A.6, and the last step follows from the definition of sin (V, U) and cos 0(V, U) (see Definition 3.2).
18

---

Published as a conference paper at ICLR 2024
Lemma A9. Let U, E R be orthogonal matrices, then
sin 0(V.U) + cos ((V 1.
Proof. Recall that cos (V, U) I[ by by- and ((V |
By Lemma A.6, we know that
((U)-=Vi =
so by the definition of sin (V, U) (see Definition 3.2), we have
sin (V, (I( U)
We define matrix T as follows,
A A A==VT.
(6)
By part of Lemma A.7, we know that A₁ and A have the same set of singular vectors.
Let E R be the unit singular vector with singular value || ||-
This implics
|| ||
(7)
Note that Aj and A have the same singular vectors implies that the singular vector realizing corresponds to the smallest singular value of A, i.e.,
||
||Az||2 miin (A).
(8)
Then, we have
1 = == ZTz
x =AT(AT A + A[A1)z
= AT 7 A[A
||A=112 ||A_
= ||A +|AA,1
- (4) + ||A1||
(9)
where the first step follows from || 1, the second step follows from A A I, the third step follows from simple algebra, the fourth step follows from x BT Bz || 2. the fifth step follows from Eq. (7), and the sixth step follows from Eq. (8).
Also, we
|| 2 (A) (IVTU)112= o ii (VTV) U)
= -IV + + 2 U) = sin? 0(V.U) + cos? ((V.U),
where the first step follows from Eq. (6), the second step follows from Lemma A.6, the third step follows from definitions of sin 0 and cos 0 (see Def. 3.2).
Therefore, by Eq. (9), we have sin? (VV, U) + cos² ((V, U) = This completes the proof.
The next lemma demonstrates relationship between several trigonometry definitions.
Lemma A.10. Let V, U ga*k be two orthogonal matrices. then
Part sin 0 (V, U) tan OVV.U).
19

---

Published as a conference paper at ICLR 2024
Part 2. L-cos ((V.U) tan (VV U). ((VU))
Part sin (V, diste U).
Part 4. diste - sin (V, 1-cos ((V.U) Cos (VV.)
Part S. (V, - 2 tan (V.U)
Proof. We define
Q" := arg
min QEOkxk
IVQ IVQ -U]
Next, we define matrix R to be
R==U-VQ.
(10)
Then we have
dVs),(VVU)) [|]
(11)
and
sin (VV = IIVTUII IIVI (VQ" + R)ll
IIVIVO + +VRRI R
= IIVI RI
S IIV I|I
$ ||]]]
(12)
where the first step follows from the definition of
sin (V, U),
the second step follows from U = VQ + R (see Eg. (10)), the third step follows from simple algebra, the fourth step follows from V = VV from AB] I B|] and the last step follows from IV || <
(see Lemma A.5), the fifth step follows
Proof of Part 1. Note that
sin O(V,U) = tan (VV cos 0(V.U) tan 0VV U),
where the first step follows from Lemma A.8, the last step follows from cos ((V.U) 1. Proof of Part 2. For simplicity, we use to represent ((V, U).
The statement is
1 - cos
< tan 0,
0
which implies
- cos 0 S sin 0.
Taking the square on both sides, we get
1 2 cos + cos² < sin?
Using Lemma A.9, the above equation is further equivalent to
cos ((cos 0 1) s 0.
This is true forever, since cos 0 E [0, 1].
20

---

Published as a conference paper at ICLR 2024
Proof of Part 3. Given (V, |R] (Eq. (11)) and sin ((V.U) & ||| (Eq. (12)), have sin (V, U) I (Vitt(VUU))
Proof of Part 4, We define A, B as the SVD matrix V U as follows
ADB SV)(V
then
A A= ABV-
(13)
and
min (D) m (V (V cos (V,
In addition,
(A = BA
(B AAA
= =(B )
(ABT)-
where the first step follows from (AB)T = BT TT for all matrices A and B, the second step follows from the simple property of matrix, the third step follows from the fact that is orthogonal, and the last step follows from simple algebra, i.c., AB Okxk
For (V, U), we have
dist. (V, & \VAB - U1|
-IVVTVBD-IB
-VVTBD--B--VVUU-VV IBV
(14)
where the first step follows from AB 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. (14), namely IVV - Ul, we have
|[V -0 - - TY
sin (V.
where the first step follows from simple algebra and the second step follows from the definition of sin 0(V, U) (see Definition 3.2).
For the first term of Eq. (14), namely UUN-IBT - VVTUJJ we have
VVTUBD-'B' VV UVV T)ll
-7I BB -
1 Il1
1 cos O(V,U)
cos O(V
where the first step follows from simple algebra, the second step follows from |VVTU] the third step follows from B is orthonormal basis, and the last step follows from | I|] =
1
1-co8
cos 0
cos
Proof of Part 5. We have
dist, I sin 0(V,U) + 1 - cos cos ((V.U) Cos CV.
< sin (V,U)) + tan tatttan UV,
tan 0(V, U),
where the first step follows from Part 4, the second step follows from Part 2, and the last step follows from Part 1.
21

---

Published as a conference paper at ICLR 2024
A.3 TOOLS FROM PRIOR WORKS
The previous paper Jain et al. (2013) 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.
Definition A.11 (Sampling probability). Let C 2 10 denote a sufficiently large constant. We define sample probubility to be
p = C (oi/og)2 n² k2.5 logn |og(k
Then, we sample 52 ~ [m] x [n] each coordinately independently according to that probability.
The parameter 82p is tuning parameter for sampling probability. Definition A.12. We choose 62 as follows
1 1
82k
100 %
We can that 62k (0, 0.01).
Given the set of indices, we denote the row and column selection operator as follows. Definition A.13. For each E [n]], we define set Ω. C [m]
an = fie [m] (i.J) e ?2.
For each i [m]. we define ser Di [m].
24, = i e [n] (i.j) e 22.
The next structural lemma bounds the inner product between vectors inside set Q.
Lemma A.14 (Lemma C.5 in Jain et al. (2013)). Let Ω C [m] x [n] be set f indices sampled
uniformly random from [m] [n]] with each element of [m] [n] sampled independently with
probability p z C) m. Let C > 1 be a sufficiently large constant.
Then with probubility 1 1/ on)y for all Tm with Di 84 and for y E IK"" we have
Σ (U)
Juyl S ((mm) 422 |//l////|lll
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. Lemma A.15 (Wedin (1973), see Theorem conforming real matrices A and B,
Meng Zheng (2010) as an example). For two
| - Bi 2 max ||
||A
B||
The next claim bounds the inner product between any unit vector and rows of incoherent matrix. Claim A.16. Suppose Ue is #2 incoherent, and U, is incoherent. For any unit vectors we have
Part Eieim (x. Uz < p2k/m
Part Lie(m) (y, U, U, (x. U,,) S p22/mm
Proof. Proof of Part 1. Note that ||, 2| S 1, so
(x, U2.) |,, (x, U2 (Ueell) - U,,lll,
(15)
where the second step follows from the inner product between unit vectors is at most 1.
Thus, based on Eq. (15),
(x, Un,)
1
22

---

Published as a conference paper at ICLR 2024
p2sk/m mm.
(16)
where the last step follows from Ug is Hz incoherent.
We have
tr,
Un
< max
(z, Ue,1)²
Σ
(x, Ue,)
im(m!
==1
k
(x, U2.1)
m
ngk x UTT,U U2E
12k TTx
m
where the first step follows from Eie(m agby S m|x ag EiE(m) 6, the second step follows from Eq. (16), the third step follows from U, U. = E. U., the fourth step follows from U. U2 = [x. and the last step follows from the Lemma statement that x is a unit vector.
Proof of Part 2. Similarly the proof of part 1. We know that (y, x),) S 11,, s p²k/m.
(17)
We can show
m
Σ (2, U2,)2 (y, U.i)² S max (y) Un,)2 .E(m)
(x, Uns)
22k
(r, Un,)
m
p²kk TUU Upx
m 12l .r: m
m
where the first step follows from Exe(m) agby S ma as Eie(m) by the second step follows from Eq. (17), the third step follows from U, U, En U...L. the fourth step follows from U. U. Tg. and the last step follows from the Lemma statement that is a unit vector.
A.4 PROBABILITY TOOLS
We introduce several well-known probability inequalities.
Lemma A.17 (Chernoff bound). Let X = X,, where X; = with probability ps and X; = with probability Pt, and all X, are independent. Let μ E[X] Ei Pc. Then
Pr[X 2 (1 + 8)m} S 2xp(-82p/33 48 0;
Pr[X <1 (1- 8)n} < exp(- Vo 10,
Lemma A.18 (Bernstein inequality). Let X1, X,, be independent zero-mean random variables
(i.e., E[X,] for all E [n]]. Suppose that X s M almost surely, for all i [n].
Then, for any positive t, we have
1/22 Σラ B[X3] + M1/3)
Pr
Σ X, >
1) < exp(
23

---

Published as a conference paper at ICLR 2024
B HIGH ACCURACY WEIGHTED REGRESSION SOLVER
We demonstrate our high accuracy, iterative solver for weighted multiple response regression this section.
B.1 DENSE, HIGH ACCURACY AND ITERATIVE SOLVER
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 Lu et al. (2013).
Definition B.1 (Subsampled randomized Hadamard transform (SRHT)). The SRHT matrix S E mxx PHD, D, where each row of matrix P E {0, 10,1)mxn contains exactly one
mmxx is defined as S == /mn
1 at a random position. H is the x n. Hadamard matrix. D is an n x n diagonal matrix with each diagonal entry being a value {-1,+1 +1} with equal probability.
Remark B.2. For an x d matrix A, SA can be computed in time O(ndlog n).
The following lemma states that suitable chosen SRHT provides the so-called subspace embedding property.
Lemma B.3 (Tropp (2011)). Let R be an SRHT matrix as in Def. B.1. Let Coses 8 E (0, 1) be parameters. Then for any integer d S n, if mak O(c 2 log(n/ (Cose, 8ose) oblivious subspace embedding, i.e., for any fixed orthonormal basis U E xn with
then matrix S is
probability least 8,s0s the singular values of SU lie in
Eose 1 Enso].
SRHT can be further utilized for a high accuracy regression solver, as presented by the following lemma.
Lemma B.4 (Dense and high accuracy regression, Avron et al. (2010)). Given matrix A E Baxd and a vector b R", let E E (0, 0.1) and 8 E (0, 0.1), there exists an algorithm that takes time ( (n/61)) log(1/es
O((ndlog d log
and outputs x' E dRd such that
||xx b112 S (1 (1) min ||Ar
bll2
ZER
holds with probability 61.
The above result also extends to weighted regression, measured in terms of the ||0|| Σi= waif norm. For the sake of completeness, we include the algorithm and a proof here.
Algorithm 2 High precision solver
procedure HIGHPRECISIONREGGA E Rexd, E R" n, n, e (0, E (0,1))
Lemma B.4
2: Ti + (llg((1/e))
3:
fase +- 0.01
4:
dose + 81
5:
Mak O(e=2 d log2 (n/8gee)
6:
Let 5 E Rmm be an SRHT matrix
7:
Compute QR decomposition of SA QR -1
8:
To - arg mingers ARR Sbll2
9:
for 1 Ti do
10:
21+1 - 24 + A -RRx)
end for
12: return RET:
end procedure
Proof of Lemma B.4. Let analyze Algorithm 2, first on its convergence then its runtime.
Note that the S we choose is an (Foan: -obliviouss subspace embedding. Since SA = QR where Q is orthonormal, know the singular values of A R are between [1 Case: 1 + Cosel.
24

---

Published as a conference paper at ICLR 2024
Let AR UEVT be the SVD of AR and x' denote the optimal solution to the regression min ||ARr - bl[2.
Let us consider
AR( x²)
AR(2; + R A (b- ARx,) - x²)
AR(2; x²) -ARRT A b- ARR A ARE
= ARR(2; - x²) - -ARR A ARr" - -ARR A ART
= -ARR - ARRR A (R))xt-22)
(UEVT - U (z) -x"),
(18)
where the first step follows from the definition of 2++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.VT.
Therefore,
AR x")|22 |IVEVT - -VEV (s: x 112
= 1(E VaIV (It - x '))2
x ( (Cnso)
1 (5t - x "1)1
< (coor)
| (xt - x² 111
coor
= 0 (Eose)
||VV (Ire - x )112
= (Eose)
||/2V (Iz- x l
(Fose)
||A xx" )l2,
where the first step follows from Eq. (18), the second step follows from U I, the third step follows from |B|| < || [[B]|, the fourth step follows from (1 <ose) < ||| the fifth step
follows from Case E (0, 0.1), the sixth step follows from U = T, and the last step follows from the SVD, AR = U.VT.
This means the error shrinks by a factor of (Coose per iteration. After T O(log(1/c)))))) iterations, we have
||R((TT x2) < O(e)) ||AR(zo x²) 22)1
(19)
and recall for initial solution Fo. we have
||ARoo - b112 S (1 + 6ose) ||ART* - 6112-
The above equation implies that
| b122 - 11ARR- - b112 < (((con))) AR -612.
(20)
We can wrap up the proof as follows:
|ReT - bll3
|AR(aT - x )113 + ||AR=* b11
S <O(E) ||AR( x²") 113 + |AR - -b12
=O(e) (IAARO 6122 - |ARx - -b1l3) ||ARx" - 612
O(G)) (O(Fose) (l A| bll)) -|ARE= - -11
(1 O(e))) ||ART" -11..
where the first step follows from the Pythagorean theorem, the second step follows from Eq. (19), the third step follows from the Pythagorean theorem again, the fourth step follows from Eq. (20), and the fifth step follows from Easc
1.
25

---

Published as a conference paper at ICLR 2024
It remains to show the runtime. Applying S to A takes O(ndlog time, the QR decomposition takes (fm Od log (n/0ose)) time.
Inverting d x d matrix Q takes O(d)) time. To solve for 20, we need to multiply SA with It in d( time and the solve takes (mm time well. To implement each iteration, multiply from right to left which takes (nd) time. Putting things together gives the desired runtime.
B.2 BACKWARD ERROR OF REGRESSION
We show how translate the error from || - b||2 || zOPTIl2 via high-aceuracy solver. In the low accuracy sketch-and-solve paradigm, SRHT provides a stronger foo guarantee, but for high accuracy solver, we only attain an & backward error bound.
Lemma B.5 (Backward error of regression). Given matrix A E BRndd vector b E R Suppose there exists a vector x' IRd such that
|Ax' - bll2 S (1 e1)
min DER
| bll2-
Let TOPT denote the exact solution to the regression problem, then it holds that
|| - =
| bl12-
O (A)
Proof. Note that
| Azorrl22 || - b- (AXOPT - b)]l2,
so we can perform the following decomposition:
A| zorr)l || b (Arort b)1l
||Ax' -113 ||ATOPT - 611
< (1 + () 2 bll2 ||Aror - b12
S 4el ||A bl(2.
(21)
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.
We expand more and explain why the second step follows from Pythagorean theorem. Ultimately, we will show that ArorT b is orthogonal to any vector in the column space of A. Recall that zorT can be written in terms of the solution to the normal equation:
TOPT (AT A'' ATb
note that A is not necessarily full column rank, hence we use pseudo-inverse. Let A = UEVT be the SVD of A, then the above can be written as
TOPT = (VV'VVT +(E')VTTVEU"
-VEE)>EUT
=VElUTb
where we crucially use the fact that for a diagonal matrix Σ, the pseudo-inverse is by taking the inverse of nonzero diagonal entries, and keeping for remaining diagonal entries. We can therefore express АΣоРT 6 as
AXOPT - b=UEV VVEU
UV b-b
= ((UIaank())U" - -I)b.
where Trank(A) is the matrix whose first rank(A) diagonal entries 1, and remaining diagonal entries are Finally, we compute AT (ANOPT- bb):
A (AxorT VEUT (UTrank(A) T)b
26

---

Published as a conference paper at ICLR 2024
(VEUT - VEU }6
=(A )b
=O,-
where for the second step, we use U = I, Elyak((A) = E since Σ only has its first rank(A) diagonal entries being nonzero. This justifies the use of Pythagorean theorem.
We can express the SVD of A in a similar manner:
A =V=V..
therefore, must have
A VEUU
rank(())) VT
and it acts as contracting mapping, the sense that for any E Rd,
|| Ayl2
[ Lank (A) V v112
(rnk(()) VT yll2
V vlle
IIV IllBl12
||ull2,
where the third step is due to we only need to compute the &a norm on sub-vector, and the last step by ||V || 1.
Therefore, we have
| - zorrIl 2 S ||AAA((x* zoPr)ll2
1|A(2' 2ooT))l2.114l ||47|
22 ||ArOr- -
-bll ||41
2VET
miin ||ATOPT bll2.
where the first step follows from A A is contracting map, the second step follows from ||ABazl2 < ||Ax||2|| the third step follows from Eq. (21), and the last step follows from |||
amin (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 nonnegative weight matrix, and show it's equivalent up rescaling.
Lemma B.6 (Reducing weighted linear regression to linear regression). Given matrix E RRax vector E IR.", and a weight vector w IR 20
Let E (0, 0.1) and 6, E (0,0.1).
Suppose there exists a regression solver that runs in time T(n, d, e1, 81) and outputs a vector x' Bd such that
|Ax' -bl2 S (1+
min Ar
bll2
ZERd
with probability at least 1 - 8, then there is algorithm that runs in O(nnz(A)) (n,,
time outputs x' E RRd such thut
||A'' bl|10 5 (1 (1 min
|| bll..
ZERd
holds with probability 1 1-8 81-
27

---

Published as a conference paper at ICLR 2024
Proof. Recall that for vector R" || = Ei= Dw,a3 define the following simple transformation on the regression problem: let b; := D /w,b: by and A.. == D.w,A
We then solve the regression the transformed problem min || - bl[2-
Let w' E IRd be the solution such that
|| b112 (1 + E1)
min | bll2.
zER
then for any Rd
1
Ayy - b112 = Σ (A..y - b.)²
D VW. DDW.AA AT, D Di
Σ Dww, (A,. - -b.)
Σ Dw: (AT,AA -b,)
= Ay - blu2
where the first step follows from the definition of || 11.. the second step follows from the definition of A and b, the third step follows from simple algebra, the fourth step follows from (zy)² x² xzy? and the last step follows from the definition of Ay bll2- 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 weighted multiple response analysis that runs in time proportional to the sparsity of weight matrix W.
Algorithm 3 Fast, high precision solver for weighted multiple response regression. We will use this algorithm in Algorithm 5 (the formal version) and Algorithm (the informal version).
1:
procedure FASTMULTREG(A mM B E Rmnk W E Rmxx m, k. cu. dg) Lemma B.7
2:
A is the i-th column of A > W, is the i-th column of W Dw, is a diagonal matrix where we put W; on diagonal, other locations are zero 61 + ep/ (nly(n,)) k)
3:
4:
5:
6:
81 + / poly(n)
7:
for i = 1 + n do
8:
X; <- HICHPRECCSIONREO(DW B E Bmnk Dw, R*, m, R k,,,ke,,1))
Algorithm 2
9: end for
10: return X
X E Raxk
11:
end procedure
Lemma B.7. For any accuracy parameter eo (0, 0.1), and failure probability & E (0,0.1).
Assume that m < n. Given mairix M E Rmxn Y E Rm and W E {0, 1mmm, let Kg a MM) Omin (Y) and arg mig I[ a (M YYX))| (Algorithm 3) that takes time
There exists an algorithm
O log n + nk log" (n/6n)) log(nno///)))
and returns a matrix Z E x such that
1 - X|| S 6n
28

---

Published as a conference paper at ICLR 2024
holds with probability 60-
Proof. We can rewrite multiple regression into linear regression in the following way,
min JM
XY
l
min X.,
ID YX,, D D.w.Mi.:lé
X XEROXA
Consider the i-th linear regression. We define
= D Dww,Y Y E Rm
x = X1: E Rt
. b: Dww,M.s E R..
Recall that Rmxx
For each (n]. let X;,: E R denote i-th row of X E Baxk For each E [n]. let M. R denote i-th column of M E Rmxx We define OPT;
OPT, = min
D
X
D Vw: M 112-
ERA
IT mX
M2 m
Here D D.W, E Ruxx is a diagonal matrix where diagonal entries are from vector vW, (where W; is the i-th column of W E 10 wW, is entry-wise sqaure root of W...
The trivial solution of regression is choosing X,, E IR* to be an all zero vector (length-k). this case OPT; < ||M,il|2-
Let C > be sufficiently large constant (The running time of the algorithm is linear in C). Using backward error Lemma B.5, know that
1
MM,il
| 21|2
S c
(nxx)
T miin (Y)
maxx (M)
S 60
(nko) C
Mmin (Y)
ED
e n Kg
Ko
S ED.
(22)
where the second step follows from ||.ll S max (M), the third step follows from the definition of Ro (see Lemma B.7), and the last step follows from simple algebra.
Using Lemma B.6 n times, we can obtain the running time.
C INITIALIZATION CONDITIONS
In this section, we deal with init conditions. In Section C. we provide the lemma which bound the distance between Ug and U.. In Section C.2, show that if U is close to U., then Un is close to U.. In Section C.3, we give the formal definition of Uo. Ur. and Ug. In Section C.4, we combine the previous lemmas form
result.
C.I BOUNDING THE DISTANCE BETWEEN Ug AND U.
We prove our init condition lemma. This can be viewed as a variation Lemma C.I in Jain et al. (2013).
29

---

Published as a conference paper at ICLR 2024
Lemma C.1. Let 2 p. Pao (M) = UEV be the SVD of the matrix 1 Pas (M), where U R E
p
Rmxm and V E <Rmx.. Let Up E mm be the k columns of U corresponding to the top-k left
singular vectors U. U. We can show that
1
s.,
10
holds with probability at least 1/ poly(n).
Proof.
Let Ms == UPEVT. Let C > 1 be some constant decided by Theorem 3.1 Keshavan et al. (2009).
We show
h//2
|M - - Mo
21/2(mn) |M]]
11/2
C
(m/2(1)) Vkoi
k
p1/2(mn)2/4 oi
< C
1/22 oi
10 O
(23)
where the first step follows from Theorem 3.1 in Keshavan et al. (2009), the second step follows from | S vkot. the third step follows from simple algebra, namely ka k2 k, the fourth step follows from n 2 m. the last step follows from
p2 10 C2, ka (ai)² (o
We also have
IIM 1
|U.E.V - U1
|U.E.VV - -U + +UGUT - U
= II(T - U.U])U.E.V. U...U. )|
[I( - U.U,),...
| U.L.V.VV |
|
|V (a (2.))² 2 (ot) U.I
(amin
(24)
where the first step follows from the SVD of M (see Definition 3.5) and Ms. 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|| 2 |||| if B = 0 (Fact 1), the fifth step follows from U&UJ + U
I, the sixth step follows from applying Part of Fact A.3 twice (one for Us and one for V.), the seventh step follows from ||AB] || 2 ||A||| mii (B) (Fact A.1), and the last step
follows from mmin (E.) ot
Combining Eq. (23) and Eq. (24), we get:
1
U0
U. 1|2 <
|M M
0
< 10
Thus, complete the proof.
30

---

Published as a conference paper at ICLR 2024
C.2 CLOSENESS BETWEEN US AND U, To CLOSENESS BETWEEN Uo AND U.
We first define T, and then provide lemma to show that whenever Up is close to U., Uo is close to U..
Definition C.2. We define as follows:
== 2 Vn n.
The initialization condition proof is very standard in the literature, we follow from Jain et al. (2013).
Lemma C.3. Let U. mRi incoherent with parameter μ.
We define
66 10
Let Ug be an orthonormal column matrix such that
dist(Uus, U.) S es.
Let U, be obtained from Ug Raxk by setting all rows with norm greater than T to zero. Let Uo be an orthonormal basis of Uy.
Then, we have
* Part 1. dist(Uo. U.) S 1/2
Part 2. Un is incoherent with parameter 4pv/k.
Remark C.A. For the convenience of matching later induction proof. when we use this lemma for the base induction, we write Ug to denote UT-
Proof. Proof of Part 1. For simplicity, in the proof,
denote ed-
Since (Us, U.) S we have that for every i, 3z₃ E span(U.), || = 1 such that
(u, 2 v 1 22
(25)
Also, since z E span(U.), we have that z; is incoherent with parameter pv
| =1
(26)
and
PVR
| 8
(27)
Vm
Let uy,i E R be the vector obtained by setting all the elements of u; E Rm with a magnitude greater than zero.
For each i E [k], let uy mm denote the i-th column of Ug.
By definition of Us. we know that
||ull22 = 1.
(28)
We define vector U7 E m
"7, == - U
(29)
Now, for each j E [n], we have
(u:))>>> 2
m
where represents the j-th entry of u, R
31

---

Published as a conference paper at ICLR 2024
Then, for each [mi] with [(u)))] > 7, [(ur,])
(2:);1= 10 10 (zi)gl = [zz))pl
uvk
Vm
uvV uvh
Vm
Vm
$ (uxss) - [(z))]l
((4))- (z+)al.
(30)
where the first step follows from truncation at 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 (44)yl and [( and the last step follows from the triangle inequality.
For each j E [m]] with [ux) S т, we know that
((,,,); (=),) = ((4); - (z))gl-
(31)
where the first step follows from (u..a); = (u:) in this case.
Combining Eq. (30) and Eq. (31), we know for all j E [m]]
((ur,)) (z+), S ((us) (24);1-
Hence,
||u,,,
2:113 < ||u =112
||u, 12 + || 2(2, 2i)
||u,
1/ ||
2/1 c
2 2-
2c
(32)
where the first step follows from taking the summation of square of Eq. (30), and the second step follows from simple algebra, the third step follows from Eq. (25), the fourth step follows from and 24 are unit vectors, and the last step follows Part 3 of Fact A.4.
This also implies the following:
||wr,ll2 2 ||2:||2 ||ur,i zi|12
||2:|12 22
= =1 - V2e, where the first step follows from triangle inequality, the second step follows from Eq. (32), and the third step follows from Eq. (26).
(33)
We show
U7 1l2
||u. u, 12
< |/ |
|
u 2|
< (1 V2e)
2c,
(34)
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. (33), and the last step follows from simple algebra.
We can show that
||=+| < ||U+1|
32

---

Published as a conference paper at ICLR 2024
|
S 1e2k
(35)
where the first step follows from of square of Eq. (34).
|| || ||r, the second step follows from taking the summation
Let
U, = UGA
(36)
be the QR decomposition.
Then, for any ux.1 E span(U,,.), we have:
| Uoll2 ||0,, U-A
- ||u, Un ||2||
(37)
where the first step follows from Eq. (36) and the second step follows from ||Ax|22 S ||| For the first term in the above equation
||0/|12-
||u,, U=l12 S ||uT,, Vollz + IIuT,, Uzll2
S + ||u,,, U7l12
S E + ||
S E 2Vke
< <3vke,
(38)
where the first step follows from triangle inequality, the second step follows from [| ll2 I d, the third step follows from the definition of) ||. the fourth step follows from Eq. (35), and the last step follows from & 2 1.
We now bound ||A| as follow:
1
||
min (A 1112
1
Omin umin (UnA-13
1
O (U,)
UT| 2
5
1 2 Tee
2,
(39)
where the first step follows from Fact A.1, the second step follows from the fact that Ug forms an orthonormal basis (see Part 2 of Fact A.3), the third step follows from the QR decomposition of U, (Eq. (36)), the fourth step follows from cos² 0 + sin? 8 = 1 (see Lemma A.9), the fifth step follows from Eq. (35), and the last step follows from using the fact that e < 1O0E
Thus, we have:
| Volla S ||uT, 11l12lAA1
$ 3vTc. ||A|
< w/ee 2
-VTe
33

---

Published as a conference paper at ICLR 2024
10
where the first step follows from Eq. (37), the second step follows from Eq. (38), the third step follows from Eq. (39), the fourth step follows from simple algebra, and the last step follows from the fact that S 10
This proves the first part of the lemma.
Proof of Part 2. The incoherence of Uo (see incoherence in Definition 3.4) is
m
Vm
|e
Uolla
||e
U,A
12
h
1E/m]
k
7Emm]
m
max rE(m)
||e U, ||||
Vk
2 2/m
max xE(m
||e, U+l12
Vk
2 v
V/:
2/m
24v k/VV
Vk
4p,
where the first step follows from the definition of incoherence, the second step follows from || S ||||| || the third step follows from Eq (39), the fourth step follows from U, truncating at
the fifth step follows from 2pv k/ v (see Definition C.2), and the last step follows from m.
C.3 DEFINITIONS FOR Uo. Ur. U
We provide the definitions for Uo. Ur, and Ug. We also include procedure that clips rows with large norm then perform Gram-Schmidt.
Definition C.5. Let 1 P (M) UEVT be the SVD of the matrix 1 Pao (M), where U
Rmxm Σ E Rmxx and V IRax..
Let r 20Vk v
Let U. Rm be the columns U corresponding to the top-k left singular vectors of U.
We define U, E ma follows:
Un = {0, Una 11 ST.
otherwise.
Finally, define Uo Ronk to be the matrix formed from performing Gram-Schmidt U,, i.e.
columns of Ug are orthonormal.
To make convenient of base case of induction proof. we call U, to be i
C.4 INITIALIZATION CONDITION: MAIN RESULT
We provide a Lemma which bounds dist(U,, U.) and shows that Up is incoherent with parameter 4pvk.
Lemma C.6. Let M E mmxx be a (Hs, -i)incoherent matrix (see Definition 3.5).
Let Ω C (m) [n) and (0, 1) be defined Definition A.I
34

---

Published as a conference paper at ICLR 2024
Algorithm 4 Clipping and Gram-Schmide
1: procedure INI RRmxk, 1a E (0)
Buy/k VR 3: for = m do
2:
Unii
if 1U S T,
4: Ur.i 00
otherwise.
5:
end for
6:
(Q, t QR(U,)
7:
Uo 10
8:
return Up, Un
9:
end procedure
Let Ug E Rmnk be defined as Definition C.S. Then, we have the following properties
dist(Uo, U.) < 1 and
. Uo is incoherent with parameter 44 suvk
holds with probability at least 1/ pnly(n).
Proof. From Lemma C.I, that Uo satisfy that
dist(Uo. U.)
100k
Using Lemma C.3, we finish the proof.
D MAIN INDUCTION HYPOTHESIS
In this section, provide main induction hypothesis: inductively bound dist(V,,1, V*), dist(Ü U*) and the incoherence of U141, V4+1- We start by presenting our formal algorithm.
Lemma D.1 (Induction hypothesis). Let M = U.E.V. be defined as Definition 3.5. Define (T), we have the following results.
6a 11= 1/10. For all
Part 1. Uf is #2 incoherent and dist U2) S dist V.) S ed. then we have
ddis((V+41, V.) I 1 dist((ū, U*) $ cd
Part 2. Uf is p2 incoherent and dist. (Ū., U.) < dist (V,, V.) & Cd. then we have
Vi4 is p2 incoherent
Part 3. V444 is na incoherent and dist dist(V V.) < dist((U,,U.) S ca then have
dist((een)U.) ddiis V.) ea
Part 4. If Vi4 is μ2 incoherent and dist (V V.) < 1 dist S ca then we have
. UUer p2 incoherent.
The above results hold with high probability.
35

---

Published as a conference paper at ICLR 2024
Algorithm 5 Alternating minimization for matrix completion, formal version of Algorithm 1.
1: procedure
[m]] x [n], ka
Theorem 4.2
2: Let E (0, 1) denote the final accuracy of algorithm.
3: Let 8 (0, denote the final failure probability.
4:
Partition Q into 27 + subsets Ωg Ωgr Each element of f belonging to one of the Q with equal probability (sampling with replacement)
5:
6:
U/ = S p Pro kM)
U E Rm
7:
Uo. U. - IN))(U&)
Algorithm
8:
T ((log(1/c)
9:
En x cf poly(n,
10:
do + 5/ poly(n, T)
11:
for t = 0, 0,...... do
V++1 + FASTMULTREG M E Rmxn, Ü, E Rm 92241, m. n, h, co, 60)
12:
13:
Alg. 3, Lem. B.7. Here s2441 can be viewed V4+1 FASTMULTREG R=xm Ven E Rank O n, m, k, co. dn)
weight matrix.
15:
p Alg. 3, Lem. B.7. Here Q2442 can be viewed as a x m weight matrix.
16:
end for
17:
X X V.
18:
return X
X E mm
19:
end procedure
Proof. Proof of Part 1. To prove this part, we need to use Lemma F.I, and Lemma F.3. To use Lemma F.I, we need the condition that Ug is da incoherent. To use Lemma F.3, we need two conditions: one is that U. be jg-incoherent and the other dist(U,, U.) S 1/2.
We can show that
dist Vs, Vi+1)
[V_ Vi+1ll
IV. (V R
IV. U.E.U. + V.J, FR
FV
|F R
EE
S FE - 1,,1
(40)
where the first step follows from the definition of distance (Definition 3.1), the second step follows from the definition of Vi+1 (V++1 = (V,EU,, U, F) R see Definition E.6), the third step follows from simple algebra, the fourth step follows from V. V. 0. the fifth step follows from Fact A.3, the sixth step follows from E.'E. I, and the seventh step follows from ||4 B|| s |||]|| || (Fact A.1).
By Eq. (40), we can upper bound
dist(V., Ve+1)
||E2 P
< 2d2u dist (U,, U.) -IE RTHll
2d2x dist(U,, U.) 20//o/ /o
< dist dist U-),
where the second step follows from Lemma F. the third step follows from Lemma F.3, the last step follows from Definition A.12.
Proof of Part 2. In this proof, we need to use Lemma F3, Lemma F.4, Lemma F.5. To use Lemma F.3, need the condition that U, is μl incoherent and the other is dis U.) < 1/2. To
36

---

Published as a conference paper at ICLR 2024
use Lemma F.4, need the condition that Uj is ag incoherent. To use Lemma F.5, need the condition that Ug is #2 incoherent.
For each j
[n]. according to Definition E.6, we have
Vi+1 (D,
Therefore,
of
Vi+11ll2 Jiin (1+11) For the first term of Eq. (41), we have
|Vaalle (1) + |B |B, -
(41)
01
20//0%
(42)
min (Re+1)
where it follows from Part 2 of Lemma E.3. For the second term of Eq. (41), we have For the third term of Eq. (41), we have
(43)
|| |1 + [ (B, c,)1 < + 1 - C,ll
$1+ | Cyll
$1+2-1B;,;-C C,ll
$1+2 (1,, + [IC,I)
21
2 10,
(44)
where the first step follows from ||AB||| I ||A||- ||B], the second step follows from | | S 1, the
third step follows from Lemma F.4, the fourth step follows from || B|| I |||||| + |B]]| the fifth
step follows from Lemma F.5 (for || |Cyl| I 2), and the last step follows from simple algebra.
Combining Eq. (41), Eq. (42), Eq. (43), and Eq. (44), have
2 of Vi+iolla
VT
10
ok
vn
Vk
where the second step follows from Definition E.2
Proof of Part 3 and Part By a symmetric argument, we can also prove
1
dist Uist(U1+1, dist(Vi+1, V.).
and U441 is μl incoherent. We are now ready to prove the main theorem of this paper (Theorem 4.2)
Proof of 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 7' iterations.
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. provide the formal definition of the updated rule. In Section E.2, give the definition of the enror matrix and analyze its properties. In Section E.3, we focus on providing the definition for the update rule for V.
37

---

Published as a conference paper at ICLR 2024
E.1 UPDATE RULE
To begin with, we formally define the updated rule as follows.
Definition E.1 (Update rule). We define several updated rules here:
Part We define the QR factorization Ü, E Bm as Ü, == Uy Rr
Here Ut E mann and RI,U R
Part 2. We define Ve41 Bank as follows Vet = arg pe [|Pa(U,TT) Pa
Part 3. We define the QR decomposition of V4+1 E Bank as follows V4+1 == V441
-Here V4+1 E Bank and R E Bk
Part 4. We define Č4t1 E Rm as follows Ü441 == arg j ( Pa
We note that the update rule does not directly reflect our algorithm. Nevertheless, we start by analyzing this bR-b update and later connecting it to our algorithm.
Definition E.2 (112). We define μ2 as follows
oi ok
Vk.u.
μ1 =
E.2 ERROR MATRIX
Next, we provide several definitions related to the error matrix F. For most of the notations, we follow Jain al. (2013) (Note that those definitions are implicitly presented on page 16 Jain et al. (2013)). Note that we use U., V. to denote the optimal low rank factor instead of U* V to case notations.
Definition F.3 (Error matrix). For a given E Bank matrix, for each j E [n], we use Ua, to denote the i-th row V..
We define U. nR as follows
"4 == vec(V.),
which can be written as
V. [w_, v..2..... v.,ell.
We use un denote the i-th row of U, m We use u to denote the i-th row of U. gmnk
We define B Rukxnk to be the matrix where the j-th block matrix is By, i.e.,
B2
B =
Ba
For each j E [n)), we define Bj E bx as follows
By=
1
Σ
p iEf
38

---

Published as a conference paper at ICLR 2024
We define matrix C E Rnnxxnk to be diagonal block matrix where the the j-th diagonal block is Cj E RR
Cj
Σ
P VERLJ
We define matrix D Rakxxn to be the matrix where the j-th diagonal block is Dj E R
D2 = U.U.U U.
We define matrix S E gakxnk as
In
o2ln
=
o n
For each i [k], we define F; E " as follows
(BD C)Su,) C)Se.)n(i-144
(B- - C)Su. )n(
F =
(BD-C)))
We define F' E ngak as follows:
F
F2
Fi.
Claim E.4. Let B, D,C be diagonal block matrices (where each block has size l k).
Let be block rescaled identity matrix (where each block has size n. X n)).
Then, we have
SB -) (BD -BD-CS..
Proof. Without loss of generality, we can assume that n/k is an integer. Then, can also be viewed as diagonal block matrix with size k x k.
The j-th block of (B--((B) C' is
C,) (B,D, Cj).
=(B~ - C)S);;
where the first step follows from all matrices are diagonal block matrix, the second step follows from S, is an identiy matrix with resacling (AI = IA), and the third step follows from all matrices ar diagonal block matrix.
Thus, we complete the proof.
Claim E.5. We have the following identity:
FE 11 11B31BB -Ce,
Proof. We have
|F ||
ΣΣ i=
B
39

---

Published as a conference paper at ICLR 2024
SB (B
$2 n(i
(BD-
= - (BD C)u
where the first step follows from the definition of || 1| the second step follows from Claim E,4, the third step follows from that fact that 5 is diagonal matrix, the fourth step follows from *((i-1)+j.a(--1)++ of, the fifth step follows from (a;)² and (o,) canceling out, and the last step follows from the definition of 1
E.3 UPDATE RULE FOR V
Now, we define the update rule for Definition E.6. We provide the definition of V4+1 E Ruxk and V411 E Baxk
We define V E Bu as follows
VA+1= V.SUUUUUU
Note that the first term can be treated power-method update, and the second term the error term. Here F E 1g is the error matrix defined in Definition E.3.
We define Ve+1 E Bank as follows
V4+1 VE+1 RG41-
Here R441 E Baok is a upper-triangular matrix obtained using QR ReR-pccompoiiionn of Vi+1 E Bank
The above two definitions imply that
V++1 = -V.E.U, FF
F TECHNICAL LEMMAS FOR DISTANCE SHRINKAGE
In this section, we prove collection of technical lemmas that will facilitate us to eventually conclude our induction.
In Section F.I, we bound |FE by distance. Section F.2, we bound [[ C)u,112 by distance. In Section F.3. we upper bound [E* R. |||. In Section F.4, we upper bound | |B- In Section F.5, we upper bound Clyl
F.1 UPPER BOUNDING || BY DISTANCE
In this section, we upper bound |FE, by distance between U2 and U.. We generally follow the approach of Jain al. (2013).
Lemma F.1. Let F be the error matrix defined by Definition E.6. Let U, be we-inncherent matrix and düs U.) < 1/2. Let M be a (p, -icchhhheenntt matrix (see Definition 3.5). Let S2 C [m]] x [n] and p (0, 1) be defined as Defimition A. Let 8aa E (0, 0.1) be defined Definition A.
40

---

Published as a conference paper at ICLR 2024
Then, we have
(F(E.))11 S 282x k- dU,t U.)
holds with probability least 1 - 1/ (nly(n))
Proof. We have
|FE, |FE,11| 1
1|8 'BD - C)uull2
$ |B |1(BD 11(BD- C)u+12
< (BD -CUull2
$ 82x dist(U,, U.).
where the first step follows from
1| S ||
|| (Fact A. the second step follows from Claim E.5, |2 the fourth step follows from Lemma F.4, and the
the third step follows from ||Ax 22 _ ||
fifth step follows from Lemma F.2.
F.2 UPPER BOUNDING (IBDD C)v.l12 BY DISTANCE
Now, we upper bound CCuu We follow similar ideas in literature Jain al. (2013).
Lemma F.2. Let M mmx" be (H, k)-inccherennt matrix (see Definition 3.5). Let Z C [m] [n] and p E 1) be defined as Definition 1. Let U. E Tm be p2 incoherent matrix. For each j E [m], let Varj denote the j-th V. Bank
We define BRnk as follows
[U,,1
Then, we have:
- C)o 12 S 82x dist(V2+1, V*), holds with probability at least 1/ poly(n).
Proof. Let X E Baxk and x vec(X] E RRn where |a||2 1. For each j E [m], let xy IR be the j-th row of X E Raxk For each j E [n], we define H, R
H, == (B,D, Cÿ)-
Then, by the definition of Bj, Cj. and Dy (see Definition E.3), we can write Hy e Rkkk
H, U.UTUUU U. uu, P iEn...
Σ
1 Σ H
P VER
For j E [n], [m], define Hj BRkk follows
H5s u.U U. - u...
(45)
Then, we have
1 Σ Hjs 11 =
E
Note that,
Σ My - -TUNUU - =.
(46)
For each j E [n], let V.j denote the j-th row of V, E Runk
41

---

Published as a conference paper at ICLR 2024
Now,
x ='(DD- C)u, [B](B,D-CJVV.
==1
*
k
ΣΣ
Σ (zz)s (Va.)) (Hzs)p
p=1g=1 (bJ)ER
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 Bj, Cj. D (see Definition E.3).
Also, using Eq. (46), we have V(p q) E [K] x [k]:
Σ
(Hja)pa =
1=1
Hence, we get with probability at least
x =BBDD- C)v. = Σ
2
==1
k $
(z)),
(V=.)
(HHD)pa)
(47)
q= j=1
where the first step follows from j being defined as the j-th row of matrices and the second step follows from Lemma A.14.
For each 9 E [k),, we use Un,q denote the q-th column of U. E Rmxk
Also,
m
m2
Σ i=1
(un,)
(U,,U,UU, - (U=)i,g)
=
E(uT,U U, UnA (U+)
S max uc, m
max (u,,))) )p- |1UUUU - 11
E ml
p2kk
[[U,U, -I)U..
m
pgk
IIU.UU 1)1.11
m
p2kk dist(U,,,.))
(48)
m
where the first step follows from Eq. (45), the second step follows from Σ, ag,; S max; Σ b, the third step follows from simple algebra, the fourth step follows from u, is Ml incoherent, the fifth step follows from spectral norm definition, the last step follows from the definition of distance.
Using Eq. (47), Eq. (48), and incoherence V, E Baak we get (w.p. 1/n²),
x. T(BDD Cju*
dUst U. 1
a 1
mp
< 62x dist (Ui U.):
(49)
where the last step follows from
Σ/ |1opl12 S < Vh.
Finally, we have
[IBBD C)0'112= max TT =TBDD (BD-C)u" -1|==|=
< 62z dist(U,, U.),
where the first step follows from Fact A.1 and the second step follows from Eq. (49).
42

---

Published as a conference paper at ICLR 2024
F.3 UPPER BOUNDING | R BY CONDITION NUMBER
To bound | R ll. we show that | RE'R 2 07/00. Similarly, we also bound
oi O (Re+1) by
showing
0i (Rii())))1) 2 oi/oj.
Lemma F.3. Let Re41 be the lower-triangular matrix obtained by QR decomposition of Ve+1 (see
Definition E. Let Ut be a jo-incoherent and dist(U,,U,, & 1/2. Let M be a (j, k)-incoherent matrix (see Definition 3.5). Let Q be defined as Definition A. 1.1. Let d2x E (0, 0.01) be defined as
Definition A.12.
Then, we have
Purt
E R S2 22/0//0-
Part 2.
oj miin RR+1)
22.01/08
Proof.
Note that
o m (R++1)
|> R
We show that
[|] = || Σ,,1 ||
< |2 ||:
< || |F -
(50)
where the first step follows from Σ- E. the third step follows from |ا S oj.
I, the second step follows from ||AB|| ||||| ||B|| and
We can show that
min x: =
|VEEU U,212 = min
U2211
s: ==1111=1
=m (.U.U.Z)
2 omin (E.) 0 (U. U.)
(at)² -2 (U. U:)
2 (a (1 - | 1)ll²).
where the first step follows from Part of Fact A.3 that V is matrix of SVD that has orthonormal basis, the second step follows from definition of amin the third step follows from Fact A. the fourth step follows from miin (2.) of and the last step follows from cos² sin 9 (sce Lemma A.9).
Now, we have
Tmin (Re+1) = min Re+12112
=
min Ro+122
=:||=||==1
min =||=||==1
|V.EUU U2z F2ll2
min
|V.EU U22122 - |F2||
=;|||||2=1
2 min
|V.E.U U2212- - IPI
=
43

---

Published as a conference paper at ICLR 2024
2 o V | Uvl1 oi | -
o dist U,)2 of |FE,
= o V
U,) 20 d2nk dis U.),
where the first step follows from the definition of miin+ the second step follows from Part of Fact A.3, the third step follows from Definition E.6, the fourth step follows from triangle inequality, the fifth step follows from the definition of || ||. the sixth step follows from Eq. (50), the seventh step follows from the definition of dist U2) (see Definition 3. and the last step follows from Lemma F.I.
We can obtain that
01/0% V1 dist(U,, U.) 2 (0i/0))0zzh dist U.)
E EE'RHII
For convenient, we define x = dist(U,, U.).
We define y = 2(or//o()dkkk
Then we now E [0, 1/2] and y E (0,0.1). Then we obtain that
0
S
VI x²
Using Part 1 of Fact A.4, we know that
v1 x² v. 1/2.
Thus, we have
E. Ri I 20///00
F.4
UPPER BOUNDING ||B CONSTANT
We analyze || ||. for variation of Lemma C.6 in Jain et al. (2013).
[m], and ||-'|| and show both of them are bounded by 2. We prove
Lemma F.4. Let M be a (j, k)) -icchhereere matrix (see Definition 3.5). Let p. be defined as Definition A. For each [n), define By kxk as follows
B : Σ UnAUTs
iEn.
Let U. be ua incoherent. Then, have:
Part 1. For all j [n].
|Bj 2
Part 2.
|B $
(51)
both events succeed with a probability at least - 1/ poly(n)
Proof. We have:
|| 1 112
m (B)
44

---

Published as a conference paper at ICLR 2024
ming / 1= [
m Br.
where z E Rnn and the first step follows from Fact 1, the second step follows from definition of mins and the last step follows from symmetric matrix.
Let vec (X), i.e., xp is the p-th column of X and zy is the j-th row of X. Let B, E R Let 2 E R. Now, Vi E Rnkk
x. Bx
Σ
x
Byaj
JE(n]
min
m (B)),
jE[n]
where the first step follows from B is a diagonal block matrix, and the second step follows from the definition of min for symmetric matrix.
Results would follow using the bound on amin (Bz), Vj E [m]] that we show below Lower bound miin BB):
Consider any R such that ||l||2 1.
We have:
Z Tw TTuBuu Byw
=w T
Σ
iEn..
(w, Ue,)?
Σ 6ig (w, U
xE[m]
where the first step follows from the definition of Z, the second step follows from the definition of B, the third step follows from the definition of inner product, and the last step follows from definition of S...
Note that,
B
E
81.5 (w, U1
+E[m]
1 Σ
E[8 (w, U2,
P [E[m)
1
Σ
p. (w. U2.)2
p vE(m)
Σ
(w, U,2))
*E(m)
Σ w UU,UU,,w
RE[m]
w T U,W
w w
1,
(52)
where the first step follows from the definition Z, the second step follows from being orthogonal, the third step follows from [[] p. the fourth step follows from simple algebra, the fifth step
45

---

Published as a conference paper at ICLR 2024
follows from the definition of the inner product, the sixth step follows from the fact that U3 is x matrix, the seventh step follows from U2U," Ix. and the last step follows from ||o||2 =
For variance, we have
B[Zz] = B(( 1 Σ
dus (w, U
rE(m]
:üg (w, 2
m
(
KGg (w, )²
pd
aE/m]
(W:
+
Σ
Elo. Ueit) El0 (wo, U1,52)
EE m
in f1z
plw, U,a)* + Σ
o² (1,,
Un,5 (w0, )2,
RE m
11212
1
(w, U,, -p Σ
(w, U,, +p p Σ
(w, Ue,)) U +p E
(w, 2 (wo, Uni22)
P iE[m
iE(mm
iE|m]
1
Σ
(w) Unia
Σ
(w, Unia)* +
Σ
(w, U1,3)
+ Σ
(w0, Un, Un
P LE iE(m)
re(m)
tE(m)
11 11
(
1)
(w, Uni) +
(w. 32
p
(m(m
kE(m
-
1)
(w, U2.))* + (B(Z))²
p
xE(m)
1
(w, Ue,a)* + (BiZ))²
p im1
1 12
(Bi2))²
(53)
p m
where the first step follows from the definition of Z, the second step follows from (ab)2 = a a²b²
the third step follows from E[ca] cBaaa. where e constant, the fourth step follows from Ela + bj = EEaa] + B(b). the fifth step follows from B[5? and subtracting the same thing, the seventh step follows [ = p. the sixth step follows from adding simple algebra, the eighth step follows
from simple algebra, the ninth step follows from Eq. (52), the tenth step follows from ( - 1) S
the last step follows from Claim A.
Then, we can compute
Var [
E[Z?] (B(2))2
(EE2)) (
mp
p
mp
where the first step follows from the definition of variance, the second step follows from Eq. (53), and the third step follows from simple algebra.
Similarly.
max (ww :[(m]
mp
46

---

Published as a conference paper at ICLR 2024
Hence, using Bernstein's inequality (Lemma A.18):
/2 mpp
Pr[1 E[Z]
82dl I exp
82k/3 /3 p2
That is, by using p in the statement of the lemma with the above equation and using union bound, we get (w.p. > 1/ 1/n") Ve E R E [n]
w T Byw 2 1 62A-
That is, Vi E [n]].
min (B,) 2 (1 - 82x) 2 0.5.
F,5 UPPER BOUNDING ||C,]| BY + 82k
Now, we analyze ||C]]| and show that it is bounded by 1 + 822 for all E [m]. We prove variation of Lemma C.7 in Jain et al. (2013).
Lemma F.5. For each j E [m], we define Cj E &R as follows
C P JED..
U,JUA,
Then, we have: for all j E [n]]
|||]|| S 1 + 82s.
Proof. Let x E R and y E R& be two arbitrary unit vectors. We define Z x TTC. Then,
z = ==x CT
1 Σ
x TuU y Un
1
Σ p
Sayz T ULi y Un.i.
where the first step follows from the definition of Z, the second step follows from the the notation Drg C [m] being defined in Definition A.13, and the third step follows from definition of 8 which is 1 i E D.. and 0 if & P..g.
Note that,
E|Z =
8 Un, v...v' U.d U.,.
1=1
1 m
LE 1l |x UU, y Un TT..
p
par Ut.i y U..i
P
Σ UUS .y" yTT. TU.
U.UYy U.y.
(54)
where the first step follows from the definition of Z, the second step follows from the linearity of expectation (E(a + b) = [[a] + E(b)), the third step follows from E662 p, the fourth step follows from simple algebra, and the last step follows from the fact that U is x k matrix.
47

---

Published as a conference paper at ICLR 2024
We compute the second moment
B|Z²| = E[(
5 Ut y U
E
6 T Uv, y Un
p
m
1102,1(x U1 y Un,)++
Σ
Uni y U.,,, Elö Uess y U.,)))
pd
$1512
p(a T Uv, UU,,)² + Σ
p²x
Ues y UnA U Ueiz y Un,22)
i1
x T UL V....... U,,,)²+++ +p E
Uni Uns
UnS Unia
Uess v Un
x
$1712
UnS y U2,))² p
xx ULs v U, + Σ
x U1s U,,)²
i=1
i=1
+P
Σ
Un. y Un x' Units v (.
117
U1, U,,))
U1 U,,))
p
1=1
i=1
x U..)) (y Unii) 2 +
Σ
x Ut y U+,)?
T
1=1
T U,,)) (y TyT U,,)² (B|2))2
pºk k + (1EZ2)) mp
(55)
where the first step follows from the definition of Z, the second step follows from E[ca] = c cE[a]] where e constant, the third step follows from Eja - b] E[a] E[b]. the fourth step follows from [5 [. = p. the fifth step follows from simple algebra, the sixth step follows from adding and subtracting the same thing, the seventh step follows from simple algebra, the eighth step follows from (zy)² x y² the ninth step follows Eq. (54), the 10th step follows from Claim A.
Then, we have
Var[Z]
E[Zz] (B[Z))²
12k
+ (E[Z))² - (E(2))2
mp
2
mp
where the first step follows from the definition of variance, the second step follows from Eq. (55), and the last step follows from simple algebra.
We have
pgkk m
max
U1,
U.Al <
1m/ml
Lemma now follows from using Bernstein's inequality.
48

---

Published as a conference paper at ICLR 2024
G A PERTURBATION THEORY FOR DISTANCES AND INCOHERENCE
In this section, we present one of the main technical contributions of this paper - a perturbation theory for distances and matrix incoherence. Our main technology is reduction from incoherence to leverage score, then utilize different parametrizations of leverage score to obtain a bound on incoherence.
In Section G.I. show to bound distance by the spectral norm. In Section G.2 we present the perturbation related lemma that is from right to left low rank factor. In Section G.3, we assert toll from the previous work: leverage score changes under row perturbation. In Section G.4, we elucidate the perturbation related lemma that from approximate exact updates.
G.1 BOUND DISTANCE BY SPECTRAL NORM
The following lemma establishes relationship between dist and the spectral norm.
Lemma G.1 (Bounded distance by spectral). Let X.Y E Runk be two matrices (not necessarily orthogonal). Suppose |X 2 m (aio( (Y). Then
dist X, Y) v 4|| Yllomin (X) (X)- min! (Y) 0.5
Proof.
cos 000, Y) "Espan(X) ( eEspan(Y)
min
|u ||||
u v
min
u |||
WE
Xw,u=Y Yu
|
2
+
|100
min
WER
2
||
|0|||
== -=Xw,u=Yu
1
1/u
min
2
|
|||||
Xw,v=Yw
1
||X
||2
min
1
WER
2
||u
|||||||||
1
|| Y11 [0
min
1
WE
2
mmin min (Y 10
X mmin
o (X) Jmin (8)
(56)
where the first step follows from the definition of cos 0(X: Y), the second step follows from max, X; 2 X; the third step follows from simple algebra, the fourth step follows from a² +52 > 2ab, the fifth step follows from ||u v112 |X Ywll2 S ||X [ 12.. the sixth step follows from ||u||2 |Xwll2 amin [x)[,/l.. and the last step follows from canceling the term w|ll
Thus,
sin ((X,V) = - cos² 0(X,Y)
2
/ |1 Y11 (X) Omia (1)
$
Omin
$ (1
||- - 2112 σ min (X) (X)-lomiu
(Y)ia(() (Y)
= || Y1? mmin (X) amin (Y)-1
(57)
where the first step follows from cos 8(X, + sin? 8(X, Y) = (see Lemma A.9) and the second
steep follows from Eq. (56), the third step follows from (a b)2 2² b2 2ab I -a² 2ab. and the fourth step follows from simple algebra.
Note that dist(X X, Y) sin (X, Y). thus, we complete the proof.
49

---

Published as a conference paper at ICLR 2024
G.2 FROM RIGHT TO LEFT FACTOR
Given an orthonormal basis Z and target matrix M, suppose M X for some matrix X. We prove some relations on singular values X and M given some conditions on Z. Lemma G.2. Let M U.E.V...
Suppose the matrix Z E Baak satisfies that
Raxk is an orthonormal basis dist(2,V..) & vI az
X E B.nkk denote matrix that
M = XZ.
(58)
Then, we have
Mmiu (X) 2 a Fmin (M)
and
mmax (X) S max (M)
Proof. We have
IV. Z = dist(Z,V.)
5v1-aa
(59)
where the first step follows from the definition of distance and the second step follows from the Lemma statement.
Using sin + cos² (Lemma A.9), we have
muin Z) + |V - =1
(60)
We can show
Mmin (V. 2) = V V. ~
2 (1
02
(61)
where the first step follows from Eq. (59), the second step follows from Eq. (60), and the third step follows from simple algebra.
We have
Omiu (X) U (M (Z (t)
O (U,E.V (ZT)
m (E.V ((T)))
m (I.V.T ZZ)
Gmin (Ex) Tmin (V. (2)
miin (M) mmin (V, Z)
min (M) a.
where the first step follows from Eq. (58), the second step follows from M = =U,E,V V.T the third step follows from U, has orthonormal columns, the fourth step follows from (z Z, the fifth step follows from part Fact A.I, the sixth step follows from definition of matrix M E xm and the last step follows from Eq. (61).
50

---

Published as a conference paper at ICLR 2024
G.3 LEVERAGE SCORE CHANGE UNDER Row PERTURBATIONS
We analyze the change to leverage scores when the rows are perturbed in a structured manner.
Lemma G.3. Given two matrices A E Rm*k and B Rm For each E [m], let a, denote the i-th row of matrix A. For each i [m]] let by denote the i-th row of matrix B.
If
||A - B|| S co
Co S 2 min (A)
then we have
III A)
[I(B" B) 1/l12l 7 (A)-'x² n:* (A)).
Proof. Without loss of generality assuming [(A A)-1/2a;ll /|2 2 [I B) B)-1//bb|| as the other case symmetric. Note that by the difference of squares formula, know that
A) -) 2 [I B)-
[I(A A)- - B)
[[ A) 1//-1/2,,11 + IIB 1/2b//b,
it suffices to provide an upper bound on the numerator and lower bound on the denominator.
Lower bound on denominator. The lower bound is relatively straightforward:
(A A)-1/2a,lle + [I(B B) 11/2bb 2
las112 +
l
o (max(A)
m (B)
1
||ai12 +
11b/12
max (A) (A)
mmax (B) Eg
las112 + |bbll2
max (A) Eo
20mi (A) ED
20 (A)
k (A)
where we use Weyl's inequality (Lemma A.2) uppper bound max by (Ax cp. co S 20 miin (A) and ||a/||2 S ||-
Upper bound on the numerator. The upper bound can be obtained via a chain of triangle inequalities.
We start by proving some auxiliary result: First, we can show
A- BI1 = | A A B +
A
B
BT BTB
A A - A B
|A B BT Bl
m (A)eo + mmax (B)ee
< (2o max (A) + E0) 60
< max (A) 60
We can then prove the discrepancy between inverses:
[I(AT A) - - B)
2 < [I B) -| (1A A) (BT B)]
2 2 (2/0min (A)3) |IA A) (B B)Ll
22 (2/0min (A)3)2 (30max (A) Ea)
-4x((Ao _ (A)co.
where the first step is by Lemma A.15.
51

---

Published as a conference paper at ICLR 2024
Finally, note
|o (A" A) (B b;l
b, $ a, (A A) a; - (A" A) b,1 + a. [ (A A) o B) B) + |,; (B B) -b) 6, (B -) by
14:122 ||;; - 1bbl1 |1<47 + ||b:
11(A II(AT)) A) - (B B) |b:lla 1la,-b:ll B)-11
m00 (A)lla:l12 + 24c (A)) (4) + (colaa112) co (A) cu) 21b1111
I cuk(A)ombn min (A) + 48 x² m (A)
co ( (A)
8
< 50 (A)o (A).
Put things together. The final upper bound can be obtained by taking the ratio between these two terms:
(I //2 aill II(B" B) 1/2112 S 75cmn* (A)omiu (A).
This completes the proof.
G.4 FROM APPROXIMATE TO EXACT DISTANCE AND INCOHERENCE
Given a matrix that is incoherent, we show that if matrix Y is close to X enough in spectral norm, then it also preserves the distance and incoherence of Y.
Lemma G.4. Let X E Rmnk and X UEVT be its SVD. Then
|lu:12 xx (x
where us, denote the i-th row of and X respectively.
Proof. Let form the projection matrix X(X X) i-th diagonal of the projection matrix.
18-1x 'x, note that the quantity the RHS is the
X(X x) = -UV VVVVV((VVVTT) (VE
=UUT,
where the first step follows from the Lemma statement: X = USVT, the second step follows from simple algebra, the third step follows from simple algebra.
The i-th diagonal of T is then u. un 1u.11.. desired.
Lemma G.5. Let X, Taxk Let po 2 Let E 1).
Suppose that
is μo incoherent, i.e. |I(x)) I PoVk/
Let IY - XII Ev-
Let < 0.1 10.1-Omin(X
For each i E [m], let X; denote the i-th row of matrix E BRmnk Let x(X) = (X)a mX)
be the condition number of X. Let Cak = O(ca (m 14 (X)) T (x)-)))
Then, we have
Part (ist((YUU)) S dist(X, U*) + 6sk-
Part 2. Y is pr Esk incoherent, i.e., [[(Uv))ll (No (kk
52

---

Published as a conference paper at ICLR 2024
Remark G.6. Eventually choose Cak c/O(T) where is the final accuracy parameter (0, 1/ and T is the number of iterations. We will use this lemma for (T) times, and each time we incur an extra e/ e/O(T) error. Our ultimate goal is shrink dist(Y. (Y, U.) ((c) after T iterations. Since all iterations only incur extra ((c) error, the final dist(Y. U.) is still bounded by ②(e). When we use this Lemma, x(X) is always bounded by ((s(M)) where M is the ground truth matrix in matrix completion problem. Note that our running time blowup is only logarithmiccaly in 1/Eo. thus it's always fine to
be 1/ poly(n, K, T) smaller. Similar argument will hold for part 2 incoherent. Since Pu 2 1, over all the iterations, the incoherent parameter is within 2po-
Proof. We prove two parts separately.
Proof of Part 1. From lemma assumptions, we have
|| X S S m.)
Then, we know that
Mmin (Y) 2 0.507 (X).
(62)
We have
(Y,s.(YUU)) S dist(X,U.) + XY,
< dist(XXUS, + ||Y -X|1 mmin (X) -0.5 mmin (V) -
dist(X,U, 60 mmin (x)-0. a (V) (V)-0.5 0.5
s dist(X, U.) + 2EO Jmin (X)
s dist(X, U.) + Cak:
where the first step follows from triangle inequality, the second step follows from Lemma G.1, the third step follows from lemma statement ||Y - X|| co. the fourth step follows from Eq. (62), the last step follows from definition 6sk in the lemma statement.
Proof of Part 2. By Lemma G.3 and Lemma G.4, know that for any E [m]
(Ux Ml
(1 )ellal S 500 co omin (x) 1 (X).
Since X E mm is yo incoherent, by triangle inequality, we have
Iil2 z po v k/ m + 500 Tmin mmin (X)-1 (X) s (14 + (k) Vk/Vin
where the last step follows from definition of 6,k in the lemma statement. Thus, we complete the proof.
53


Reviews:
[{"review_id": "FbJy5Omh5w", "reviewer": "Reviewer_QBsW", "summary": "The authors give a nearly linear time algorithm (in the number of samples) for low-rank matrix completion. Specifically, they give a $O(|\\Omega| k)$ time alternating-minimization based algorithm that converges to the original underlying rank-$k$, $\\mu$-incoherent matrix $M \\in \\mathbb{R}^{m \\times n}$ when $|\\Omega| = \\tilde{O}(\\kappa^2 \\mu^2 n k^{4.5})$ samples are drawn from it. \n\nThe running time guarantee improves on a line of works, starting with that of Jain et. al (2013), on the efficiency of each step in AM framework -- going from $O(|\\Omega| k^2)$ running time to $O(|\\Omega| k)$ time. This compares however to a recent paper (that uses a different approach altogether) by Kelner et. al (2023) also achieving a $O(|\\Omega| k)$ running time with significantly fewer samples $|\\Omega| = O(n k^{2 + o(1)})$.\n\nThe improvement comes from solving each multiple response regression problem (to obtain the low-rank factorization $UV$) approximately instead of exactly. \n\nThe authors main technical contribution is in analyzing the how the error introduced in solving for $U$ and $V$ approximately, propagates in the iterative process. Specifically they show, using a careful double induction argument and an incoherence bound on the perturbation of row norms of incoherent matrices that the incoherence of the approximate factors in the $t$-th iteration $\\hat{U}_t, \\hat{V}_t$ as well as the exact solutions they are approximating $U_t, V_t$ are incoherent as well as approach the true subspaces $U^*, V^*$. \n\n\\textbf{References}\n\nPrateek Jain, Praneeth Netrapalli, and Sujay Sanghavi. Low-rank matrix completion using alternating\nminimization. In Proceedings of the forty-fifth annual ACM symposium on Theory of computing,\npp. 665–674, 2013\n\nJonathan Kelner, Jerry Li, Allen Liu, Aaron Sidford, and Kevin Tian. Matrix completion in almostverification time. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science,\nFOCS’23, 2023", "questions": "- Can you speak more to the significance of your result as compared to that of Kelner et. al (2023)? Specifically to the significance of the running time result given they achieve an asymptotically smaller running time result (please correct me if that is incorrect).", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Originality and Significance \nThe main contribution is the error analysis in the AM iterations, showing how the subspaces of the approximate solutions to the multiple response regressions $\\hat{U}_t, \\hat{V}_t$ converge to the true factors. The novelty comes from a double induction argument tying the incoherence and the closeness of the approximate solution to that of the exact solution in each iteration.\n\nThe technique sheds light on how AM algorithms for low-rank matrix completion can be sped-up (using approximate solvers). Since AM algorithms are popular in practice for this problem, this theoretical result can help substantiate the design of new more efficient algorithms.\n\nQuality and Clarity \nOverall the paper is well organized and written. The paper compares to relevant works sufficiently well and highlights the difference facets in which this result compares.", "weaknesses": "The main weakness might be in the significance of the final running time result in the context of the recent result by Kelner et. al (2023). Given that Kelner et. al achieve a significantly lower sample complexity of $\\tilde{O}(n k^2)$ (with no dependence on $\\kappa$), the novelty of this result could be questioned. Especially since the result is theoretical and no experiments have been provided to justify the efficiency of this approach.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w2oKeXSoif", "reviewer": "Reviewer_CTEU", "summary": "The paper studies the low rank matrix completion problem using alternating minimization. Existing algorithms based on alternating minimization for this problem (Jain, Netrapalli and Sanghavi) takes time $\\tilde{O}(|\\Omega|k^2)$ time where $\\Omega$ is the set of entries samples (nearly linear in $n$ for an $m \\times n$ incoherent matrix $M$) and $k$ is the target rank $(k<<m,n)$. The main computational bottleneck in alternating minimization comes from solving two multiple response regressions per iteration (once for U and once for V). The algorithm presented in this paper proposes solving the regression problems approximately using off-the shelf sketching based solvers which take nearly linear time in input size per iteration and thus, the time for solving each regression problem reduces to $\\tilde{O}(|\\Omega|k)$ (with extra $\\log(1/\\epsilon)$ steps for convergence). However, this complicates the analysis of the algorithm as the solution at every iteration cannot be written exactly in factorized form (so the previous analysis doesn't carry through). This runtime is equal to verification time for the solution upto polylog factors. To analyze this, an inductive argument is presented which shows that at every step, the approximate solution for $U$ or $V$ is close to the optimal solution $U^*$ and $V^*$. Moreover, it is shown that the incoherence of the exact solutions to the regression problem is preserved. Finally, to show that the incoherence of the approximate solution is also preserved, some matrix perturbation bounds are developed which show that as long as any two matrices are very close in spectral norm and one matrix is incoherent, the other matrix will also be incoherent. The sample complexity for the proposed algorithm is the same as that of the old algorithm.", "questions": "I could be misunderstanding the following steps in the proofs:\n\n1)  In forward error bound of Lemma B.5, I'm confused why the step ||Ax'-b-(Ax_{OPT}-b)||_2^2=||Ax'-b||_2^2-||Ax_{OPT}-b||_2^2 should be true. Why should the Pythagorean theorem hold in this case? Is Ax_{OPT}-b orthogonal to Ax'-b-(Ax_{OPT}-b) due to some condition? \nAlso, it seems A is assumed to have full column rank for the proof. Is A guaranteed to have full column rank whenever this result is applied i.e. in all iterations wheneer B.7 is invoked?\n\n2) In Lemma G.3, I'm not able to understand how $\\sigma_{min}(B) \\geq 0.5\\sigma_{min}(A)$ follows from $||A-B|| \\leq \\epsilon_o \\leq \\sigma_{min}(A)$.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1) The algorithm presented improves upon the runtime to make it nearly linear in verification time of the solution (up to log factors) i.e. $\\tilde{O}(|\\Omega|k)$. Previous alternating minimization based algorithms try to solve the regressions exactly and hence incur $\\tilde{O}(|\\Omega|k^2)$ time. Moreover, the proposed algorithm is practical and easy to implement as different off-the-shelf sketching based solvers can be used for this regression step. Also, the sample complexity remains the same as previous algorithms.\n\n2) Some interesting technical result are developed for the theoretical analysis of the algorithm. Specifically, some matrix perturbation bounds are proven which show that if a matrix with incoherent rows and columns is close in spectral norm to another matrix, that matrix will also be incoherent with the incoherence factor depending on the condition number of the first matrix. This seems to be an interesting result which could be of independent interest (though I have some questions related to the proof, please see the questions section).\n\nRemark: I haven't checked all the proofs in the appendix closely (especially the proofs related to induction in Section E and F of the appendix).", "weaknesses": "1) Though the runtime of the proposed algorithm is nearly linear in verification time and improves on the runtime compared to previous algorithms, without any discussion on computational limitations or lower bounds, it is hard to judge if this is indeed a significant theoretical result for this problem. Some discussion on runtime or sample complexity lower bound could be useful to understand what is the runtime one should be aiming for this problem.\n\n2) I'm unsure of certain key steps in the proofs for the forward error bound and the matrix perturbation results (please see the questions).\n\n3) The proofs in the appendix seems some confusing notations and sometimes uses certain notations without defining first them which cause problems while reading the proofs:\n\n  i) For example, in Lemma B.6, in some places $D_{W_i}$ seems to be indicate a matrix with $W_i$ on diagonal and on other places, a constant? When defining $\\| z\\|_w^2$ is should be just ||z ||_w^2=\\sum_{i=1}^n  w_i^2   I think for a vector $w$?\n\n  ii) Also, in definition 3.5, M is factorized as $U \\Sigma V^T$ while in the appendix, it seems $U^* \\Sigma^* V^*$ is used?\n\n\nThough the paper has interesting results, I'm recommending a borderline reject with a major concern being some of the key steps in the proofs (please see the questions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TeXoNm8p11", "reviewer": "Reviewer_kPm7", "summary": "In this work, the authors proposed the analysis of a robust and fast matrix completion algorithm based on the alternating minimization method. The total running time is linear in terms of the complexity of verifying the correctness of a completion.", "questions": "(1) Page 2, line 1: \\epsilon is not defined.\n\n(2) Page 2: \"as the perturbation to incoherence itself is not enough the algorithm approaches the true optimum\". It seems that the sentence is not complete.\n\n(3) Section 2: it might be better to compare the running time and sample complexity of alternating minimization and (stochastic) gradient descent.\n\n(4) Page 3: \"weighted low rank approximation\" -> \"weighted low-rank approximation\"\n\n(5) Page 5: the (total) instance size for the multiple response regression is not defined.\n\n(6) Section 4: I wonder if the partition of samples across iterations can be avoided? Namely, can we use all samples in different iterations? It would be better to clarify if the reuse of samples will fail the proposed algorithms, or only makes it technically difficult to prove the theoretical results.\n\n(7) Algorithm 1, line 5: it seems that U_0 is not used later in the algorithm.\n\n(8) Section 4.1: \"but to conclude the desired guarantee on the output, we also need to show that...\" It would be helpful to be more specific on the connection between the desired guarantee and the incoherence condition of \\hat{U}_t, \\hat{V}_t.\n\n(9) Theorem 4.2: I think it might be better to provide the main results (Theorem 4.2) a little earlier in the paper. The preparation for the statement of the main results is too long. The contents of Section 4 is basically a more detailed version of Section 1. Given the page limit, I feel that it is more efficient to simplify the discussion of techniques in Section 1, but include more details in Sections 4.1-4.3.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The work provides novel theoretical results on the alternating minimization approach for matrix completion. The results should be interesting to researchers in the optimization and machine learning fields.", "weaknesses": "In my opinion, the presentation of the paper can be improved. The current paper spends too much space on providing the intuition of the proposed results. This makes the paper too dry to understand. In addition, I think the authors need to include more technical details in the main body of the paper. Due to the time limit, I do not have time to check the appendix. So I cannot be sure about the correctness of the theoretical results given the limited information in the main manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)