Efficient Alternating Minimization with Applications to Weighted Low Rank Approximation

## Abstract

Weighted low rank approximation is a fundamental problem in numerical linear algebra, and it has many applications in machine learning. Given a matrix M ∈ ℝ n × n 𝑀 superscript ℝ 𝑛 𝑛 M\in\mathbb{R}^{n\times n} , a weight matrix W ∈ ℝ ≥ 0 n × n 𝑊 superscript subscript ℝ absent 0 𝑛 𝑛 W\in\mathbb{R}_{\geq 0}^{n\times n} , a parameter k 𝑘 k , the goal is to output two matrices U , V ∈ ℝ n × k 𝑈 𝑉 superscript ℝ 𝑛 𝑘 U,V\in\mathbb{R}^{n\times k} such that ‖ W ∘ ( M − U ​ V ⊤ ) ‖ F subscript norm 𝑊 𝑀 𝑈 superscript 𝑉 top 𝐹 \|W\circ(M-UV^{\top})\|_{F} is minimized, where ∘ \circ denotes the Hadamard product. Such a problem is known to be NP-hard and even hard to approximate assuming Exponential Time Hypothesis [ 15 , 35 ] . Meanwhile, alternating minimization is a good heuristic solution for approximating weighted low rank approximation. The work [ 27 ] shows that, under mild assumptions, alternating minimization does provide provable guarantees. In this work, we develop an efficient and robust framework for alternating minimization. For weighted low rank approximation, this improves the runtime of [ 27 ] from n 2 ​ k 2 superscript 𝑛 2 superscript 𝑘 2 n^{2}k^{2} to n 2 ​ k superscript 𝑛 2 𝑘 n^{2}k . At the heart of our work framework is a high-accuracy multiple response regression solver together with a robust analysis of alternating minimization.

## 1 Introduction

Given a matrix $M\in\mathbb{R}^{n\times n}$, the low rank approximation problem with rank $k$ asks us to find a pair of matrices $\widetilde{U},\widetilde{V}\in\mathbb{R}^{n\times k}$ such that $\|M-\widetilde{U}\widetilde{V}^{\top}\|_{F}$ is minimized over all rank $k$ matrices $U$ and $V$, where $\|\cdot\|_{F}$ is the Frobenious norm of a matrix. Finding a low rank approximation efficiently is a core algorithmic problem that is well studied in machine learning, numerical linear algebra, and theoretical computer science. The exact solution follows directly from SVD: let $M=U\Sigma V^{\top}$ and set $\widetilde{U}=U_{k}\sqrt{\Sigma_{k}}$, $\widetilde{V}=V_{k}\sqrt{\Sigma_{k}}$, i.e., picking the space spanned by the top-$k$ singular values and corresponding singular vectors. Faster algorithms utilizing linear sketches can run in input sparsity time []. In addition to the standard model and Frobenious norm, low rank approximation has also been investigated in distributed setting [], for entrywise $\ell_{1}$ norm [] and for tensors [].

In practice, it is often the case that some entries of $M$ are more important than others, so it’s natural to look for a *weighted* low rank approximation. More specifically, given target matrix $M\in\mathbb{R}^{n\times n}$ and a non-negative weight matrix $W\in\mathbb{R}_{\geq 0}^{n\times n}$, the goal is to find $\widetilde{U},\widetilde{V}\in\mathbb{R}^{n\times k}$ with $\|W\circ(M-\widetilde{U}\widetilde{V}^{\top})\|_{F}$ minimized, where $\circ$ is the Hadamard product of two matrices. Weighted low rank approximation formulation covers many interesting matrix problems, for example, the classic low rank approximation is by setting $W={\bf 1}_{n}{\bf 1}_{n}^{\top}$ and the low rank matrix completion [] is by setting $W$ to be a binary matrix. In addition to its theoretical importance, weighted low rank approximation also has a significant practical impact in many fields, such as natural language processing [, , ], collaborative filtering [, , , ], ecology [, ], and chromatin conformation reconstruction [].

The study of algorithms for weighted low rank approximation can dated back to []. Gillis and Glineur [] have shown that the general weighted low rank approximation is NP-hard even if the ground truth matrix is rank $1$. The hardness is further enhanced by [] by showing that assuming Random Exponential Time Hypothesis, the problem is hard to approximate. Despite its hardness, many heuristic approaches have been proposed and witnessed many successes. For example, Shpak [] implements gradient-based algorithms, while [, ] use the alternating minimization framework. [] develops algorithm based on expectation-maximization (EM). Unfortunately, all these approaches are without provable guarantees. [] is the first to provide algorithms with theoretical guarantees. They propose algorithms with parameterized complexity on different parameters of $W$, such as the number of distinct columns or low rank. In general, these algorithms are not polynomial which is also indicated by their lower bound results. [] subsequently studies the weighted low rank approximation problem with regularization, and they manage to obtain an improved running time depending on the statistical dimension of the input, rather than the rank.

How to bypass the barrier of [] while still getting provable guarantees? [] analyzes the performance of alternating minimization when 1). ground truth is incoherent, 2). weight matrix has a spectral gap to all-$1$’s matrix, and 3). weight matrix is non-degenerate. Under these assumptions, they show that the alternating minimization algorithm provably finds a pair of matrices $\widetilde{U},\widetilde{V}\in\mathbb{R}^{n\times k}$ such that $\|M-\widetilde{U}\widetilde{V}^{\top}\|\leq O(k)\cdot\|W\circ\overline{M}\|+\epsilon$, where $\overline{M}\in\mathbb{R}^{n\times n}$ is the rank $n-k$ component of $M$ that removes the top-$k$ singular values and directions and $\|\cdot\|$ is the spectral norm of a matrix. This provides a solid theoretical ground on why alternating minimization works for weighted low rank approximation.

While the [] analysis provides a polynomial time algorithm for weighted low rank approximation under certain assumptions, the algorithm itself is still far from efficient. In particular, the alternating minimization framework requires one to solve $O(n)$ different linear regressions exactly per iteration. The overall runtime of their algorithm is $O((n^{2}k^{2}+nk^{3})\log(1/\epsilon))$, making it inefficient for practical deployment. Moreover, their analysis is non-robust, meaning that it cannot account for the error at any step. This is in drastic contrast with practice, where floating point errors and inexact solvers are used everywhere. In fact, there are good reasons for them to mandate exact regression solvers, as their algorithm only requires $\log(1/\epsilon)$ iterations to converge and any fast but approximate regression solver might break the nice convergence behavior of the algorithm. Hence, we ask the following question:

Is it possible to obtain a faster and more robust alternating minimization algorithm with a similar convergence rate?

In this paper, we provide a positive answer to this question.

###### Theorem 1.1 (Informal version of Theorem 5.6 ) .

There is an algorithm (see Algorithm [1](#alg1)) that runs in $\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$ and solves the weighted low-rank approximation problem.

###### Theorem 1.1 (Informal version of Theorem 5.6 ) .

#### Roadmap.

In Section [2](#S2), we introduce several basic notations and definitions which we will use throughout this paper.
In Section [3](#S3), we give a brief overview of our techniques. In Section [4](#S4), we provide and explain the important definitions and properties that we will be using. In Section [5](#S5), we present our main result. In Section [6](#S6), we give a conclusion for this paper.

Figure: Algorithm 1 Main Algorithm. Note the blue lines in the following algorithm are only used for the purpose of analysis. The Clip procedure zeros out rows whose $\ell_{2}$ norm are large, and the QR procedure computes the QR decomposition of the matrix and outputs the orthonormal factor $Q$.

## 2 Notation

Let $n,m$ be arbitrary positive integers. We define a set $[n]$ as $\{1,2,\cdots,n\}$. We use $\mathbb{R}$, $\mathbb{R}^{m}$, $\mathbb{R}_{\geq 0}^{m}$, and $\mathbb{R}^{n\times m}$ to denote the sets containing all the real numbers, $m$ dimensional vectors with real entries, $m$ dimensional vectors with non-negative real entries, and $n\times m$ matrices with real entries, respectively.

Let $x\in\mathbb{R}^{m}$ and $w\in\mathbb{R}_{\geq 0}^{m}$. Let $i\in[m]$. Let $x_{i}\in\mathbb{R}$ represent the $i$-th entry of $x$. We use $\sqrt{x}\in\mathbb{R}^{m}$ to represent a vector satisfying $\sqrt{x}_{i}=\sqrt{x_{i}}$. We define $\|x\|_{w}:=(\sum_{i=1}^{n}w_{i}x_{i}^{2})^{1/2}$.

Let $A,W$ be two arbitrary matrices in $\mathbb{R}^{n\times m}$. Let $i\in[n]$ and $j\in[m]$. We use $A_{i,:}\in\mathbb{R}^{m}$ to represent a column vector that is equal to the $i$-th row of $A$ and $A_{:,j}\in\mathbb{R}^{n}$ represent a column vector that is equal to the $j$-th column of $A$. $A_{i,j}\in\mathbb{R}$ represents a entry of $A$, located at the $i$-th row and $j$-th column. $\mathrm{diag}(x)\in\mathbb{R}^{n\times n}$ represents the matrix satisfying $\mathrm{diag}(x)_{i,j}=x_{i}$ if $i=j$ and $\mathrm{diag}(x)_{i,j}=0$ if $i\neq j$. $\operatorname{nnz}(A)$ represents the number of nonzero entries of $A$.

Suppose that $n\geq m$. We represent the spectral norm of $A$ as $\|A\|=\sup_{x\in\mathbb{R}^{m}}\|Ax\|_{2}/\|x\|_{2}$, represent the Frobenius norm of $A$ as $\|A\|_{F}$, which is equal to $(\sum_{i=1}^{n}\sum_{j=1}^{m}A_{i,j}^{2})^{1/2}$, and represent $\|A\|_{\infty,1}$ as $\max\{\max_{i\in[n]}\|A_{i,:}\|_{1},\max_{j\in[m]}\|A_{:,j}\|_{1}\}$.

Further suppose that $A$ has the singular value decomposition (SVD), which is $U\Sigma V^{\top}$. Then, we have $U\in\mathbb{R}^{n\times m}$ and $\Sigma,V\in\mathbb{R}^{m\times m}$, where $U$ has orthonormal columns and $\Sigma$ is diagonal. The Moore-Penrose pseudoinverse of a matrix $A$ is $A^{\dagger}=V\Sigma^{-1}U^{\top}$. If $\Sigma$ is a sorted diagonal matrix and $\sigma_{1},\cdots,\sigma_{m}$ represent the diagonal entries of $\Sigma$, then we use $\sigma_{i}$ to represent the $i$-th singular value of $A$, namely $\sigma_{i}(A)$. We define $\sigma_{\min}(A):=\min_{x}\|Ax\|_{2}/\|x\|_{2}$ and $\sigma_{\max}(A):=\max_{x}\|Ax\|_{2}/\|x\|_{2}$.

Now, we suppose that $m=n$, namely $A,W\in\mathbb{R}^{n\times n}$. We define $\|A\|_{W}:=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{n}W_{i,j}A_{i,j}^{2}}$. $W\circ A$ is a matrix whose entries are defined as $(W\circ A)_{i,j}:=W_{i,j}A_{i,j}$. We define $D_{W_{i}}:=\mathrm{diag}(W_{i,:})$. If $A$ is invertible, then the true inverse of $A$ is denoted as $A^{-1}$ and $\|A\|=\sigma_{\min}(A^{-1})$. If $A$ is symmetric, then we define as $U\Lambda U^{\top}$ the eigenvalue decomposition of $A$, where $\Lambda$ is a diagonal matrix. Let $\lambda_{1},\cdots,\lambda_{n}$ represent the entries on diagonal of $\Lambda\in\mathbb{R}^{n\times n}$. $\lambda_{i}$ is called the $i$-th eigenvalue, namely $\lambda_{i}(B)$. Furthermore, the eigenvalue and the singular value satisfy $\sigma_{i}^{2}(A)=\lambda_{i}(A^{\top}A)$.

For any function $f$, we use $\widetilde{O}(f)$ to denote $f\cdot\operatorname{poly}(\log f)$.

## 3 Technique Overview

In this section, we introduce the techniques we use in this paper.
Before demonstrating our main techniques, let us first review the algorithm of []. At each iteration, the algorithm alternates by solving two weighted multiple response regressions: starting with an initial matrix $Y$, it tries to find a matrix $X\in\mathbb{R}^{n\times k}$ that minimizes $\|W\circ(M-XY^{\top})\|_{F}^{2}$, then they zero out the rows of $X$ with large $\ell_{2}$ norms and use the QR factor of $X$ to proceed. Then, they alternate and solve $\min_{Y\in\mathbb{R}^{n\times k}}\|W\circ(M-XY^{\top})\|_{F}^{2}$ given the new $X$. After proper zeroing out and QR, the algorithm proceeds to the next iteration. The main runtime bottleneck is to solve the weighted multiple response regression per iteration.

Following the trend of low rank approximation [] and fixed parameter tractable algorithm for weighted low rank approximation [], it is natural to consider using sketching to speed up the multiple response regression solves. Let us take the regression

$$ $\displaystyle\min_{Y\in\mathbb{R}^{n\times k}}\|W\circ(M-XY^{\top})\|_{F}^{2}$ (1) $$

as an example. Let $D_{\sqrt{W_{i}}}$ denote the $n\times n$ diagonal matrix that puts $\sqrt{W_{i}}$ on the diagonal, where $W_{i}$ is the $i$-th row of $W$. It is not hard to verify that ([1](#S3.E1)) can be cast into $n$ linear regressions (see details in Claim [A.2](#A1.Thmtheorem2)), each of which is in the form of

$$ $\displaystyle\min_{y\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}M_{:,i}-D_{\sqrt{W_{i}}}Xy\|_{2}^{2},$ $$

to solve these regressions fast. One can pick a random sketching matrix $S\in\mathbb{R}^{s\times n}$ where $s=O(\epsilon_{0}^{-2}k)$ and instead solve

$$ $\displaystyle\min_{y\in\mathbb{R}^{k}}\|SD_{\sqrt{W_{i}}}M_{:,i}-SD_{\sqrt{W_{i}}}Xy\|_{2}^{2}.$ $$

By picking a sparse sketching matrix $S$, the above regression can be solved in $\widetilde{O}(\epsilon_{0}^{-1}\operatorname{nnz}(X)+\epsilon_{0}^{-2}k^{3})$ time with high probability, and the output solution $y$ has cost at most $(1+\epsilon_{0})\cdot{\rm OPT}$ where OPT is the optimal regression cost. Aggregate over $n$ regressions, this gives an $\widetilde{O}(\epsilon_{0}^{-1}n\cdot\operatorname{nnz}(X)+\epsilon_{0}^{-2}nk^{3})$ time per iteration (see Lemma [C.3](#A3.Thmtheorem3)).

This approach, however, has several drawbacks that make it infeasible for our application. The first is the error guarantee of such approximates regression solves. Essentially, we compute a matrix $\widetilde{Y}\in\mathbb{R}^{n\times k}$ such that

$$ $\displaystyle\|W\circ(M-X\widetilde{Y}^{\top})\|_{F}^{2}\leq(1+\epsilon_{0})\cdot\min_{Y\in\mathbb{R}^{n\times k}}\|W\circ(M-XY^{\top})\|_{F}^{2},$ $$

in other words, the approximate solution $\widetilde{Y}$ provides a relative *backward error*. Unfortunately, the backward error is much less helpful when we want to analyze how close $\widetilde{Y}$ is to the optimal solution $Y$, i.e., the *forward error*. It is possible to translate backward error to forward error at the expense of dependence on other terms such as multiplicatively depending on the cost of the regression and the spectral norm of $X^{\dagger}$, the pseudo inverse of $X$. To cancel out the effect of these extra terms, we will have to set the error parameter $\epsilon_{0}$ to be very small, thus, a polynomial dependence on $\epsilon_{0}^{-1}$ in the running time is unacceptable.

This motivates us to design a fast and high precision regression solver whose $\epsilon_{0}$ dependence is $\log(1/\epsilon_{0})$ (see Lemma [4.8](#S4.Thmtheorem8)). Given an algorithm that produces an $(1+\epsilon_{0})$ relative backward error of regression in $\log(1/\epsilon_{0})$ iterations, we can set $\epsilon_{0}$ to inverse proportionally to ${\rm OPT}\cdot\|(W\circ X)^{\dagger}\|$. As the spectral norm of $(W\circ X)^{\dagger}$ is polynomially bounded, this incurs an extra $\log n$ term in the runtime. It remains to devise a regression solver with such runtime behavior. Our approach is to use the sketch as a preconditioner: we pick a dense sketching matrix $S\in\mathbb{R}^{s\times n}$ with $s=\widetilde{O}(k)$ rows such as for any $k$ dimensional vector $x$, $\|Sx\|_{2}=(1\pm O(1))\cdot\|x\|_{2}$. We then apply $S$ to $D_{\sqrt{W_{i}}}X$ to form a short fat matrix and compute the QR decomposition of this matrix. It turns out that the right QR factor of $SD_{\sqrt{W_{i}}}X$ is a good preconditioner to $D_{\sqrt{W_{i}}}X$. We then use $S$ to find a constant approximation to the regression problem and utilize it as a starting point. The algorithm then iteratively performs gradient descent to optimize towards an $\epsilon$-approximate solution. Overall, such an algorithm takes $\log(1/\epsilon_{0})$ iterations to converge, and each iteration can be implemented in $\widetilde{O}(nk)$ time. Plus the extra $\widetilde{O}(nk+k^{3})$ time to compute the initial solution, this yields an algorithm that runs in $\widetilde{O}((nk+k^{3})\log(1/\epsilon_{0}))$ time to compute an $\epsilon_{0}$ backward error solution. Note here we sacrifice the input sparsity time in exchange of a sketching matrix that works with high probability. This also accounts for the fact that both $X$ and $Y$ are quantities changed across iterations and the sparsity cannot be controlled.

We want to remark that our high precision and dense regression solver not only works for weighted low rank approximation, but for any alternating minimization frameworks that require one to solve $O(1)$ multiple response regressions per iteration. Due to the good error dependence, the overall $\log(1/\epsilon)$ convergence is well-preserved, even though each iteration is only solved approximately. We believe this high precision solver will also find its use in problems like (low rank) matrix sensing and matrix completion and tasks in which forward error for multiple response regression is required.

In addition to our high-accuracy, high probability solver, we also devise a robust analytical framework for alternating minimization, which is the core to enable us with fast approximate solvers. In particular, we show that if we only output a matrix $\widetilde{Y}$ that is close to the exact regression solution $Y$ in the spectral norm, then the alternating minimization still converges to the fixed point $\|W\circ\overline{M}\|$ with good speed. Our analysis uses a different strategy from [] where they heavily rely on the closed-form of the regression solution. We show that the guarantees of the algorithm mainly follow from the $\ell_{2}$ row norm of the matrices. Specifically, given two matrices whose $\ell_{2}$ row norms are close for each corresponding rows, we prove that statistics such as incoherence can be well-preserved. Our argument relies on a novel interpolation between different equivalent formulations of incoherence, especially the point of view of leverage scores. We believe such an analytical framework will also be extremely helpful for robustifying the alternating minimization framework for faster matrix sensing and matrix completion [].

## 4 High Accuracy Weighted Regression Solver

In Section [4.1](#S4.SS1), we explain the definition of Subsampled randomized Hadamard transform (SRHT) and analyze its properties. In Section [4.2](#S4.SS2), we analyze the forward error of regression. In Section [4.3](#S4.SS3), we study the properties of the weighted linear regression.

### 4.1 Dense, high accuracy and iterative solver

In this section, we first give the formal definition of SRHT matrix and then analyze its properties.

###### Definition 4.1 (Subsampled randomized Hadamard transform ( SRHT ), [ 25 ] ) .

Let $P$ be an arbitrary matrix in $\{0,1\}^{m\times n}$ and for each row of $P$, there exists a $1$ at an arbitrary place.

Let $H\in\{-1,1\}^{n\times n}$ be the Hadamard matrix.

Let $D\in\mathbb{R}^{n\times n}$ be a diagonal matrix, whose diagonal entries are all in $\{-1,+1\}$ with the same probability.

We define the SRHT matrix $S\in\mathbb{R}^{m\times n}$ as

$$ $\displaystyle S:=\frac{1}{\sqrt{m}}PHD.$ $$

###### Remark 4.2 .

Let $A$ be a matrix whose dimension is $n\times d$.

Then, it takes $O(nd\log n)$ time to compute $SA$.

###### Lemma 4.3 .

$S\in\mathbb{R}^{m\times n}$ is a SRHT matrix (see Definition [4.1](#S4.Thmtheorem1)).

Let $\epsilon,\delta\in(0,1)$ be parameters.

Let $d$ be an arbitrary integer, which is less than or equal to $n$.

Suppose $m=O(\epsilon^{-2}d\log(n/\delta))$.

Let $U\in\mathbb{R}^{n\times d}$ be a fixed orthonormal basis.

Then, the singular values of the matrix $SU$ are in the interval $[1-\epsilon,1+\epsilon]$, with probability at least $1-\delta$. We say that $S$ is an $(\epsilon,\delta)$ oblivious subspace embedding.

###### Lemma 4.4 (Dense and high accuracy regression, Lemma 5.4 in [ 18 ] ) .

Let $A$ be an arbitrary matrix in $\mathbb{R}^{n\times d}$.

Let $b$ be an arbitrary vector in $\mathbb{R}^{n}$.

Let $\epsilon\in(0,0.1)$.

Let $\delta\in(0,0.1)$.

Then, there exists an algorithm that takes time

$$ $\displaystyle O((nd\log n+d^{3}\log^{2}(n/\delta))\log(1/\epsilon))$ $$

which outputs a vector $x^{\prime}\in\mathbb{R}^{d}$ satisfying

$$ $\displaystyle\|Ax^{\prime}-b\|_{2}\leq(1+\epsilon)\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$ $$

holds with probability $1-\delta$.

Figure: Algorithm 2 High precision solver

###### Definition 4.1 (Subsampled randomized Hadamard transform ( SRHT ), [ 25 ] ) .

###### Remark 4.2 .

###### Lemma 4.3 .

###### Lemma 4.4 (Dense and high accuracy regression, Lemma 5.4 in [ 18 ] ) .

### 4.2 Forward error of regression

We start to analyze the forward error of regression in order to choose parameters for the Algorithm [1](#alg1). In this section, the translation of the error from $\|Ax^{\prime}-b\|_{2}$ to $\|x^{\prime}-x_{\mathrm{OPT}}\|_{2}$ is shown.

###### Lemma 4.5 (Forward error, Lemma 5.5 in [ 18 ] ) .

Let $A$ be an arbitrary matrix in $\mathbb{R}^{n\times d}$, which has the full column rank.

Let $b$ be an arbitrary vector in $\mathbb{R}^{n}$.

$x_{\operatorname{OPT}}$ represents the exact solution to the regression problem.

Suppose that there exists a vector $x^{\prime}\in\mathbb{R}^{d}$, satisfying

$$ $\displaystyle\|Ax^{\prime}-b\|_{2}\leq(1+\epsilon)\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}.$ $$

Then, we have

$$ $\displaystyle\|x^{\prime}-x_{\rm OPT}\|_{2}\leq$ $\displaystyle~{}O(\sqrt{\epsilon})\cdot\frac{1}{\sigma_{\min}(A)}\cdot\|Ax_{\rm OPT}-b\|_{2}.$ $$

###### Lemma 4.5 (Forward error, Lemma 5.5 in [ 18 ] ) .

### 4.3 Weighted linear regression

In this section, we introduce the weighted linear regression.

###### Lemma 4.6 (Lemma B.1 of [ 18 ] on page 30) .

Let $A$ be an arbitrary matrix in $\mathbb{R}^{n\times d}$, which has the full column rank.

Let $b$ be an arbitrary vector in $\mathbb{R}^{n}$.

Let $w$ be the weight vector, which is in $\mathbb{R}_{\geq 0}^{n}$.

$\epsilon_{0}$ is an arbitrary real number in $(0,0.1)$.

$\delta_{0}$ is an arbitrary real number in $(0,0.1)$.

Suppose that ${\cal T}(n,d,\epsilon_{0},\delta_{0})$ is the running time of a certain regression solver, and $x^{\prime}\in\mathbb{R}^{d}$ is the output of this this regression solver, which satisfy

$$ $\displaystyle\|Ax^{\prime}-b\|_{2}\leq$ $\displaystyle~{}(1+\epsilon_{0})\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$ $$

with probability at least $1-\delta_{0}$.

Then, we have an algorithm whose running time is

$$ $\displaystyle O(\operatorname{nnz}(A))+{\cal T}(n,d,\epsilon_{0},\delta_{0})$ $$

and outputs $x^{\prime}\in\mathbb{R}^{d}$, which satisfy

$$ $\displaystyle\|Ax^{\prime}-b\|_{w}\leq(1+\epsilon_{0})\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{w}$ $$

holds with probability $1-\delta_{0}$.

###### Lemma 4.7 (Dense and high accuracy weighted regression, Lemma 5.6 of [ 18 ] on page 16) .

Let $A$ be an arbitrary matrix in $\mathbb{R}^{n\times d}$.

Let $b$ be an arbitrary vector in $\mathbb{R}^{n}$.

Let $w$ be the weight vector, which is in $\mathbb{R}_{\geq 0}^{n}$.

$\epsilon$ is an arbitrary real number in $(0,0.1)$.

$\delta$ is an arbitrary real number in $(0,0.1)$.

Then, we can get an algorithm, namely Algorithm [2](#alg2), which runs in

$$ $\displaystyle O((nd\log n+d^{3}\log^{2}(n/\delta))\log(1/\epsilon))$ $$

time and outputs a vector $x^{\prime}\in\mathbb{R}^{d}$, satisfying

$$ $\displaystyle\|Ax^{\prime}-b\|_{w}\leq(1+\epsilon)\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{w}$ $$

holds with probability $1-\delta$.

###### Proof.

The proof is by instantiating the meta result Lemma [4.6](#S4.Thmtheorem6) with

$$ $\displaystyle{\cal T}(n,d,\epsilon,\delta)=O((nd\log n+d^{3}\log^{2}(n/\delta))\log(1/\epsilon))$ $$

due to Lemma [4.4](#S4.Thmtheorem4).
∎

###### Lemma 4.8 .

For any accuracy parameter $\epsilon_{0}\in(0,0.1)$, and failure probability $\delta_{0}\in(0,0.1)$.
Given matrix $M\in\mathbb{R}^{n\times n}$, $Y\in\mathbb{R}^{n\times k}$ and $W\in\mathbb{R}^{n\times n}$, there is an algorithm (Algorithm [3](#alg3)) that takes

$$ $\displaystyle O((n^{2}k\log n+nk^{3}\log^{2}(n/\delta_{0}))\cdot\log(1/\epsilon_{0}))$ $$

returns a matrix $X^{\prime}\in\mathbb{R}^{n\times k}$ such that

$$ $\displaystyle\|M-X^{\prime}Y^{\top}\|_{W}^{2}\leq(1+\epsilon_{0})\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2}$ $$

holds with probability at least $1-\delta_{0}$.

###### Proof.

By Claim [A.2](#A1.Thmtheorem2), we have

$$ $\displaystyle\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2}=\sum_{i=1}^{n}\min_{X_{i,:}\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|_{2}^{2},$ $$

For the $i$-th linear regression, we let

- •
$A$ to be $D_{\sqrt{W_{i}}}Y$, which is a matrix in $\mathbb{R}^{n\times k}$,
- •
$x$ to be $X_{i,:}$, which is a vector in $\mathbb{R}^{k}$, and
- •
$b$ to be $D_{\sqrt{W_{i}}}M_{i,:}$, which is a vector in $\mathbb{R}^{n}$.

Then by Lemma [4.7](#S4.Thmtheorem7), it takes time $O((nk\log n+k^{3}\log^{2}(n/\delta_{0}))\cdot\log(1/\epsilon_{0}))$ to compute a vector $x^{\prime}\in\mathbb{R}^{k}$ such that

$$ $\displaystyle\|Ax^{\prime}-b\|_{2}\leq(1+\epsilon_{0})\min_{x\in\mathbb{R}^{k}}\|Ax-b\|_{2}$ $$

with probability at least $1-\delta_{0}/n$. Taking the summation over the $n$ approximate linear regressions and union bounding over all $n$ of them gives the conclusion.
∎

###### Lemma 4.6 (Lemma B.1 of [ 18 ] on page 30) .

###### Lemma 4.7 (Dense and high accuracy weighted regression, Lemma 5.6 of [ 18 ] on page 16) .

###### Proof.

###### Lemma 4.8 .

###### Proof.

## 5 Our Results

In this section, we present our main theorem (Theorem [5.6](#S5.Thmtheorem6)) and its proof. Before presenting our proofs, we also need to make mild assumptions in the literature, which will be introduced in Section [5.1](#S5.SS1). In Section [5.2](#S5.SS2), we rigorously introduce our main result in Theorem [5.6](#S5.Thmtheorem6). There are two parts of the proof: the running time part and the correctness part.

### 5.1 Assumptions

We start by introducing the assumptions.

###### Definition 5.1 ( $(\mu,\tau)$ -incoherent) .

$M^{*}$ has SVD $M^{*}=U\Sigma V^{\top}$, where

$$ $\displaystyle\max\{\|U_{i,:}\|_{2}^{2},\|V_{i,:}\|_{2}^{2}\}_{i=1}^{n}\leq\frac{\mu k}{n}.$ $$

Let $\sigma_{\max}(\Sigma)=1$. Let $\tau:=\sigma_{\max}(\Sigma)/\sigma_{\min}(\Sigma)$.

###### Definition 5.2 ( $\gamma$ -spectral gap) .

Let $\gamma>0$.
We assume that
$\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|\leq\gamma n$.

###### Definition 5.3 (Weight is $(\alpha,\beta)$ -bounded) .

For $0<\alpha\leq 1\leq\beta$,

$$ $\displaystyle\alpha I\preceq$ $\displaystyle~{}U^{\top}D_{W_{i}}U\preceq\beta I,$ $\displaystyle\alpha I\preceq$ $\displaystyle~{}V^{\top}D_{W_{i}}V\preceq\beta I.$ $$

###### Definition 5.4 .

Let

$$ $\displaystyle\gamma\leq\frac{1}{100}\cdot\frac{\alpha}{\operatorname{poly}(k,\tau,\mu)\cdot n^{c_{0}}}$ $$

where $c_{0}$ is a fixed constant between $(0,1/2]$.

For the convenience of analysis, we define threshold parameters

###### Definition 5.5 .

Let $C\geq 10^{5}$ denote a sufficiently large constant.
We define

$$ $\displaystyle\Delta_{d}:=$ $\displaystyle~{}C\alpha^{-1.5}\mu^{1.5}k^{2}\gamma(\|W\|_{\infty,1}/n)^{1/2}+C\alpha^{-1}\eta\mu k^{2}\tau^{0.5}\gamma$ $\displaystyle\Delta_{f}:=$ $\displaystyle~{}C\alpha^{-1}\eta k.$ $$

The choice of $\Delta_{d}$ is decided in Eq. ([8](#A5.E8)) and Eq. ([14](#A5.E14)). The choice of $\Delta_{f}$ is decided in Eq. ([15](#A5.E15)). Let $\eta$ be defined as Definition [E.3](#A5.Thmtheorem3). Note that $\eta$ is the parameter to distinguish random and SVD initialization.

###### Definition 5.1 ( ( μ , τ ) 𝜇 𝜏 (\mu,\tau) -incoherent) .

###### Definition 5.2 ( γ 𝛾 \gamma -spectral gap) .

###### Definition 5.3 (Weight is ( α , β ) 𝛼 𝛽 (\alpha,\beta) -bounded) .

###### Definition 5.4 .

###### Definition 5.5 .

### 5.2 Main Result

Our main theorem is as follows:

###### Theorem 5.6 (Formal version of Theorem 1.1 ) .

Suppose $M^{*}\in\mathbb{R}^{n\times n}$ is $(\mu,\tau)$-incoherent (see Definition [5.1](#S5.Thmtheorem1)). Assume that $W$ is $\gamma$-spectral gap (see Definition [5.2](#S5.Thmtheorem2)) and $(\alpha,\beta)$-bounded (see Definition [5.3](#S5.Thmtheorem3)).
Let $\gamma$ satisfy condition in Definition [5.4](#S5.Thmtheorem4).

There is an algorithm (Algorithm [1](#alg1)) uses initialization and runs in $O(\log(1/\epsilon))$ iterations and generates a matrix $\widetilde{M}$, which is in $\mathbb{R}^{n\times n}$ such that

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq O(\alpha^{-1}k\tau)\|W\circ N\|+\epsilon.$ $$

The total running time is

$$ $\displaystyle\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon)).$ $$

Due to space limitation, we delay the proof of Theorem [5.6](#S5.Thmtheorem6) in Appendix [K](#A11).

Compared to the result of [], we significantly improved the running time from $O((n^{2}k^{2}+nk^{3})\log(1/\epsilon))$ to $\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$. For moderately large $k$ (say $k=O(\sqrt{n})$), the [] algorithm would take $O(n^{3}\log(1/\epsilon))$ time, while ours only takes $\widetilde{O}(n^{2.5}\log(1/\epsilon))$ time. Moreover, our analysis accounts for approximated computation at each step, thus opens up the gate for further speedup.

###### Theorem 5.6 (Formal version of Theorem 1.1 ) .

## 6 Conclusion

To sum up, the weighted low rank approximation is a very important task not only in optimization but also in machine learning because of its broad application. Although this problem has been shown to be NP-hard and difficult to approximate in [], with some assumptions, it is shown that there exists an algorithm that has a running time of $\widetilde{O}(n^{2}k^{2})$ in [].

In our paper, the running time has been improved to $n^{2}k$. We would like to remark that this running time is nearly linear for this problem, in the sense that if one wants to verify $X,Y$ are indeed weighted low rank factors of $M$, multiplying them out without using fast matrix multiplication would take $O(n^{2}k)$ time. To achieve this result, we propose an efficient alternating minimization framework that accounts for approximation error. To combat the inherent fragility of the alternating minimization framework, we show that a high accuracy regression solver actually suffices to realize the $O(\log(1/\epsilon))$ iteration convergence behavior.

One of the major limitations of this work is that we only analyze approximately solving the multiple response regressions, as these steps are the runtime bottleneck. We believe that our analysis can be well-extended to approximately compute the QR factorization. As our work is theoretical in nature, we believe it does not incur any negative societal impact.

## Acknowledgement

Lichen Zhang is supported by NSF grant No. 1955217 and NSF grant No. 2022448.

## Appendix

#### Roadmap.

In Section [A](#A1), we provide several basic definitions and tools. In Section [B](#A2), we discuss more related work. In Section [C](#A3), we give a brief discussion for low accuracy sketching solver. In Section [D](#A4), we provide definitions and basic properties for angles and distances. In Section [E](#A5), we provide our key lemmas for the update step. In Section [F](#A6), we prove our induction lemma. In Section [G](#A7), we state several tools from previous work. In Section [H](#A8), we analyze the SVD initialization and present our main result. In Section [I](#A9), we present the random initialization algorithm and analyze its properties. In Section [J](#A10), we show how to prove the final guarantee of our main Theorem. In Section [K](#A11), we present the complete proof of our main Theorem.

## Appendix A Basic Definitions and Algebra Tools

In Section [A.1](#A1.SS1), we introduce weighted regression. In Section [A.2](#A1.SS2), we present the properties of the weight matrix. Moreover, we explain the algebra tools which are used for later proofs.
In Section [A.3](#A1.SS3), we present some basic algebraic inequalities. In Section [A.4](#A1.SS4), we state a few simple facts about the norm properties.

### A.1 Weighted Regression

In this section, we start to introduce the basic properties of weighted regression.

###### Definition A.1 (Diagonalization of a weight vector) .

Given a square weight matrix $W\in\mathbb{R}^{n\times n}$.
For each $i\in[n]$, we use $W_{i}$ to denote the $i$-th column of $W$. We use $D_{W_{i}}\in\mathbb{R}^{n\times n}$ to denote the diagonal matrix where putting $W_{i}$ on main diagonal of $n\times n$ matrix where all the other entries are 0 0.

###### Claim A.2 .

Given matrices $M,W\in\mathbb{R}^{n\times n}$ and $X,Y\in\mathbb{R}^{n\times k}$, we have

$$ $\displaystyle~{}\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2}=~{}\sum_{i=1}^{n}\min_{X_{i,:}\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|_{2}^{2},$ $$

and

$$ $\displaystyle~{}\min_{Y\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2}=~{}\sum_{i=1}^{n}\min_{Y_{i,:}\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}XY_{i,:}-D_{\sqrt{W_{i}}}M_{:,i}\|_{2}^{2}.$ $$

###### Proof.

Since the two equations can be proved in a similar way, we only prove the first one.

$$ $\displaystyle\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2}=$ $\displaystyle~{}\min_{X\in\mathbb{R}^{n\times k}}\sum_{i,j}W_{i,j}(XY^{\top}-M)_{i,j}^{2}$ $\displaystyle=$ $\displaystyle~{}\min_{X\in\mathbb{R}^{n\times k}}\sum_{i=1}^{n}\|D_{\sqrt{W_{i}}}(YX_{i,:}-M_{i,:})\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\min_{X\in\mathbb{R}^{n\times k}}\sum_{i=1}^{n}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{n}\min_{X_{i,:}\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|_{2}^{2},$ $$

where the 1st step is due to $\|A\|_{W}^{2}$’s definition, the 2nd step is by rewriting each row as an independent regression problem, the 3rd step follows from simple algebra, and the last step follows from the fact that there is no $X$ in $\min_{X\in\mathbb{R}^{n\times k}}\sum_{i=1}^{n}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|_{2}^{2}$ but only $X_{i,:}$.

Thus, we complete the proof.
∎

###### Remark A.3 .

Claim [A.2](#A1.Thmtheorem2) provides a reduction of solving multiple response regression to solving $n$ weighted linear regression. In the following result, we shall use the same oblivious subspace embedding matrix $S$ with parameter $O(1)$ error and $\delta/n$ probability, as we will union bound over the events that $S$ preserves the subspaces for $n$ regressions.

###### Definition A.1 (Diagonalization of a weight vector) .

###### Claim A.2 .

###### Proof.

###### Remark A.3 .

### A.2 Properties of Weight Matrix

Here, we present the properties of weighted matrices.

###### Definition A.4 .

For weight matrix $W$, we define

$$ $\displaystyle\|W\|_{\infty,1}:=\max\{\max_{i\in[n]}\|W_{i,:}\|_{1},\max_{j\in[n]}\|W_{:,j}\|_{1}\}$ $$

and

$$ $\displaystyle\|W\|_{\infty,2}:=\max\{\max_{i\in[n]}\|W_{i,:}\|_{2},\max_{j\in[n]}\|W_{:,j}\|_{2}\}.$ $$

###### Lemma A.5 .

Let $\gamma>0$, if $\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|\leq\gamma n$, then we have

- •
Part 1. $\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{F}\leq n^{1.5}\gamma$
–
Further $\|W\|_{F}\leq n^{1.5}\gamma+n$
- •
Part 2. $\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{\infty,1}\leq n^{1.5}\gamma$
–
Further $\|W\|_{\infty,1}\leq n^{1.5}\gamma+n$

###### Proof.

Proof of Part 1.
We have

$$ $\displaystyle\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{F}^{2}\leq$ $\displaystyle~{}n\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}n\cdot(\gamma n)^{2}$ $\displaystyle\leq$ $\displaystyle~{}n^{3}\gamma^{2}$ $$

By the triangle inequality, we have

$$ $\displaystyle\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{F}\leq n^{1.5}\gamma+n$ $$

Proof of Part 2.

Note that

$$ $\displaystyle\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{\infty,1}\leq$ $\displaystyle~{}\sqrt{n}\cdot\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{\infty,2}$ $\displaystyle\leq$ $\displaystyle~{}\sqrt{n}\cdot\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|$ $\displaystyle\leq$ $\displaystyle~{}n^{1.5}\gamma$ $$

By the triangle inequality, we have

$$ $\displaystyle\|W\|_{\infty,1}\leq$ $\displaystyle~{}\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{\infty,1}+\|{\bf 1}_{n}{\bf 1}_{n}^{\top}\|_{\infty,1}$ $\displaystyle\leq$ $\displaystyle~{}n^{1.5}\gamma+n$ $$

∎

###### Lemma A.6 .

We can show that

- •
Part 1. If $\gamma<1/(10n^{1/6})$, then we have
$\displaystyle\gamma\cdot(\|W\|_{\infty,1}/n)^{1/2}<1$
- •
Part 2. If $\gamma<1/(10n^{1/2})$, then we have
$\displaystyle\gamma\cdot(\|W\|_{\infty,1})^{1/2}<1$

###### Remark A.7 .

In previous work [], they wrote the final bound as $\gamma<f/(\|W\|_{\infty,1}/n)^{1/2}$ where $f$ are other factors not depending on $\gamma$. For example $f=\operatorname{poly}(\alpha^{-1},k,\tau,\mu)$. Their bound technically is not complete, because $\|W\|_{\infty,1}$ is also function of $\gamma$. So, in our work, our Lemma [A.6](#A1.Thmtheorem6) further calculates the real condition that is required in [].

###### Proof.

Proof of Part 1.
We need that

$$ $\displaystyle\gamma\cdot(\|W\|_{\infty,1}/n)^{1/2}<1$ $$

It suffices to show that

$$ $\displaystyle\gamma\cdot((n^{1.5}\gamma+n)/n)^{1/2}<1$ $$

The above equation is equivalent to

$$ $\displaystyle\gamma\cdot(n^{0.5}\gamma+1)^{1/2}<1$ $$

It is sufficient to show that

$$ $\displaystyle\gamma^{1.5}n^{0.25}+\gamma<1$ $$

Thus, as long as

$$ $\displaystyle\gamma<1/(10n^{1/6})$ $$

then, we are fine.

Proof of Part 2.

We need that

$$ $\displaystyle\gamma\cdot(\|W\|_{\infty,1})^{1/2}<1$ $$

It suffices to show that

$$ $\displaystyle\gamma\cdot(n^{1.5}\gamma+n)^{1/2}<1$ $$

It is sufficient to show that

$$ $\displaystyle\gamma^{1.5}n^{0.75}+\gamma n^{0.5}<1$ $$

Thus, as long as

$$ $\displaystyle\gamma<1/(10n^{1/2})$ $$

then, we are fine.
∎

###### Definition A.4 .

###### Lemma A.5 .

###### Proof.

###### Lemma A.6 .

###### Remark A.7 .

###### Proof.

### A.3 Basic Inequalities

In this section, we introduce some basic inequalities.

###### Fact A.8 .

For any $x,y$ and $\epsilon\in(0,1)$, we have

$$ $\displaystyle(x+y)^{2}\geq(1-\epsilon)x^{2}-\epsilon^{-1}y^{2}$ $$

###### Proof.

It suffices to show

$$ $\displaystyle x^{2}+2xy+y^{2}\geq(1-\epsilon)x^{2}-\epsilon^{-1}y^{2}.$ $$

Re-organizing the above terms, we have

$$ $\displaystyle\epsilon x^{2}+2xy+(1+\epsilon^{-1})y^{2}\geq 0$ $$

Thus it suffices to show that

$$ $\displaystyle\epsilon x^{2}+2xy+\epsilon^{-1}y^{2}\geq 0.$ $$

It is obvious that

$$ $\displaystyle\epsilon x^{2}+\epsilon^{-1}y^{2}\geq 2|xy|.$ $$

Thus, we can complete the proof.
∎

###### Fact A.9 .

Let $n$ be an arbitrary positive integer.

Let $a_{i}\geq 0$ and $b_{i}\geq 0$ for all $i\in[n]$.

Then, the following two inequalities hold

$$ $\displaystyle\min_{i\in[n]}\{a_{i}\}\sum_{i\in[n]}b_{i}\leq$ $\displaystyle~{}\sum_{i\in[n]}a_{i}b_{i}\leq\max_{i\in[n]}\{a_{i}\}\sum_{i\in[n]}b_{i}$ $\displaystyle\min_{i\in[n]}\{b_{i}\}\sum_{i\in[n]}a_{i}\leq$ $\displaystyle~{}\sum_{i\in[n]}a_{i}b_{i}\leq\max_{i\in[n]}\{b_{i}\}\sum_{i\in[n]}a_{i}.$ $$

###### Fact A.8 .

###### Proof.

###### Fact A.9 .

### A.4 Properties for Norms

We state some standard facts without providing proofs.

###### Fact A.10 .

- •
Part 1. For any matrix $A\in\mathbb{R}^{n\times n}$, let $A_{j}$ denote the $j$-th column of $A$. Then we have $\sum_{j=1}^{n}\|A_{j}\|_{2}^{2}=\|A\|_{F}^{2}$.
- •
Part 2. For any psd matrix $A$, for any vector $x$, $x^{\top}Ax\geq\sigma_{\min}(A)$.
- •
Part 3. Let $U\in\mathbb{R}^{n\times k}$ denote an orthonormal basis. Then for any $k\times k$ matrix $B$, we have $\|UB\|=\|B\|$.
- •
Part 4. For any matrix $A\in\mathbb{R}^{n\times k}$, we have $\|A\|\leq\|A\|_{F}\leq\sqrt{k}\|A\|$.
- •
Part 5. For any matrix $A$ and $B$, $\sigma_{\min}(A)\geq\sigma_{\min}(B)-\|A-B\|$
- •
Part 6. For any matrix $A\in\mathbb{R}^{n\times k}$ and any orthonormal basis $Q\in\mathbb{R}^{k\times k}$. $\sigma_{\min}(A)=\sigma_{\min}(AQ)$.
- •
Part 7. For any vector $x\in\mathbb{R}^{k}$ and for any orthornomal basis $Q\in\mathbb{R}^{k\times k}$, we have $\|x\|_{2}=\|Qx\|_{2}$.

###### Fact A.10 .

## Appendix B More Related Work

Sketching is a powerful tool and has been applied to many machine learning problems. Usually, there are two ways of applying sketching matrices. The first way is applying sketching once (or constant times), which is called sketch-and-solve. The second way is applying sketching in each iteration of the optimization algorithm, and in the meanwhile designing a robust analysis framework. This is called iterate-and-sketch. This work falls into the second category.

Sketch-and-solve can be applied in various fields, such as linear regression [, ], low-rank approximation with Frobenious norm [, ], matrix CUR decomposition [, , ], weighted low rank approximation [], entrywise $\ell_{1}$ norm low-rank approximation [, ], tensor regression [, , , ], tensor low-rank approximation [], and general norm column subset selection [].

Iterate-and-sketch has been applied to many fundamental problems, such as linear programming [, , , ], empirical risk minimization [, ], semi-definite programming [], John Ellipsoid computation [], Frank-Wolfe algorithm [, ], reinforcement learning [], softmax-inspired regression [, , , ], federated learning [], discrepancy problem [, ], non-convex optimization [, , , ].

## Appendix C Low Accuracy Solver

In Section [C.1](#A3.SS1), we present the definition of the OSNAP matrix. In Section [C.2](#A3.SS2), we show one property of the OSNAP matrix: the OSNAP matrix produces a subspace embedding. In Section [C.3](#A3.SS3), we provide the regression solver by using the OSNAP matrix.

### C.1 OSNAP matrix

In this section, we start by introducing the definition of the OSNAP matrix.

###### Definition C.1 (OSNAP matrix, [ 31 ] ) .

For every sparsity parameter $s$, target dimension $m$, and positive integer $d$, the OSNAP matrix with sparsity $s$ is defined as

$$ $\displaystyle S_{r,j}=$ $\displaystyle~{}\frac{1}{\sqrt{s}}\cdot\delta_{r,j}\cdot\sigma_{r,j},$ $$

for all $r\in[m],j\in[d]$, where $\sigma_{r,j}$ are independent Rademacher random variables and $\delta_{r,j}$ are Bernoulli random variables with

- •
For every $i\in[d]$, $\sum_{r\in[m]}\delta_{r,i}=s$, which means each column of $S$ contains exactly $s$ nonzero entries.
- •
For all $r\in[m]$ and $i\in[d]$, $\operatorname*{{\mathbb{E}}}[\delta_{r,i}]=s/m$.
- •
$\forall T\in[m]\times[d]$, $\operatorname*{{\mathbb{E}}}[\prod_{(r,i)\in T}\delta_{r,i}]\leq\prod_{(r,i)\in T}\operatorname*{{\mathbb{E}}}[\delta_{r,i}]=(s/m)^{|T|}$, i.e., $\delta_{r,i}$ are negatively correlated.

###### Definition C.1 (OSNAP matrix, [ 31 ] ) .

### C.2 OSNAP matrix Implies Subspace Embedding

Crucially, the OSNAP matrix produces a subspace embedding with nearly linear in $d$ row count.

###### Lemma C.2 ( [ 8 ] ) .

Let $S\in\mathbb{R}^{m\times n}$ be an OSNAP matrix as in Def. [C.1](#A3.Thmtheorem1).

Let $\epsilon,\delta\in(0,1)$ be parameters.

For any integer $d\leq n$, if

- •
$m=O(\epsilon^{-2}d\log(d/\delta))$;
- •
$s=O(\epsilon^{-1}\log(d/\delta))$,

then an $s$-sparse OSNAP matrix $S$ is an $(\epsilon,\delta)$ oblivious subspace embedding, i.e., for any fixed orthonormal basis $U\in\mathbb{R}^{n\times d}$ with probability at least $1-\delta$, and the singular values of $SU$ lie in $[1-\epsilon,1+\epsilon]$.

###### Lemma C.2 ( [ 8 ] ) .

### C.3 The Regression Solver

To distinguish with $\epsilon,\delta$ for our final algorithm, here we use $\epsilon_{0},\delta_{0}$ for the subroutine (approximate linear regression).

###### Lemma C.3 (Input sparsity and low accuracy regression) .

Given a matrix $A\in\mathbb{R}^{n\times d}$ and a vector $b\in\mathbb{R}^{n}$, let $\epsilon_{0}\in(0,0.1)$ and $\delta_{0}\in(0,0.1)$, there exists an algorithm that takes time

$$ $\displaystyle O((\epsilon_{0}^{-1}\operatorname{nnz}(A)+\epsilon_{0}^{-2}d^{3})\cdot\log(d/\delta_{0}))$ $$

and outputs $x^{\prime}\in\mathbb{R}^{d}$ such that

$$ $\displaystyle\|Ax^{\prime}-b\|_{2}\leq(1+\epsilon_{0})\min_{x\in\mathbb{R}^{d}}\|Ax-b\|_{2}$ $$

holds with probability $1-\delta_{0}$.

###### Proof.

To obtain desired accuracy and probability guarantee, we pick $S$ to be an OSNAP (Definition [C.1](#A3.Thmtheorem1)) with

$$ $\displaystyle m=O(\epsilon_{0}^{-2}d\log(d/\delta_{0}))$ $$

and

$$ $\displaystyle s=O(\epsilon_{0}^{-1}\log(d/\delta_{0})).$ $$

We simply apply $S$ to $A$ then solve the sketched regression $\min_{x\in\mathbb{R}^{d}}\|SAx-Sb\|_{2}$.

- •
As $S$ is a matrix where each column only has $s$ nonzero entries, the time to compute $SA$ is
$\displaystyle O(s\operatorname{nnz}(A))=O(\epsilon_{0}^{-1}\operatorname{nnz}(A)\log(d/\delta_{0})).$
- •
The regression can then be solved via normal equation, i.e.,
$\displaystyle(A^{\top}S^{\top}SA)^{\dagger}A^{\top}S^{\top}b.$
The time to form the Gram matrix is
$\displaystyle O(md^{2}),$
computing the $d\times d$ inversion takes $O(d^{3})$ time, and forming the final solution takes another
$\displaystyle O(md^{2})$
time. Overall, this gives a runtime of
$\displaystyle O(\epsilon_{0}^{-2}d^{3}\log(d/\delta_{0})).$

Thus, the overall runtime is

$$ $\displaystyle O((\epsilon_{0}^{-1}\operatorname{nnz}(A)+\epsilon_{0}^{-2}d^{3})\cdot\log(d/\delta_{0})).$ $$

∎

Figure: Algorithm 3 Fast, high precision solver for weighted multiple response regression

###### Lemma C.3 (Input sparsity and low accuracy regression) .

###### Proof.

## Appendix D Properties of Angles and Distances

In Section [D.1](#A4.SS1), we explain the formal definition of $\rho$ and then present its properties. In Section [D.2](#A4.SS2), we define the angles and distances. Then, we present their properties. In Section [D.3](#A4.SS3), we present more properties of angles and distances.

### D.1 Definition and Property of ρ 𝜌 \rho

In this section, we introduce the definition and the properties of $\rho$.

###### Definition D.1 .

Let $A\in\mathbb{R}^{n\times k}$. The generalized incoherence of $A$ is denoted as $\rho(A)$, i.e.,

$$ $\displaystyle\rho(A):=\frac{n}{k}\cdot\max_{i\in[n]}\{\|A_{i,:}\|_{2}^{2}\}.$ (2) $$

###### Claim D.2 .

When $A\in\mathbb{R}^{n\times k}$ is an orthogonal matrix, $1\leq\rho(A)\leq\frac{n}{k}$.

###### Proof.

Since $A$ is an orthogonal matrix, $\|A_{i,:}\|_{2}^{2}\leq 1$ for all $i\in[n]$, and thus $\rho(A)\leq\frac{n}{k}$. In addition, $\sum_{i=1}^{n}\|A_{i,:}\|_{2}^{2}=k$, we have $\max_{i\in[n]}\{\|A_{i,:}\|_{2}^{2}\}\geq\frac{k}{n}$ and then $\rho(A)\geq 1$.
∎

###### Definition D.1 .

###### Claim D.2 .

###### Proof.

### D.2 Angle and Distance Notation

In this section, we formally define $\sin$, $\cos$, $\tan$, and $\operatorname{dist}$ and analyze their properties.

###### Definition D.3 .

We any two matrices $X\in\mathbb{R}^{n\times k}$ and $Y\in\mathbb{R}^{n\times k}$.

Let $X,Y$ be an orthogonal matrix, namely $XX^{\top}=I_{k}$ and $YY^{\top}=I_{k}$.

We define $\tan\theta(Y,X)$ to be equal to

$$ $\displaystyle\|Y_{\bot}^{\top}X(Y^{\top}X)^{-1}\|.$ $$

Let $O_{k}$ be a set containing all the orthogonal matrices, whose dimension is $k\times k$.

We define $\cos(Y,X)$ to be equal to

$$ $\displaystyle\sigma_{\min}(Y^{\top}X);$ $$

we define $\sin\theta(Y,X)$ to be equal to

$$ $\displaystyle\|(I-YY^{\top})X\|;$ $$

we define $\operatorname{dist}(Y,X)$ to be equal to

$$ $\displaystyle\min_{Q\in O_{k}}\|YQ-X\|.$ $$

Note that by their definitions, we can get

- •
$\cos(Y,X)=1/\|(Y^{\top}X)^{-1}\|$,
- •
$\cos(Y,X)\leq 1$,
- •
$\sin\theta(Y,X)=\|Y_{\bot}Y_{\bot}^{\top}X\|=\|Y_{\bot}^{\top}X\|$, and
- •
$\sin\theta(Y,X)\leq 1$.

###### Lemma D.4 (Structural lemma for orthogonal matrices, Lemma A.5 of [ 18 ] , page 24) .

We let $X$ and $Y$ to be arbitrary matrices in $\mathbb{R}^{n\times k}$ and both are orthogonal.

Then, we can get

$$ $\displaystyle(Y^{\top}X)_{\bot}=$ $\displaystyle~{}Y_{\bot}^{\top}X.$ $$

###### Lemma D.5 (Orthogonal and inverse share singular vectors, Lemma A.6 of [ 18 ] , page 24) .

We let $A$ to be a non-singular matrix in $\mathbb{R}^{k\times k}$.

Then, we can get that $A^{-1}$ and $A_{\bot}$ both have the same singular vectors. Consequently, $\|A_{\bot}A^{-1}\|=\|A_{\bot}\|\cdot\|A^{-1}\|$.

###### Lemma D.6 (Lemma A.7 of [ 18 ] , page 26) .

We let $X$ and $Y$ to be arbitrary matrices in $\mathbb{R}^{n\times k}$ and both are orthogonal.

Then, we have that $\tan\theta(Y,X)$ is equal to

$$ $\displaystyle\frac{\sin\theta(Y,X)}{\cos\theta(Y,X)}.$ $$

###### Proof.

Due to Lemma [D.4](#A4.Thmtheorem4), we have $(Y^{\top}X)_{\bot}=Y^{\top}_{\bot}X$. Thus, $\tan\theta(Y,X)=\|(Y^{\top}X)_{\bot}(Y^{\top}X)^{-1}\|$. The proof then follows straightforwardly from Lemma [D.5](#A4.Thmtheorem5).
∎

###### Lemma D.7 (Lemma A.8 of [ 18 ] , page 26) .

Let $X,Y\in\mathbb{R}^{n\times k}$ be orthogonal matrices.

Then, we can get

$$ $\displaystyle\sin^{2}\theta(Y,X)+\cos^{2}\theta(Y,X)=1.$ $$

###### Definition D.3 .

###### Lemma D.4 (Structural lemma for orthogonal matrices, Lemma A.5 of [ 18 ] , page 24) .

###### Lemma D.5 (Orthogonal and inverse share singular vectors, Lemma A.6 of [ 18 ] , page 24) .

###### Lemma D.6 (Lemma A.7 of [ 18 ] , page 26) .

###### Proof.

###### Lemma D.7 (Lemma A.8 of [ 18 ] , page 26) .

### D.3 More properties for angles and distance

In this section, we keep analyzing the properties of $\sin$, $\cos$, $\tan$, and $\operatorname{dist}$.

###### Lemma D.8 (Lemma A.9 of [ 18 ] in page 27) .

Let $U$ and $V$ be two arbitrary matrices in $\mathbb{R}^{n\times k}$, both of which are orthogonal.

Then, we can get

- •
Part one. $\tan\theta(Y,V)\geq\sin\theta(Y,V)$
- •
Part two. $\tan\theta(Y,V)\geq\frac{1-\cos\theta(Y,V)}{\cos\theta(Y,V)}$
- •
Part three. $\operatorname{dist}(Y,V)\geq\sin\theta(Y,V)$
- •
Part four. $\sin\theta(Y,V)+\frac{1-\cos\theta(Y,V)}{\cos\theta(Y,V)}\geq\operatorname{dist}(Y,V)$
- •
Part five. $2\tan\theta(Y,V)\geq\operatorname{dist}(Y,V)$

###### Lemma D.8 (Lemma A.9 of [ 18 ] in page 27) .

## Appendix E Key Property for Robust Update

In Section [E.1](#A5.SS1), we formally define several necessary notations needed to analyze our robust updated step. In Section [E.2](#A5.SS2), we analyze the key properties of our robust update step.

### E.1 Definitions for Update Step

We present a standard for linear regression.

###### Fact E.1 .

Define $x:=\arg\min_{x}\|Ax-b\|_{2}$, then we have

$$ $\displaystyle x=(A^{\top}A)^{-1}A^{\top}b.$ $$

Similarly, for weighted regression, we define

$$ $\displaystyle x:=\arg\min_{x}\|D_{W_{i}}Ax-D_{W_{i}}b\|_{2}.$ $$

Then, we have

$$ $\displaystyle x=(A^{\top}D_{W_{i}}A)^{-1}A^{\top}D_{W_{i}}b$ $$

###### Definition E.2 .

We define $\xi$ as

$$ $\displaystyle\xi:=\mu k/n.$ $$

###### Definition E.3 .

We define $\eta\geq 1$ to be parameter that distinguish ranom and SVD initialization.

- •
For random initialization, we set $\eta:=\mu k$.
- •
For SVD initialization, we set $\eta:=1$.

###### Definition E.4 .

Let $\Delta_{d}$ and $\Delta_{f}$ be defined as Definition [5.5](#S5.Thmtheorem5).
We define

$$ $\displaystyle\Delta_{u}:=$ $\displaystyle~{}\Delta_{d}\cdot\operatorname{dist}(Y,V)+\Delta_{f}\cdot\|W\circ N\|.$ $$

and

$$ $\displaystyle\Delta_{g}:=$ $\displaystyle~{}0.01\Delta_{d}\cdot\operatorname{dist}(Y,V)+0.01\Delta_{f}\cdot\|W\circ N\|+2\sqrt{\epsilon_{\mathrm{sk}}}$ $$

It is obvious that

###### Claim E.5 .

If

$$ $\displaystyle\epsilon_{\mathrm{sk}}\leq 10^{-4}\Delta_{f}^{2}\cdot\|W\circ N\|^{2},$ $$

then

$$ $\displaystyle\Delta_{g}\leq 0.1\Delta_{u}.$ $$

###### Proof.

We have

$$ $\displaystyle\Delta_{g}=$ $\displaystyle~{}0.01\Delta_{d}\cdot\operatorname{dist}(Y,V)+0.01\Delta_{f}\cdot\|W\circ N\|+2\sqrt{\epsilon_{\mathrm{sk}}}$ $\displaystyle\leq$ $\displaystyle~{}0.01\Delta_{d}\cdot\operatorname{dist}(Y,V)+0.01\Delta_{f}\cdot\|W\circ N\|+0.02\Delta_{f}\cdot\|W\circ N\|$ $\displaystyle\leq$ $\displaystyle~{}0.1\Delta_{u}$ $$

where the second step follows from condition on $\epsilon_{\mathrm{sk}}$
, and the last step follows from the definition of $\Delta_{u}$

∎

###### Claim E.6 .

By choice of $\epsilon_{\mathrm{sk}}$, we have

$$ $\displaystyle\log(n/\epsilon_{\mathrm{sk}})=O(\log(n))$ $$

By choice of failure probability ($\delta_{0}$) of sketch,

$$ $\displaystyle\log(n/\delta_{0})=\log(n\log(1/\epsilon))$ $$

###### Remark E.7 .

The $\widetilde{O}$ in Theorem [5.6](#S5.Thmtheorem6) hides $\operatorname{poly}(\log(n),\log(\log(1/\epsilon))$ factor.

###### Proof.

By assumption on $W$, we can see that

$$ $\displaystyle\|W\|_{\infty}\leq\operatorname{poly}(n).$ $$

Since $W\circ N$ is a noisy part, it is also natural to consider

$$ $\displaystyle\|W\circ N\|_{\infty}\leq\operatorname{poly}(n),$ $$

otherwise, it is not interesting.

Since the noise cannot be 0 0, thus it is natural to assume that

$$ $\displaystyle\|N\|_{\infty}\geq 1/\operatorname{poly}(n).$ $$

Thus, we know

$$ $\displaystyle 1/\operatorname{poly}(n)\leq\|W\circ N\|_{F}\leq\operatorname{poly}(n).$ (3) $$

We also know that $k\leq n$.

Now, we can compute

$$ $\displaystyle\log(n/\epsilon_{\mathrm{sk}})\leq$ $\displaystyle~{}O(\log(n/(\Delta_{f}^{2}\|W\circ N\|_{F}^{2})))$ $\displaystyle\leq$ $\displaystyle~{}O(\log(n/\|W\circ N\|_{F}^{2}))$ $\displaystyle\leq$ $\displaystyle~{}O(\log(n)),$ $$

where the first step follows from we choose $\epsilon_{\mathrm{sk}}=\Theta(\Delta_{f}^{2}\|W\circ N\|_{F}^{2})$, the second step follows from $\Delta_{f}\geq 1$, the third step follows from $\|W\circ N\|_{F}^{2}\geq 1/\operatorname{poly}(n)$ (see Eq. ([3](#A5.E3))).

We union over all the $T=O(\log(1/\epsilon))$ iterations, so

$$ $\displaystyle\log(n/\delta_{0})=O(\log(n\log(1/\epsilon)))$ $$

∎

**Table 1: For convenience, we provide a table to summarize the notations in a different setting defined in Lemma [E.8](#A5.Thmtheorem8).**
| Notation | Meaning |
| --- | --- |
| $\widetilde{X}$ | Optimal matrix for exact regression |
| $\overline{X}$ | Clipped matrix of $\widetilde{X}$ |
| $\vec{X}$ | Optimal matrix for sketched regression |
| $\widehat{X}$ | Clipped matrix of $\vec{X}$ |

Figure: Algorithm 4 Clipping

###### Fact E.1 .

###### Definition E.2 .

###### Definition E.3 .

###### Definition E.4 .

###### Claim E.5 .

###### Proof.

###### Claim E.6 .

###### Remark E.7 .

###### Proof.

### E.2 Key Lemma for Robust Update Step

Here, we analyze the key properties of the robust update step.

###### Lemma E.8 (Key lemma for update step) .

Let $Y\in\mathbb{R}^{n\times k}$ be a (column) orthogonal matrix. Let $\xi$ be defined as Definition [E.2](#A5.Thmtheorem2). Let $\Delta_{u}$ be defined as Definition [E.4](#A5.Thmtheorem4).

We define matrix $\widetilde{X}\in\mathbb{R}^{n\times k}$ as follows:

$$ $\displaystyle\widetilde{X}:=\arg\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W},$ $$

We define matrix $\overline{X}\in\mathbb{R}^{n\times k}$ as follows

$$ $\displaystyle\overline{X}_{i,:}:=\begin{cases}\widetilde{X}_{i,:}&\text{if $\|\widetilde{X}_{i,:}\|^{2}\leq 4\xi$}\\ 0&\text{otherwise}\end{cases}$ $$

We define $X\in\mathbb{R}^{n\times k},R\in\mathbb{R}^{k\times k}$ to the QR decomposition of $\overline{X}$, i.e. $\overline{X}=XR$.

We define $\vec{X}\in\mathbb{R}^{n\times k}$ to be the sketch solution such that for all $i\in[n]$

$$ $\displaystyle\|\vec{X}_{i,:}-\widetilde{X}_{i,:}\|^{2}\leq\epsilon_{\mathrm{sk}}/n.$ $$

We define $\widehat{X}\in\mathbb{R}^{n\times k}$ to denote the truncation of the sketch solution.

Then

- •
Part 1.
$\displaystyle\|\overline{X}-U\Sigma V^{\top}Y\|_{F}^{2}\leq\Delta_{u}^{2};$
- •
Part 2. If $\Delta_{u}<0.1\sigma_{\min}(M^{*})$, then
$\displaystyle\operatorname{dist}(U,X)\leq 8\Delta_{u}/\sigma_{\min}(M^{*})$
- •
Part 3. If $\Delta_{u}<0.1\sigma_{\min}(M^{*})$, then
$\displaystyle\rho(X)\leq 8\mu/\sigma_{\min}(M^{*})^{2}$

###### Proof.

Proof of Part 1.
For the convex problem

$$ $\displaystyle\min_{X\in\mathbb{R}^{n\times k}}\|M-XY^{\top}\|_{W}^{2},$ $$

The above problem can be written as $n$ different regression problems. The $i$-th linear regression has the formulation

$$ $\displaystyle\min_{X_{i,:}\in\mathbb{R}^{k}}\|D_{\sqrt{W_{i}}}YX_{i,:}-D_{\sqrt{W_{i}}}M_{i,:}\|^{2}.$ $$

We have

$$ $\displaystyle\widetilde{X}_{i,:}^{\top}=$ $\displaystyle~{}M_{i,:}^{\top}\cdot D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}((M^{*})_{i,:}^{\top}+N_{i,:}^{\top})\cdot D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}(M^{*})_{i,:}^{\top}\cdot D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}+N_{i,:}^{\top}\cdot D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1},$ (4) $$

where the first step follows from the Fact [E.1](#A5.Thmtheorem1), and the second step follows from $M_{i,:}^{\top}=(M^{*})_{i,:}^{\top}+N_{i,:}^{\top}$ (because $M=M^{*}+N$), and the third step follows from simple algebra.

Given $M^{*}=U\Sigma V^{\top}$, the first term in Eq. ([E.2](#A5.Ex108)) can be rewritten as follows:

$$ $\displaystyle~{}(M^{*})_{i,:}^{\top}\cdot D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}U_{i,:}^{\top}\cdot\Sigma V^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}U_{i,:}^{\top}\cdot\Sigma V^{\top}(YY^{\top}+Y_{\bot}Y_{\bot}^{\top})D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}U_{i,:}^{\top}\cdot\Sigma V^{\top}YY^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}+U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ $\displaystyle=$ $\displaystyle~{}U_{i,:}^{\top}\cdot\Sigma V^{\top}Y+U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1},$ (5) $$

where the first step follows from the fact that $(M^{*})_{i,:}^{\top}=U_{i,:}^{\top}\Sigma V^{\top}$, the second step follows from $I=YY^{\top}+Y_{\bot}Y_{\bot}^{\top}$, the third step follows from simple algebra, and the last step follows from $AA^{-1}=I$.

Combining Eq. ([E.2](#A5.Ex108)) and Eq. ([E.2](#A5.Ex110))

$$ $\displaystyle\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y=$ $\displaystyle~{}U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}+N_{i,:}^{\top}D_{W_{i}}Y(Y^{\top}D_{W_{i}}Y)^{-1}$ (6) $$

$\eta$ is defined as Definition [E.3](#A5.Thmtheorem3).

We define set $T\subset[n]$ as follows

$$ $\displaystyle T:=\{i\in[n]~{}|~{}\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\leq 0.25\alpha/\eta\}.$ (7) $$

We upper bound $|T|$ in different ways for SVD initialization and random initialization.

SVD case. We have $\eta=1$

Using Lemma [G.1](#A7.Thmtheorem1) and choose $\epsilon=\Theta(1)$, we have

$$ $\displaystyle|T|\leq$ $\displaystyle~{}10^{5}\cdot\alpha^{-3}\mu^{2}k^{3}\gamma^{2}\cdot\|W\|_{\infty,1}\cdot\|V-Y\|^{2}$ $\displaystyle=$ $\displaystyle~{}10^{5}\cdot\alpha^{-3}\mu^{2}k^{3}\gamma^{2}\cdot\mu k\cdot(\|W\|_{\infty,1}/n)\cdot\|V-Y\|^{2}/\xi$ $\displaystyle\leq$ $\displaystyle~{}0.1\Delta_{d}^{2}\cdot\operatorname{dist}(V,Y)^{2}/\xi$ $\displaystyle\leq$ $\displaystyle~{}\Delta_{g}^{2}/\xi$ $$

where the second step follows from $\xi=\mu k/n$, the third step follows from Definition of $\Delta_{d}$ (Definition [5.5](#S5.Thmtheorem5)).

(In particular, the third step requires

$$ $\displaystyle\Delta_{d}\geq\Omega(\alpha^{-1.5}\mu^{1.5}k^{2}\gamma\cdot(\|W\|_{\infty,1}/n)^{1/2})$ (8) $$

)

Random case. We have $\eta=\mu k$.
Using Lemma [I.1](#A9.Thmtheorem1), with high probability we know that $|T|=0\leq\Delta_{g}^{2}/\xi$.

In the next analysis, we unify the SVD and random proofs into same way.

For each $i\in[n]\backslash T$, we have

$$ $\displaystyle\|\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}=$ $\displaystyle~{}\|(U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y+N_{i,:}^{\top}D_{i}Y)(Y^{\top}D_{W_{i}}Y)^{-1}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\|(U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y+N_{i,:}^{\top}D_{W_{i}}Y)\|_{2}^{2}\cdot\|(Y^{\top}D_{W_{i}}Y)^{-1}\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}20\alpha^{-2}\eta^{2}\cdot\|(U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y+N_{i,:}^{\top}D_{W_{i}}Y)\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}20\alpha^{-2}\eta^{2}\cdot 2(\|U_{i,:}^{\top}\Sigma V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|_{2}^{2}+\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2})$ $\displaystyle\leq$ $\displaystyle~{}40\alpha^{-2}\eta^{2}\cdot(\|U_{i,:}^{\top}\|_{2}^{2}\|\Sigma\|^{2}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}+\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2})$ $\displaystyle\leq$ $\displaystyle~{}40\alpha^{-2}\eta^{2}\cdot(\frac{\mu k}{n}\|\Sigma\|^{2}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}+\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2})$ (9) $$

where
the first step follows from Eq. ([6](#A5.E6)), the second step follows from $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$, the third step follows from $\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\geq 0.25\alpha/\eta$ (for all $i\in[n]\backslash T$, see Eq. ([7](#A5.E7))), the fourth step follows from $(a+b)^{2}\leq 2a^{2}+2b^{2}$, the fifth step follows from $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$, the sixth step follows from $\|U_{i,:}^{\top}\|^{2}\leq\mu k/n$.

Taking the summation over $i\in[n]\backslash T$ coordinates (for Eq. ([E.2](#A5.Ex118))), we have

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\leq$ $\displaystyle~{}\sum_{i\in[n]\backslash T}40\alpha^{-2}\eta^{2}\cdot(\frac{\mu k}{n}\|\Sigma\|^{2}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}+\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2})$ (10) $$

For the first term in Eq. ([10](#A5.E10)) (ignore coefficients $40\alpha^{-2}\eta^{2}$ and $\frac{\mu k}{n}\|\Sigma\|^{2}$), we have

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}\leq$ $\displaystyle~{}n\gamma^{2}\rho(Y)k^{3}\operatorname{dist}(Y,V)^{2}$ $\displaystyle\leq$ $\displaystyle~{}n\gamma^{2}\mu\sigma_{\min}^{-1}(\Sigma)k^{3}\operatorname{dist}(Y,V)^{2}$ (11) $$

where the first step follows from Lemma [G.2](#A7.Thmtheorem2), the last step follows from $\rho(Y)\leq\mu/\sigma_{\min}(\Sigma)$.

For the second term in Eq. ([10](#A5.E10)) (ignore coefficients $40\alpha^{-2}\eta^{2}$), we have

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2}\leq$ $\displaystyle~{}\sum_{i\in[n]}\|N_{i,:}^{\top}D_{W_{i}}Y\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\|(W\circ N)Y\|_{F}^{2}$ $\displaystyle\leq$ $\displaystyle~{}k\|(W\circ N)Y\|^{2}.$ (12) $$

where the last step follows from Fact [A.10](#A1.Thmtheorem10).

Loading Eq. ([E.2](#A5.Ex123)) and Eq. ([E.2](#A5.Ex124)) into Eq. ([10](#A5.E10)), we have

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\leq$ $\displaystyle~{}40\alpha^{-2}\eta^{2}\cdot(\frac{\mu k}{n}\|\Sigma\|^{2}\cdot n\gamma^{2}\mu\sigma_{\min}^{-1}(\Sigma)k^{3}\operatorname{dist}(Y,V)^{2}+k\|W\circ N\|^{2})$ $\displaystyle\leq$ $\displaystyle~{}40\alpha^{-2}\eta^{2}\cdot(\mu^{2}k^{4}\tau\gamma^{2})\cdot\operatorname{dist}(Y,V)^{2}+40\alpha^{-2}\eta^{2}k\|W\circ N\|^{2}$ (13) $$

where the last step follows from $\|\Sigma\|=1$ and $\tau=\sigma_{\max}(\Sigma)/\sigma_{\min}(\Sigma)$.

Thus, we have

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\leq$ $\displaystyle~{}40\alpha^{-2}\eta^{2}\cdot(\mu^{2}k^{4}\tau\gamma^{2})\cdot\operatorname{dist}(Y,V)^{2}+40\alpha^{-2}\eta^{2}k\|W\circ N\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}0.01\Delta_{d}^{2}\cdot\operatorname{dist}(Y,V)^{2}+0.01\Delta_{f}^{2}\cdot\|W\circ N\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}0.1\Delta_{g}^{2}$ $$

where the first step follows from Eq. ([E.2](#A5.Ex126)), the second step follows from Definition [5.5](#S5.Thmtheorem5), and the last step follows from Definition [E.4](#A5.Thmtheorem4).

(In particular, the second step above requires

$$ $\displaystyle\Delta_{d}\geq\Omega(\alpha^{-1}\eta\mu k^{2}\tau^{0.5}\gamma)$ (14) $$

and

$$ $\displaystyle\Delta_{f}\geq\Omega(\alpha^{-1}\eta k)$ (15) $$

)

By Definition [E.4](#A5.Thmtheorem4) and choosing $\epsilon_{\mathrm{sk}}$ to be sufficiently small as Claim [E.5](#A5.Thmtheorem5), we know that

$$ $\displaystyle\Delta_{g}^{2}\leq 0.01\Delta_{u}^{2}$ $$

Then, we can show

$$ $\displaystyle\sum_{i\in[n]\backslash T}\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\leq$ $\displaystyle~{}2\sum_{i\in[n]\backslash T}\|\widetilde{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}+2\sum_{i\in[n]\backslash T}\|\vec{X}_{i,:}^{\top}-\widetilde{X}_{i,:}^{\top}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\Delta_{g}^{2},$ $$

Note that

$$ $\displaystyle\|U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\leq\mu k/n=\xi.$ $$

If $\|\vec{X}_{i,:}^{\top}\|_{2}^{2}\geq 4\xi$, then

$$ $\displaystyle\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}\geq 2\sqrt{\xi}-\sqrt{\xi}\geq\sqrt{\xi}$ $$

which implies that

$$ $\displaystyle\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\geq\xi.$ (16) $$

We define set $S\subset[n]$ as follows

$$ $\displaystyle S:=\{i\in[n]\backslash T~{}|~{}\|\vec{X}_{i,:}^{\top}\|_{2}^{2}\geq 4\xi\}.$ $$

Then we have

$$ $\displaystyle|S|=$ $\displaystyle~{}|\{i\in[n]\backslash T\mid\|\vec{X}_{i,:}^{\top}\|_{2}^{2}\geq 4\xi\}|$ $\displaystyle\leq$ $\displaystyle~{}|\{i\in[n]\backslash T\mid\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}\geq\xi\}|$ $\displaystyle\leq$ $\displaystyle~{}\Delta_{g}^{2}/\xi.$ $$

where the first step follows from the definition of $S$, the second step follows from Eq. ([16](#A5.E16)), the third step follows from $\sum_{i\in[n]\backslash T}\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|^{2}\leq\Delta_{g}^{2}$.

We can show

$$ $\displaystyle\|\widehat{X}-U\Sigma V^{\top}Y\|_{F}^{2}=$ $\displaystyle~{}\sum_{i=1}^{n}\|\widehat{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i\in T\cup S}\|\widehat{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}+\sum_{i\notin T\cup S}\|\widehat{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i\in T\cup S}\|\widehat{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}+\sum_{i\notin S}\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\sum_{i\in T\cup S}2(\|\widehat{X}_{i,:}^{\top}\|_{2}^{2}+\|U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2})+\sum_{i\notin T\cup S}\|\vec{X}_{i,:}^{\top}-U_{i,:}^{\top}\Sigma V^{\top}Y\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}|T\cup S|\cdot 2\cdot(4\xi+\xi)+\Delta_{g}^{2}$ $\displaystyle=$ $\displaystyle~{}|T\cup S|\cdot 10\xi+\Delta_{g}^{2}$ $\displaystyle\leq$ $\displaystyle~{}50\Delta g^{2}$ $\displaystyle\leq$ $\displaystyle~{}\Delta_{u}^{2}$ $$

where the first step follows from the definition of $\|\widehat{X}-U\Sigma V^{\top}Y\|_{F}^{2}$, the second step follows from $S\subseteq[n]$, the third step follows from $\widehat{X}_{i,:}^{\top}=\vec{X}_{i,:}^{\top}$ when $i\notin S$, the fourth step follows from the triangle inequality, the fifth step follows from $\|\widehat{X}_{i,:}^{\top}\|^{2}\leq 4\xi$ and $\|U_{i,:}^{\top}\Sigma V^{\top}Y\|^{2}\leq\xi$, and the sixth step follows from $|T\cup S|\leq 2\Delta_{g}^{2}/\xi$, the last step follows from Claim [E.5](#A5.Thmtheorem5).

Proof of Part 2.

We let $B=\Sigma V^{\top}Y$ and have

$$ $\displaystyle\sin\theta(U,X)=$ $\displaystyle~{}\|U_{\bot}^{\top}X\|$ $\displaystyle=$ $\displaystyle~{}\|U_{\bot}^{\top}(\overline{X}-UB)R^{-1}\|$ $\displaystyle\leq$ $\displaystyle~{}\|(\overline{X}-UB)\|\cdot\|R^{-1}\|$ $\displaystyle=$ $\displaystyle~{}\frac{\|(\overline{X}-UB)\|}{\sigma_{\min}(\overline{X})}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\Delta_{u}}{\sigma_{\min}(\overline{X})},$ (17) $$

where the first step follows from the definition of

$$ $\displaystyle\sin\theta(U,X)$ $$

(see Definition [D.3](#A4.Thmtheorem3)), the second step follows from

$$ $\displaystyle X=(\overline{X}-UB)R^{-1},$ $$

the 3rd step is due to the Cauchy-Schwarz inequality, and the 4th step is because of

$$ $\displaystyle\|R^{-1}\|=\frac{1}{\sigma_{\min}(\overline{X})},$ $$

and the 5th step follows from

$$ $\displaystyle\|(\overline{X}-U\Sigma V^{\top}Y)\|^{2}\leq\Delta_{u}^{2},$ $$

which was proved in part 1, and it infers $\|(\overline{X}-UB)\|\leq\Delta_{u}$ for $B=\Sigma V^{\top}Y$.

Using $\|(\overline{X}-UB)\|\leq\Delta_{u}$, we have

$$ $\displaystyle\sigma_{\min}(\overline{X})\geq$ $\displaystyle~{}\sigma_{\min}(UB)-\Delta_{u}$ $\displaystyle=$ $\displaystyle~{}\sigma_{\min}(U\Sigma V^{\top}Y)-\Delta_{u}$ $\displaystyle=$ $\displaystyle~{}\sigma_{\min}(\Sigma V^{\top}Y)-\Delta_{u}$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(M^{*})\cos\theta(Y,V)-\Delta_{u}$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(M^{*})/2-\Delta_{u}$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(M^{*})/4,$ (18) $$

where the second step follows from how we defined $B$, the third step follows from $U$ has orthonormal columns, the third step follows from

$$ $\displaystyle\sigma_{\min}(\Sigma V^{\top}Y)\geq\sigma_{\min}(M^{*})\cos\theta(Y,V),$ $$

where the forth step follows from $\cos\geq 1/2$, and $\Delta_{u}\leq\sigma_{\min}(M^{*})/10$.

Then, by combining Eq. ([E.2](#A5.Ex147)) and Eq. ([E.2](#A5.Ex155)), we have

$$ $\displaystyle\sin\theta(U,X)\leq$ $\displaystyle~{}\frac{1}{\sigma_{\min}(\overline{X})}\Delta_{u}$ $\displaystyle\leq$ $\displaystyle~{}4\Delta_{u}/\sigma_{\min}(M^{*}).$ (19) $$

Therefore,

$$ $\displaystyle\operatorname{dist}(U,X)\leq$ $\displaystyle~{}2\sin\theta(U,X)$ $\displaystyle\leq$ $\displaystyle~{}8\Delta_{u}/\sigma_{\min}(M^{*}).$ $$

where the first step follows from Part 5 of Lemma [D.8](#A4.Thmtheorem8), and the last step follows from Eq. ([E.2](#A5.Ex161)).

Proof Part 3

Given $\overline{X}=XR$, we have $\overline{X}_{i,:}^{\top}=X_{i,:}^{\top}R$ and

$$ $\displaystyle\|X_{i,:}\|_{2}^{2}\leq$ $\displaystyle~{}\|\overline{X}_{i,:}\|_{2}^{2}\|R^{-1}\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\xi}{\sigma_{\min}(\overline{X})^{2}}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\xi}{(\sigma_{\min}(M^{*})-2\Delta_{u})^{2}}$ $\displaystyle\leq$ $\displaystyle~{}8\xi/\sigma_{\min}(M^{*})^{2},$ (20) $$

where the first step follows from $\overline{X}_{i,:}^{\top}=X_{i,:}^{\top}R$ and Cauchy-Schwarz inequality, the second step follows from $\|\overline{X}_{i,:}\|^{2}\leq\xi$ and $\|R^{-1}\|=\frac{1}{\sigma_{\min}(\overline{X})}$, the third step follows from $\frac{1}{\sigma_{\min}(\overline{X})^{2}}\leq\frac{1}{(\sigma_{\min}(M^{*})-2\Delta_{u})^{2}}$, and the last step follows from $\Delta_{u}\leq 0.1\sigma_{\min}(M^{*})$

To see this, we have

$$ $\displaystyle\|R^{-1}\|^{2}=$ $\displaystyle~{}\lambda_{\max}(R^{-1}(R^{-1})^{\top})$ $\displaystyle=$ $\displaystyle~{}\lambda_{\max}((\overline{X}^{\top}\overline{X})^{-1})$ $\displaystyle=$ $\displaystyle~{}\frac{1}{\lambda_{\min}(\overline{X}^{\top}\overline{X})}$ $\displaystyle=$ $\displaystyle~{}\frac{1}{\sigma_{\min}^{2}(\overline{X})},$ $$

where the first step follows from $\|A\|^{2}=\lambda_{\max}(AA^{\top})$, the second step follows from $\overline{X}^{\top}\overline{X}=R^{\top}R$, the third step follows from $\lambda_{\max}(A^{-1})=\lambda_{\min}(A)^{-1}$, and the last step follows from $\lambda(A^{\top}A)=\sigma^{2}(A)$.

Then,

$$ $\displaystyle\rho(X)=$ $\displaystyle~{}\max_{i\in[n]}\frac{n}{k}\|X_{i,:}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{n}{k}\max_{i\in[n]}\|X_{i,:}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{n}{k}\frac{8\xi}{\sigma_{\min}(M^{*})^{2}}$ $\displaystyle=$ $\displaystyle~{}\frac{8\mu}{\sigma_{\min}(M^{*})^{2}},$ $$

where the first step follows from the definition of $\rho(X)$, the second step follows from simple algebra, the third step follows from Eq. ([E.2](#A5.Ex164)), and the last step follows from $\frac{\xi n}{k}=\mu$.
∎

###### Lemma E.8 (Key lemma for update step) .

###### Proof.

## Appendix F The Analysis of the Induction Lemma

The goal of this section is to prove induction.

###### Lemma F.1 .

Suppose

$$ $\displaystyle\Delta_{u}\leq\Delta_{d}\cdot\operatorname{dist}(Y_{t},V)+\Delta_{f}\cdot\|W\circ N\|.$ $$

and

$$ $\displaystyle\Delta_{d}\leq\frac{1}{100}\sigma_{\min}(M^{*})$ $$

For any $t\geq 1$,

$$ $\displaystyle\operatorname{dist}(X_{t},U)\leq\frac{1}{2^{t}}+100\sigma_{\min}(M^{*})^{-1}\cdot\Delta_{f}\cdot\|W\circ N\|,$ $\displaystyle\operatorname{dist}(Y_{t},V)\leq\frac{1}{2^{t}}+100\sigma_{\min}(M^{*})^{-1}\cdot\Delta_{f}\cdot\|W\circ N\|,$ (21) $$

###### Proof.

By using induction, we show that Eq. ([F.1](#A6.Ex177)) holds.

Base case:

By Lemma [G.3](#A7.Thmtheorem3), $Y_{1}$ satisfies

$$ $\displaystyle\operatorname{dist}(Y_{1},V)\leq$ $\displaystyle~{}\frac{1}{2}+8\sigma_{\min}(M^{*})^{-1}\cdot\Delta_{f}\cdot\|W\circ N\|$ $$

Inductive case:

Suppose that it holds for the first $t$ cases.

By definition of $\Delta_{u}$, we have

$$ $\displaystyle\Delta_{u}\leq\Delta_{d}\cdot\operatorname{dist}(Y_{t},V)+\Delta_{f}\cdot\|W\circ N\|$ (22) $$

We have

$$ $\displaystyle~{}\operatorname{dist}(X_{t+1},U)$ $\displaystyle\leq$ $\displaystyle~{}\frac{8}{\sigma_{\min}(M^{*})}\cdot\Delta_{u}$ $\displaystyle=$ $\displaystyle~{}\frac{8}{\sigma_{\min}(M^{*})}\cdot(\Delta_{d}\cdot\operatorname{dist}(Y_{t},V)+\Delta_{f}\cdot\|W\circ N\|)$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{2}\operatorname{dist}(Y_{t},V)+8\sigma_{\min}(M^{*})^{-1}\cdot\Delta_{f}\cdot\|W\circ N\|$ $$

where the first step follows from Part 2 of Lemma [E.8](#A5.Thmtheorem8), the second step follows from Eq. ([22](#A6.E22)) the last step follows from $\Delta_{d}/\sigma_{\min}(M^{*})\leq 1/100$.
∎

###### Lemma F.1 .

###### Proof.

## Appendix G Tools from Previous Work

In this section, we state several tools from previous work.
In Section [G.1](#A7.SS1), we introduce a varied version of a Lemma from [] to bound the eigenvalues. In Section [G.2](#A7.SS2), we bound $\|V^{\top}Y_{\bot}(Y_{\bot})^{\top}D_{W_{i}}Y\|^{2}$. In Section [G.3](#A7.SS3), we summarize the base case lemma.

### G.1 Bounding Eigenvalues

Now, in this section, we start to bound the eigenvalues.

###### Lemma G.1 (A variation of Lemma 10 in [ 27 ] ) .

Let $Y$ be a (column) orthogonal matrix in $\mathbb{R}^{n\times k}$.

Let $\epsilon\in(0,1)$.

We have

$$ $\displaystyle|\{i\in[n]~{}|~{}\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\leq(1-\epsilon)\alpha\}|\leq 10^{4}\cdot\frac{\mu^{2}k^{3}\gamma^{2}}{\epsilon^{4}\alpha^{3}}\cdot\|W\|_{\infty,1}\cdot\|V-Y\|^{2}.$ $$

###### Proof.

Let $j$ be an arbitrary integer in $[n]$.

Let $g$ be greater than 0 0.

$j$ is called “good” if

$$ $\displaystyle\|Y_{j}-V_{j}\|_{2}^{2}\leq g^{2}.$ $$

We define $S_{g}\subset[n]$ as follows

$$ $\displaystyle S_{g}:=\{j\in[n]~{}|~{}\|Y_{j}-V_{j}\|_{2}^{2}\leq g^{2}\}.$ $$

For convenient, we define $\overline{S}_{g}\subset[n]$ as follows

$$ $\displaystyle\overline{S}_{g}:=[n]\backslash S_{g}.$ $$

We choose $g$ to satisfy the following condition

$$ $\displaystyle g^{2}=\frac{\epsilon^{2}\alpha}{20\|W\|_{\infty,1}}.$ (23) $$

Let $a$ be an arbitrary unit vector in $\mathbb{R}^{k}$.

Thus, we have

$$ $\displaystyle a^{\top}Y^{\top}D_{W_{i}}Ya=$ $\displaystyle~{}\sum_{j\in[n]}(D_{W_{i}})_{j}\langle a,Y_{j}\rangle^{2}$ $\displaystyle\geq$ $\displaystyle~{}\sum_{j\in S_{g}}(D_{W_{i}})_{j}\langle a,Y_{j}\rangle^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{j\in S_{g}}(D_{W_{i}})_{j}(\langle a,V_{j}\rangle+\langle a,Y_{j}-V_{j}\rangle)^{2}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in S_{g}}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-4\epsilon^{-1}\sum_{j\in S_{g}}(D_{W_{i}})_{j}\langle a,Y_{j}-V_{j}\rangle^{2}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in S_{g}}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-4\epsilon^{-1}g^{2}\sum_{j\in S_{g}}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in S_{g}}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in[n]}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in[n]}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-\frac{\mu k}{n}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j},$ (24) $$

where the first step follows from simple algebra, the second step follows from $S_{g}\subset[n]$, the third step follows from the property of the inner product, the fourth step follows from Fact [A.8](#A1.Thmtheorem8),
the fifth step follows from the definition of $S_{g}$, the sixth step follows from $(D_{W_{i}})_{j}\geq 0$, the seventh step follows from $1-\epsilon/4\leq 1$, and the last step follows from the property of $V$ (e.g. $\langle a,V_{j}\rangle^{2}\leq\|a\|_{2}^{2}\cdot\|V_{j}\|_{2}^{2}\leq\|V_{j}\|_{2}^{2}\leq\xi\leq\mu k/n$).

We can show that

$$ $\displaystyle\sum_{j\in[n]}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}=$ $\displaystyle~{}a^{\top}V^{\top}(D_{W_{i}})_{j}Va$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(V^{\top}(D_{W_{i}})_{j}V)$ $\displaystyle\geq$ $\displaystyle~{}\alpha,$ (25) $$

where the second step follows from Fact [A.10](#A1.Thmtheorem10) and the third step follows from definition of $\alpha$ (see Definition [5.3](#S5.Thmtheorem3)) and $\sigma_{\min}(A)\leq\sigma_{\min}(B)$ if $A\preceq B$.

Moreover, recall

$$ $\displaystyle\|W\|_{\infty,1}=\max_{i\in[n]}\sum_{j\in[n]}|(D_{W_{i}})_{j}|,$ (26) $$

We can show that

$$ $\displaystyle 4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}\leq$ $\displaystyle~{}4\epsilon^{-1}g^{2}\|W\|_{\infty,1}$ $\displaystyle=$ $\displaystyle~{}4\epsilon^{-1}\frac{\epsilon^{2}\alpha}{20\|W\|_{\infty,1}}\|W\|_{\infty,1}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\epsilon\alpha}{4},$ (27) $$

where the first step follows from the definition of $\|W\|_{\infty,1}$ (see Eq. ([26](#A7.E26))), the second step follows from the definition of $g^{2}$ (see Eq. ([23](#A7.E23))), and the last step follows from simple algebra.

We define

$$ $\displaystyle T:=\{i\in[n]~{}|~{}\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\leq(1-\epsilon)\alpha\}.$ $$

Let us consider

$$ $\displaystyle\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}.$ $$

We define

$$ $\displaystyle S:=\{i\in[n]\mid\frac{\mu k}{n}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}\geq\frac{\epsilon\alpha}{4}\}.$ (28) $$

If $i\notin S$, then we have

$$ $\displaystyle a^{\top}Y^{\top}D_{W_{i}}Ya\geq$ $\displaystyle~{}(1-\epsilon/4)\sum_{j\in[n]}(D_{W_{i}})_{j}\langle a,V_{j}\rangle^{2}-\frac{\mu k}{n}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\alpha-\frac{\mu k}{n}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\alpha-\epsilon\alpha/4-4\epsilon^{-1}g^{2}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon/4)\alpha-\epsilon\alpha/4-\epsilon\alpha/4$ $\displaystyle\geq$ $\displaystyle~{}(1-\epsilon)\alpha,$ $$

where the first step follows from Eq. ([G.1](#A7.Ex187)), the second step follows Eq. ([G.1](#A7.Ex194)), the third step follows from the Definition of $S$ (see Eq. ([28](#A7.E28))), the fourth step follows from Eq. ([G.1](#A7.Ex196)), and the last step follows from simple algebra.

In summary, we know that if $i\notin S$, then $i\notin T$. By taking its contraposition, we have that if $i\in T$, then $i\in S$.

Thus, we can show that

$$ $\displaystyle|T|\leq|S|$ $$

In the next a few paragraphs, we will explain how to upper bound $|S|$.

Using Fact [A.10](#A1.Thmtheorem10)

$$ $\displaystyle\sum_{j\in[n]}\|V_{j}-Y_{j}\|_{2}^{2}=\|V-Y\|_{F}^{2},$ $$

By simple counting argument (you have $n$ positive values, their summation is $\|V-Y\|_{F}^{2}$, you can’t have more than ${\|V-Y\|_{F}^{2}}/{g^{2}}$ of them that are bigger than $g^{2}$), we have

$$ $\displaystyle|\overline{S}_{g}|\leq$ $\displaystyle~{}{\|V-Y\|_{F}^{2}}/{g^{2}}.$ (29) $$

Let $u_{S}\in\mathbb{R}^{n}$ be the indicator vector of $S$, i.e.,

$$ $\displaystyle\forall i\in[n],~{}~{}~{}(u_{S})_{i}=\begin{cases}1&\text{~{}if~{}}i\in S;\\ 0&\text{~{}otherwise~{}}i\notin S.\end{cases}$ $$

Let $u_{g}\in\mathbb{R}^{n}$ be the indicator vector of $\overline{S}_{g}$, i.e.,

$$ $\displaystyle\forall i\in[n],~{}~{}~{}(u_{g})_{i}=\begin{cases}1&\text{~{}if~{}}i\in\overline{S}_{g};\\ 0&\text{~{}otherwise~{}}i\notin\overline{S}_{g}.\end{cases}$ $$

Then, we know that

$$ $\displaystyle u_{S}^{\top}Wu_{g}=$ $\displaystyle~{}\sum_{i\in S}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}|S|\cdot\min_{i\in S}\sum_{j\in\overline{S}_{g}}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}|S|\cdot\frac{\epsilon\alpha n}{4\mu k},$ (30) $$

where the first step follows from simple algebra, and the second step follows from simple algebra, the third step follows from Definition ([28](#A7.E28)).

On the other hand,

$$ $\displaystyle u_{S}^{\top}Wu_{g}=$ $\displaystyle~{}u_{S}^{\top}{\bf 1}_{n}{\bf 1}_{n}^{\top}u_{g}+u_{S}^{\top}(W-{\bf 1}_{n}{\bf 1}_{n}^{\top})u_{g}$ $\displaystyle=$ $\displaystyle~{}\|u_{S}\|_{1}\cdot\|u_{g}\|_{1}+u_{S}^{\top}(W-{\bf 1}_{n}{\bf 1}_{n}^{\top})u_{g}$ $\displaystyle\leq$ $\displaystyle~{}\|u_{S}\|_{1}\cdot\|u_{g}\|_{1}+\|u_{S}\|_{2}\cdot\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|\cdot\|u_{g}\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\|u_{S}\|_{1}\cdot\|u_{g}\|_{1}+\gamma n\cdot\|u_{S}\|_{2}\cdot\|u_{g}\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}|S||\overline{S}_{g}|+\gamma n\sqrt{|S||\overline{S}_{g}|},$ (31) $$

where the first step follows from simple algebra, the second step follows from simple algebra, the third step follows from $x^{\top}Ay\leq\|x\|_{2}\|A\|\|y\|_{2}$, the fourth step follows from Definition [5.2](#S5.Thmtheorem2), and the last step follows from $u_{S}$ and $u_{g}$ are indicator vectors.

By combining Eq. ([G.1](#A7.Ex209)) and Eq. ([G.1](#A7.Ex211)), we have

$$ $\displaystyle|\overline{S}_{g}|+\gamma n\cdot\sqrt{|\overline{S}_{g}|/|S|}\geq\frac{\epsilon\alpha n}{4\mu k}.$ (32) $$

Note that if $A+B\geq C$. Then if $A\leq C/2$, then $B\geq C/2$.

For the terms in Eq. ([32](#A7.E32)), we define $A,B$ and $C$ as follows

$$ $\displaystyle A:=$ $\displaystyle~{}|\overline{S}_{g}|$ $\displaystyle B:=$ $\displaystyle~{}\gamma n\cdot\sqrt{|\overline{S}_{g}|/|S|}$ $\displaystyle C:=$ $\displaystyle~{}\frac{\epsilon\alpha n}{4\mu k}$ $$

If

$$ $\displaystyle|\overline{S}_{g}|\leq\frac{\epsilon\alpha n}{8\mu k},$ $$

then, we have

$$ $\displaystyle\gamma n\cdot\sqrt{|\overline{S}_{g}|/|S|}\geq\frac{\epsilon\alpha n}{8\mu k}.$ $$

The above equation implies

$$ $\displaystyle|S|\leq$ $\displaystyle~{}500\cdot\frac{\mu^{2}k^{2}\gamma^{2}}{\epsilon^{2}\alpha^{2}}\cdot|\overline{S}_{g}|$ $\displaystyle\leq$ $\displaystyle~{}500\cdot\frac{\mu^{2}k^{2}\gamma^{2}}{\epsilon^{2}\alpha^{2}}\cdot(\|V-Y\|_{F}^{2}/g^{2}),$ $\displaystyle\leq$ $\displaystyle~{}500\cdot\frac{\mu^{2}k^{2}\gamma^{2}}{\epsilon^{2}\alpha^{2}}\cdot\|V-Y\|_{F}^{2}\cdot\frac{20\|W\|_{\infty,1}}{\epsilon^{2}\alpha}$ (33) $$

where the second step follows from Eq. ([29](#A7.E29)) and last step follows from Eq. ([23](#A7.E23)).

We have

$$ $\displaystyle|\{i\in[n]~{}|~{}\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\leq(1-\epsilon)\alpha\}|\leq$ $\displaystyle~{}|S|$ $\displaystyle\leq$ $\displaystyle~{}10^{4}\cdot\frac{\mu^{2}k^{2}\gamma^{2}}{\epsilon^{4}\alpha^{3}}\cdot\|W\|_{\infty,1}\cdot\|V-Y\|_{F}^{2}$ $\displaystyle\leq$ $\displaystyle~{}10^{4}\cdot\frac{\mu^{2}k^{2}\gamma^{2}}{\epsilon^{4}\alpha^{3}}\cdot\|W\|_{\infty,1}\cdot k\cdot\|V-Y\|^{2}$ $$

where the first step follows from the definition of $S$ and the second step follows from combining Eq. ([G.1](#A7.Ex220)) and Eq. ([23](#A7.E23)), and the last step follows from Fact [A.10](#A1.Thmtheorem10).

This completes the proof.

∎

###### Lemma G.1 (A variation of Lemma 10 in [ 27 ] ) .

###### Proof.

### G.2 Bounding ‖ V ⊤ ​ Y ⊥ ​ ( Y ⊥ ) ⊤ ​ D W i ​ Y ‖ 2 superscript norm superscript 𝑉 top subscript 𝑌 bottom superscript subscript 𝑌 bottom top subscript 𝐷 subscript 𝑊 𝑖 𝑌 2 \|V^{\top}Y_{\bot}(Y_{\bot})^{\top}D_{W_{i}}Y\|^{2}

In this section, we bound $\|V^{\top}Y_{\bot}(Y_{\bot})^{\top}D_{W_{i}}Y\|^{2}$.

###### Lemma G.2 (A variation of Lemma 11 in [ 27 ] ) .

Let $Y$ be a (column) orthogonal matrix in $\mathbb{R}^{n\times k}$.

Let $i\in[n]$.

Then we have

$$ $\displaystyle\sum_{i\in[n]}\|V^{\top}Y_{\bot}(Y_{\bot})^{\top}D_{W_{i}}Y\|^{2}\leq\gamma^{2}\rho(Y)nk^{3}\|Y-V\|^{2}$ $$

For the completeness, we still provide the proof.

###### Proof.

Let $j^{\prime},j$ be two positive integers in $[k]$.

$Y_{j}$ represents the matrix $Y$’s j-th column.

$\widetilde{V}_{j}$ represents the matrix $Y_{\bot}Y_{\bot}^{\top}V$’s j-th column.

We define $x^{j,j^{\prime}}\in\mathbb{R}^{n}$ as

$$ $\displaystyle x_{i}^{j,j^{\prime}}=(\widetilde{V}_{j})_{i}(Y_{j^{\prime}})_{i}.$ $$

We need to show that the spectral norm of

$$ $\displaystyle V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y,$ $$

is bounded.

Note that $\langle\widetilde{V}_{j},Y_{j^{\prime}}\rangle=0$, which implies that

$$ $\displaystyle\sum_{i\in[n]}x_{i}^{j,j^{\prime}}=0.$ $$

For $V_{j}^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y_{j^{\prime}}$,

$$ $\displaystyle V_{j}^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y_{j^{\prime}}=$ $\displaystyle~{}\sum_{s\in[n]}(D_{W_{i}})_{s}(\widetilde{V}_{j})_{s}(Y_{j^{\prime}})_{s}$ $\displaystyle=$ $\displaystyle~{}\sum_{s\in[n]}(D_{W_{i}})_{s}x_{s}^{j,j^{\prime}},$ (34) $$

where the first step follows from the definition of

$$ $\displaystyle V_{j}^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y_{j^{\prime}}$ $$

and the second step follows from $(\widetilde{V}_{j})_{s}(Y_{j^{\prime}})_{s}=x_{s}^{j,j^{\prime}}$.

It implies that

$$ $\displaystyle\sum_{i\in[n]}(\sum_{s\in[n]}(D_{W_{i}})_{s}x_{s}^{j,j^{\prime}})^{2}=$ $\displaystyle~{}\|Wx^{j,j^{\prime}}\|_{2}^{2}$ $\displaystyle=$ $\displaystyle~{}\|(W-{\bf 1}_{n}{\bf 1}_{n}^{\top})x^{j,j^{\prime}}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|^{2}\|x^{j,j^{\prime}}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\gamma^{2}n^{2}\|x^{j,j^{\prime}}\|_{2}^{2},$ $$

where the first step follows from the definition of $\|Wx^{j,j^{\prime}}\|_{2}^{2}$, the second step follows from ${\bf 1}_{n}{\bf 1}_{n}^{\top}x^{j,j^{\prime}}=0$, the third step follows from $\|Ax\|_{2}\leq\|A\|\|x\|_{2}$, and the last step follows from $\|W-{\bf 1}_{n}{\bf 1}_{n}^{\top}\|\leq\gamma n$ (see Definition [5.2](#S5.Thmtheorem2)).

Observe that

$$ $\displaystyle\|x^{j,j^{\prime}}\|_{2}^{2}=$ $\displaystyle~{}\sum_{i\in[n]}(x^{j,j^{\prime}})^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i\in[n]}(\widetilde{V}_{j})_{i}^{2}(Y_{j^{\prime}})_{i}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\rho(Y)k}{n}\sum_{i\in[n]}(\widetilde{V}_{j})_{i}^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{\rho(Y)k}{n}\|\widetilde{V}_{j}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\rho(Y)k}{n}\|Y_{\bot}Y_{\bot}^{\top}V\|^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{\rho(Y)k}{n}\|Y_{\bot}Y_{\bot}^{\top}(Y-V)\|^{2}$ $\displaystyle=$ $\displaystyle~{}\frac{\rho(Y)k}{n}\|Y_{\bot}Y_{\bot}^{\top}\|\cdot\|Y-V\|^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\rho(Y)k}{n}\|Y-V\|^{2}$ $$

where the first step follows from the definition of $\|x^{j,j^{\prime}}\|_{2}^{2}$, the second step follows from $(x^{j,j^{\prime}})^{2}=(\widetilde{V}_{j})_{i}^{2}(Y_{j^{\prime}})_{i}^{2}$, the third step follows from definition of $\rho$, the fourth step follows from the definition of $\|\cdot\|_{2}^{2}$, the fifth step follows from the fact that $\widetilde{V}_{j}$ is defined to be the $j$-th column of $Y_{\bot}Y_{\bot}^{\top}V$, the sixth step follows from $Y_{\bot}^{\top}Y=0$, the seventh step follows from $\|AB\|\leq\|A\|\cdot\|B\|$, and the last step follows from $\|Y_{\bot}Y_{\bot}\|\leq 1$.

It implies that

$$ $\displaystyle\sum_{i\in[n]}(\sum_{s\in[n]}(D_{W_{i}})_{s}x_{s}^{j,j^{\prime}})^{2}\leq\gamma^{2}\rho(Y)nk\|Y-V\|^{2}.$ (35) $$

Now we are ready to bound $V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y$.

Note that

$$ $\displaystyle\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}\leq$ $\displaystyle~{}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|_{F}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\sum_{j,j^{\prime}\in[k]}(V_{j}^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y_{j^{\prime}})^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{j,j^{\prime}\in[k]}(\sum_{s\in[n]}(D_{W_{i}})_{s}x_{s}^{j,j^{\prime}})^{2},$ (36) $$

where the first step follows from $\|A\|\leq\|A\|_{F}$ for all matrix $A$, the second step follows from definition of $\|\cdot\|_{F}$, and the third step follows from Eq. ([G.2](#A7.Ex229)).

This implies that

$$ $\displaystyle\sum_{i\in[n]}\|V^{\top}Y_{\bot}Y_{\bot}^{\top}D_{W_{i}}Y\|^{2}\leq$ $\displaystyle~{}\sum_{i\in[n]}\sum_{j,j^{\prime}\in[k]}(\sum_{s\in[n]}(D_{W_{i}})_{s}x_{s}^{j,j^{\prime}})^{2}$ $\displaystyle\leq$ $\displaystyle~{}\sum_{j,j^{\prime}\in[k]}\gamma^{2}\rho(Y)nk\|Y-V\|^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{j\in[k]}\sum_{j^{\prime}\in[k]}\gamma^{2}\rho(Y)nk\|Y-V\|^{2}$ $\displaystyle=$ $\displaystyle~{}kk\gamma^{2}\rho(Y)nk\|Y-V\|^{2}$ $\displaystyle=$ $\displaystyle~{}\gamma^{2}\rho(Y)nk^{3}\|Y-V\|^{2},$ $$

where the first step follows from Eq. ([G.2](#A7.Ex243)), the second step follows from Eq. ([35](#A7.E35)), the third step follows from simple algebra, the fourth step follows from the property of $\sum$ (e.g. $\sum_{i=1}^{n}a=an$), and the last step follows from simple algebra.

This completes the proof.
∎

###### Lemma G.2 (A variation of Lemma 11 in [ 27 ] ) .

###### Proof.

### G.3 Summary of Base case Lemma

We state a general base case lemma that covers both random initialization and SVD initialization.

###### Lemma G.3 (General base case lemma ) .

Let $\Delta_{f}:=20\alpha^{-1}\eta k$.

For the base case, we have

$$ $\displaystyle\operatorname{dist}(Y_{1},V)\leq\frac{1}{2}+8\sigma_{\min}(M^{*})^{-1}\cdot\Delta_{f}\cdot\|W\circ N\|_{F}.$ $$

The proofs are delayed into Section [I](#A9) and Section [H](#A8).

###### Lemma G.3 (General base case lemma
) .

## Appendix H SVD Initialization and Main Result

In Section [H.1](#A8.SS1), we introduce our assumption on $\delta$. In Section [H.2](#A8.SS2), we bound $\|(W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ H\|$. In Section [H.3](#A8.SS3), we analyze $\operatorname{rank}$-$k$. In Section [H.4](#A8.SS4), we analyze the properties of $\operatorname{dist}$ and $\rho$. In Section [H.5](#A8.SS5), we present our main result.

### H.1 Assumption

Here, we explain how we assume the value of $\delta$.

###### Definition H.1 ( $\delta$ ) .

We assume that

$$ $\displaystyle\delta:=0.001\cdot\|W\circ N\|\leq\alpha\sigma_{\min}(M^{*})/k.$ $$

###### Definition H.1 ( δ 𝛿 \delta ) .

### H.2 Bounding ‖ ( W − 𝟏 n ​ 𝟏 n ⊤ ) ∘ H ‖ norm 𝑊 subscript 1 𝑛 superscript subscript 1 𝑛 top 𝐻 \|(W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ H\|

In this section, we bound $\|(W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ H\|$.

###### Lemma H.2 (Spectral lemma, Lemma 5 in [ 27 ] ) .

Let $K$ and $J$ be (column) orthogonal matrices, whose dimensions are $n\times n$.

Let $H$ be an arbitrary matrix in $\mathbb{R}^{n\times n}$ satisfying

$$ $\displaystyle H=A\Sigma B^{\top},$ (37) $$

where $A\in\mathbb{R}^{n\times k}$, $B\in\mathbb{R}^{n\times k}$, and $\Sigma\in\mathbb{R}^{k\times k}$.

$A$ and $B$ might not be orthogonal, but $\Sigma$ is diagonal.

$W\in\mathbb{R}^{n\times n}$ is an entry wise non-negative matrix, which has a spectral gap, satisfying

$$ $\displaystyle W=\mathbf{1}_{n}\mathbf{1}_{n}^{\top}+\gamma nJ\Sigma_{W}K^{\top},$ $$

where

$$ $\displaystyle\|\Sigma_{W}\|=1$ $$

Let $\sigma_{1}:=\max_{r\in[k]}\sigma_{r}(\Sigma)$.

Then, we have

$$ $\displaystyle\|(W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ H\|\leq\gamma k\sigma_{1}\sqrt{\rho(A)\rho(B)}.$ $$

###### Proof.

For each $i\in[n]$, let $A_{i,:}$ denote the $i$-th row of matrix $A\in\mathbb{R}^{n\times k}$.

For each $r\in[k]$, let $A_{r}$ denote the $r$-th column of matrix $A\in\mathbb{R}^{n\times k}$.

Then we have

$$ $\displaystyle\sum_{r=1}^{k}\|A_{r}\circ x\|_{2}^{2}=$ $\displaystyle~{}\sum_{r=1}^{k}\sum_{i=1}^{n}A_{i,r}^{2}x_{i}^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{n}x_{i}^{2}\sum_{r=1}^{k}A_{i,r}^{2}$ $\displaystyle=$ $\displaystyle~{}\sum_{i=1}^{n}x_{i}^{2}\|A_{i,:}\|_{2}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\sum_{i=1}^{n}x_{i}^{2}\frac{k}{n}\rho(A)$ $\displaystyle\leq$ $\displaystyle~{}\frac{k}{n}\rho(A)$ (38) $$

where the first step follows from the definition of $\|\cdot\|_{2}^{2}$, the second step follows from simple algebra, the third step follows from the definition of $\|\cdot\|_{2}^{2}$, the fourth step follows from the definition of $\rho$ (Definition [D.1](#A4.Thmtheorem1)), and the last step follows from $\sum_{i=1}^{n}x_{i}^{2}\leq 1$.

Let $x,y\in\mathbb{R}^{n}$ be two arbitrary unit vectors.

Then, we have

$$ $\displaystyle x^{\top}((W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ H)y=$ $\displaystyle~{}x^{\top}((W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ(A\Sigma B^{\top}))y$ $\displaystyle=$ $\displaystyle~{}\sum_{r=1}^{k}\sigma_{r}x^{\top}((W-\mathbf{1}_{n}\mathbf{1}_{n}^{\top})\circ A_{r}B_{r}^{\top})y$ $\displaystyle=$ $\displaystyle~{}\gamma n\sum_{r=1}^{k}\sigma_{r}(A_{r}\circ x)^{\top}J\Sigma_{W}K^{\top}(B_{r}\circ y)$ $\displaystyle\leq$ $\displaystyle~{}\gamma n\sum_{r=1}^{k}\sigma_{r}\|A_{r}\circ x\|_{2}\cdot\|J\Sigma_{W}K^{\top}\|\cdot\|B_{r}\circ y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\gamma n\sum_{r=1}^{k}\sigma_{r}\|A_{r}\circ x\|_{2}\cdot\|B_{r}\circ y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\gamma n\sigma_{1}\sum_{r=1}^{k}\|A_{r}\circ x\|_{2}\cdot\|B_{r}\circ y\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\gamma n\sigma_{1}(\sum_{r=1}^{k}\|A_{r}\circ x\|_{2}^{2})^{1/2}(\sum_{r=1}^{k}\|B_{r}\circ y\|_{2}^{2})^{1/2}$ $\displaystyle\leq$ $\displaystyle~{}\gamma n\sigma_{1}\sqrt{\frac{k}{n}\rho(A)}\sqrt{\frac{k}{n}\rho(B)}$ $\displaystyle\leq$ $\displaystyle~{}\gamma\sigma_{1}\cdot k\cdot(\rho(A)\rho(B))^{1/2},$ $$

where the first step follows from the definition of $H$ (see Eq. ([37](#A8.E37))), the second step follows from $\Sigma$ is a diagonal matrix, the third step follows from the definition of $W$, the fourth step follows from $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$, the fifth step follows from $\|J\Sigma_{W}K^{\top}\|\leq\|J\|\cdot\|\Sigma_{W}\|\cdot\|W\|\leq 1$, the sixth step follows from $\sigma_{1}=\max_{r\in[k]}\sigma_{r}$, the seventh step follows from Cauchy-Schwarz inequality, the eighth step follows from Eq. ([H.2](#A8.Ex255)), and the last step follows from simple algebra.

The lemma follows from the definition of the operator norm.

∎

###### Lemma H.3 (Wedin’s Theorem, Lemma 6 in [ 27 ] ) .

$M^{*}$ is a matrix, and $\sigma_{1},\ldots,\sigma_{n}$ are the singular values of $M^{*}$.

${\widetilde{M}}$ is a matrix, and ${\widetilde{\sigma}}_{1},\ldots,{\widetilde{\sigma}}_{n}$ are the singular values of ${\widetilde{M}}$.

Suppose that $X,Y$ and $U,V$ are the first $k$ singular vectors (left and right) of ${\widetilde{M}},M^{*}$ respectively.

If there exists $a$ which is greater than 0 0 and satisfies

$$ $\displaystyle\max_{r\in\{k+1,\cdots,n\}}{\widetilde{\sigma}}_{r}\leq\min_{i\in\{1,\cdots,k\}}\sigma_{i}-a,$ $$

then

$$ $\displaystyle\frac{\|M^{*}-{\widetilde{M}}\|}{a}\geq\max\{\sin{\theta(V,Y)},\sin{\theta(U,X)}\}.$ $$

###### Lemma H.2 (Spectral lemma, Lemma 5 in [ 27 ] ) .

###### Proof.

###### Lemma H.3 (Wedin’s Theorem, Lemma 6 in [ 27 ] ) .

### H.3 Property of rank- k 𝑘 k

Now, we first define $\Delta_{1}$, and then analyze the properties of $\operatorname{rank}$-$k$.

###### Definition H.4 .

We define $\Delta_{1}$ as follows

$$ $\displaystyle\Delta_{1}:=\frac{10(\gamma\mu k+\delta)}{\sigma_{\min}(M^{*})}.$ $$

###### Lemma H.5 (Lemma 7 in [ 27 ] ) .

Assume that $W$ and $M^{*}$ satisfy every assumption.

We define $(X,\Sigma,Y):=\operatorname{rank}$-$k$ $\mathrm{SVD}(W\circ M)$.

Let $\Delta_{1}$ be defined as Definition [H.4](#A8.Thmtheorem4) and assume that $\Delta_{1}\leq 0.01$.

Then, we have

$$ $\displaystyle\max\{\tan{\theta(X,U)},\tan{\theta(Y,V)}\}\leq 0.5\Delta_{1}.$ $$

###### Proof.

We know that

$$ $\displaystyle\|W\circ M-M^{*}\|=$ $\displaystyle~{}\|W\circ(M^{*}+N)-M^{*}\|$ $\displaystyle\leq$ $\displaystyle~{}\|W\circ M^{*}-M^{*}\|+\|W\circ N\|$ $\displaystyle=$ $\displaystyle~{}\|W\circ M^{*}-M^{*}\|+\delta$ $\displaystyle\leq$ $\displaystyle~{}\gamma\mu k\sigma_{\max}(M^{*})+\delta$ $\displaystyle\leq$ $\displaystyle~{}\gamma\mu k+\delta$ (39) $$

where the first step follows from the definition of $M$, the second step follows from triangle inequality and the third step follows from Definition [H.1](#A8.Thmtheorem1), the fourth step follows from Lemma [H.2](#A8.Thmtheorem2), the last step follows from $\sigma_{\max}(M^{*})=1$.

Therefore,

$$ $\displaystyle\max_{r\in[k+1,n]}\sigma_{r}(W\circ M)\leq$ $\displaystyle~{}\max_{r\in[k+1,n]}\sigma_{r}(W\circ M-M^{*})+\max_{r\in[k+1,n]}\sigma_{r}(M^{*})$ $\displaystyle\leq$ $\displaystyle~{}\max_{r\in[k+1,n]}\sigma_{r}(W\circ M-M^{*})+0$ $\displaystyle\leq$ $\displaystyle~{}\|W\circ M-M^{*}\|$ $\displaystyle\leq$ $\displaystyle~{}\gamma\mu k+\delta$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{4}\sigma_{\min}(M^{*})+\delta$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{2}\sigma_{\min}(M^{*}),$ $$

where the first step follows from triangle inequality, the second step follows from the fact that $M^{*}$ has rank-$k$, the third step follows from Eq. ([H.3](#A8.Ex272)), the fourth step follows from $\gamma\mu k<0.1\sigma_{\min}(M^{*})$, and the last step follows from $\delta\leq 0.1\sigma_{\min}(M^{*})$.

Now, by Wedin’s theorem (see Lemma [H.3](#A8.Thmtheorem3)) with

$$ $\displaystyle a=\frac{1}{2}\sigma_{\min}(M^{*}),$ $$

for

$$ $\displaystyle(X,\Sigma,Y)=\text{rank-}k\,\mathrm{SVD}(W\circ M),$ $$

we have

$$ $\displaystyle\max\{\sin{\theta(U,X)},\sin{\theta(V,Y)}\}\leq\frac{2(\gamma\mu k+\delta)}{\sigma_{\min}(M^{*})}.$ $$

By our choice of parameters

$$ $\displaystyle\sin{\theta}\leq 1/2.$ $$

Using Lemma [D.8](#A4.Thmtheorem8), we have

$$ $\displaystyle\tan{\theta}\leq 2\sin{\theta}.$ $$

Then the lemma follows.

∎

###### Definition H.4 .

###### Lemma H.5 (Lemma 7 in [ 27 ] ) .

###### Proof.

### H.4 Init Property of distance and ρ 𝜌 \rho

Here, we analyze the properties of $\operatorname{dist}$ and $\rho$.

###### Lemma H.6 ((SVD initialization, a variation of Lemma 8 in [ 27 ] ) .

Assume that $W$ and $M^{*}$ satisfy every assumption.

Let $\Delta_{1}$ be defined as Defintion [H.4](#A8.Thmtheorem4).

Assume that $\Delta_{1}\leq 0.01/k$.

Then, we have

- •
Part 1. $\operatorname{dist}(V,Y_{1})\leq 1/2$.
- •
Part 2. Let $\rho(\cdot)$ be defined as Definition [D.1](#A4.Thmtheorem1). We have $\rho(Y_{1})\leq 4\mu$.

###### Proof.

Proof of Part 1.

First, we consider ${\widetilde{Y}}_{1}\in\mathbb{R}^{n\times k}$.

By Lemma [H.5](#A8.Thmtheorem5), we get that

$$ $\displaystyle\operatorname{dist}({\widetilde{Y}}_{1},V)\leq\Delta_{1},$ $$

which means that there exists $Q\in O^{k\times k}$, such that

$$ $\displaystyle\|{\widetilde{Y}}_{1}Q-V\|\leq\Delta_{1}.$ (40) $$

Hence,

$$ $\displaystyle\|{\widetilde{Y}}_{1}Q-V\|_{F}\leq$ $\displaystyle~{}\sqrt{k}\cdot\|{\widetilde{Y}}_{1}Q-V\|$ $\displaystyle\leq$ $\displaystyle~{}\sqrt{k}\cdot\Delta_{1}$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{10},$ (41) $$

where the first step follows from Fact [A.10](#A1.Thmtheorem10), the second step follows from Eq. ([40](#A8.E40)), and the last step follows from $\Delta_{1}\leq 0.01/k$ .

Next, we consider $\overline{Y_{1}}\in\mathbb{R}^{n\times k}$.

In the clipping step, there are two cases for all $i\in[n]$.

Case 1. $\|\widetilde{Y}_{1,i}\|_{2}\geq\xi$. Case 2. $\|\widetilde{Y}_{1,i}\|_{2}<\xi$.

Let us consider case 1. We know

$$ $\displaystyle\|\widetilde{Y}_{1,i}Q\|_{2}=$ $\displaystyle~{}\|\widetilde{Y}_{1,i}\|_{2}$ $\displaystyle\geq$ $\displaystyle~{}\xi$ $\displaystyle=$ $\displaystyle~{}\frac{2\mu k}{n},$ (42) $$

where the first step follows from Fact [A.10](#A1.Thmtheorem10), the second step follows from our Case 1 assumption, and the last step follows from the definition of $\xi$ (see Definition [E.2](#A5.Thmtheorem2)).

We have

$$ $\displaystyle\|\widetilde{Y}_{1,i}Q-V_{i}\|_{2}\geq$ $\displaystyle~{}\|\widetilde{Y}_{1,i}Q\|_{2}-\|V_{i}\|_{2}$ $\displaystyle\geq$ $\displaystyle~{}\frac{2\mu k}{n}-\|V_{i}\|_{2}$ $\displaystyle=$ $\displaystyle~{}\frac{2\mu k}{n}-\frac{\mu k}{n}$ $\displaystyle=$ $\displaystyle~{}\frac{\mu k}{n},$ (43) $$

where the first step follows from the triangle inequality, the second step follows from Eq. ([H.4](#A8.Ex290)), the third step follows from the property of $V_{i}$, and the last step follows from simple algebra.

By the definition of clipping, in this time, $\overline{Y}_{1,i}=0$.

$$ $\displaystyle\|\overline{Y}_{1,i}Q-V_{i}\|_{2}=$ $\displaystyle~{}\|0-V_{i}\|_{2}$ $\displaystyle=$ $\displaystyle~{}\|V_{i}\|_{2}$ $\displaystyle=$ $\displaystyle~{}\frac{\mu k}{n}$ $\displaystyle\leq$ $\displaystyle~{}\|Q^{\top}\widetilde{Y}_{1,i}-V_{i}\|_{2}$ $$

where the first step follows from $\overline{Y}_{1,i}=0$ and the second step follows from simple algebra, the third step follows from the property of $V_{i}$, and the last step follows from Eq. ([H.4](#A8.Ex292)).

Let us consider case 2. In this case, we know

$$ $\displaystyle\overline{Y}_{1,i}=\widetilde{Y}_{1,i}.$ $$

Thus,

$$ $\displaystyle\|\overline{Y}_{1,i}Q-V_{i}\|_{2}=\|\widetilde{Y}_{1,i}Q-V_{i}\|_{2}.$ $$

Combining Case 1 and Case 2, we know that for all $i\in[n]$,

$$ $\displaystyle\|\overline{Y}_{1,i}-V_{i}\|_{2}\leq\|\widetilde{Y}_{1,i}-V_{i}\|_{2}.$ $$

Taking the summation of squares, we have

$$ $\displaystyle\|\overline{Y}_{1}Q-V\|_{F}^{2}\leq$ $\displaystyle~{}\|\widetilde{Y}_{1}Q-V\|_{F}^{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{100}$ (44) $$

the last step follows from Eq. ([H.4](#A8.Ex288)).

Eventually, we show $V$ is close to $Y_{1}$.

Suppose

$$ $\displaystyle Y_{1}=\overline{Y_{1}}R^{-1},$ $$

where $R$ is the upper-triangular matrix.

Then,

$$ $\displaystyle\sin{\theta(V,Y_{1})}=$ $\displaystyle~{}\|V_{\bot}^{\top}Y_{1}\|$ $\displaystyle=$ $\displaystyle~{}\|Y_{1}\|$ $\displaystyle=$ $\displaystyle~{}\|(\overline{Y}_{1}-VQ^{-1})R^{-1}\|$ $\displaystyle\leq$ $\displaystyle~{}\|\overline{Y}_{1}Q-V\|\cdot\|R^{-1}\|$ $\displaystyle\leq$ $\displaystyle~{}\|\overline{Y}_{1}Q-V\|\cdot\frac{1}{\sigma_{\min}(\overline{Y}_{1})}$ $\displaystyle\leq$ $\displaystyle~{}\|\overline{Y}_{1}Q-V\|_{F}\cdot\frac{1}{\sigma_{\min}(\overline{Y}_{1})},$ $$

where the first step follows from definition of $\sin$, the second step follows from Fact [A.10](#A1.Thmtheorem10), the third step follows from definition of $Y_{1}$, and the fourth step follows from $\|AB\|\leq\|A\|\cdot\|B\|$, the fifth step follows from singular values of $R$ and those of $\overline{Y}_{1}$ are identical, and the last step follows from $\|\cdot\|\leq\|\cdot\|_{F}$.

Note that

$$ $\displaystyle\sigma_{\min}(\overline{Y}_{1})=$ $\displaystyle~{}\sigma_{\min}(\overline{Y}_{1}Q)$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(V)-\|\overline{Y}_{1}Q-V\|$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(V)-\|\overline{Y}_{1}Q-V\|_{F}$ $\displaystyle\geq$ $\displaystyle~{}\sigma_{\min}(V)-1/10$ $\displaystyle\geq$ $\displaystyle~{}\frac{1}{2},$ (45) $$

where the first step follows from Fact [A.10](#A1.Thmtheorem10), the second step follows from Fact [A.10](#A1.Thmtheorem10), the third step follows from $\|\cdot\|\leq\|\cdot\|_{F}$, the fourth step follows from Eq. ([H.4](#A8.Ex302)), and the last step follows from $\sigma_{\min}(V)=1$.

Thus,

$$ $\displaystyle\sin{\theta(V,Y_{1})}\leq$ $\displaystyle~{}2\cdot\|\overline{Y}_{1}Q-V\|_{F}$ $\displaystyle\leq$ $\displaystyle~{}2\cdot\frac{1}{10}$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{2},$ (46) $$

where the first step follows from Eq. ([H.4](#A8.Ex310)), and the second step follows from Eq. ([H.4](#A8.Ex302)), the last step follows from simple algebra.

Therefore,

$$ $\displaystyle\operatorname{dist}(V,Y_{1})\leq$ $\displaystyle~{}2\tan{\theta(V,Y_{1})}$ $\displaystyle\leq$ $\displaystyle~{}4\sin{\theta(V,Y_{1})}$ $\displaystyle\leq$ $\displaystyle~{}1/2,$ $$

where the first step follows from Lemma [D.8](#A4.Thmtheorem8), the second step follows from Lemma [D.8](#A4.Thmtheorem8), the third step follows from Eq. ([H.4](#A8.Ex314)).

Proof of Part 2.

For $\rho(Y_{1})$, we observe that

$$ $\displaystyle Y_{1,i}=\overline{Y}_{i}R^{-1},$ $$

We have

$$ $\displaystyle\|Y_{1,i}\|_{2}\leq$ $\displaystyle~{}\|\overline{Y}_{1,i}\|_{2}\cdot\|R^{-1}\|$ $\displaystyle\leq$ $\displaystyle~{}\xi\cdot\|R^{-1}\|$ $\displaystyle\leq$ $\displaystyle~{}\xi\cdot\sigma_{\min}(\overline{Y}_{1})^{-1}$ $\displaystyle\leq$ $\displaystyle~{}\xi\cdot 2$ (47) $$

where the first step follows from $\|Ax\|_{2}\leq\|A\|\cdot\|x\|_{2}$, the second step follows from $\|\overline{Y}_{1,i}\|_{2}\leq\xi$, and the third step follows from $\|R^{-1}\|=\sigma_{\min}(\overline{Y})^{-1}$, and last step follows from $\sigma_{\min}(\overline{Y}_{1})^{-1}\leq 2$ (see Eq. ([H.4](#A8.Ex310))).

Note that

$$ $\displaystyle\rho(Y_{1,i})=$ $\displaystyle~{}\frac{n}{k}\cdot\max_{i\in[n]}\|Y_{1,i}\|_{2}$ $\displaystyle\leq$ $\displaystyle~{}\frac{n}{k}\cdot 2\xi$ $\displaystyle\leq$ $\displaystyle~{}4\mu$ $$

where the first step follows from Definition [D.1](#A4.Thmtheorem1), the second step follows from Eq. ([H.4](#A8.Ex320)), last step follows from $\xi=\mu k/n$

This leads to the bound, which completes the proof.

∎

###### Lemma H.6 ((SVD initialization, a variation of Lemma 8 in [ 27 ] ) .

###### Proof.

### H.5 Main Result

Finally, in this section, we present our main result.

**Table 2: Summary of our results.**
| References | Init | Time |
| --- | --- | --- |
| [] | Random | $\widetilde{O}(n^{2}k^{2}\log(1/\epsilon))$ |
| Theorem [I.2](#A9.Thmtheorem2) | Random | $\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$ |
| [] | SVD | $O(n^{3})+\widetilde{O}(n^{2}k^{2}\log(1/\epsilon))$ |
| Theorem [H.7](#A8.Thmtheorem7) | SVD | $O(n^{3})+\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$ |

###### Theorem H.7 (Main result, SVD initialization) .

Let $\eta=1$.

There is an algorithm starts from SVD initialization runs in $\log(1/\epsilon)$ iterations and generates $\widetilde{M}$, which is a matrix in $\mathbb{R}^{n\times n}$ and

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq O(\alpha^{-1}\eta k\tau)\|W\circ N\|_{F}+\epsilon$ $$

$$ $\displaystyle O(n^{3})+\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$ $$

is the total running time.

###### Proof.

It follows directly from Lemma [K.1](#A11.Thmtheorem1) and Lemma [K.2](#A11.Thmtheorem2).
∎

###### Theorem H.7 (Main result, SVD initialization) .

###### Proof.

## Appendix I Random Initialization

In Section [I.1](#A9.SS1), we present our random initialization algorithm (see Algorithm [5](#alg5)) and analyze its properties. In Section [I.2](#A9.SS2), we summarize our main result.

### I.1 Initialization

Now, we start to present Algorithm [5](#alg5).

Figure: Algorithm 5 Random Initialization

Consider the random initialization.

###### Lemma I.1 (Random initialization, Lemma 9 in [ 27 ] ) .

Let $Y\in\mathbb{R}^{n\times k}$ be a random matrix with $Y_{i,j}=\frac{1}{\sqrt{n}}b_{i,j}$, where $b_{i,j}$ are independent and uniform variables from $\{-1,1\}$.

Let $\mu\geq 1$. Let $k\geq 1$. Let $\alpha>0$.

Let $D_{W_{i}}$ be defined in Definition [A.1](#A1.Thmtheorem1).

We assume that $\|W\|_{\infty}\leq\frac{\alpha}{k^{2}\mu\log^{2}{n}}\cdot n$.

Then, we have

$$ $\displaystyle\Pr\Big{[}\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\geq\frac{\alpha}{4\mu k},\ \forall i\in[n]\Big{]}\geq 1-1/n^{2}.$ $$

###### Proof.

Notice that

$$ $\displaystyle Y^{\top}D_{W_{i}}Y=$ $\displaystyle~{}\sum_{j\in[n]}(Y_{j})^{\top}(D_{W_{i}})_{j}Y_{j}.$ $$

For every $j\in[n]$,

$$ $\displaystyle(Y_{j})^{\top}(D_{W_{i}})_{j}Y_{j}$ $$

is independent, and

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[(Y_{j})^{\top}(D_{W_{i}})_{j}(Y_{j})]=\frac{1}{n}(D_{W_{i}})_{j}.$ $$

Using the linearity property of expectation, we have

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{j\in[n]}(Y^{j})^{\top}(D_{W_{i}})_{j}(Y_{j})]=\frac{1}{n}\sum_{j\in[n]}(D_{W_{i}})_{j}.$ $$

Then, we can get that the following equation holds. We use this first and will prove it from Eq. ([49](#A9.E49))

$$ $\displaystyle\sum_{j\in[n]}(D_{W_{i}})_{j}\geq\frac{\alpha n}{k\mu}.$ (48) $$

Indeed, by the assumption weight is not degenerate, we can get that for all vectors $a$ in $\mathbb{R}^{n}$,

$$ $\displaystyle a^{\top}V^{\top}D_{W_{i}}Va=$ $\displaystyle~{}\sum_{j\in[n]}(D_{W_{i}})_{j}\langle V_{j},a\rangle^{2}$ $\displaystyle\geq$ $\displaystyle~{}\min_{j\in[n]}\{\langle V_{j},a\rangle^{2}\}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle=$ $\displaystyle~{}\frac{\mu k}{n}\sum_{j\in[n]}(D_{W_{i}})_{j}$ $\displaystyle\geq$ $\displaystyle~{}\frac{\mu k}{n}\frac{\alpha n}{k\mu}$ $\displaystyle=$ $\displaystyle~{}\alpha,$ $$

where the second step follows from Fact [A.9](#A1.Thmtheorem9), the third step follows from the incoherence of $V$, the fourth step follows from our claim (see Eq. ([48](#A9.E48))), and the last step follows from simple algebra.

Then, by the incoherence of $V$, we have

$$ $\displaystyle\sum_{j\in[n]}(D_{W_{i}})_{j}\langle V_{j},a\rangle^{2}\leq\sum_{j\in[n]}(D_{W_{i}})_{j}\frac{\mu k}{n}.$ (49) $$

Hence,

$$ $\displaystyle\sum_{j\in[n]}(D_{W_{i}})_{j}\geq\frac{\alpha n}{k\mu}.$ $$

Combining everything together, we get

$$ $\displaystyle\operatorname*{{\mathbb{E}}}[\sum_{j\in[n]}(Y^{j})^{\top}(D_{W_{i}})_{j}Y_{j}]\geq\frac{\alpha}{k\mu}.$ $$

Define

$$ $\displaystyle B:=\|(Y^{j})^{\top}(D_{W_{i}})_{j}Y_{j}\|_{2}\leq$ $\displaystyle~{}\frac{k}{n}(D_{W_{i}})_{j}$ $\displaystyle\leq$ $\displaystyle~{}\frac{\alpha}{k\mu\log^{2}{n}},$ $$

where the first step follows from our sampling procedure and the second step follows from the assumption that $\|W\|_{\infty}\leq\frac{\alpha n}{k^{2}\mu\log^{2}{n}}$.

Since all the random variables

$$ $\displaystyle(Y_{j})^{\top}(D_{W_{i}})_{j}Y_{j}$ $$

are independent, applying Matrix Chernoff we get that

$$ $\displaystyle\Pr[\sum_{j\in[n]}(Y_{j})^{\top}(D_{W_{i}})_{j}Y_{j}\leq(1-\delta)\frac{\alpha}{k\mu}]\leq$ $\displaystyle~{}n(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}})^{\frac{\alpha}{k\mu B}}$ $\displaystyle\leq$ $\displaystyle~{}n(\frac{e^{-\delta}}{(1-\delta)^{(1-\delta)}})^{\log^{2}{n}}.$ $$

Picking $\delta=\frac{3}{4}$, and union bounding over all $i$, with probability at least $1-\frac{1}{n^{2}}$, for all $i$,

$$ $\displaystyle\sigma_{\min}(Y^{\top}D_{W_{i}}Y)\geq\frac{\alpha}{4k\mu}$ $$

as needed.

∎

###### Lemma I.1 (Random initialization, Lemma 9 in [ 27 ] ) .

###### Proof.

### I.2 Main Result

In this section, we summarize our main result.

###### Theorem I.2 (Main result, random initialization) .

Let $\eta$ be defined as Definition [E.3](#A5.Thmtheorem3).
There is an algorithm starts from random initialization runs in $\log(1/\epsilon)$ iterations and generates $\widetilde{M}$, which is a matrix in $\mathbb{R}^{n\times n}$ and

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq O(\alpha^{-1}\eta k\tau)\|W\circ N\|+\epsilon.$ $$

$$ $\displaystyle\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon)).$ $$

is the total running time.

###### Proof.

We use Algorithm [5](#alg5) to initialize $Y$.

Then, we use the proof of Lemma [E.8](#A5.Thmtheorem8), and $T$ is changed to

$$ $\displaystyle T=\{i\in[n]\mid\sigma_{\min}(Y^{\top}D_{i}Y)\leq 0.25\alpha/\eta\}.$ $$

where $\eta=\mu k$.

However, because of this change, $T=\emptyset$, with high probability.

Then, the same calculation follows as in Lemma [E.8](#A5.Thmtheorem8).

Note that in this case, Lemma [G.1](#A7.Thmtheorem1) is not needed because $S_{1}=\emptyset$.

Then, we can use Lemma [K.1](#A11.Thmtheorem1) and Lemma [K.2](#A11.Thmtheorem2), directly.

∎

###### Theorem I.2 (Main result, random initialization) .

###### Proof.

## Appendix J Bounding the Final Error

In Section [J.1](#A10.SS1), we rewrite $\widetilde{M}-M^{*}$ into a form that is easy for further analysis. In Section [J.2](#A10.SS2), we prove that $\widetilde{M}-M^{*}$ is bounded. Both of these are used to support the proof of our main theorem.

### J.1 Rewrite M ~ − M ∗ ~ 𝑀 superscript 𝑀 \widetilde{M}-M^{*}

In this section, we start to simplify/rewrite $\widetilde{M}-M^{*}$.

###### Claim J.1 .

Let $M^{*}\in\mathbb{R}^{n\times n}$ is $(\mu,\tau)$-incoherent (see Definition [5.1](#S5.Thmtheorem1)).
Let $\widetilde{M}$ be defined as Theorem [5.6](#S5.Thmtheorem6).

Then, we have

$$ $\displaystyle\widetilde{M}-M^{*}=U\Sigma Q\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}Y^{\top}+RY^{\top}$ $$

###### Proof.

$$ $\displaystyle\widetilde{M}-M^{*}=$ $\displaystyle~{}\overline{X}Y^{\top}-M^{*}$ $\displaystyle=$ $\displaystyle~{}(U\Sigma V^{\top}(VQ+\Delta_{y})+R)(VQ+\Delta_{y})^{\top}-U\Sigma V^{\top}$ $\displaystyle=$ $\displaystyle~{}U\Sigma V^{\top}(VQ+\Delta_{y})(VQ+\Delta_{y})^{\top}+R(VQ+\Delta_{y})^{\top}$ $\displaystyle-$ $\displaystyle~{}U\Sigma V^{\top}$ $\displaystyle=$ $\displaystyle~{}U\Sigma V^{\top}VQ(VQ+\Delta_{y})^{\top}+U\Sigma V^{\top}\Delta_{y}(VQ+\Delta_{y})^{\top}+R(VQ+\Delta_{y})^{\top}-U\Sigma V^{\top}$ $\displaystyle=$ $\displaystyle~{}U\Sigma V^{\top}VQQ^{\top}V^{\top}-U\Sigma V^{\top}+U\Sigma V^{\top}VQ\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}(VQ+\Delta_{y})^{\top}+R(VQ+\Delta_{y})^{\top}$ $\displaystyle=$ $\displaystyle~{}U\Sigma V^{\top}VQ\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}(VQ+\Delta_{y})^{\top}+R(VQ+\Delta_{y})^{\top}$ $\displaystyle=$ $\displaystyle~{}U\Sigma Q\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}Y^{\top}+RY^{\top},$ $$

where the first step follows from $\widetilde{M}=\overline{X}Y^{\top}$, the second step follows from $\overline{X}=U\Sigma V^{\top}Y+R$, $Y=VQ+\Delta_{y}$, and $M^{*}=U\Sigma V$, the third step follows from simple algebra, the fourth step follows from the simple algebra, the fifth step follows from that for all matrices $A,B$, $(A+B)^{\top}=A^{\top}+B^{\top}$, the sixth step follows from $V\in\mathbb{R}^{n\times k}$ is an orthogonal matrix and $Q\in\mathbb{R}^{k\times k}$ is a rotation matrix, and the last step follows from $Y=VQ+\Delta_{y}$.
∎

###### Claim J.1 .

###### Proof.

### J.2 Bounding ‖ M ~ − M ∗ ‖ norm ~ 𝑀 superscript 𝑀 \|\widetilde{M}-M^{*}\|

In this section, we bound $\|\widetilde{M}-M^{*}\|$.

###### Claim J.2 .

Let $M^{*}\in\mathbb{R}^{n\times n}$ is $(\mu,\tau)$-incoherent (see Definition [5.1](#S5.Thmtheorem1)).
Let $\widetilde{M}$ be defined as Theorem [5.6](#S5.Thmtheorem6).

Then, we have

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq(2\Delta_{F})\|W\circ N\|+\epsilon$ $$

###### Proof.

$$ $\displaystyle\|\widetilde{M}-M^{*}\|=$ $\displaystyle~{}\|U\Sigma Q\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}Y^{\top}+RY^{\top}\|$ $\displaystyle\leq$ $\displaystyle~{}\|U\Sigma\|\|Q\|\|\Delta_{y}\|+\|U\Sigma V^{\top}\|\|\Delta_{y}\|\|Y\|+\|R\|\|Y\|$ $\displaystyle\leq$ $\displaystyle~{}\Theta(1)\cdot\|\Delta_{y}\|+\|R\|$ $\displaystyle\leq$ $\displaystyle~{}O(\operatorname{dist}(Y,V))+\Delta_{f}\cdot\|W\circ N\|$ $\displaystyle\leq$ $\displaystyle~{}\frac{1}{2^{t}}+\Delta_{F}\cdot\|W\circ N\|+\Delta_{f}\cdot\|W\circ N\|$ $\displaystyle=$ $\displaystyle~{}(\Delta_{F}+\Delta_{f})\|W\circ N\|+\frac{1}{2^{t}}$ $\displaystyle\leq$ $\displaystyle~{}(2\Delta_{F})\|W\circ N\|+\frac{1}{2^{t}}$ $\displaystyle\leq$ $\displaystyle~{}(2\Delta_{F})\|W\circ N\|+\epsilon$ $$

where the second step is due to the inequalities $\|A+B\|\leq\|A\|+\|B\|$ and $\|AB\|\leq\|A\|\|B\|$, the third step is supported by $\|U\Sigma\|=\|\Sigma\|$, $\|Q\|=1$, $\|U\Sigma V^{\top}\|=\|\Sigma\|=1$ (See Definition [5.1](#S5.Thmtheorem1)), $\|Y\|=1$, the second last step follows from $\Delta_{f}\geq\Delta_{F}$, and the last step follows from $t=O(\log(1/\epsilon))$.
∎

###### Claim J.2 .

###### Proof.

## Appendix K Proof of Theorem 5.6

There are two parts of Theorem [5.6](#S5.Thmtheorem6): the correctness part and the running time part. In Section [K.1](#A11.SS1), we present the proof of the correctness part of Theorem [5.6](#S5.Thmtheorem6). In Section [K.2](#A11.SS2), we display the proof of the running time part of Theorem [5.6](#S5.Thmtheorem6).

### K.1 Correctness Part of Theorem 5.6

Now, we start proving the correctness part of Theorem [5.6](#S5.Thmtheorem6).

###### Lemma K.1 (Correctness part of Theorem 5.6 ) .

Suppose $M^{*}\in\mathbb{R}^{n\times n}$ is $(\mu,\tau)$-incoherent (see Definition [5.1](#S5.Thmtheorem1)). Assume that $W$ is $\gamma$-spectral gap (see Definition [5.2](#S5.Thmtheorem2)) and $(\alpha,\beta)$-bounded (see Definition [5.3](#S5.Thmtheorem3)). Let $\gamma$ satisfy condition in Definition [5.4](#S5.Thmtheorem4).

There is an algorithm (Algorithm [1](#alg1)) takes $M^{*}+N\in\mathbb{R}^{n\times n}$ as input, uses initialization and runs in $O(\log(1/\epsilon))$ iterations and generates $\widetilde{M}$, which is a matrix in $\mathbb{R}^{n\times n}$ and

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq O(\alpha^{-1}k\tau)\cdot\|W\circ N\|+\epsilon.$ $$

###### Proof.

By Lemma [F.1](#A6.Thmtheorem1), we can prove, for any $t>1$

$$ $\displaystyle\operatorname{dist}(X_{t},U)\leq\frac{1}{2^{t}}+100\alpha^{-1}\sigma_{\min}(M^{*})^{-1}k\cdot\|W\circ N\|,$ $\displaystyle\operatorname{dist}(Y_{t},V)\leq\frac{1}{2^{t}}+100\alpha^{-1}\sigma_{\min}(M^{*})^{-1}k\cdot\|W\circ N\|.$ (50) $$

Note that $\sigma_{\min}(M^{*})^{-1}\leq\tau$ (see Definition [5.1](#S5.Thmtheorem1)), then the above statement becomes

$$ $\displaystyle\operatorname{dist}(X_{t},U)\leq\frac{1}{2^{t}}+\Delta_{F}\cdot\|W\circ N\|,$ $\displaystyle\operatorname{dist}(Y_{t},V)\leq\frac{1}{2^{t}}+\Delta_{F}\cdot\|W\circ N\|.$ $$

where
$\Delta_{F}:=5\Delta_{f}.$
By Lemma [E.8](#A5.Thmtheorem8) and Claim [E.5](#A5.Thmtheorem5),

$$ $\displaystyle~{}\|\overline{X}-U\Sigma V^{\top}Y\|_{F}$ $\displaystyle\leq$ $\displaystyle~{}\Delta_{d}\cdot\operatorname{dist}(Y,V)+\Delta_{f}\cdot\|W\circ N\|,$ (51) $$

where $\Delta_{d}$ and $\Delta_{f}$ are defied as Definition [5.5](#S5.Thmtheorem5).

To promise the first term in $\Delta_{d}^{2}$ is less than $0.1$ and using Lemma [A.6](#A1.Thmtheorem6), we need to choose (note that $c_{0}$ is defined as Definition [5.4](#S5.Thmtheorem4))

$$ $\displaystyle\gamma\leq\frac{1}{20}\cdot\frac{\alpha}{\operatorname{poly}(\mu,k)\cdot n^{c_{0}}}$ $$

To promise the second term in $\Delta_{d}^{2}$ is less than $0.1$, we have to choose

$$ $\displaystyle\gamma\leq\frac{1}{20}\cdot\frac{\alpha}{\operatorname{poly}(\mu,k,\tau)}$ $$

For $\operatorname{dist}(Y,V)$, let

$$ $\displaystyle P:=\arg\min_{Q\in O^{k\times k}}\|YQ-V\|.$ $$

We define

$$ $\displaystyle V:=YP+\Delta$ $$

and $Y=VP^{\top}-\Delta P^{\top}$.

Let $Q:=P^{\top}\in O^{k\times k}$ and $\Delta_{y}:=-\Delta P^{\top}$, then

$$ $\displaystyle Y=VQ+\Delta_{y}$ $$

with $\|\Delta_{y}\|=\operatorname{dist}(Y,V)$.

We define

$$ $\displaystyle R:=\overline{X}-U\Sigma V^{\top}Y.$ $$

Then Eq. ([K.1](#A11.Ex371)) implies that

$$ $\displaystyle\|R\|_{F}\leq$ $\displaystyle~{}\operatorname{dist}(Y,V)+\Delta_{f}\|W\circ N\|$ $$

Let $\overline{X}:=\overline{X}_{T+1}$ and $Y:=Y_{T}$,
then

$$ $\displaystyle\widetilde{M}=\overline{X}Y^{\top}.$ $$

Using Claim [J.1](#A10.Thmtheorem1), we have

$$ $\displaystyle\widetilde{M}-M^{*}=U\Sigma Q\Delta_{y}^{\top}+U\Sigma V^{\top}\Delta_{y}Y^{\top}+RY^{\top}.$ (52) $$

Using Claim [J.2](#A10.Thmtheorem2), we have

$$ $\displaystyle\|\widetilde{M}-M^{*}\|\leq(2\Delta_{F})\|W\circ N\|+\epsilon.$ (53) $$

∎

###### Lemma K.1 (Correctness part of Theorem 5.6 ) .

###### Proof.

### K.2 Running Time Part of Theorem 5.6

Now, we start proving the running time part of Theorem [5.6](#S5.Thmtheorem6).

###### Lemma K.2 (Running Time Part of Theorem 5.6 ) .

The running time of Algorithm [1](#alg1) is $\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$.

###### Proof.

Now we analyze the running time.
We first compute the initialization time. The entry $Y_{i,j}$ of the matrix $Y$ is equal to $\frac{1}{\sqrt{n}}b_{i,j}$, where $b_{i,j}$’s are independent uniform from $\{-1,1\}$. Hence, the time complexity of random initialization is $O(nk)$. There are $T$ iterations. For each iteration, there are three major steps, solving regression, Clip and QR.
The dominating step is to solve regression. We choose $\epsilon_{\mathrm{sk}}$ as Claim [E.5](#A5.Thmtheorem5).
Using Lemma [4.5](#S4.Thmtheorem5) and Lemma [4.8](#S4.Thmtheorem8), we know that we should choose $\epsilon_{0}=\epsilon_{\mathrm{sk}}/\operatorname{poly}(n)$
and $\delta_{0}=1/\operatorname{poly}(n,\log(1/\epsilon))$, this step takes $\widetilde{O}(n^{2}k+nk^{3})$ time. The Clip and QR algorithms take time $O(nk)$ and $O(nk^{2})$ respectively. Hence, the $T$ iterations take time $\widetilde{O}((n^{2}k+nk^{3})\log(1/\epsilon))$.
∎

###### Lemma K.2 (Running Time Part of Theorem 5.6 ) .

###### Proof.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: Are you aware of any practical application where the improvement in the running time by a factor of k obtained in this paper may be significant to applications, and where one might expect assumptions to hold?
soundness: 3
strengths: The problem of weighted low-rank matrix approximation is an important practical problem and an important algorithmic primitive that arises in numerical linear algebra, and various machine learning applications. The problem naturally generalizes classical low-rank matrix approximation problems and a matrix completion problem. Alternating minimization is an extremely successful practical approach to matrix completion problem, so establishing theoretical guarantees for this approach to the weighted low-rank matrix approximation problem is of high interest.

This paper builds on top algorithm analyzed in (Li et al., 2016) and the key difference between the algorithm in (Li et al., 2016) and this paper is that exact solvers for linear regression is replaced with an approximate solver that can be traced back to (Rokhlin & Tygert, 2008). This allows authors to improve runtime by a factor of $k$ and to get a nearly optimal runtime.
summary: This paper studies the problem of weighted low-rank matrix approximation. In this problem one is given a weight matrix W
 and observes a matrix M', and the goal is to recover a matrix M of rank at most k that minimizes  $\Vert W \circ (M'- M)\Vert$..

This paper provides new theoretical guarantees within the alternating minimization framework for weighted low-rank matrix approximation. The authors propose a new alternating minimization algorithm that uses high-accuracy regression solver based on sketching instead of exact regression solvers in the optimization step of the algorithm compared to the work of (Li et al, 2016). This allows authors to improve runtime by a factor of $k$. 
.
weaknesses: The assumption 2.4.2 asks that $||W - J||<\gamma n$, where J is an all-one matrix with $\gamma = O(n^{-c})$ (compared to O(1) in  (Li et al., 2016)). This assumption sounds quite strong to me. This means that in the matrix completion scenario, this allows one to have only o(1)-fraction of entries not observed in every row. Considering that one of the key regimes for low-rank problems assumes that the rank satisfies k = O(1), I am not sure if improvement in runtime completely justifies slightly stronger assumption on W.

Another slight weakness of the paper is that most of the key techniques used in this paper were introduced in prior work, so the paper lacks a bit of novelty in this sense.

---

confidence: 2
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. Could the authors explain the connection between the problem they considered (Problem 2.4) and the original problem? Are they equivalent under some conditions?
2. Could the authors explain the meaning of $\epsilon_0$ in Line 351?
soundness: 3
strengths: 1. The authors propose a high-precision regression solver and extend it to the weighted case. They also demonstrate the robustness of the alternating minimization framework. The theoretical analysis is a significant contribution.
2. The motivation behind their method is detailed and well-presented in the paper.
summary: The authors propose an efficient framework for alternating minimization, which allows the subproblems to be solved approximately. They apply the framework to the weighted low rank approximation problem, theoretically improving the runtime.
weaknesses: The authors did not conduct experiments to verify the performance of their algorithm. I am interested in whether the algorithm is feasible in practice.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: Can the authors comment on the performance of their algorithm on some real or even synthetic problems?
soundness: 3
strengths: I think the theoretical results in this paper is solid: the proof that the alternating minimization framework is robust enough to tolerate large errors induced in the approximate solution is interesting, and can possibly be generalized to other similar problems in matrix optimization.
summary: This paper considers the weighted low-rank approximation problem, which can be solved using alternating minimization. In previous methods, the alternating minimization algorithm requires solving n linear regression problems each iteration. In this work, the authors develop a framework based sketching, and they prove that alternating minimization is robust enough such that the approximate solution return each iteration also converges towards the optimal solution. As a result, they obtain an improved running time compared to Li et al. 2016.
weaknesses: I see two main weaknesses. First, I think the writing of this paper needs to be improved, especially in section 3, where the algorithm is first introduced. Algorithm 1 is outlined in a dense way that makes it hard for the reader to parse exactly what is going on. Also, lines 270-280 contain numerous sentences that are a bit awkward or hard to understand. I suggest that the authors use a separate section to slowly present algorithm 1 step by step, and describe which parts are new. 

Another weakness i see is the lack of any numerical results. In the introduction (lines 80) the authors say that the results of Li et al. 2016 are hard to deploy in practice because of the high time complexity. While this paper reduces the time complexity in theory, there are no numerical section to demonstrate that the reduction in time complexity is useful in practice. I suggest that the authors at least run some synthetic experiments to demonstrate a reduction in real runtime.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 3
questions: I have a few other minor comments for the authors to consider:

- Theorem 4.6: I wonder if the time complexity also depends on the scale of $M^*$ and $N$. For example, let $c>0$ be a constant. If we multiply $M^*$ and $N$ by $c$, then the solution $\tilde{M}$ will also be multiplied by $c$. However, the value $\epsilon$ is not changed in the error bound. In addition, Assumption 2.3 does not bound the scale of $M^*$ and $N$ either. If I did not miss anything, I feel that the number of iterations or the error $\epsilon$ should depend on the scale of $M^*$ and $N$.


- Line 499: it would be helpful if the authors could provide supporting evidence for the claim that the spectral norm is more robust than the Frobenius norm.
soundness: 3
strengths: The paper provides a novel algorithm for the low-rank matrix approximation problem. The results in this work may also be applied to other optimization and machine learning problems. After checking the paper, I think the theoretical results in the paper should be sound, although I did not check all proofs due to the time limit.
summary: In this work, the authors proposed a new alternating minimization method for the weighted low-rank matrix approximation problem. They utilized an efficient multiple-response regression solver to reduce the computational time from ${O}((\|W\|_0k^2 + nk^3)\log(1/\epsilon))$ to $\tilde{O}((\|W\|_0k + nk^3)\log(1/\epsilon))$.
weaknesses: Although this paper is mostly a theoretical paper, I think it is still beneficial to include numerical illustrations to verify the theoretical findings and show the usefulness of the proposed method. For example, the authors may generate artificial datasets that satisfy the assumptions in this work and compare their method with the methods in (Li et al., 2016). It would be even better if the authors can verify that Assumption 2.3 holds in some practical examples and exhibit the empirical performance on these real-world examples.

Moreover, in Line 223, the authors claimed that Assumption 3 is a generalization to the RIP condition. Although I agree with the authors that the assumption is more general in the sense that it contains the weight matrix $W$, I think it is more restrictive than the RIP condition. Suppose that $W$ is a boolean matrix and each column of $W$ contains at most $k$ 1's. In this case, the assumption considers at most $n$ combinations of rows of $U$ and $V$. In contrast, the RIP condition requires the error bound to hold for all $k$-dimensional subspace. In addition, I feel that Assumption 3 is not directly comparable with the classical RIP condition. The definition of the classic $(r, \delta)$-RIP condition would imply that $(1-\delta) \lVert K \rVert_F^{2} \leq \lVert W \circ K \rVert_F^{2} \leq (1+\delta) \lVert K \rVert_{F}^{2}$ holds for any matrix $K$ of rank at most $k$, which is independent of $M^*$. I would suggest the authors include more detailed explanations to this claim.

Meta-review: This paper introduces a new framework for weighted low-rank approximation based on approximate alternating updates. With the proposed approach, the authors show that the algorithm’s runtime is reduced from $\|W\|_0 k^2$ to $\|W\|_0 k$ , where 
$k$ is the rank of the sought matrix. The paper provides a solid theoretical analysis, and the reviewers acknowledge its technical soundness, the significance of the work, and the potential for generalizing the results to other low-rank matrix estimation problems. During the rebuttal phase, the authors addressed the reviewers’ concerns and provided numerical results that corroborate their theoretical findings.  I believe that the paper offers valuable insights into an important problem and thus recommend its acceptance to ICLR.

Decision: Accept (Poster)