$\ell_{2}$-norms of columns of $\mathbf{A}$.

We extend the above statement to rectangular matrices:

######  Corollary 4.24 (Spectral Decay for Rectangular Matrices).

Given a matrix $\mathbf{A}\in\mathbb{R}^{n\times m}$, s.t. for all
$j,j^{\prime}\in[m]$,
$\|\mathbf{A}_{*,j}\|^{2}_{2}=\Theta(\|\mathbf{A}_{*,j^{\prime}}\|^{2}_{2})$.
Let $\mathcal{Q}$ be a uniformly random subset of $[n]$ s.t.
${\bf\mathbb{E}}\left[\mathcal{Q}\right]=q$. Let $b=\left\lceil
n/m\right\rceil$ and $\mathbf{A}_{|\mathcal{Q}}$ denote the submatrix
restricted to the rows indexed by $\mathcal{Q}$. Then,

${\bf\mathbb{E}}\left[\big{\|}\mathbf{A}_{|\mathcal{Q}}\big{\|}_{2}\right]=O\left(\sqrt{\frac{q}{n}}\|\mathbf{A}\|_{2}+\sqrt{\log(q)/b}\|\mathbf{A}\|_{(n/q)}\right)$

###### Proof.

First, consider the case when $m\geq n$. To see this, let
$\textsf{SVD}(\mathbf{A})=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{\top}$ where
$\mathbf{U}\mathbf{\Sigma}$ is an $n\times n$ matrix. Now,
$\|\mathbf{A}\|_{2}=\|\mathbf{U}\mathbf{\Sigma}\|_{2}$ and applying Theorem
4.23 to $\mathbf{U}\mathbf{\Sigma}$, we have

$\begin{split}{\bf\mathbb{E}}\left[\big{\|}\mathbf{A}_{|\mathcal{Q}}\big{\|}_{2}\right]={\bf\mathbb{E}}\left[\big{\|}(\mathbf{U}\mathbf{\Sigma})_{|\mathcal{Q}}\big{\|}_{2}\right]&=O\left(\sqrt{\frac{q}{n}}\|\mathbf{U}\mathbf{\Sigma}\|_{2}+\sqrt{\log(q)}\|\mathbf{U}\mathbf{\Sigma}\|_{(n/q)}\right)\\\
&=O\left(\sqrt{\frac{q}{n}}\|\mathbf{A}\|_{2}+\sqrt{\log(q)}\|\mathbf{A}\|_{(n/q)}\right)\end{split}$
(4.22)

where we repeatedly use that $\mathbf{V}^{T}$ has orthonormal rows. Here, we
note that since the columns of $\mathbf{A}$ have the same squared norm up to a
constant,$\|\mathbf{A}\|_{(n/q)}=\Theta(\|\mathbf{A}\|_{1\to 2})$, i.e. the
max column norm of $\mathbf{A}$.

Next, consider the case where $m<n$. Let $b=\left\lceil n/m\right\rceil$. In
order to analyze the spectral norm of $\mathbf{A}_{\mathcal{Q}}$, we create
$b$ copies of $\mathbf{A}$ and concatenate them such that the resulting matrix
$\mathbf{A}^{*}$ has more columns than rows. Applying Equation (4.22) to
$\mathbf{A}^{*}$ and substituting the average with max, we have

${\bf\mathbb{E}}\left[\big{\|}\mathbf{A}^{*}_{|\mathcal{Q}}\big{\|}_{2}\right]=O\left(\sqrt{\frac{q}{n}}\|\mathbf{A}^{*}\|_{2}+\sqrt{\log(q)}\|\mathbf{A}^{*}\|_{1\to
2}\right)$ (4.23)

Observe, $\mathbf{A}^{*}_{\mid\mathcal{Q}}$ selects uniformly random rows of
$\mathbf{A}^{*}$ and
$\big{\|}\mathbf{A}^{*}_{|\mathcal{Q}}\big{\|}_{2}=\max_{\|x\|_{2}=1}\|x^{\top}\mathbf{A}^{*}_{|\mathcal{Q}}\|_{2}$
and for any vector $x$,
$\|x^{\top}\mathbf{A}^{*}_{|\mathcal{Q}}\|_{2}=\sqrt{b}\|x^{\top}\mathbf{A}_{|\mathcal{Q}}\|_{2}$.
Therefore,
${\bf\mathbb{E}}\left[\big{\|}\mathbf{A}^{*}_{|\mathcal{Q}}\big{\|}_{2}\right]=\sqrt{b}\cdot{\bf\mathbb{E}}\left[\big{\|}\mathbf{A}_{|\mathcal{Q}}\big{\|}_{2}\right]$
and $\|\mathbf{A}^{*}\|_{2}=\sqrt{b}\cdot\|\mathbf{A}^{*}\|_{2}$. Finally, it
is easy to see that since the columns of $\mathbf{A}^{*}$ are copies of
columns of $\mathbf{A}$, the max column norm does not change. Therefore,
(4.22) to $\mathbf{A}^{*}$, we have

${\bf\mathbb{E}}\left[\big{\|}\mathbf{A}_{|\mathcal{Q}}\big{\|}_{2}\right]=O\left(\sqrt{\frac{q}{n}}\|\mathbf{A}\|_{2}+\sqrt{\log(q)/b}\|\mathbf{A}\|_{1\to
2}\right)=O\left(\sqrt{\frac{q}{n}}\|\mathbf{A}^{*}\|_{2}+\sqrt{\log(q)}\|\mathbf{A}^{*}\|_{(n/q)}\right)$
(4.24)

and the claim follows. ∎

Intuitively, there are two technical challenges in applying Corollary 4.24.
First, a leverage score sampling matrix need not sample columns uniformly at
random, since we have no control over the column norms of $\mathbf{Z}^{\top}$.
Second, the $\|\cdot\|_{(n/q)}$ norm only shrinks when all columns of
$\mathbf{A}$ have roughly the same squared norm. We overcome these challenges
by partitioning the matrix, first according to row norms, such that each
partition does indeed have the same row norm, up to a factor of $2$. Next, we
further partition each such matrix according to the sampling probabilities,
such that within each partition, the sampling process is close to uniform
sampling. Formally,

######  Lemma 4.25.

(Weak Spectral Approximate Matrix Product.) Let $\mathbf{Z},\mathbf{C}^{*}$
and $\SS$ be as defined in Lemma 4.19. Then, with probability at least
$99/100$, $\SS$ satisfies $(\widetilde{O}(1),k/\epsilon)$-Spectral AMM, i.e.,

$\|\mathbf{C}^{*}\SS\SS^{\top}\mathbf{Z}\|^{2}_{2}\leq\widetilde{O}(1)\left(\frac{\epsilon}{k}\|\mathbf{C}^{*}\|^{2}_{F}+\|\mathbf{C}^{*}\|^{2}_{2}\right)$

###### Proof.

By sub-multiplicativity of the spectral norm and $\SS$ being an
$O(1)$-subspace embedding for $\mathbf{Z}^{\top}$, we have

$\begin{split}\|\mathbf{C}^{*}\SS\SS^{\top}\mathbf{Z}\|^{2}_{2}&\leq\|\mathbf{C}^{*}\SS\|^{2}_{2}\cdot\|\SS^{\top}\mathbf{Z}\|^{2}_{2}\\\
&\leq O(1)\|\mathbf{C}^{*}\SS\|^{2}_{2}\end{split}$ (4.25)

where the second inequality follows from $\mathbf{Z}^{\top}$ having
orthonormal rows.

We begin by observing that Corollary 4.24 requires the squared row norms of
$\mathbf{C}^{*}$ to be roughly the same, which need not be the case in
general. Note, here the sampling matrix subsamples columns of
$\mathbf{C}^{*}$, as opposed to rows in Corollary 4.24. Thus, we partition the
rows of $\mathbf{C}^{*}$ into $O(\log(n))$ blocks such that either the squared
column norms are the same up to a factor of $2$ or they are at most
$\|\mathbf{C}^{*}\|^{2}_{F}/\textrm{poly}(n)$. Formally, for all
$\ell\in[c\log(n)]$, let

$\mathcal{B}_{\ell}=\left\\{i\in[n]:\frac{\|\mathbf{C}^{*}\|^{2}_{F}}{2^{\ell+1}}\leq\|\mathbf{C}^{*}_{i,*}\|^{2}_{2}\leq\frac{\|\mathbf{C}^{*}\|^{2}_{F}}{2^{\ell}}\right\\}$

represent the blocks for rows with large squared norm. Let
$\mathcal{B}_{r}=[n]\setminus\cup_{\ell\in[\log(n)]}\mathcal{B}_{\ell}$ be the
remaining rows, which have norm at most
$\|\mathbf{C}^{*}\|^{2}_{F}/\textrm{poly}(n)$. Since the set of indices in the
blocks form a partition of the rows of $\mathbf{C}^{*}$, we can write
$\|\mathbf{C}^{*}\|^{2}_{F}=\sum_{\ell\in[\log(n)]}\|\mathbf{C}^{*}_{\mathcal{B}_{\ell}}\|^{2}_{F}+\|\mathbf{C}^{*}_{\mathcal{B}_{r}}\|^{2}_{F}$.
Similarly, we can bound the spectral norm as follows:

$\begin{split}\|\mathbf{C}^{*}\SS\|^{2}_{2}=\max_{\|y\|^{2}_{2}=1}\|\mathbf{C}^{*}\SS
y\|^{2}_{2}&\leq
O\left(\sum_{\ell\in[\log(n)]}\|\mathbf{C}^{*}_{\mathcal{B}_{\ell}}\SS
y\|^{2}_{2}+\|\mathbf{C}^{*}_{\mathcal{B}_{r}}\SS y\|^{2}_{2}\right)\\\ &\leq
O\left(\sum_{\ell\in[\log(n)]}\|\mathbf{C}^{*}_{\mathcal{B}_{\ell}}\SS\|^{2}_{2}+\|\mathbf{C}^{*}_{\mathcal{B}_{r}}\SS\|^{2}_{2}\right)\end{split}$
(4.26)

We now handle the two separately. Since $\SS$ is an unbiased estimator of the
squared Frobenius norm of $\mathbf{Z}^{\top}$, it is an unbiased estimator of
the squared Frobenius norm of $\mathbf{C}^{*}$. Therefore, with probability at
least $99/100$,

$\|\mathbf{C}^{*}_{|\mathcal{B}_{r}}\SS\|^{2}_{2}\leq\|\mathbf{C}^{*}_{|\mathcal{B}_{r}}\SS\|^{2}_{F}=O(\|\mathbf{C}^{*}_{|\mathcal{B}_{r}}\|^{2}_{F})\leq\frac{\|\mathbf{C}^{*}\|_{F}^{2}}{\textrm{poly}(n)}<<\frac{\epsilon}{k}\|\mathbf{C}^{*}\|^{2}_{F}$
(4.27)

For the remaining terms, we cannot use this näive analysis as this would only
leave us with an upper bound of $\|\mathbf{C}^{*}\|^{2}_{F}$, which is too
large.

If instead of a leverage score sampling matrix, $\SS$ were a uniform sampling
sketch that samples $k/\epsilon$ columns of $\mathbf{C}^{*}$ in expectation,
we could apply Corollary 4.24 for each $\ell$, with $q=k/\epsilon$ and
$n=\sqrt{nk/\epsilon}$ and
$b=\left\lceil\sqrt{nk}/(\sqrt{\epsilon}|\mathcal{B}_{\ell}|)\right\rceil$, to
obtain

$\begin{split}{\bf\mathbb{E}}\left[\big{\|}\mathbf{C}^{*}_{|\mathcal{B}_{\ell}}\SS\big{\|}^{2}_{2}\right]=\sqrt{\frac{n\epsilon}{k}}{\bf\mathbb{E}}\left[\big{\|}(\mathbf{C}^{*}_{|\mathcal{B}_{\ell}})_{Q}\big{\|}^{2}_{2}\right]&\leq
O\left(\big{\|}\mathbf{C}^{*}_{|\mathcal{B}_{\ell}}\big{\|}^{2}_{2}+\frac{\epsilon\log(k/\epsilon)|\mathcal{B}_{\ell}|}{k}\big{\|}(\mathbf{C}^{*})^{\top}_{|\mathcal{B}_{\ell}}\big{\|}^{2}_{\sqrt{\epsilon
n/k}}\right)\\\ &\leq
O\left(\big{\|}\mathbf{C}^{*}_{|\mathcal{B}_{\ell}}\big{\|}^{2}_{2}+\frac{\epsilon\log(k/\epsilon)}{k}\big{\|}\mathbf{C}^{*}_{|\mathcal{B}_{\ell}}\big{\|}^{2}_{F}\right)\end{split}$
(4.28)

where $Q$ is the subset of columns selected by $\SS$ and the second inequality
follows from observing that the all the row norms of
$(\mathbf{C}^{*})_{\mid\mathcal{B}_{\ell}}$ are within a factor of $2$ of each
other and thus the max squared row norm times the size of the set is the
squared Frobenius norm.

Using Equations 4.27 and 4.28 to upper bound the two terms in Equation 4.26
suffices to finish the proof. Unfortunately, a similar analysis does not
immediately go through when we replace a uniform sampling matrix with a
leverage score sketch. Instead, we partition the sketch $\SS$ into buckets
such that each bucket corresponds to rows in $\SS$ that scale columns of
$\mathbf{C}^{*}$ within a factor of $2$. For notational convenience, let
$m=\sqrt{nk/\epsilon}$ and $t=k/\epsilon$. Recall, we construct $\SS$ by
sampling the $j$-th column of $\mathbf{Z}^{\top}$ independently with
probability $q_{j}=\min(\|\mathbf{Z}_{j,*}\|^{2}_{2}\log(k),1)$ and scale this
column by $1/\sqrt{q_{j}}$. We group the scaling factors into buckets. Note,
if for some $j$, $q_{j}<1/n^{3}$, we can ignore the corresponding column.

Let $\zeta_{j}$ be the indicator for a column of $\mathbf{Z}^{\top}$ to be
sampled by $\SS$. Then,
$\Pr[\zeta_{j}=1]=q_{j}=\min(\|\mathbf{Z}^{\top}_{*,j}\|^{2}_{2}\log(k),1)$.
Since $q_{j}\leq 1/n^{3}$, we can union bound over at most $m$ such events and
conclude with probability at least $1-1/n^{2}$, for all $j\in m$, no column
$\mathbf{Z}^{\top}_{*,j}$ is sampled such that $q_{j}\leq 1/n^{3}$. Further,
since $q_{j}\leq 1$, $1/\sqrt{q_{j}}\in[1,n^{1.5}]$. Therefore, it suffices to
bucket values in the range $[1,n^{1.5}]$. For all $h\in[c\log(n)]$, let
$\mathcal{S}$ denote the set of column indices from $\mathbf{Z}^{\top}$ that
were sampled by the sketch $\SS$. Then,

$\mathcal{T}_{h}=\left\\{j\in\mathcal{S}:2^{h}\leq\frac{1}{\sqrt{q_{j}}}\leq
2^{h+1}\right\\}$

Let $\SS_{\mathcal{T}_{h}}$ be the subset of rows of $\SS$ which are indexed
by the set $\mathcal{T}_{h}$. Since $t$ is fixed and the scaling factors in
$\mathcal{T}_{h}$ differ by at most a factor of $2$, the corresponding
sampling probabilities in $\mathbf{D}$ differ by at most $\sqrt{2}$, which is
still not uniform. To fix this, we change the sampling process and
independently sample each column indexed by $j\in\mathcal{T}_{h}$ with
probability $2^{h+1}$, while still scaling it by $1/\sqrt{tq_{j}}$. Let this
new distribution be denoted by $q^{\prime}$. Under the new sampling process,
we now sample rows independently and therefore, we are at least as likely to
see all the rows sampled by $\SS_{\mathcal{T}_{h}}$ in our new sampling
process. Therefore, it now holds that

${\bf\mathbb{E}}_{q}\left[\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}\|^{2}_{2}\right]\leq{\bf\mathbb{E}}_{q^{\prime}}\left[\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}\|^{2}_{2}\right]$

Further, in the new sampling process, each row restricted to the set
$\mathcal{T}_{h}$ is uniformly sampled with probability $1/2^{(h+1)/2}$ and
thus we can apply Corollary 4.24 to
$\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}$.

$\begin{split}{\bf\mathbb{E}}_{q^{\prime}}\left[\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}\|^{2}_{2}\right]&\leq
O\left(\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{2}+\frac{\epsilon\log(k/\epsilon)|\mathcal{B}_{\ell}|}{k}\big{\|}(\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}})^{\top}\big{\|}_{(\sqrt{\epsilon
n/k})}\right)\\\ &\leq
O\left(\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{2}+\frac{\epsilon\log(k/\epsilon)}{k}\big{\|}\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\big{\|}^{2}_{F}\right)\end{split}$
(4.29)

where the second inequality follows from squared row norms in
$\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}$ being equal up to a factor of $2$.
Therefore, with probability at least $1-1/c^{\prime}\log(n)$,

$\big{\|}\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}\big{\|}^{2}_{2}\leq\widetilde{O}\left(\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{2}+\frac{\epsilon\log(k/\epsilon)}{k}\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{F}\right)$
(4.30)

Let $\eta_{h}$ be the event that the above bound holds. Then, union bounding
over all $c\log(n)$ such events, with probability at least $99/100$,
simultaneously for all $h$,

$\begin{split}\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS\|^{2}_{2}&\leq
O\left(\sum_{h\in[c\log(n)]}\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS_{\mathcal{T}_{h}}\|^{2}_{2}\right)\\\
&\leq\widetilde{O}\left(\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\|^{2}_{F}\right)\end{split}$
(4.31)

which follows from Equation 4.30. Substituting this back into Equation 4.26,

$\begin{split}\|\mathbf{C}^{*}\SS\|^{2}_{2}&\leq
O\left(\sum_{\ell\in[\log(n)]}\|\mathbf{C}^{*}_{\mid\mathcal{B}_{\ell}}\SS\|^{2}_{2}+\|\mathbf{C}^{*}_{\mid\mathcal{B}_{r}}\SS\|^{2}_{2}\right)\\\
&\leq\widetilde{O}\left(\|\mathbf{C}^{*}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{C}^{*}\|^{2}_{F}\right)\\\
\end{split}$ (4.32)

where the second inequality follows from Equation 4.31 and observing that
$\|\mathbf{C}^{*}_{\mathcal{B}_{\ell}}\|^{2}_{2}\leq\|\mathbf{C}^{*}\|^{2}_{2}$
and
$\sum_{\ell}\|\mathbf{C}^{*}_{\mathcal{B}_{\ell}}\|^{2}_{F}=\|\mathbf{C}^{*}\|^{2}_{F}$,
which completes the proof. ∎

Combining the above lemma with 4.19, and observing that
$\|\mathbf{C}^{*}\|^{2}_{F}\leq\|\mathbf{C}-\mathbf{C}_{k/\epsilon}\|^{2}_{F}$,
we can bound the cost of $\widehat{\mathbf{W}}$

$\|\mathbf{C}-\widehat{\mathbf{W}}\mathbf{Z}^{\top}\|^{2}_{2}\leq\widetilde{O}\left(\min_{\mathbf{W}}\|\mathbf{C}-\mathbf{W}\mathbf{Z}^{\top}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k/\epsilon}\|^{2}_{F}\right)$

which completes the correctness proof of Theorem 4.18. Next, we analyze the
running time. In Step 1 of Algorithm 4.2, we compute a distribution over the
columns of $\mathbf{Z}^{\top}$, which does not require reading any entries in
$\mathbf{A}$ and takes time $\sqrt{nk/\epsilon}\cdot
k/\epsilon=\sqrt{n}(k/\epsilon)^{1.5}$. Step 2 requires computing
$\mathbf{C}\SS$ and $\mathbf{Z}^{\top}\SS$. Note since $\SS$ samples
$\widetilde{O}(k/\epsilon)$ columns in $\mathbf{C}$, we have to query
$n\cdot\widetilde{O}(k/\epsilon)$ entries in $\mathbf{A}$ to explicitly
compute $\mathbf{C}\SS$ and can be computed in as much time. Since
$\mathbf{Z}^{\top}$ has fewer rows the running time is dominated by computing
$\mathbf{C}\SS$. For Step 3, we compute
$(\mathbf{Z}^{\top}\SS\SS^{\top}\mathbf{Z})^{-1}$, which requires no queries
to $\mathbf{A}$ and runs in time $\widetilde{O}((k/\epsilon)^{\omega})$ and
thus $(\mathbf{Z}^{\top}\SS)^{\dagger}$ can be computed in the same time.
Therefore, the total query complexity of Algorithm 4.2 is
$\widetilde{O}(nk/\epsilon)$ and the running time is
$\widetilde{O}(nk/\epsilon+(k/\epsilon)^{\omega})$, which concludes the proof.

###  4.3 Sample-Optimal Algorithm

In this subsection, we describe our main algorithm for PSD Low-Rank
Approximation. Given a PSD matrix $\mathbf{A}$, our algorithm queries
$\widetilde{O}(nk/\epsilon)$ entries in $\mathbf{A}$ and runs in time
$\widetilde{O}(n(k/\epsilon)^{\omega-1}+(k/\epsilon^{3})^{\omega})$. This
resolves an open question on the $\epsilon$-dependence of the query complexity
and matches the lower bound of $\Omega(nk/\epsilon)$ up to polylog factors
from [MW17]. At a high level, our algorithm consists of two stages: first, we
use the existing machinery developed by Musco and Woodruff to obtain weak PCPs
by setting $\epsilon$ to be a constant. By observing that their algorithms
have linear dependence on the rank, we can afford to rank-$(k/\epsilon)$ PCPs
instead. This enables us to find a structured subspace that contains a
spectral low-rank approximation for the PCP.

Since our PCPs are accurate only up to $O(1)$-error, we cannot directly
extract a $(1+\epsilon)$ relative error approximation for $\mathbf{A}$.
However, we show that the PCPs have enough structure to obtain a structured
subspace that spans a $(1+\epsilon)$-approximate solution for $\mathbf{A}$. A
key ingredient to recover this structured subspace is an efficient algorithm
for Spectral Regression.

Following the approach of Musco and Woodruff we use the ridge leverage scores
of $\mathbf{A}^{1/2}$ to compute $\mathbf{C}$, a column PCP for $\mathbf{A}$
and $\mathbf{R}$ a row PCP for $\mathbf{C}$, with a minor tweak: we
instantiate their theorems (Lemmas 4.11 and 4.12) with $k=k/\epsilon$ and
$\epsilon=O(1)$. While the precise guarantees satisfied by our PCPs are weaker
than the PCPs used by Musco and Woodruff, the dimensions of our PCPs are
smaller.

Input: A PSD Matrix $\mathbf{A}\in\mathbb{R}^{n\times n}$, integer $k$, and
$\epsilon>0$. 1. Let $t=c\sqrt{\frac{nk}{\epsilon}}\log(n)$, for some constant
$c$ and let $k^{\prime}=\widetilde{O}(k/\epsilon)$. For all $j\in[n]$, let
$\bar{\rho}^{k^{\prime}}_{j}(\mathbf{A}^{1/2})$ be the approximate column
ridge-leverage scores that satisfy Lemma 4.9. Let $q=\\{q_{1},q_{2}\ldots
q_{n}\\}$ denote a distribution over columns of $\mathbf{A}$ such that
$q_{j}=\rho_{j}^{k^{\prime}}(\mathbf{A}^{1/2})/\sum_{j}\rho_{j}^{k^{\prime}}(\mathbf{A}^{1/2})$.
2. Construct a column PCP for $\mathbf{A}$ by sampling $t$ columns of
$\mathbf{A}$ such that each column is set to
$\frac{\mathbf{A}_{*,j}}{\sqrt{tq_{j}}}$ with probability $q_{j}$, for all
$j\in[n]$. Let $\mathbf{C}$ be the resulting $n\times t$ matrix that satisfies
the guarantee of Lemma 4.11 instantiated with $k=k^{\prime}$ and
$\epsilon=O(1)$. 3. Construct a row PCP for $\mathbf{C}$ by sampling $t$ rows
of $\mathbf{C}$ such that each row is set to
$\frac{\mathbf{C}_{i,*}}{\sqrt{tq_{i}}}$ with probability $q_{i}$, for all
$i\in[n]$. Let $\mathbf{R}$ be the resulting $t\times t$ matrix that satisfies
the guarantee of Lemma 4.12 instantiated with $k=k/\epsilon$ and
$\epsilon=O(1)$. 4. Run the input-sparsity algorithm from Lemma 4.6 to compute
a rank-$k/\epsilon$ matrix $\mathbf{Z}$ with orthonormal columns such that
$\|\mathbf{R}-\mathbf{R}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}\leq
O\left(\frac{\epsilon}{k}\right)\|\mathbf{R}-\mathbf{R}_{k/\epsilon}\|^{2}_{F}$.
5. Run Algorithm 4.2 with parameters $k$, $\epsilon$ on the Spectral
Regression problem
$\min_{\mathbf{W}}\|\mathbf{C}-\mathbf{W}\mathbf{Z}^{\top}\|_{2}$ Let
$\widehat{\mathbf{W}}$ be the output of Algorithm 4.2. Compute an orthonormal
basis $\mathbf{Q}$ for $\mathbf{W}$. Note, $\mathbf{Q}\mathbf{Q}^{\top}$ is an
$(O(1),k/\epsilon)$-SF projection for $\mathbf{A}$. 6. Run Algorithm 4.1 with
input $\mathbf{A}$, $\mathbf{Q}$, $k$ and $\epsilon$ to approximately minimize
$\|\mathbf{A}-\mathbf{Q}\mathbf{X}\mathbf{Q}^{\top}\|^{2}_{F}$ over rank $k$
matrices $\mathbf{X}$. Let $\mathbf{M},\mathbf{N}$ be the output of Algorithm
4.1. Output: $\mathbf{M},\mathbf{N}^{\top}\in\mathbb{R}^{n\times k}$ such that
$\|\mathbf{A}-\mathbf{M}\mathbf{N}\|^{2}_{F}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$

In particular, we obtain a row PCP $\mathbf{R}$, which is a
$\sqrt{nk/\epsilon}\times\sqrt{nk/\epsilon}$ matrix (ignoring polylogarithmic
factors) and we can afford to read all of it. The input-sparsity time
algorithm from Lemma 4.6 queries
$\textsf{nnz}(\mathbf{R})=\widetilde{O}(nk/\epsilon)$ entries to obtain a
rank-$(k/\epsilon)$ matrix $\mathbf{Z}$ with orthonormal columns such that

$\|\mathbf{R}-\mathbf{R}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}\leq\frac{\epsilon}{k}\|\mathbf{R}-\mathbf{R}_{k}\|^{2}_{F}$
(4.33)

Since $\mathbf{R}$ is a Spectral-Frobenius PCP for $\mathbf{C}$,
$\mathbf{Z}\mathbf{Z}^{\top}$ satisfies
$\|\mathbf{C}-\mathbf{C}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}\leq\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k}\|^{2}_{F}$.
Since $\mathbf{C}$ is a Spectral-Frobenius PCP for $\mathbf{A}$, it suffices
to obtain a projection for the column space of $\mathbf{C}$ that also
satisfies the above guarantee. Therefore, we solve the following Spectral
Regression problem:
$\min_{\mathbf{W}}\|\mathbf{C}-\mathbf{W}\mathbf{Z}^{\top}\|^{2}_{2}$. Recall,
we can approximately optimize this using Algorithm 4.2. Let
$\widehat{\mathbf{W}}$ be the resulting solution. We can then compute an
orthonormal basis for $\widetilde{\mathbf{W}}$ (denoted by $\mathbf{Q}$) and
show that $\mathbf{Q}\mathbf{Q}^{\top}$ is an $(O(1),k/\epsilon)$-SF
projection for $\mathbf{A}$. Then, we can obtain a low rank approximation for
$\mathbf{A}$ by simply running Algorithm 4.1.

Proof of Theorem 4.1. Let $k^{\prime}=\widetilde{O}(k/\epsilon)$. It follows
from Lemma 4.9 that we can compute the rank-$k^{\prime}$ ridge leverage scores
of $\mathbf{A}^{1/2}$, up to a constant factor using the algorithm of Musco
and Musco [MM17]. By Lemma 4.10, the ridge leverage scores of
$\mathbf{A}^{1/2}$ are a $\sqrt{\epsilon n/k^{\prime}}$-approximation to the
ridge leverage scores of $\mathbf{A}$. Let $q$ be a distribution over rows and
columns of $\mathbf{A}$ as defined in Algorithm 4.3. Since we sample
$t=O(\sqrt{nk/\epsilon}\log(n))$ columns of $\mathbf{A}$ proportional to $q$,
instantiating Lemma 4.12 with $k=k^{\prime}$ and $\epsilon=0.1$, we obtain a
mixed Spectral-Frobenius column PCP $\mathbf{C}$ such that with probability at
least $1-c_{1}$, for all rank-$k^{\prime}$ projections $\mathbf{X}$,

$\frac{9}{10}\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{2}-\frac{1}{10k^{\prime}}\|\mathbf{A}-\mathbf{A}_{k^{\prime}}\|^{2}_{F}\leq\|\mathbf{C}-\mathbf{X}\mathbf{C}\|^{2}_{2}\leq\frac{11}{10}\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{2}+\frac{1}{10k^{\prime}}\|\mathbf{A}-\mathbf{A}_{k^{\prime}}\|^{2}_{F}$
(4.34)

Let $\zeta_{1}$ be the indicator for $\mathbf{C}$ satisfying the above
guarantee. Similarly, sampling $t$ rows of $\mathbf{C}$ proportional to $q$,
results in a mixed Spectral-Frobenius row PCP for $\mathbf{R}$ such that with
probability at least $1-c_{2}$, for all rank-$k^{\prime}$ projection matrices
$\mathbf{X}$,

$\frac{9}{10}\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{2}-\frac{1}{10k^{\prime}}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\leq\|\mathbf{R}-\mathbf{R}\mathbf{X}\|^{2}_{2}\leq\frac{11}{10}\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{2}+\frac{1}{10k^{\prime}}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}$
(4.35)

Further, it is well-known that with the same probability
$\|\mathbf{R}-\mathbf{R}_{k^{\prime}}\|^{2}_{F}=\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}$.
Let $\zeta_{2}$ be the event that $\mathbf{R}$ satisfies the above guarantee.
Next, we compute a Spectral Low-Rank Approximation for $\mathbf{R}$, using the
algorithm from Lemma 4.6, with $k=k^{\prime}$ and $\epsilon=0.1$. As a result,
with probability at least $1-c_{3}$, we obtain a rank-$k^{\prime}$ matrix
$\mathbf{Z}\in\mathbb{R}^{t\times k}$, such that $\mathbf{Z}\mathbf{Z}^{\top}$
is a $(0.1,k^{\prime})$-SF projection for $\mathbf{R}$, i.e.,

$\|\mathbf{R}-\mathbf{R}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}\leq\frac{1}{10k^{\prime}}\|\mathbf{R}-\mathbf{R}_{k^{\prime}}\|^{2}_{F}$
(4.36)

Let $\zeta_{3}$ be the event that $\mathbf{Z}$ satisfies the above guarantee.
Union bounding over $\zeta_{1},\zeta_{2},\zeta_{3}$, we know that all of them
hold with probability at least $1-(c_{1}+c_{2}+c_{3})$. Since $\mathbf{R}$ is
a Spectral-Frobenius row PCP for $\mathbf{C}$ and
$\mathbf{Z}\mathbf{Z}^{\top}$ is a rank-$k^{\prime}$ projection matrix, it
follows from Equation 4.35

$\begin{split}\|\mathbf{C}-\mathbf{C}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}&\leq\frac{10}{9}\|\mathbf{R}-\mathbf{R}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}+\frac{1}{9k^{\prime}}\|\mathbf{R}-\mathbf{R}_{k^{\prime}}\|^{2}_{F}\\\
&\leq\frac{1}{10k^{\prime}}\|\mathbf{R}-\mathbf{R}_{k}\|^{2}_{F}+\frac{1}{9k^{\prime}}\|\mathbf{R}-\mathbf{R}_{k^{\prime}}\|^{2}_{F}\\\
&\leq\widetilde{O}\left(\frac{\epsilon}{k}\right)\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\end{split}$
(4.37)

where the second inequality follows from Equation 4.33 and the third follows
from the fact that PCPs preserve Frobenius norm up to a constant factor. While
conditioning on $\zeta_{3}$, it follows from Equation 4.37 that
$\mathbf{Z}\mathbf{Z}^{\top}$ is an $(\widetilde{O}(1),k/\epsilon)$-SF
projection for $\mathbf{C}$, our goal is to compute an SF projection for
$\mathbf{A}$. Since $\mathbf{Z}\mathbf{Z}^{\top}$ is a $t\times t$ matrix, it
does not even match the dimensions of $\mathbf{A}$. Therefore, we set up the
following Spectral Regression problem:

$\min_{\mathbf{W}\in\mathbb{R}^{n\times
k^{\prime}}}\|\mathbf{C}-\mathbf{W}\mathbf{Z}^{\top}\|^{2}_{2}$ (4.38)

Let $\widehat{\mathbf{W}}$ be the approximate minimizer of the above problem
obtained by running Algorithm 4.2. Then, it follows from Theorem 4.18 that
with probability at least $99/100$,

$\begin{split}\|\mathbf{C}-\widehat{\mathbf{W}}\mathbf{Z}^{\top}\|^{2}_{2}&\leq\widetilde{O}(1)\left(\min_{\mathbf{W}}\|\mathbf{C}-\mathbf{W}\mathbf{Z}^{\top}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\right)\\\
&\leq\widetilde{O}(1)\left(\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\right)\\\
&\leq\widetilde{O}(1)\left(\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\right)\end{split}$
(4.39)

where the second inequality follows from
$\|\mathbf{C}-\mathbf{C}\mathbf{Z}\mathbf{Z}^{\top}\|^{2}_{2}\leq\widetilde{O}\left(\frac{\epsilon}{k}\right)\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}$
(by definition of an SF projection) and observing that
$\mathbf{W}=\mathbf{C}\mathbf{Z}^{\top}$ is a feasible solution to Equation
4.38. Let $\zeta_{4}$ be the event that Equation 4.39 holds. Next, let
$\mathbf{Q}$ be an orthonormal basis for $\mathbf{W}$. We observe that
$\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}$ is the orthogonal projection of
$\mathbf{C}$ onto the subspace spanned by $\mathbf{Q}$ and the matrix
$\widehat{\mathbf{W}}\mathbf{Z}^{\top}$ also lies in the subspace. Therefore,
by the Pythagorean Theorem, for any fixed unit vector $y$,

$\|\mathbf{C}y-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}y\|^{2}_{2}\leq\|\mathbf{C}y-\widehat{\mathbf{W}}\mathbf{Z}^{\top}y\|^{2}_{2}\leq\|\mathbf{C}-\widehat{\mathbf{W}}\mathbf{Z}^{\top}\|^{2}_{2}$

Picking $y$ such that
$\|\mathbf{C}y-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}y\|^{2}_{2}=\|\mathbf{C}-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}\|^{2}_{2}$,
and combining it with Equation 4.39 we have

$\|\mathbf{C}-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}\|^{2}_{2}\leq\widetilde{O}(1)\left(\frac{\epsilon}{k}\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}\right)$
(4.40)

Conditioning on event $\zeta_{1}$, we know that
$\|\mathbf{C}-\mathbf{C}_{k^{\prime}}\|^{2}_{F}=\|\mathbf{A}-\mathbf{A}_{k^{\prime}}\|^{2}_{F}$.
Since $\mathbf{Q}\mathbf{Q}^{\top}$ is a rank-$k^{\prime}$ projection matrix
and $\mathbf{C}$ is a mixed Spectral-Frobenius column PCP for $\mathbf{A}$, it
follows from Equation 4.34,

$\begin{split}\|\mathbf{A}-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{A}\|^{2}_{2}&\leq\frac{10}{9}\|\mathbf{C}-\mathbf{Q}\mathbf{Q}^{\top}\mathbf{C}\|^{2}_{2}+\frac{1}{9k^{\prime}}\|\mathbf{A}-\mathbf{A}_{k^{\prime}}\|^{2}_{F}\\\
&\leq\widetilde{O}(1)\left(\frac{\epsilon}{k}\|\mathbf{A}-\mathbf{A}_{k^{\prime}}\|^{2}_{F}\right)\end{split}$
(4.41)

where the last inequality follows from Equation 4.40. Therefore,
$\mathbf{Q}\mathbf{Q}^{\top}$ is a $(0.1,k^{\prime})$-SF projection for
$\mathbf{A}$. Finally, we run Algorithm 4.1 on
$\min_{\textrm{rank}(\mathbf{X})=k}\|\mathbf{A}-\mathbf{Q}\mathbf{X}\mathbf{Q}^{\top}\|^{2}_{F}$.
Here, we note that for Algorithm 4.1, a $(0.1,k^{\prime})$-SF projection is
equivalent to an $(\epsilon,k)$-SF projection, up to polylogarithmic factors.
Therefore, Theorem 4.16 holds as is. Then, by Theorem 4.16, we know that with
probability at least $99/100$ Algorithm 4.1 outputs matrices
$\mathbf{M},\mathbf{N}$ such that
$\|\mathbf{A}-\mathbf{M}\mathbf{N}^{\top}\|^{2}_{F}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$.
Let $\zeta_{5}$ be the event that the aforementioned algorithm succeeds. Then,
union bounding over $\zeta_{1},\zeta_{2},\zeta_{3},\zeta_{4}$ and $\zeta_{5}$,
with probability at least $9/10$, $\mathbf{M},\mathbf{N}$ is a relative-error
Low-Rank Approximation for $\mathbf{A}$, which concludes correctness.

Next, we analyze the query complexity and running time of Algorithm 4.3. Step
$1$ computes the rank-$k^{\prime}$ ridge leverage scores of $\mathbf{A}^{1/2}$
and by Lemma 4.9, requires reading
$O(nk^{\prime}\log(k^{\prime}))=\widetilde{O}(nk/\epsilon)$ entries in
$\mathbf{A}$ and runs in time $\widetilde{O}(n(k/\epsilon)^{\omega-1})$. Steps
$2$ and $3$ require no queries to $\mathbf{A}$ and the sampling can be
performed in $O(n)$ time. In step $4$, the input sparsity algorithm from Lemma
4.6 queries $\textsf{nnz}(\mathbf{R})=t^{2}=\widetilde{O}(nk/\epsilon)$
entries in $\mathbf{A}$ and runs in
$\widetilde{O}(nk/\epsilon+\sqrt{n}\textrm{poly}(k/\epsilon))=\widetilde{O}(nk/\epsilon)$
time. We know from Theorem 4.16 that Step $5$ requires
$\widetilde{O}(nk/\epsilon)$ queries to $\mathbf{A}$ and runs in
$\widetilde{O}(nk/\epsilon+(k/\epsilon)^{\omega})$ time. Finally, in Step $6$,
we run Algorithm 4.1 such that $\mathbf{Q}$ is a $n\times k^{\prime}$ matrix.
Therefore, it follows from Theorem 4.16, that the total number of queries to
$\mathbf{A}$ is $\widetilde{O}(nk/\epsilon+k^{2}/\epsilon^{6})$ and the
running time is
$\widetilde{O}(n(k/\epsilon)^{\omega-1}+(k/\epsilon^{3})^{\omega})$. The final
query complexity and running time follows, and this concludes the proof.

Outputting a PSD Low-Rank Approximation. Here, we extend our algorithm to show
that we can obtain a relative-error low-rank approximation matrix $\mathbf{B}$
such that $\mathbf{B}$ itself is a PSD matrix, using the same sample
complexity and running time as in Theorem 4.1. Outputting a PSD low-rank
approximation was first considered by Clarkson and Woodruff [CW17], who obtain
an input-sparsity algorithm for arbitrary $\mathbf{A}$. When $\mathbf{A}$ is
PSD, Musco and Woodruff show that this problem can be solved with
$\widetilde{O}(nk/\epsilon^{3}+nk^{2}/\epsilon^{2})$ queries, in time
$\widetilde{O}(n(k/\epsilon)^{\omega}+nk^{\omega-1}/\epsilon^{3(\omega-1)})$.

We run Algorithm 4.3 till Step 5, i.e., we recover $\mathbf{Q}$ such that
$\mathbf{Q}\mathbf{Q}^{\top}$ is a SF projection for $\mathbf{A}$. We then
modify Algorithm 4.1 by considering the following optimization problem
instead:

$\min_{\begin{subarray}{c}\textrm{rank}(\mathbf{X})\leq k\\\ \mathbf{X}\succeq
0\end{subarray}}\|\mathbf{A}-\mathbf{Q}\mathbf{X}\mathbf{Q}^{\top}\|^{2}_{F}$
(4.42)

As before, we sketch on both sides by sampling proportional to the leverage
scores of $\mathbf{Q}$. Let the resulting sampling matrices be denoted by
$\SS,\mathbf{T}$. Then, we have the following sketched optimization problem:

$\min_{\begin{subarray}{c}\textrm{rank}(\mathbf{X})\leq k\\\ \mathbf{X}\succeq
0\end{subarray}}\|\SS\mathbf{A}\mathbf{T}-\SS\mathbf{Q}\mathbf{X}\mathbf{Q}^{\top}\mathbf{T}\|^{2}_{F}$
(4.43)

Following Step 4 in Algorithm 4.1, we can compute $\SS\mathbf{A}\mathbf{T}$,
$\mathbf{P}_{\SS\mathbf{Q}}$, $\mathbf{P}_{\mathbf{Q}^{\top}\mathbf{T}}$. We
then compute
$\widehat{\mathbf{X}}=(\SS\mathbf{Q})^{\dagger}\mathbf{P}_{\SS\mathbf{Q}}\SS\mathbf{A}\mathbf{T}\mathbf{P}_{\mathbf{Q}^{\top}\mathbf{T}}(\mathbf{Q}^{\top}\mathbf{T})^{\dagger}$
and
$\mathbf{X}^{*}=[(\widehat{\mathbf{X}}+\widehat{\mathbf{X}}^{\top})/2]_{k+}$,
where for any matrix $\mathbf{M}$, $[\mathbf{M}]_{k+}$ is defined by setting
all but the top-$k$ positive eigenvalues to $0$. Finally, we output
$\mathbf{N}\mathbf{N}^{\top}$ where
$\mathbf{N}=\mathbf{Q}(\mathbf{X}^{*})^{1/2}$.

######  Corollary 4.26.

(Outputting a PSD Low-Rank Approximation.) Given an $n\times n$ PSD matrix
$\mathbf{A}$, an integer $k$, and $1>\epsilon>0$, there exists an algorithm
that samples $\widetilde{O}(nk/\epsilon)$ entries in $\mathbf{A}$ and outputs
a rank-$k$ $\mathbf{M}\mathbf{M}^{\top}$ such that with probability at least
$9/10$,

$\|\mathbf{A}-\mathbf{M}\mathbf{M}^{\top}\|^{2}_{F}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$

Further, the algorithm runs in
$\widetilde{O}(n(k/\epsilon)^{\omega-1}+(k/\epsilon^{3})^{\omega})$ time.

###### Proof.

We first note that an extension of Lemma 4.14 holds for outputting a PSD
matrix as well. As a consequence of the following lemma, obtaining an
approximate solution to the optimization problem in Equation 4.42 suffices.

######  Lemma 4.27.

(Structured Projections and PSD LRA [CW17].) Let
$\mathbf{P}\in\mathbb{R}^{n\times n}$ be an $(\epsilon,k)$-SF projection w.r.t
$\mathbf{A}$, then

$\|\mathbf{A}-\mathbf{P}\mathbf{A}_{k+}\mathbf{P}\|^{2}_{F}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k+}\|^{2}_{F}$

We then use the analysis of Lemma 15 from [CW17] to conclude that
$\mathbf{X}^{*}$ is the minimizer for Equation 4.43. Finally, we note that the
running time and query complexity is dominated by computing $\mathbf{Q}$ and
thus is the same as Theorem 4.1. Computing $\mathbf{X}^{*}$ requires no
additional queries to $\mathbf{A}$ and only contributes a lower order term to
the running time. ∎

###  4.4 Negative-Type Distances

In this subsection, we consider the problem of computing low-rank
approximation for distance matrices. Here, the input matrix $\mathbf{A}$ is
formed by the pairwise distances between a set of points
$\mathbf{P}=\\{p_{1},\ldots,p_{n}\\}$ in an underlying metric space $d$, i.e.,
$A_{i,j}=d(p_{i},p_{j})$. Low-rank approximation for distance matrices was
introduced by Bakshi and Woodruff [BW18] who obtained sublinear time additive-
error algorithms for arbitrary metrics. Subsequently, Indyk et. al. [IVWW19]
provided sample-optimal algorithms for additive-error low-rank approximation.
For arbitrary distance matrices, it is known that relative-error algorithms
require $\Omega(\textrm{nnz}(\mathbf{A}))$ queries [BW18].

Here, we focus on the special case of negative-type (Euclidean Squared)
metrics [Sch38]. Negative-type metrics have numerous applications in algorithm
design since it is possible to optimize over them using a semidefinite program
(SDP). One significant algorithmic application of negative-type metrics
appears in the Arora-Rao-Vazirani algorithm for the Sparsest Cut problem
[ARV09]. We refer the reader to extensive subsequent work on embeddability of
such metrics and the references therein [ALN08, ALN07, CGR05]. It is well-
known that negative-type metrics include $\ell_{1}$ and $\ell_{2}$ metrics,
spherical metrics and hyper metrics [DL09, TD87]. Therefore, our algorithms
extend to distance matrices that arise from all such metrics.

For negative-type metrics, Bakshi and Woodruff obtain a bi-criteria relative-
error low-rank approximation algorithm that queries
$\widetilde{O}(nk/\epsilon^{2.5})$ entries in $\mathbf{A}$ and output a rank
$k+4$ matrix. In contrast, we obtain a sample-optimal algorithm that does not
require a bi-criteria guarantee. As noted above, our algorithm works for any
distance matrix where the distance can be realized as a negative-type metric.

######  Theorem 4.28 (Sample-Optimal Negative-Type LRA).

Let $\mathbf{A}\in\mathbb{R}^{n\times n}$ be a negative-type distance matrix.
Given $\epsilon>0$ and $k\in[n]$, there exists an algorithm that queries
$\widetilde{O}(nk/\epsilon)$ entries in $\mathbf{A}$ and outputs matrices
$\mathbf{M},\mathbf{N}^{\top}\in\mathbb{R}^{n\times k}$ such that with
probability $99/100$,

$\|\mathbf{A}-\mathbf{M}\mathbf{N}\|^{2}_{F}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$

Further, the algorithm runs in time $\widetilde{O}(n(k/\epsilon)^{\omega-1})$.

To demonstrate the connection between negative-type metrics and PSD matrices,
we observe that a negative-type distance matrix $\mathbf{A}$ can be realized
as the distances corresponding to a point set
$\mathcal{P}=\\{x_{1},x_{2},\ldots x_{n}\\}$ such that
$\mathbf{A}_{i,j}=\|x_{i}-x_{j}\|^{2}_{2}=\|x_{i}\|^{2}_{2}+\|x_{j}\|^{2}_{2}-2\langle
x_{i},x_{j}\rangle$. Therefore, we can rewrite $\mathbf{A}$ as
$\mathbf{R}_{1}+\mathbf{R}_{2}-2\mathbf{B}$, where for all $j\in[n]$,
$(\mathbf{R}_{1})_{i,j}=\|x_{i}\|^{2}_{2}$,
$\mathbf{R}_{2}=\mathbf{R}_{1}^{\top}$ and $\mathbf{B}$ is PSD. Further, we
can obtain query access to $\mathbf{B}$ by simply assuming w.l.o.g. that
$x_{1}$ is centered at the origin and the $i$-th entry in the first row
corresponds to $\|x_{i}\|^{2}_{2}$. Therefore, we can simulate our PSD low-
rank approximation algorithms on the matrix $\mathbf{B}$ by only having query
access to $\mathbf{A}$.

Our main contribution here is to show that if
$\mathbf{P}=\mathbf{Q}\mathbf{Q}^{\top}$ is an $(O(1),k/\epsilon)$-SF
projection matrix for $\mathbf{B}$, then adjoining $\mathbf{Q}^{\top}$ with
the row span of $\mathbf{R}_{1}$ and $\mathbf{R}_{2}$ results in an SF-
projection matrix for $\mathbf{A}$. Here, the row span of $\mathbf{R}_{1}$ is
$\mathbf{1}^{\top}/\sqrt{n}$ and $\mathbf{R}_{2}$ is $v$ such that for all
$i\in[n]$ $v_{i}=\|x_{i}\|^{2}_{2}/\sum_{i}\|x_{i}\|^{2}_{2}$. We note that
once we obtain an SF projection for $\mathbf{A}$, we can run Algorithm 4.1 to
output a $(1+\epsilon)$ relative-error low-rank approximation.

######  Lemma 4.29 (Structured Projections for Distance Matrices).

Let $\mathbf{A}$ be a negative-type matrix such that
$\mathbf{A}=\mathbf{R}_{1}+\mathbf{R}_{2}-2\mathbf{B}$, as defined above and
let $\epsilon>0$. Given an $(O(1),k/\epsilon)$-SF projection
$\mathbf{P}=\mathbf{Q}\mathbf{Q}^{\top}$ for $\mathbf{B}$, let
$\mathbf{\Omega}^{\top}$ be a basis for $\mathbf{Q}^{\top}$ appended with the
basis vectors for rowspan$(\mathbf{R}_{1})$ and rowspan$(\mathbf{R}_{2})$.
Then, with probability at least $99/100$,

$\min_{\textrm{rank}(\mathbf{X})\leq
k}\|\mathbf{A}-\mathbf{\Omega}\mathbf{X}\mathbf{\Omega}^{\top}\|^{2}_{2}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$

###### Proof.

By Lemma 7 in [CW17], for any symmetric matrices $\mathbf{Y},\mathbf{Z}$ such
that $(\mathbf{Y}-\mathbf{Z})\mathbf{Z}=0$ and projection matrix $\mathbf{P}$,
the following holds:

$\|\mathbf{Y}-\mathbf{P}\mathbf{Z}\mathbf{P}\|^{2}_{F}=\|\mathbf{Y}-\mathbf{Z}\|^{2}_{F}+\|\mathbf{Z}-\mathbf{P}\mathbf{Z}\mathbf{P}\|^{2}_{F}+2\mathrm{Tr}\left((\mathbf{Y}-\mathbf{Z})(\mathbf{I}-\mathbf{P})\mathbf{Z}\mathbf{P}\right)$
(4.44)

Applying Equation 4.44 with $\mathbf{Y}=\mathbf{A}$ and
$\mathbf{Z}=\mathbf{A}_{k}$, for any projection matrix $\mathbf{P}$, we have

$\|\mathbf{A}-\mathbf{P}\mathbf{A}_{k}\mathbf{P}\|^{2}_{F}=\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}+\|\mathbf{A}_{k}-\mathbf{P}\mathbf{A}_{k}\mathbf{P}\|^{2}_{F}+2\mathrm{Tr}\left((\mathbf{A}-\mathbf{A}_{k})(\mathbf{I}-\mathbf{P})\mathbf{A}_{k}\mathbf{P}\right)$
(4.45)

Next, we bound the
$\|\mathbf{A}_{k}-\mathbf{P}\mathbf{A}_{k}\mathbf{P}\|^{2}_{F}$ as follows:

$\begin{split}\|\mathbf{A}_{k}-\mathbf{P}\mathbf{A}_{k}\mathbf{P}\|^{2}_{F}&\leq
2\|\mathbf{A}_{k}(\mathbf{I}-\mathbf{P})\|^{2}_{F}\\\ &\leq
2k\|\mathbf{A}_{k}(\mathbf{I}-\mathbf{P})\|^{2}_{2}\\\ &\leq
2k\|\mathbf{A}(\mathbf{I}-\mathbf{P})\|^{2}_{2}\\\ \end{split}$ (4.46)

To bound the trace, we use the Von Neuman trace inequality,

$\begin{split}2\mathrm{Tr}\left((\mathbf{A}-\mathbf{A}_{k})(\mathbf{I}-\mathbf{P})\mathbf{A}_{k}\mathbf{P}\right)&=2\mathrm{Tr}\left((\mathbf{A}-\mathbf{A}_{k})(\mathbf{I}-\mathbf{P})^{2}\mathbf{A}_{k}\mathbf{P}\right)\\\
&\leq
2\sum_{i\in[n]}\sigma_{i}((\mathbf{A}-\mathbf{A}_{k})(\mathbf{I}-\mathbf{P}))\sigma_{i}((\mathbf{I}-\mathbf{P})\mathbf{A}_{k}\mathbf{P})\\\
&\leq
2k\|(\mathbf{A}-\mathbf{A}_{k})(\mathbf{I}-\mathbf{P})\|_{2}\|(\mathbf{I}-\mathbf{P})\mathbf{A}_{k}\mathbf{P}\|_{2}\\\
&\leq 2k\|\mathbf{A}(\mathbf{I}-\mathbf{P})\|^{2}_{2}\end{split}$ (4.47)

It suffices to bound $\|\mathbf{A}(\mathbf{I}-\mathbf{P})\|^{2}_{2}$ for
$\mathbf{P}=\mathbf{\Omega}\mathbf{\Omega}^{\top}$. Since
$\mathbf{A}=\mathbf{R}_{1}+\mathbf{R}_{2}-2\mathbf{B}$ and
$(\mathbf{R}_{1}+\mathbf{R}_{2})(\mathbf{I}-\mathbf{P})=0$, we have

$\begin{split}\|\mathbf{A}(\mathbf{I}-\mathbf{P})\|^{2}_{2}&\leq
2\|\mathbf{B}(\mathbf{I}-\mathbf{P})\|^{2}_{2}\\\ &\leq
2\|\mathbf{B}(\mathbf{I}-\mathbf{Q}\mathbf{Q}^{\top})\|^{2}_{2}\\\ &\leq
O\left(\frac{\epsilon}{k}\right)\|\mathbf{B}-\mathbf{B}_{k+2}\|^{2}_{F}\\\
\end{split}$

To relate $\|\mathbf{B}-\mathbf{B}_{k}\|^{2}_{F}$ back to $\mathbf{A}$,
observe

$\begin{split}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}=\|\mathbf{R}_{1}+\mathbf{R}_{2}-2\mathbf{B}-\mathbf{A}_{k}\|^{2}_{F}&=4\|\mathbf{B}-(\mathbf{R}_{1}+\mathbf{R}_{2}-\mathbf{A}_{k})/2\|^{2}_{F}\\\
&\geq 4\|\mathbf{B}-\mathbf{B}_{k+2}\|^{2}_{F}\end{split}$

Therefore, $\|\mathbf{A}(\mathbf{I}-\mathbf{P})\|^{2}_{2}\leq
O(\epsilon/k)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$. We can thus bound
Equations 4.47 and 4.46 with
$O(\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$. Substituting this into
Equation 4.45, we conclude that
$\|\mathbf{A}-\mathbf{P}\mathbf{A}_{k}\mathbf{P}\|^{2}_{F}\leq(1+O(\epsilon))\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$,
for $\mathbf{P}=\mathbf{\Omega}\mathbf{\Omega}^{\top}$ and the claim follows.
∎

Recall, we can compute an SF projection for the PSD matrix $\mathbf{B}$
efficiently using Algorithm 4.3 and then solve the optimization problem in
Lemma 4.29 using Algorithm 4.1. We can therefore reduce low-rank approximation
of negative-type matrices to PSD low-rank approximation with only $O(n)$
additional queries and Theorem 4.28 follows.

###  4.5 Ridge Regression

We consider the following regression problem: given a PSD matrix $\mathbf{A}$,
a vector $y$ and a ridge parameter $\lambda$,

$\min_{x}\|\mathbf{A}x-y\|^{2}_{2}+\lambda\|x\|^{2}_{2}.$

As a corollary of Theorem 4.1, we obtain a faster algorithm for the
aforementioned problem. We begin with the following simple lemma from [MW17]:

######  Lemma 4.30 (Lemma 26 in [MW17]).

Given a PSD matrix $\mathbf{A}$, vector $y$, and $\lambda>0$, let $\mathbf{B}$
be a matrix such that
$\|\mathbf{A}-\mathbf{B}\|^{2}_{2}\leq\epsilon^{2}\lambda$. Then, for any
vector $\tilde{x}$ such that

$\|\mathbf{B}\tilde{x}-y\|^{2}_{2}+\lambda\|\tilde{x}\|^{2}_{2}\leq(1+\epsilon^{\prime})\left(\min_{x}\|\mathbf{B}x-y\|^{2}_{2}+\lambda\|x\|^{2}_{2}\right)$

we have

$\|\mathbf{A}\tilde{x}-y\|^{2}_{2}+\lambda\|\tilde{x}\|^{2}_{2}\leq(1+\epsilon^{\prime})(1+5\epsilon)\left(\min_{x}\|\mathbf{A}x-y\|^{2}_{2}+\lambda\|x\|^{2}_{2}\right)$

Therefore, it suffices to find a rank-$k$ matrix $\mathbf{B}$ such that
$\|\mathbf{A}-\mathbf{B}\|^{2}_{2}\leq\epsilon^{2}\lambda$. Let
$\widetilde{s}_{\lambda}$ be an upper bound on the statistical dimension
$s_{\lambda}=\mathrm{Tr}\left((\mathbf{A}^{2}+\lambda\mathbf{I})^{-1}\mathbf{A}^{2}\right)$
Setting $k=\widetilde{s}_{\lambda}/\epsilon^{2}$, we can bound
$\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$ as follows:

$\begin{split}\frac{\epsilon^{2}}{\widetilde{s}_{\lambda}}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}&\leq\epsilon^{2}\frac{\sum^{n}_{i=k+1}\lambda_{i}^{2}(\mathbf{A})}{\sum^{n}_{i=1}\lambda_{i}^{2}(\mathbf{A})/(\lambda^{2}_{i}(\mathbf{A})+\lambda)}\\\
&\leq\epsilon^{2}\frac{\sum^{n}_{i=k+1}\lambda_{i}^{2}(\mathbf{A})}{\sum^{n}_{i=k+1}\lambda_{i}^{2}(\mathbf{A})/(\lambda^{2}_{i}(\mathbf{A})+\lambda)}\\\
&\leq c\epsilon^{2}\lambda\end{split}$

We can then solve the regression problem
$\min_{x}\|\mathbf{B}x-y\|^{2}_{2}+\lambda\|x\|^{2}_{2}$ exactly in time
$O(nk^{\omega-1})$ and obtain the following result:

######  Theorem 4.31 (Ridge Regression).

Given a PSD matrix $\mathbf{A}$, a regularization parameter $\lambda$ and an
upper bound $\widetilde{s}_{\lambda}$ on the statistical dimension
$s_{\lambda}=\mathrm{Tr}\left((\mathbf{A}^{2}+\lambda\mathbf{I})^{-1}\mathbf{A}^{2}\right)$,
there exists an algorithm that queries
$\widetilde{O}(n\widetilde{s}_{\lambda}/\epsilon^{2})$ entries of $\mathbf{A}$
and with probability $99/100$ outputs $\widehat{x}$ such that for all
$y\in\mathbb{R}^{d}$,

$\|\mathbf{A}\widehat{x}-y\|^{2}_{2}+\lambda\|\widehat{x}\|^{2}_{2}\leq(1+\epsilon)\left(\min_{x}\|\mathbf{A}x-y\|^{2}_{2}+\lambda\|x\|^{2}_{2}\right)$

Further, the algorithm runs in
$\widetilde{O}(n(\tilde{s}_{\lambda}/\epsilon^{2})^{\omega-1})$ time.

######  Remark 4.32.

Observe that we can derive a data structure from our algorithm that preserves
the objective cost (up to $1+\epsilon$) for all $x$ and $y$ simultaneously and
thus we obtain a coreset for Ridge Regression.

To complement the above algorithmic result, we present a new lower bound for
coreset constructions for ridge regression, which matches our upper bound in
all parameters. At a high level, our hard instance for constant $s_{\lambda}$
consists of $1/\epsilon^{2}$ blocks of all $1$s, each of size
$\epsilon\sqrt{n}\times\epsilon\sqrt{n}$, placed randomly across the matrix.
Since any coreset construction must preserve the cost of all $x,y$, we pick
pairs $(x,y)$ to be the eigenvectors of $\mathbf{A}$ (scaled appropriately)
and show that in order to preserve the cost of all pairs, the coreset
algorithm must find all the blocks, which requires $\Omega(n/\epsilon^{2})$
queries to $\mathbf{A}$. Repeating the above construction $s_{\lambda}$-times
suffices to obtain a linear lower bound in terms of $s_{\lambda}$. Formally,

######  Theorem 4.33 (Coreset Lower Bound for Ridge Regression).

Given a PSD matrix $\mathbf{A}$ and $\epsilon,\lambda>0$ let
$s_{\lambda}=\mathrm{Tr}\left((\mathbf{A}^{2}+\lambda\mathbf{I})^{-1}\mathbf{A}^{2}\right)$
denote the statistical dimension of $\mathbf{A}$. Then, any coreset
construction $\mathcal{C}$ that with constant probability, preserves the ridge
regression cost up to $(1+\epsilon)$ simultaneously for all $x,y$, must read
$\Omega(ns_{\lambda}/\epsilon^{2})$ entries in $\mathbf{A}$.

We recall the lower bound instance for low rank approximation of PSD matrices
shown by Musco and Woodruff :

######  Theorem 4.34 (Lower Bound for PSD LRA ([MW17])).

Given an $n\times n$ PSD matrix $\mathbf{A}$, $\epsilon_{0}>0$ and
$k_{0}\in[n]$, any randomized algorithm that outputs a rank $k_{0}$ matrix
$\mathbf{B}$ such that with probability at least $9/10$,

$\|\mathbf{A}-\mathbf{B}\|^{2}_{F}\leq(1+\epsilon_{0})\|\mathbf{A}-\mathbf{A}_{k_{0}}\|^{2}_{F}$

must query $\Omega(nk_{0}/\epsilon_{0})$ entries in $\mathbf{A}$.

We consider the hard distribution defined by Musco and Woodruff, and show that
we can obtain a low rank approximation to this instance with strengthened
parameters by using a coreset for ridge regression.

######  Definition 4.35 (Hard Input Distribution for LRA ([MW17])).

Let $\mathbf{M}$ be an $n\times n$ matrix and let $\epsilon_{0}>0$,
$k_{0}\in[n]$. Let $\gamma(n,\epsilon_{0},k_{0})$ be a distribution over
$\mathbf{M}$ such that $\mathcal{S}\subset[n]$ is a uniformly random subset of
size $n/2$, which is further partitioned into subsets
$\mathcal{S}_{1},\mathcal{S}_{2},\ldots\mathcal{S}_{k_{0}}$ such that for all
$\ell\in[k]$, $\mathcal{S}_{\ell}$ is picked uniformly at random and
$|\mathcal{S}_{\ell}|=n/(2k_{0})$. For each subset $\mathcal{S}_{\ell}$, let
$\mathbf{A}_{\mathcal{S}_{\ell}}$ denote the principle submatrix of $A$
indexed by the set $\mathcal{S}_{\ell}$. Then, with probability $1/2$,
$\mathbf{A}_{\mathcal{S}_{\ell}}$ is such that all the diagonal entries are
set to $1$ and a uniformly random principle submatrix of
$\mathbf{A}_{\mathcal{S}_{\ell}}$, indexed by the set $\mathcal{T}_{\ell}$,
such that $|\mathcal{T}_{\ell}|=c\sqrt{\epsilon_{0}|\mathcal{S}_{\ell}|}$ is
set to all $1$s. With the remaining probability
$\mathbf{A}_{\mathcal{S}_{\ell}}$ is set to the $\mathbf{I}$.

We show that we can derive a low-rank matrix $\mathbf{B}$ that satisfies the
relative-error guarantee above from a coreset for ridge regression.

###### Proof of Theorem 4.33.

We show a proof by contradiction, where the high level idea is that a coreset
for ridge regression can be used to derive a low-rank approximation to
$\mathbf{A}$, when $\mathbf{A}$ is picked from
$\gamma(n,O(1),s_{\lambda}/\epsilon^{2})$ (the hard distribution defined in
4.35). First, we observe that with probability at least $99/100$, the input
distribution has $\Omega(s_{\lambda}/\epsilon^{2})$ blocks that contain a
principle submatrix with all $1$s. To see this let $X_{1},\ldots
X_{s_{\lambda}/\epsilon^{2}}$ be indicators for the corresponding blocks
$\mathbf{A}_{\mathcal{S}_{\ell}}$ having a principle submatrix of all $1$s.
Then,

${\bf\mathbb{E}}\left[\sum_{\ell\in[s_{\lambda}/\epsilon^{2}]}X_{\ell}\right]=\frac{\epsilon^{2}n}{2s_{\lambda}}$
(4.48)

Since the $X_{\ell}$’s are independent, by a Chernoff bound we have

$\mbox{\bf
Pr}\left[\sum_{\ell\in[s_{\lambda}/\epsilon^{2}]}X_{\ell}\leq(1-\delta)\frac{\epsilon^{2}n}{2s_{\lambda}}\right]\leq\exp\left(-\frac{c\delta\epsilon^{2}n}{s_{\lambda}}\right)$
(4.49)

For $n\geq\Omega(s_{\lambda}/\epsilon^{2})$, we can bound the above
probability by $1/100$. We begin by showing that for our input instance,
$s_{\lambda}=\Theta(n/\lambda)$ and thus the aforementioned equations differ
by $O(\epsilon n/s_{\lambda})$. To see this observe

$s_{\lambda}=\sum_{i\in[n]}\frac{\sigma_{i}^{2}(\mathbf{A})}{\sigma_{i}^{2}(\mathbf{A})+\lambda}$
(4.50)

Then, there are $s_{\lambda}/2\epsilon^{2}$ large eigenvalues, each of
magnitude $\epsilon\sqrt{n/s_{\lambda}}$ and thus the total contribution is

$\frac{s_{\lambda}}{2\epsilon^{2}}\cdot\frac{(\epsilon^{2}n/s_{\lambda})}{(\epsilon^{2}n/s_{\lambda})+\lambda}=\frac{n}{\epsilon^{2}n/s_{\lambda}+\lambda}$

The remaining eigenvalues simply contribution $1/(1+\lambda)$ to the sum and
since there are at most $n$ of them, the total contribution is
$n/(1+\lambda)$. Therefore, we can conclude $s_{\lambda}=\Theta(n/\lambda)$.

For a block in $\mathbf{A}$ indexed by $\ell$, let $\hat{x}_{\ell}$ be the
eigenvector supported on indices in $\mathcal{S}_{\ell}$ and let
$\hat{y}_{\ell}=\sqrt{n/s_{\lambda}}\hat{x}_{\ell}$. For non-identity blocks,
$\mathbf{A}\hat{x}_{\ell}=|\mathcal{T}_{\ell}|\hat{x}_{\ell}=\sqrt{\epsilon^{2}n/s_{\lambda}}\hat{x}_{\ell}$
and the regression cost is

$\|(1-\epsilon)\sqrt{n/s_{\lambda}}\hat{x}_{\ell}\|^{2}_{2}+\lambda=(1-2\epsilon)n/s_{\lambda}+cn/s_{\lambda}$
(4.51)

When the block indexed by $\ell$ is the identity block, we get
$\mathbf{A}\hat{x}_{\ell}=\hat{x}$ and the regression cost is

$\|(\sqrt{n/s_{\lambda}}-1)\hat{x}_{\ell}\|^{2}_{2}+\lambda=(n/s_{\lambda}+1-2\sqrt{n/s_{\lambda}})+cn/s_{\lambda}$
(4.52)

Instead consider a vector that intersects an eigenvector $\tilde{x}_{\ell}$ on
a $(1-\gamma)$-fraction of the support and the rest is arbitrary. Then, when
an an all $1$s block exists,
$\mathbf{A}\tilde{x}_{\ell}\geq(1-\gamma)^{2}|\mathcal{T}_{\ell}|\hat{x}_{\ell}=(1-\gamma)^{2}\sqrt{\epsilon^{2}n/s_{\lambda}}\hat{x}_{\ell}$
and thus the regression cost is at most

$(1-\epsilon(1-2\gamma))^{2}n/s_{\lambda}+cn/s_{\lambda}$

Further, when the block is simply the identity, a similar calculation shows
that the regression cost is at least
$(1-2\epsilon\gamma)^{2}n/s_{\lambda}+cn/s_{\lambda}$. Therefore, the ridge
regression cost determines the existence of a $(1-2\gamma)$-fraction of an all
$1$s principle submatrix even when $\hat{x}_{\ell}$ intersects with an
eigenvector on a $(1-\gamma)$-fraction of coordinates.

Consider a coreset $\mathcal{C}$ for the above instance. Since this coreset
preserves the ridge regression objective upto a $(1+\epsilon/1000)$ factor for
all $x,y$, as per our above discussion we can query the coreset on the tuples
$(\hat{x}_{\ell},\hat{y}_{\ell})$, which represent the eigenvectors of each
block, to determine if a block contains a principle submatrix with all $1$s.
However, a priori we do not know the support of the eigenvector within each
block $\mathbf{A}_{\mathcal{S}_{\ell}}$.

Instead we query the coreset on all possible supports and show we can
determine the right one as follows: let $\tilde{x}$ be supported on a set that
intersects with a principle submatrix of all $1$s on at most a $\gamma$
fraction. Observe that
$\mathbf{A}\tilde{x}\leq\frac{1}{\gamma}\left(\gamma^{2}\epsilon\tilde{x}\right)$
and thus the ridge regression cost can be lower bounded as follows:

$(1-\epsilon\gamma)^{2}n/s_{\lambda}+cn/s_{\lambda}$ (4.53)

We therefore take the set of all vectors on which the coreset cost is less
than the above cost and let the resulting list be $\mathcal{L}$. Note, this
list must include the eigenvectors and further, only includes vectors which
intersect an all $1$’s submatrix on a $1-\gamma$-fraction. Therefore, picking
a set of $\epsilon^{2}n/s_{\lambda}$ vectors that have maximum support
suffices.

Since we detect a $(1-\gamma)$-fraction of all principle submatrices in
$\mathbf{A}$, it follows that we can output a $1+c^{\prime}$-approximate low-
rank approximation for $\mathbf{A}$, for a fixed small constant $c^{\prime}$.
To see this, observe that the optimal low-rank approximation to $\mathbf{A}$
is given by the matrix that selects all the principle submatrices with all
$1$s and thus
$\|\mathbf{A}-\mathbf{A}_{k_{0}}\|^{2}_{F}=n-k_{0}=n-s_{\lambda}/\epsilon^{2}$.
Further, our approximation to $\mathbf{A}_{k}$, denoted by $\mathbf{B}$,
matches $\mathbf{A}_{k}$ on a $(1-\gamma)$-fraction of each principle
submatrix of all $1$s and thus we match $\mathbf{A}_{k}$ on these entries.
Subsequently we bound the additional cost that $\mathbf{B}$ incurs which
$\mathbf{A}_{k}$ does not. This includes entries that are $1$ in
$\mathbf{A}_{k}$ and $0$ in $\mathbf{B}$ and vice versa.

To bound the cost of the entries that exist in $\mathbf{A}_{k}$ but do not
exist in $\mathbf{B}$, observe on each principle submatrix, $\mathbf{B}$ and
$\mathbf{A}$ intersect in at least $(1-\gamma)^{2}$-fraction of the entries
and thus the remaining entries are at most
$(1-(1-\gamma)^{2})\cdot\frac{\epsilon^{2}n}{cs_{\lambda}}\cdot\frac{s_{\lambda}}{\epsilon^{2}}=4\gamma
n/c$, since the size of each block is $\frac{\epsilon^{2}n}{cs_{\lambda}}$ and
the number of blocks are at most $\frac{s_{\lambda}}{\epsilon^{2}}$. Finally,
observe that since we do not pick exact eigenvectors we can have non-zero off
diagonal entries in $\mathbf{B}$ that do not exist in $\mathbf{A}_{k}$.
However, we have at most $\gamma$-fraction of the support on each indicator
vector remaining and contributing to two rectangular blocks of $1$s, each of
size
$\gamma\cdot\frac{\epsilon^{2}n}{cs_{\lambda}}\cdot\frac{s_{\lambda}}{\epsilon^{2}}=\gamma
n/c$. Therefore, the additional non-zero entries in $\mathbf{B}$ that do not
appear in $\mathbf{A}$ are $2\gamma n/c$ in number.

Therefore, the overall cost
$\|\mathbf{A}-\mathbf{B}\|^{2}_{F}\leq(1+6\gamma/c)n$. By setting the
constants $\gamma$ and $c$ and observing that $s_{\lambda}/\epsilon^{2}\ll n$,
we obtain a $(1+c^{\prime})$-low-rank approximation to $\mathbf{A}$, for any
arbitrary small constant $c^{\prime}$. Therefore, our reduction suffices to
solve the hard instance above and a lower bound of
$\Omega(nk_{0}/\epsilon_{0})=\Omega(ns_{\lambda}/\epsilon^{2})$ queries
follows. ∎

##  5 Robust Low-Rank Approximation

One drawback of relative-error guarantees is that the corresponding algorithms
cannot tolerate any amount of noise. Therefore, we introduce a robust model
for low-rank approximation by relaxing the requirement from relative-error
guarantees to additive-error guarantees. In the robustness model we consider,
we begin with an $n\times n$ PSD matrix $\mathbf{A}$. An adversary is then
allowed to arbitrarily corrupt $\mathbf{A}$ by adding a corruption matrix
$\mathbf{N}$ such that the corruption in each row is an fixed constant times
the $\ell^{2}_{2}$ row norm of the row and the total corruption is an
$\eta$-fraction of squared Frobenius norm of $\mathbf{A}$. While the adversary
may corrupt any number of entries of $\mathbf{A}$, the norm of the corruption
matrix is bounded and the algorithm has query access to
$\mathbf{A}+\mathbf{N}$. We parameterize our lower bound and algorithms by the
largest ratio between a diagonal entry of $\mathbf{A}$ and
$\mathbf{A}+\mathbf{N}$, denoted by
$\phi_{\max}=\max_{j\in[n]}\mathbf{A}_{j,j}/|(\mathbf{A}+\mathbf{N})_{j,j}|$.
This captures the intuition that the diagonal is crucial for sublinear time
low rank approximation and the sample complexity degrades as we corrupt larger
diagonals entries.

###  5.1 Lower Bound for Robust PSD Low-Rank Approximation

In this subsection, we show a query lower bound of
$\Omega(\eta^{2}n^{2}k/\epsilon^{2})=\Omega(\phi^{2}_{\max}nk/\epsilon)$ for
any algorithm that outputs a low rank approximation up to additive-error
$(\epsilon+\eta)\|\mathbf{A}\|^{2}_{F}$. Note, obtaining error smaller than
$\eta\|\mathbf{A}\|^{2}_{F}$ is information-theoretically impossible and
reflected in the query lower bound.

Our lower bound holds for randomized algorithms, and uses Yao’s minimax
principle [Yao77]. The overall strategy is to demonstrate a lower bound for
deterministic algorithms on a carefully chosen input distribution. We
construct our input distributions as follows: let
$\mathbf{A}\in\mathbb{R}^{n\times n}$ be a block diagonal matrix with such
that $\mathbf{B}_{1}$ is $5\epsilon/\eta\times 5\epsilon/\eta$ randomly
positioned, non-contiguous block with all entries $\sqrt{n\eta^{2}/5\epsilon}$
and $\mathbf{B}_{2}$ is the identity matrix on the remaining indices.
$\mathbf{A}$ is clearly a PSD matrix since each principle submatrix is PSD.
Observe
$\|\mathbf{A}\|^{2}_{F}=(25\epsilon/\eta^{2})\cdot(n\eta^{2}/5\epsilon)+(n-5\epsilon/\eta)=(1+5\epsilon)n-o(n)$.
Further, the dense block $\mathbf{B}_{1}$ contributes a total squared
Frobenius norm of at least $4\epsilon n$ and the diagonal entry contributes an
$\eta/\epsilon$ fraction of each row. Since $\epsilon\geq\eta$, the diagonal
contributes at most the entire $\ell^{2}_{2}$ norm. The corresponding diagonal
of $\mathbf{B}_{1}$ also has $\ell^{2}_{2}$ squared norm $5\epsilon/\eta\cdot
n\eta^{2}/5\epsilon=\eta n$.

At a high level, the adversary can then corrupt the diagonal and set each
diagonal entry to be $1$, making it hard for the algorithm to find rows
corresponding to $\mathbf{B}_{1}$. We show that any $\epsilon$-additive-error
low-rank approximation must detect at least one entry in $\mathbf{B}_{1}$ to
adaptively sample the corresponding row and column, but the diagonals no
longer provide any useful information. Thus any algorithm must query most
entries in $\mathbf{A}$. Further, in our construction, note
$\phi_{\max}=\sqrt{n\eta^{2}/5\epsilon}$.

We first describe intuitively why a low rank approximation needs to recover
many rows from the block $\mathbf{B}_{1}$. Since $\mathbf{A}$ has this block
structure, the best rank-$1$ approximation satisfies
$\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}=n-|\mathbf{B}_{1}|$. Therefore,
assuming the cardinality of $\mathbf{B}_{1}$ is negligible, in order to obtain
an overall error bound of $\epsilon\|\mathbf{A}\|^{2}_{F}\geq\epsilon n$, the
algorithm must find a constant fraction of off-diagonal entries in
$\mathbf{B}_{1}$. This is because $\mathbf{B}_{1}$ contributes at least
$5\epsilon n$ norm. However, since the diagonals no longer convey any
information about the off-diagonals, and the block $\mathbf{B}_{1}$ is placed
on a random subset of indices, any deterministic algorithm must read arbitrary
off-diagonal entries until it finds a non-zero entry. Since there are only
$25\epsilon^{2}/\eta^{2}$ non-zeros in $\mathbf{B}_{1}$, to find one in
expectation (over the input distribution) requires sampling
$\epsilon^{2}n^{2}/\eta^{2}$ entries. While the above serves well as
intuition, a rigorous proof requires many additional steps. We begin by
defining a distribution over the input matrices :

######  Definition 5.1.

Given $n\in\mathbb{N},\epsilon>\eta>0$, let $\mathcal{S}\subset[n]$ be a
uniformly random subset of size $\lceil 5\epsilon/\eta\rceil$. Let
$\mu(n,\epsilon,\eta)$ be a distribution over matrices
$\mathbf{M}\in\mathbb{R}^{n\times n}$ such that $\forall i\in[n]$,
$\mathbf{M}_{i,i}=1$ and $\forall i,j\in\mathcal{S}$,
$\mathbf{M}_{i,j}=\sqrt{\eta^{2}n/5\epsilon}$. All remaining entries in
$\mathbf{M}$ are $0$.

Next, we show that any $\mathbf{M}$ sampled from $\mu(n,\epsilon,\eta)$ can be
decomposed into $\mathbf{A}+\mathbf{N}$ such that $\mathbf{A}$ is PSD and
$\|\mathbf{N}\|^{2}_{F}\leq\eta\|\mathbf{A}\|^{2}_{F}$. To see this, let
$\mathbf{N}$ be a diagonal matrix such that for all $i\in\mathcal{S}$,
$\mathbf{N}_{i,i}=-\sqrt{\eta^{2}n/5\epsilon}$ and let
$\mathbf{A}=\mathbf{M}-\mathbf{N}$. We give an algebraic proof that
$\mathbf{A}$ is PSD, but $\mathbf{A}$ can also be decomposed into a rank-$1$
block of all $\sqrt{\eta^{2}n/5\epsilon}$-s corresponding to all
$i,j\in\mathcal{S}$ and identity on the remaining indices. For all
$x\in\mathbb{R}^{n}$,

$\begin{split}x^{T}\mathbf{A}x&=\sum_{i,j\in\mathcal{S}}\mathbf{A}_{i,j}x_{i}x_{j}+\sum_{i,j\notin\mathcal{S}}\mathbf{A}_{i,j}x_{i}x_{j}\\\
&=\sqrt{\eta^{2}n/5\epsilon}\sum_{i,j\in\mathcal{S}}x_{i}x_{j}+\sum_{i\notin\mathcal{S}}x_{i}^{2}\\\
&=\sqrt{\eta^{2}n/5\epsilon}\left(\sum_{i\in\mathcal{S}}x_{i}\right)^{2}+\sum_{i\notin\mathcal{S}}x_{i}^{2}\\\
&\geq 0\end{split}$ (5.1)

and thus $\mathbf{A}$ is PSD. Further,
$\|\mathbf{A}\|^{2}_{F}=(25\epsilon^{2}/\eta^{2})\cdot(n\eta^{2}/5\epsilon)+(n-5\epsilon/\eta)=(1+5\epsilon)n-5\epsilon/\eta$.
Then,
$\|\mathbf{N}\|^{2}_{F}=5\epsilon/\eta\cdot\eta^{2}n/\epsilon=\eta\|\mathbf{A}\|^{2}_{F}$,
as desired. Intuitively, we show that if $\mathbf{B}$ is a rank-$k$ matrix
that is a good low-rank approximation for $\mathbf{M}$ sampled from $\mu$,
then it cannot be a good low-rank approximation for $\mathbf{I}$. To this end,
we consider a distribution where $\mathbf{M}$ is drawn from
$\mu(n,\epsilon,\eta)$ with probability $1/2$ and is $\mathbf{I}_{n\times n}$
with probability $1/2$.

######  Definition 5.2.

(Hard Distribution) Given $n\in\mathbb{N},\epsilon>\eta>0$, let
$\nu(n,\epsilon,\eta)$ be a distribution over
$\mathbf{M}\in\mathbb{R}^{n\times n}$ such that with probability $1/2$,
$\mathbf{M}$ is sampled from $\mu(n,\epsilon,\eta)$ and with probability
$1/2$, $\mathbf{M}=\mathbf{I}_{n\times n}$.

We now show that a low-rank approximation to $\mathbf{M}$ can be used as a
certificate to separate the mixture $\nu(n,\epsilon,\eta)$ since it can
distinguish between the input being identity or far from it. Thus if the
distributions are close in a statistical sense, any algorithm to distinguish
between the two would require querying many entries in $\mathbf{M}$. Formally,

######  Lemma 5.3.

(LRA as a Distinguisher.) Let $\mathbf{M}$ be a matrix drawn from
$\mu(n,\epsilon,\eta)$ and let $\mathbf{B}$ be a rank-$k$ matrix that is the
candidate low-rank approximation to $\mathbf{M}$ such that
$\|\mathbf{M}-\mathbf{B}\|^{2}_{F}\leq\epsilon n$. Then,
$\|\mathbf{M}-\mathbf{I}\|^{2}_{F}>1.1\epsilon n$.

###### Proof.

Since $\|\mathbf{M}-\mathbf{B}\|^{2}_{F}\leq\epsilon n$, $\mathbf{B}$ must
have at least $4\epsilon n$ mass on the off-diagonal entries of $\mathbf{M}$.
So, $\mathbf{B}$ must have at least $10\epsilon^{2}/\eta^{2}$ non-zero off-
diagonal entries. Therefore, it must have at least $5\epsilon^{2}/\eta^{2}$
entries with squared mass $\epsilon n/2$. To see why, assume there is a subset
of at least $12\epsilon^{2}/\eta^{2}$ entries, each being at most
$\sqrt{n\eta^{2}/10\epsilon}$. Restricted to only these entries, the squared
Frobenius norm difference between $\mathbf{M}$ and $\mathbf{B}$ is already at
least $1.2\epsilon n$, contradicting our assumption. Given that there exists a
subset of $5\epsilon^{2}/\eta^{2}$ off-diagonal entries having squared mass
$1.2\epsilon n$, $\|\mathbf{B}-\mathbf{I}\|^{2}_{F}>1.2\epsilon n$, and thus
$\mathbf{B}$ is not an additive error low-rank approximation for $\mathbf{I}$.
∎

######  Theorem 5.4.

(Lower bound for PSD Matrices.) Let $\mathbf{A}$ be a PSD matrix,
$k\in\mathbb{Z}$ and $\epsilon>0$ be any constant. Let $\mathbf{N}$ be an
arbitrary matrix such that
$\|\mathbf{N}\|^{2}_{F}\leq\eta\|\mathbf{A}\|^{2}_{F}$. Any randomized
algorithm $\mathcal{A}$ that only has query access to $\mathbf{A}+\mathbf{N}$,
with probability at least $2/3$, computes a rank-$k$ matrix $\mathbf{B}$ such
that

$\|\mathbf{A}-\mathbf{B}\|^{2}_{F}\leq\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}+\epsilon\|\mathbf{A}\|^{2}_{F}$

must read $\Omega\left(\phi_{\max}^{2}nk/\epsilon\right)$ entries of
$\mathbf{A}+\mathbf{N}$ on some input, possibly adaptively, in expectation.

###### Proof.

Let Algorithm $\mathcal{A}$ be a deterministic algorithm that outputs a
rank-$k$ matrix $\mathbf{B}$ such that it is an additive-error low-rank
approximation $\mathbf{M}$. Let $T\subset[n^{2}]$ be the subset of entries
read by $\mathcal{A}$. Let $L(\mu)$ denote the distribution of $T$ conditioned
on $\mathbf{M}\sim\mu(n,\epsilon,\eta)$ and $L(i)$ be the distribution of $T$
conditioned on $\mathbf{M}=\mathbf{I}$. By Lemma 5.3, since the output of
$\mathcal{A}$ can be used to distinguish between the two distributions, it is
well-known that the success probability over the randomness in $T$ is at most
$1/2+D_{TV}(L(\mu),L(i))/2$ [BY02]. Since we assume $\mathcal{A}$ succeeds
with probability at least $2/3$,

$D_{TV}(L(\mu),L(i))\geq 1/3$ (5.2)

It remains to upper bound $D_{TV}$ in terms of $|T|$. Recall, $\mathcal{S}$ is
the random set of indices where $\mu(n,\epsilon,\eta)$ is non-zero. Let
$\widehat{\mathcal{S}}$ be the subset of $\mathcal{S}$ restricted to the off-
diagonal entries of $\mathbf{M}$. When $\mathbf{M}\sim\mu(n,\epsilon,\eta)$,
$\forall i,j\in\widetilde{\mathcal{S}}$, $\mathbf{M}_{i,j}$ is non-zero and
when $\mathbf{M}=\mathbf{I}$, the same entries are $0$. Observe, for all
$i,j\notin\widetilde{\mathcal{S}}$, $\mathbf{M}_{i,j}$ are fixed. Further,
$\mathcal{S}$ is a uniform subset of $[n]$. Therefore,

$\Pr\left[(i,j)\in
T\mid(i,j)\in\mathcal{S}\right]=\frac{|T|\epsilon^{2}}{\eta^{2}n^{2}}$ (5.3)

Then, with probability at least $1-|T|\epsilon^{2}/\eta^{2}n^{2}$,
$\mathcal{A}$ queries the same entries for both $L(\mu)$ and $L(i)$. Therefore

$D_{TV}(L(\mu),L(i))\leq|T|\epsilon^{2}/\eta^{2}n^{2}.$

Combined with Equation 5.2, if $\mathcal{A}$ succeeds with probability at
least $2/3$, $|T|\epsilon^{2}/\eta^{2}n^{2}\geq 1/3$ and thus
$|T|=\Omega(\eta^{2}n^{2}/\epsilon^{2})$. Given that any deterministic
algorithm must query
$\Omega(\eta^{2}n^{2}/\epsilon^{2})=\Omega(\phi_{\max}^{2}n/\epsilon)$ entries
for $\nu(n,\epsilon,\eta)$, to now obtain a linear dependence on the rank $k$,
we can use the standard approach of creating $k$ disjoint copies of the block
$\mathbf{B}_{1}$ in the hard distribution, as shown in [MW17]. The theorem
follows from Yao’s minimax principle. ∎

###  5.2 Robust Sublinear Low-Rank Approximation Algorithms

In this subsection, we provide a robust algorithm for the model discussed
above. We parameterize our algorithms and lower bound by the largest ratio
between a diagonal entry of $\mathbf{A}$ and $\mathbf{A}+\mathbf{N}$, denoted
by
$\phi_{\max}=\max_{j\in[n]}\mathbf{A}_{j,j}/|(\mathbf{A}+\mathbf{N})_{j,j}|$.
In addition, we provide robust PCP constructions, by introducing a new
sampling procedure to construct projection-cost preserving sketches. Our
sampling procedure is straightforward: we sample each column proportional to
the diagonal entry in that column. This sampling requires $n$ queries to the
matrix $\mathbf{A}$ to obtain an additive-error projection cost preservation
guarantee. Further, for the special case of correlation matrices, we can
uniformly sample columns of $\mathbf{A}$ to obtain a smaller matrix such that
all rank $k$ projections in the column and row space are preserved.

For our algorithms, we assume we know $\phi_{\max}$. In practice, this
assumption may not hold, but we can query as many entries in
$\mathbf{A}+\mathbf{N}$ as our budget allows, given that correctness holds
only when the queries are at least
$\widetilde{O}(\phi^{2}_{\max}nk/\epsilon)$. Since we read the diagonals of
$\mathbf{A}+\mathbf{N}$ and we know $\phi_{\max}$, we can obtain an upper
bound on $\mathbf{A}_{i,i}$ and $\mathbf{A}_{j,j}$. Therefore, whenever we
query an off-diagonal entry in $\mathbf{A}+\mathbf{N}$, we can truncate it to
$\phi_{\max}\sqrt{|(\mathbf{A}+\mathbf{N})_{i,i}|\cdot|(\mathbf{A}+\mathbf{N})_{j,j}|}$
without increasing the corruption in our input.

Robust Projection-Cost Preserving Sketches. Here, we show that diagonal
sampling is a robust sampling procedure to create projection-cost preserving
sketches. We begin by relating the $\ell^{2}_{2}$ row (or column) norms of a
PSD matrix to it’s spectral norm. Let $\mathbf{A}$ be a PSD matrix and let
$\mathbf{U}\mathbf{\Sigma}\mathbf{U}^{T}$ be the SVD for $\mathbf{A}$.

######  Lemma 5.5.

Given an $n\times n$ PSD matrix $\mathbf{A}$, for all $i\in[n]$,
$\|\mathbf{A}_{i,*}\|^{2}_{2}\leq\|\mathbf{A}\|_{2}\cdot\mathbf{A}_{i,i}$.

###### Proof.

Observe, $\mathbf{A}_{i,*}=\mathbf{U}_{i}\mathbf{\Sigma}\mathbf{U}^{T}$ and
$\mathbf{A}_{i,i}=(\mathbf{U}_{i,*}\mathbf{\Sigma}\mathbf{U}^{T})_{i}=\sum^{n}_{j=1}\sigma_{j}(\mathbf{A})\mathbf{U}^{2}_{i,j}$.
Then,

$\begin{split}\|\mathbf{A}_{i,*}\|^{2}_{2}=\mathbf{A}_{i,*}\mathbf{A}^{T}_{i,*}=\mathbf{U}_{i,*}\mathbf{\Sigma}\mathbf{U}^{T}\mathbf{U}\mathbf{\Sigma}\mathbf{U}_{i,*}^{T}&=\sum_{j=1}^{n}\sigma^{2}_{j}(\mathbf{A})\mathbf{U}_{i,j}^{2}\\\
&\leq\|\mathbf{A}\|_{2}\sum_{j=1}^{n}\sigma_{j}\mathbf{U}_{i,j}^{2}\\\
&=\|\mathbf{A}\|_{2}\cdot\mathbf{A}_{i,i}\end{split}$

∎

An immediate consequence of Lemma 5.5 is that the $\ell^{2}_{2}$ norm of a row
or column of a PSD matrix is at most
$\frac{\|\mathbf{A}\|_{F}}{\mathbf{A}_{i,i}}$. Note, this precludes matrices
where most of the mass in concentrated on a small number of rows or columns.
Recall, we observe as input the matrix $\mathbf{A}+\mathbf{N}$ and our goal is
to obtain a PCP for this in sublinear time and queries.

Musco and Musco [MM17] describe how to approximately compute the ridge
leverage scores of $\mathbf{A}^{\frac{1}{2}}$ (if $\mathbf{A}$ is PSD) using a
Nystrom approximation. [MW17] use this method to compute the ridge leverage
scores of $\mathbf{A}^{\frac{1}{2}}$ with $O(nk)$ queries, where
$\mathbf{A}=\mathbf{A}^{\frac{1}{2}}\cdot\mathbf{A}^{\frac{1}{2}}$. However,
these approaches do not apply when we perturb the input and it may no longer
be PSD. Therefore, the best known construction by Cohen et. al. [CMM17] would
require $\Omega(nnz(\mathbf{A}))$ time to compute approximate ridge-leverage
scores of $\mathbf{A}$. Note, this does not use the structure that
$\mathbf{A}$ has.

In contrast, we show that sampling columns proporitional to the diagonal
entries suffices to obtain a PCP. Note, we only need to query the diagonal of
$\mathbf{A}$ to compute the distribution over columns exactly. The main
technical challenge here is to obtain the correct dependence on $n$ and $k$
and account for the perturbation to the input, given that our sampling
probabilities are straightforward to compute and do not rely on spectral
properties of $\mathbf{A}+\mathbf{N}$. Note, the following is a structural
result and while we do not know $\mathbf{A}$, we can still show the following
:

######  Theorem 5.6.

(Robust Spectral Bound.) Let $\mathbf{A}$ be an $n\times n$ PSD matrix and
$\mathbf{N}$ be an arbitrary matrix such that
$\|\mathbf{N}\|^{2}_{F}\leq\eta\|\mathbf{A}\|^{2}_{F}$ and for all $j\in[n]$,
$\|\mathbf{N}_{*,j}\|^{2}_{2}\leq c\|\mathbf{A}_{*,j}\|^{2}_{2}$, for any
fixed constant $c$. Let
$\phi_{\max}=\max_{j}\mathbf{A}_{j,j}/(\mathbf{A}+\mathbf{N})_{j,j}$ and let
$q=\\{q_{1},q_{2}\ldots q_{n}\\}$ be a distribution over the columns of
$\mathbf{A}+\mathbf{N}$ such that for all $j$,
$q_{j}=(\mathbf{A}+\mathbf{N})_{j,j}/\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)$
and let $t=O\left(\phi_{\max}\sqrt{n}k^{2}\log(n/\delta)/\epsilon^{2}\right)$.
Then, construct a sampling matrix $\mathbf{T}$ that samples $t$ columns of
$\mathbf{A}+\mathbf{N}$ such that it samples
column$(\mathbf{A}+\mathbf{N})_{*,j}$ with probability $q_{j}$ and scales it
by $1/\sqrt{tq_{j}}$. With probability at least $1-\delta$, for any rank-$k$
orthogonal projection $\mathbf{X}$,

$\mathbf{A}\mathbf{A}^{T}-\left(\frac{\epsilon}{k}\right)\|\mathbf{A}\|^{2}_{F}\mathbf{I}\preceq\mathbf{A}\mathbf{T}(\mathbf{A}\mathbf{T})^{T}\preceq\mathbf{A}\mathbf{A}^{T}+\left(\frac{\epsilon}{k}\right)\|\mathbf{A}\|^{2}_{F}\mathbf{I}$

###### Proof.

First, we note that we cannot explicitly compute $\mathbf{A}\mathbf{T}$, but
we can show that the sampling probabilities we have access to result in a PCP
for $\mathbf{A}$. Let
$\mathbf{Y}=\mathbf{A}\mathbf{T}(\mathbf{A}\mathbf{T})^{T}-\mathbf{A}\mathbf{A}^{T}$.
For notational convenience let $\mathbf{A}_{j}=\mathbf{A}_{*,j}$. We can then
write
$\mathbf{Y}=\sum_{j\in[t]}\left(\mathbf{C}_{*,j}\mathbf{C}_{*,j}^{T}-\frac{1}{t}\mathbf{A}\mathbf{A}^{T}\right)=\sum_{j\in[t]}\mathbf{X}_{j}$,
where
$\mathbf{X}_{j}=\frac{1}{t}(\frac{1}{q_{j}}\mathbf{A}_{j}\mathbf{A}^{T}_{j}-\mathbf{A}\mathbf{A}^{T})$
with probability $q_{j}$. We observe that
${\bf\mathbb{E}}[\mathbf{X}_{j}]={\bf\mathbb{E}}[\mathbf{C}_{*,j}\mathbf{C}_{*,j}^{T}-\frac{1}{t}\mathbf{A}\mathbf{A}^{T}]=0$,
and therefore, ${\bf\mathbb{E}}[\mathbf{Y}]=0$. Next, we bound the operator
norm of $\mathbf{Y}$. To this end, we use the Matrix Bernstein inequality,
which in turn requires a bound on the operator norm of $\mathbf{X}_{j}$ and
variance of $\mathbf{Y}$. Recall,

$\begin{split}\|\mathbf{X}_{j}\|_{2}&=\left\|\frac{1}{tq_{j}}\mathbf{A}_{j}\mathbf{A}_{j}-\frac{1}{t}\mathbf{A}\mathbf{A}^{T}\right\|_{2}\\\
&\leq\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}{t(\mathbf{A}+\mathbf{N})_{j,j}}\|\mathbf{A}_{j}\|^{2}_{2}+\frac{1}{t}\|\mathbf{A}\|^{2}_{2}\\\
&\leq\frac{2\mathrm{Tr}\left(\mathbf{A}\right)+|\mathrm{Tr}\left(\mathbf{N}\right)|}{t(\mathbf{A}+\mathbf{N})_{j,j}}\left((1+\eta)\|\mathbf{A}\|_{2}\mathbf{A}_{j,j}\right)\\\
&\leq\frac{c(\mathrm{Tr}\left(\mathbf{A}\right)+|\mathrm{Tr}\left(\mathbf{N}\right)|)\|\mathbf{A}\|_{2}\phi_{\max}}{t}\\\
&\leq\frac{c\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2}}{t}\end{split}$
(5.4)

where we use triangle inequality for operator norm to obtain the first
inequality, triangle inequality up to a factor of $2$ for $\ell^{2}_{2}$ norms
for the second inequality,
$\|\mathbf{N}_{j}\|^{2}_{2}\leq\eta\|\mathbf{A}_{*,j}\|^{2}_{2}$ and
$\|\mathbf{A}_{j}\|^{2}_{2}\leq\|\mathbf{A}\|_{2}\cdot\mathbf{A}_{j,j}$ (from
Lemma 5.5) for the third inequality and definition of $\phi_{\max}$ and
$\eta=O(1)$ for the fourth. Finally, we relate the trace of $\mathbf{A}$ and
$\mathbf{N}$ to their respective Frobenius norm using Cauchy-Schwarz:

$\begin{split}\mathrm{Tr}\left(\mathbf{A}\right)=\sum^{n}_{i=1}\sigma_{i}(\mathbf{A})\leq\sqrt{\sum^{n}_{i=1}\sigma_{i}^{2}(\mathbf{A})\cdot
n}=\sqrt{n\|\mathbf{A}\|^{2}_{F}}\end{split}$

and

$\begin{split}|\mathrm{Tr}\left(\mathbf{N}\right)|=\left|\sum^{n}_{i=1}\sigma_{i}(\mathbf{A})\right|\leq\sqrt{\sum^{n}_{i=1}\sigma_{i}^{2}(\mathbf{N})\cdot
n}=\sqrt{n\|\mathbf{N}\|^{2}_{F}}\leq\sqrt{n\eta}\|\mathbf{A}\|_{F}\end{split}$

where the last inequality follows from
$\|\mathbf{N}\|_{F}\leq\sqrt{\eta}\|\mathbf{A}\|_{F}$. Next, we bound
$\mbox{\bf Var}[\mathbf{Y}]\leq{\bf\mathbb{E}}\left[\mathbf{Y}^{2}\right]$.

$\begin{split}{\bf\mathbb{E}}\left[\mathbf{Y}^{2}\right]&=t{\bf\mathbb{E}}\left[\left((\mathbf{A}\mathbf{T})_{*,j}(\mathbf{A}\mathbf{T})_{*,j}^{T}-\frac{1}{t}\mathbf{A}\mathbf{A}^{T}\right)^{2}\right]\\\
&=t{\bf\mathbb{E}}\left[\left((\mathbf{A}\mathbf{T})_{*,j}(\mathbf{A}\mathbf{T})_{*,j}^{T}\right)^{2}+\frac{1}{t^{2}}\left(\mathbf{A}\mathbf{A}^{T}\right)^{2}-\frac{2}{t}(\mathbf{A}\mathbf{T})_{*,j}(\mathbf{A}\mathbf{T})_{*,j}^{T}\mathbf{A}\mathbf{A}^{T}\right]\\\
&=\frac{1}{t}\left(\sum_{j\in[n]}\frac{(\mathbf{A}_{j}\mathbf{A}^{T}_{j})^{2}}{q_{j}}+(\mathbf{A}\mathbf{A}^{T})^{2}-\sum_{j\in[n]}2\mathbf{A}_{j}\mathbf{A}^{T}_{j}\mathbf{A}\mathbf{A}^{T}\right)\\\
&\preceq\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}{t\mathbf{A}_{j,j}}\left(\sum_{j\in[n]}(\mathbf{A}_{j}\mathbf{A}^{T}_{j})^{2}\right)\\\
&\preceq\frac{c\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2}}{t}\mathbf{A}\mathbf{A}^{T}\\\
\end{split}$ (5.5)

where we use linearity of expectation, $(\mathbf{A}\mathbf{A}^{T})^{2}\succeq
0$ and
$\|\mathbf{A}_{j,*}\|^{2}_{2}\leq\|\mathbf{A}\|_{2}\cdot\mathbf{A}_{j,j}$.
Applying the Matrix Bernstein inequality,

$\begin{split}\mbox{\bf
Pr}\left[\|\mathbf{Y}\|_{2}\geq\epsilon\|\mathbf{A}\|^{2}_{F}\right]&\leq
2n\exp{\left(-\frac{\epsilon^{2}\|\mathbf{A}\|^{4}_{F}}{\frac{c\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|^{3}_{2}}{t}+\frac{2\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2}\left(\epsilon\|\mathbf{A}\|^{2}_{F}\right)}{3t}}\right)}\\\
&\leq
2n\exp{\left(-\frac{\epsilon^{2}t}{c\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2}}\left(\frac{\|\mathbf{A}\|^{4}_{F}}{\|\mathbf{A}\|^{2}_{2}+\epsilon\|\mathbf{A}\|^{2}_{F}}\right)\right)}\\\
&\leq
2n\exp{\left(-\frac{\epsilon^{2}t}{c^{\prime}\phi_{\max}\sqrt{n}}\right)}\\\
&\leq\delta/2\end{split}$

where the last inequality follows from setting
$t=O(\phi_{\max}\sqrt{n}\log(n/\delta)/\epsilon^{2})$. To yield the claim, we
set $\epsilon=\epsilon/k$. ∎

We use the above spectral bound to show that sampling proportional to diagonal
entries preserves the projection cost of the columns of $\mathbf{A}$ on to any
$k$-dimensional subspace up to an additive
$(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$.

######  Theorem 5.7.

(Column Projection-Cost Preservation.) Given $\mathbf{A}+\mathbf{N}$, where
$\mathbf{A}$ is an $n\times n$ PSD matrix and $\mathbf{N}$ is an arbitrary
noise matrix as defined above, $k\in\mathbb{Z}$ and $\epsilon>\eta>0$, let
$q=\\{q_{1},q_{2}\ldots q_{n}\\}$ be a probability distribution over the
columns of $\mathbf{A}+\mathbf{N}$ such that
$q_{j}=\frac{(\mathbf{A}+\mathbf{N})_{j,j}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Let
$t=O\left(\phi_{\max}\sqrt{n}k^{2}\log(\frac{n}{\delta})/\epsilon^{2}\right)$.
Then, construct $\mathbf{C}$ using $t$ columns of $\mathbf{A}+\mathbf{N}$ and
set each one to $\frac{(\mathbf{A}+\mathbf{N})_{*,j}}{\sqrt{tq_{j}}}$ with
probability $q_{j}$. With probability at least $1-c$, for any rank-$k$
orthogonal projection $\mathbf{X}$,

$\|\mathbf{C}-\mathbf{X}\mathbf{C}\|^{2}_{F}=\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{F}\pm(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$

for a fixed constant $c$.

###### Proof.

Here, the matrix $\mathbf{C}$ is actually a matrix we can compute. Observe
that we can relate $\mathbf{C}$ to the sampling matrix $\mathbf{T}$ as defined
in Theorem 5.6 as $\mathbf{C}=(\mathbf{A}+\mathbf{N})\mathbf{T}$. We follow
the proof strategy of the relative error guarantees in [CMM17] and additive
error guarantees in [BW18] but note, our spectral bounds from Theorem 5.6
apply to matrices that we do not actually compute. Observe,
$\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{F}=\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{A}\mathbf{A}^{T}(\mathbb{I}-\mathbf{X})\right)$.
Then,

$\begin{split}\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{A}\mathbf{A}^{T}(\mathbb{I}-\mathbf{X})\right)&=\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)+\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\right)\\\
&=\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)+\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\mathbf{X}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{X}\mathbf{A}\mathbf{A}^{T}\right)\\\
&=\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)+\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)\\\
&=\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)\end{split}$
(5.6)

where we used the fact that for any projection matrix
$\mathbf{X}=\mathbf{X}^{2}$ in addition to the cyclic property of the trace.
Similarly,

$\begin{split}\|\mathbf{C}-\mathbf{X}\mathbf{C}\|^{2}_{F}=\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{C}\mathbf{C}^{T}(\mathbb{I}-\mathbf{X})\right)&=\mathrm{Tr}\left(\mathbf{C}\mathbf{C}^{T}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{C}\mathbf{C}^{T}\mathbf{X}\right)\end{split}$
(5.7)

We first relate $\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)$ and
$\mathrm{Tr}\left(\mathbf{C}\mathbf{C}^{T}\right)$. Recall,

${\bf\mathbb{E}}\left[\mathrm{Tr}\left(\mathbf{C}\mathbf{C}^{T}\right)\right]={\bf\mathbb{E}}\left[\|\mathbf{C}\|^{2}_{F}\right]=\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\leq\mathrm{Tr}\left(\mathbf{A}\mathbf{A}^{T}\right)+2\sqrt{\eta}\|\mathbf{A}\|^{2}_{F}$

Using a scalar Chernoff bound, we show that with probability at least
$1-1/\textrm{poly}(n)$,
$\|\mathbf{C}\|^{2}_{F}=(1\pm\epsilon)\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$. This
is equivalent to
$|\|\mathbf{C}\|^{2}_{F}-\|\mathbf{A}+\mathbf{N}\|^{2}_{F}|\leq\epsilon\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$.
Observe, for all $j\in[t]$,
$\mathbf{C}_{*,j}=\frac{1}{\sqrt{q_{j^{\prime}}t}}(\mathbf{A}+\mathbf{N})_{*,j^{\prime}}$
for some $j^{\prime}\in[n]$. Then,

$\begin{split}\|\mathbf{C}_{*,j}\|^{2}_{2}=\frac{1}{q_{j^{\prime}}t}\|(\mathbf{A}+\mathbf{N})_{*,j^{\prime}}\|^{2}_{2}&=\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)\epsilon^{2}}{\phi_{\max}\sqrt{n}k\log(n/\delta)(\mathbf{A}+\mathbf{N})_{j^{\prime},j^{\prime}}}\|(\mathbf{A}+\mathbf{N})_{*,j^{\prime}}\|^{2}_{2}\\\
&\leq\frac{c\sqrt{n}\|\mathbf{A}\|_{F}\epsilon^{2}}{\sqrt{n}\log(n/\delta)}\|\mathbf{A}\|_{2}\\\
&\leq\frac{c\epsilon^{2}}{k\log(n/\delta)}\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\end{split}$
(5.8)

where we use
$\mathrm{Tr}\left(\mathbf{A}\right)\leq\sqrt{n}\|\mathbf{A}\|_{F}$,
$\mathrm{Tr}\left(\mathbf{N}\right)\leq\sqrt{\eta n}\|\mathbf{A}\|_{F}$ and
$t=O(\phi_{\max}\sqrt{n}k\log(n/\delta)/\epsilon^{2})$. Therefore,
$\frac{k\log(n/\delta)}{\epsilon^{2}\|\mathbf{A}\|^{2}_{F}}\|\mathbf{C}_{*,j}\|^{2}_{2}\in[0,1]$.
By a Chernoff bound,

$\begin{split}\mbox{\bf
Pr}\left[\|\mathbf{C}\|^{2}_{F}\geq(1+2\epsilon)\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\right]&=\mbox{\bf
Pr}\left[\frac{k\log(n/\delta)}{\epsilon^{2}\|\mathbf{A}+\mathbf{N}\|^{2}_{F}}\|\mathbf{C}\|^{2}_{F}\geq\frac{k\log(n/\delta)}{\epsilon^{2}}(1+\epsilon)\right]\\\
&\leq\exp\left(-\frac{k\epsilon^{2}\log(n/\delta)}{\epsilon^{2}}\right)\\\
&\leq\frac{\delta}{2}\end{split}$ (5.9)

We can repeat the above argument to lower bound $\|\mathbf{C}\|^{2}_{F}$.
Therefore, with probability $1-\delta$, we have

$|\|\mathbf{C}\|^{2}_{F}-\|\mathbf{A}+\mathbf{N}\|^{2}_{F}|\leq\epsilon\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$

Here, we can upper bound this by observing
$\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\leq\|\|^{2}_{F}+\|\mathbf{N}\|^{2}_{F}+2\langle\mathbf{A},\mathbf{N}\rangle\leq\|\mathbf{A}\|^{2}_{F}+3\sqrt{\eta}\|\mathbf{A}\|^{2}_{F}$.
Therefore,

$|\|\mathbf{C}\|^{2}_{F}-\|\mathbf{A}\|^{2}_{F}|\leq\epsilon\|\mathbf{A}\|^{2}_{F}+(1+\epsilon)\sqrt{\eta}\|\mathbf{A}\|^{2}_{F}\leq(\epsilon+2\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$
(5.10)

Next, we relate
$\mathrm{Tr}\left(\mathbf{X}\mathbf{C}\mathbf{C}^{T}\mathbf{X}\right)$ and
$\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)$. First,
we observe

$\mathbf{C}\mathbf{C}^{T}=(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})^{T}=(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}+(\mathbf{A}\mathbf{T})(\mathbf{N}\mathbf{T})^{T}+(\mathbf{N}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}+(\mathbf{N}\mathbf{T})(\mathbf{N}\mathbf{T})^{T}$
(5.11)

We begin by first bounding
$\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{X}\right)$.
Observe, $\mathbf{X}$ is a rank $k$ projection matrix and we can represent it
as $\mathbf{Z}\mathbf{Z}^{T}$, where $\mathbf{Z}\in\mathbb{R}^{n\times k}$ and
has orthonormal columns. By the cyclic property of the trace, we have

$\mathrm{Tr}\left(\mathbf{Z}\mathbf{Z}^{T}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{Z}\mathbf{Z}^{T}\right)=\mathrm{Tr}\left(\mathbf{Z}^{T}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{Z}\right)=\sum_{j\in[k]}\mathbf{Z}^{T}_{*,j}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{Z}_{*,j}$

Similarly,
$\mathrm{Tr}\left(\mathbf{Z}\mathbf{Z}^{T}\mathbf{A}\mathbf{A}^{T}\mathbf{Z}\mathbf{Z}^{T}\right)=\sum_{j\in[k]}\mathbf{Z}^{T}_{*,j}\mathbf{A}\mathbf{A}^{T}\mathbf{Z}_{*,j}$.
By Theorem 5.6 , we have

$\begin{split}\sum_{j\in[k]}\left(\mathbf{Z}^{T}_{*,j}\mathbf{A}\mathbf{A}^{T}\mathbf{Z}_{*,j}-\left(\frac{\epsilon}{k}\right)\|\mathbf{A}\|_{F}^{2}\mathbf{Z}^{T}_{*,j}\mathbf{I}\mathbf{Z}_{*,j}\right)&\leq\sum_{j\in[k]}\left(\mathbf{Z}^{T}_{*,j}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{Z}_{*,j}\right)\\\
&\leq\sum_{j\in[k]}\left(\mathbf{Z}^{T}_{*,j}\mathbf{A}\mathbf{A}^{T}\mathbf{Z}_{*,j}+\left(\frac{\epsilon}{k}\right)\|\mathbf{A}\|_{F}^{2}\mathbf{Z}^{T}_{*,j}\mathbf{I}\mathbf{Z}_{*,j}\right)\end{split}$
(5.12)

Since $\mathbf{Z}^{T}_{*,j}\mathbf{Z}_{*,j}=1$ and
$\mathrm{Tr}\left(\mathbf{Z}^{T}\mathbf{A}\mathbf{A}^{T}\mathbf{Z}\right)=\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)$,
we have

$\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)-\epsilon\|\mathbf{A}\|_{F}^{2}\leq\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})(\mathbf{A}\mathbf{T})^{T}\mathbf{X}\right)\leq\mathrm{Tr}\left(\mathbf{X}\mathbf{A}\mathbf{A}^{T}\mathbf{X}\right)+\epsilon\|\mathbf{A}\|_{F}^{2}$
(5.13)

Next, we focus on
$\mathrm{Tr}\left(\mathbf{X}(\mathbf{N}\mathbf{T})(\mathbf{N}\mathbf{T})^{T}\mathbf{X}\right)=\|\mathbf{X}\mathbf{N}\mathbf{T}\|^{2}_{F}$.
Observe, since $\mathbf{T}$ is an unbiased estimator of Frobenius norm, by
Markov’s inequality we can show with probability at least $1-c$,
$\|\mathbf{X}\mathbf{N}\mathbf{T}\|_{F}=c\|\mathbf{N}\|_{F}=O(\sqrt{\eta})\|\mathbf{A}\|_{F}$.
Therefore, we can upper bound
$\mathrm{Tr}\left(\mathbf{X}(\mathbf{N}\mathbf{T})(\mathbf{N}\mathbf{T})^{T}\mathbf{X}\right)$
by $O(\eta)\|\mathbf{A}\|^{2}_{F}$. Now, we focus on the cross terms. By
Cauchy-Schwartz, and a Markov bound, with probability at least $1-c$,

$\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})(\mathbf{N}\mathbf{T})^{T}\mathbf{X}\right)\leq\|\mathbf{A}\mathbf{T}\|_{F}\cdot\|\mathbf{N}\mathbf{T}\|_{F}\leq
O(\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$ (5.14)

Combining equations 5.10, 5.13, 5.14 and union bounding over the success of
the random events, with probability $1-c$,

$\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{F}-O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}\leq\|\mathbf{C}-\mathbf{X}\mathbf{C}\|^{2}_{F}\leq\|\mathbf{A}-\mathbf{X}\mathbf{A}\|^{2}_{F}+O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$

∎

Robust Row Projection Cost Preserving Sketches. We now extend the diagonal
sampling algorithm to construct a row projection cost preserving sketch for
the matrix $\mathbf{C}$. We note that following the construction for
$\mathbf{A}$ does not immediately give a row PCP for $\mathbf{C}$ since
$\mathbf{C}$ is no longer PSD or even square matrix. Here, all previous
approaches to construct a PCP with sublinear queries hit a roadblock, since
the matrix $\mathbf{C}$ need not have any well defined structure apart from
being a scaled subset of the columns of a PSD matrix. However, we show that
sampling rows of $\mathbf{C}$ proportional to the diagonal entries of
$\mathbf{A}$ results in a row PCP.

We begin by relating the row norms of $\mathbf{C}$ to the row norms of
$\mathbf{A}$. Note, we do not expect to obtain concentration here, since such
a sampling procedure would then help us estimate row norms of $\mathbf{A}$ up
to a constant and we would be done by using [FKV04]. Therefore, we obtain the
following one-sided guarantee:

######  Lemma 5.8.

Let $\mathbf{A}\mathbf{T}\in\mathbb{R}^{n\times t}$ be a column projection-
cost preserving sketch for $\mathbf{A}$ as described in Theorem 5.6. For all
$i\in[n]$, with probability at least $1-1/n^{c}$,

$\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}\leq
O\left(\log(n)\max\left\\{\|\mathbf{A}_{i,*}\|^{2}_{2},\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right\\}\right)$

where $c$ is a fixed constant.

###### Proof.

Observe that
$\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}=\sum_{j\in[t]}(\mathbf{A}\mathbf{T})_{i,j}^{2}$,
where
$(\mathbf{A}\mathbf{T})_{i,j}^{2}=\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}{t(\mathbf{A}+\mathbf{N})_{j,j}}\mathbf{A}_{i,j}^{2}$
with probability
$\frac{(\mathbf{A}+\mathbf{N})_{j,j}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Then,
${\bf\mathbb{E}}[\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}]=\sum^{n}_{i=1}\mathbf{A}^{2}_{i,j}=\|\mathbf{A}_{i,*}\|^{2}_{2}$.
Next, we compute the variance of $\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}$.
$\mbox{\bf
Var}\left[\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}\right]=t\mbox{\bf
Var}\left[(\mathbf{A}\mathbf{T})^{2}_{i,j}\right]\leq{\bf\mathbb{E}}\left[(\mathbf{A}\mathbf{T})^{4}_{i,j}\right]$.
Then,

$\begin{split}t{\bf\mathbb{E}}\left[(\mathbf{A}\mathbf{T})^{4}_{i,j}\right]=\sum_{j\in[n]}\frac{1}{tq_{j}}\mathbf{A}_{i,j}^{4}&\leq\sum_{j\in[n]}\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}{t(\mathbf{A}+\mathbf{N})_{j,j}}\mathbf{A}_{i,j}^{2}\mathbf{A}_{i,i}\mathbf{A}_{j,j}\\\
&\leq\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)\phi_{\max}\mathbf{A}_{i,i}}{t}\|\mathbf{A}_{i,*}\|^{2}_{2}\\\
&\leq\left(\frac{2\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}+\|\mathbf{A}_{i,*}\|^{4}_{2}\hskip
28.90755pt\textrm{ [AM-GM]}\\\ \end{split}$

where we use $\mathbf{A}^{2}_{i,j}\leq\mathbf{A}_{i,i}\mathbf{A}_{j,j}$, which
follows from applying Cauchy-Schwarz to
$\langle\mathbf{A}^{1/2}_{i,*},\mathbf{A}^{1/2}_{j,*}\rangle$, i.e.,

$\mathbf{A}^{2}_{i,j}=\langle\mathbf{A}^{1/2}_{i,*},\mathbf{A}^{1/2}_{j,*}\rangle^{2}\leq\|\mathbf{A}^{1/2}_{i,*}\|^{2}_{2}\|\mathbf{A}^{1/2}_{j,*}\|^{2}_{2}=\mathbf{A}_{i,i}\mathbf{A}_{j,j}$

Similarly, we bound

$(\mathbf{A}\mathbf{T})^{2}_{i,j}=\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}{t(\mathbf{A}+\mathbf{N})_{j,j}}\mathbf{A}^{2}_{i,j}\leq\frac{2\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}}{t}\mathbf{A}_{i,i}$

Applying Bernstein’s inequality,

$\begin{split}&\mbox{\bf
Pr}\left[|\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}-\|\mathbf{A}_{i,*}\|^{2}_{2}\geq\gamma\max\left\\{\|\mathbf{A}_{i,*}\|^{2}_{2},\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right\\}\right]\\\
&\leq
2\exp\left(-\frac{\gamma^{2}\max\left\\{\|\mathbf{A}_{i,*}\|^{4}_{2},\left(\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}\right\\}}{\left(\frac{2\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}+\|\mathbf{A}_{i,*}\|^{4}_{2}+\gamma\max\left\\{\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}\|\mathbf{A}_{i,*}\|^{2}_{2}}{t},\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)\mathbf{A}_{i,i}}{t}\right)^{2}\right\\}}\right)\\\
&\leq
2\exp\left(-\frac{\gamma\max\left\\{\|\mathbf{A}_{i,*}\|^{4}_{2},\left(\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}\right\\}}{c^{\prime}\left(\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}+c^{\prime}\|\mathbf{A}_{i,*}\|^{4}_{2}}\right)\\\
\end{split}$

where
$\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\|\mathbf{A}_{i,*}\|^{2}_{2}\leq\left(\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right)^{2}+\|\mathbf{A}_{i,*}\|^{4}_{2}$
follows from the AM-GM inequality. Setting $\gamma=\Omega(\log(n))$ completes
the proof.

∎

To construct a row projection cost preserving sketch of $\mathbf{C}$, we
sample $t$ rows of $\mathbf{C}$ proportional to the corresponding diagonal
entries of $\mathbf{A}$. Formally, we consider a probability distribution,
$p=\\{p_{1},p_{2},\ldots p_{n}\\}$, over the rows of $\mathbf{C}$ such that
$p_{i}=\frac{\mathbf{A}_{i,i}}{\mathrm{Tr}\left(\mathbf{A}\right)}$. Let
$\mathbf{R}$ be a $t\times t$ matrix where each row of $\mathbf{R}$ is set to
$\frac{1}{\sqrt{tp_{i}}}\mathbf{C}_{i,*}$ with probability $p_{i}$. As before,
$\mathbf{R}$ can be represented as
$\SS\mathbf{C}=\SS(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})$. We first
obtain a spectral guarantee for $\SS\mathbf{A}\mathbf{T}$, while we cannot
actually compute this.

######  Theorem 5.9.

(Spectral Bounds.) Let $\mathbf{A}\mathbf{T}$ be an $n\times t$ matrix
constructed as shown in Theorem 5.6. Let $p=\\{p_{1},p_{2}\ldots p_{n}\\}$ be
a probability distribution over the rows of $\mathbf{A}\mathbf{T}$ such that
$p_{i}=\frac{(\mathbf{A}+\mathbf{N})_{i,i}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Let
$t=O\left(\frac{\sqrt{n}k^{2}}{\epsilon^{2}}\log(\frac{n}{\delta})\right)$.
Construct a sampling matrix $\SS$ that samples $t$ rows of
$\mathbf{A}\mathbf{T}$ such that row $(\mathbf{A}\mathbf{T})_{i,*}$ is picked
with with probability $p_{i}$ and scaled by $\frac{1}{\sqrt{tp_{i}}}$ . Then,
with probability at least $1-\delta$,

$(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})-\frac{\epsilon}{k}\|\mathbf{A}\|^{2}_{F}\mathbf{I}\preceq(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\preceq(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})+\frac{\epsilon}{k}\|\mathbf{A}\|^{2}_{F}\mathbf{I}$

###### Proof.

Let
$\mathbf{Y}=(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})-(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})$.
For notational convenience let
$(\mathbf{A}\mathbf{T})_{i}=(\mathbf{A}\mathbf{T})_{{i,*}}$ and
$(\SS\mathbf{A}\mathbf{T})_{i}=(\SS\mathbf{A}\mathbf{T})_{{i,*}}$. We can then
write
$\mathbf{Y}=\sum_{i\in[t]}\left((\SS\mathbf{A}\mathbf{T})^{T}_{{i}}(\SS\mathbf{A}\mathbf{T})_{{i}}-\frac{1}{t}(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\right)=\sum_{i\in[t]}\mathbf{X}_{i}$,
where
$\mathbf{X}_{i}=\frac{1}{t}\left(\frac{1}{p_{i}}(\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i}-(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\right)$
with probability $p_{i}$. We observe that
${\bf\mathbb{E}}[\mathbf{X}_{i}]={\bf\mathbb{E}}[(\SS\mathbf{A}\mathbf{T})^{T}_{i}(\SS\mathbf{A}\mathbf{T})_{i}-\frac{1}{t}(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})]=\sum_{i}\frac{p_{i}}{p_{i}}(\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i}-(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})=0$,
and therefore, ${\bf\mathbb{E}}[\mathbf{Y}]=0$. Next, we bound the operator
norm of $\mathbf{Y}$. To this end, we use the Matrix Bernstein inequality,
which in turn requires a bound on the operator norm of $\mathbf{X}_{i}$ and
variance of $\mathbf{Y}$. Recall, for some $i^{\prime}\in[n]$

$\begin{split}\|\mathbf{X}_{i}\|_{2}&=\left\|\frac{1}{tp_{i^{\prime}}}(\mathbf{A}\mathbf{T})^{T}_{{i^{\prime}}}(\mathbf{A}\mathbf{T})_{{i^{\prime}}}-\frac{1}{t}(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\right\|_{2}\\\
&\leq\frac{1}{tp_{i^{\prime}}}\|(\mathbf{A}\mathbf{T})^{T}_{{i^{\prime}}}(\mathbf{A}\mathbf{T})_{{i^{\prime}}}\|_{2}+\frac{1}{t}\|(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\|_{2}\\\
&=\frac{\|(\mathbf{A}\mathbf{T})_{{i^{\prime}}}\|^{2}_{2}}{tp_{i^{\prime}}}+\frac{\|(\mathbf{A}\mathbf{T})\|^{2}_{2}}{t}\\\
&\leq\frac{\log(n)}{tp_{i^{\prime}}}\max\left\\{\|\mathbf{A}_{i^{\prime},*}\|^{2}_{2},\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i,i}}{t}\right\\}+\frac{\|(\mathbf{A}\mathbf{T})\|^{2}_{2}}{t}\hskip
36.135pt\textrm{[by Lemma \ref{lem:row_norm_bound}]}\\\
&\leq\frac{\log(n)}{t}\max\left\\{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2},\frac{(\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F})^{2}}{t},\|(\mathbf{A}\mathbf{T})\|^{2}_{2}\right\\}\hskip
39.74872pt\textrm{[by Lemma \ref{lem:row_norm_spectral_norm}]}\\\
&\leq\frac{\phi_{\max}\sqrt{n}\log(n)\|\mathbf{A}\|^{2}_{F}}{t}\left(1+\frac{\sqrt{n}}{t}\right)\leq\frac{2\phi_{\max}\sqrt{n}\log(n)\|\mathbf{A}\|^{2}_{F}}{t}\end{split}$
(5.15)

where the last inequality uses that $t=\Omega(\sqrt{n})$. Next, we bound
$\mbox{\bf Var}[\mathbf{Y}]\leq{\bf\mathbb{E}}\left[\mathbf{Y}^{2}\right]$ as
follows

$\begin{split}{\bf\mathbb{E}}\left[\mathbf{Y}^{2}\right]&=t\left(\sum_{i\in[n]}\frac{p_{i}}{t^{2}p_{i}^{2}}((\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i})^{2}+\frac{1}{t^{2}}((\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T}))^{2}-\sum_{i\in[n]}\frac{2p_{i}}{p_{i}t^{2}}(\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i}(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\right)\\\
&=\frac{1}{t}\left(\sum_{i\in[n]}\frac{((\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i})^{2}}{p_{i}}+((\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T}))^{2}-\sum_{i\in[n]}2(\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i}(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})\right)\\\
&\preceq\frac{1}{t}\left(\sum_{i\in[n]}\frac{((\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i})^{2}}{p_{i}}\right)\\\
&\preceq\frac{\log(n)}{t}\max\left\\{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\|\mathbf{A}\|_{2},\frac{(\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F})^{2}}{t}\right\\}\left(\sum_{i\in[n]}(\mathbf{A}\mathbf{T})^{T}_{i}(\mathbf{A}\mathbf{T})_{i}\right)\\\
&\preceq\frac{c\log(n)\sqrt{n}\|\mathbf{A}\|^{2}_{F}\|(\mathbf{A}\mathbf{T})\|^{2}_{2}}{t}\mathbf{I}_{n\times
n}\end{split}$ (5.16)

where we again use Lemma 5.5 and Theorem 5.7. Observe,

Applying the Matrix Bernstein inequality with equations 5.15 and 5.16

$\begin{split}\mbox{\bf
Pr}\left[\|\mathbf{Y}\|_{2}\geq\epsilon\|\mathbf{A}\|^{2}_{F}\right]&\leq
2n\exp{\left(-\frac{\epsilon^{2}\|\mathbf{A}\|^{4}_{F}}{\frac{c\log(n)\sqrt{n}\phi_{\max}\|\mathbf{A}\|^{2}_{F}\|(\mathbf{A}\mathbf{T})\|^{2}_{2}}{t}+\frac{\epsilon\sqrt{n}\log(n)\phi_{\max}}{3t}\|\mathbf{A}\|^{4}_{F}}\right)}\\\
&\leq
2n\exp{\left(-\frac{\epsilon^{2}t}{c^{\prime}\phi_{\max}\sqrt{n}\log(n)}\right)}\\\
\end{split}$ (5.17)

where the second inequality uses Theorem 5.6, to conclude that with
probability at least $1-\delta/2$
$\|\mathbf{A}\mathbf{T}\|^{2}_{2}\leq\|\mathbf{A}\|^{2}_{2}+\epsilon/k\|\mathbf{A}\|^{2}_{F}\leq
O(\|\mathbf{A}\|^{2}_{F})$. Therefore, it suffices to set
$t=\frac{c^{\prime}\phi_{\max}\sqrt{n}\log(n))}{\epsilon^{2}}\log(n/\delta)$,
to bound the above probability by $\delta/2$. Union bounding over the error
for both PCPs, and setting $\epsilon=\epsilon/k$, we can conclude that with
probability at least $1-\delta$,

$(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})-\frac{\epsilon}{k}\|\mathbf{A}\|^{2}_{F}\mathbf{I}\preceq(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\preceq(\mathbf{A}\mathbf{T})^{T}(\mathbf{A}\mathbf{T})+\frac{\epsilon}{k}\|\mathbf{A}\|^{2}_{F}\mathbf{I}$

when $t=\Omega\left(\frac{\phi_{\max}\sqrt{n}k^{2}}{\epsilon^{2}}\right)$.

∎

We use the spectral bound from Theorem 5.9 to obtain a row projection-cost
preservation guarantee. We follow the same proof strategy as Theorem 5.7,
while requiring modified version of the scalar Chernoff bound. We do away with
the head-tail split from [CMM17],[MW17] and [BW18] and analyze the projection-
cost guarantee directly. This enables us to obtain a better $\epsilon$
dependence than [MW17] and [BW18]. Note, our $\epsilon$ dependence matches
that of [CMM17] but our row projection cost preserving sketch can be computed
in sub-linear time, albeit for PSD matrices.

######  Theorem 5.10.

(Row Projection-Cost Preservation.) Given as input $\mathbf{A}+\mathbf{N}$ let
$\mathbf{C}$ be an $n\times t$ matrix as defined in Theorem 5.7 such that
$\mathbf{C}=\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T}$. Let
$p=\\{p_{1},p_{2}\ldots p_{n}\\}$ be a probability distribution over the rows
of $\mathbf{C}$ such that
$p_{j}=\frac{(\mathbf{A}+\mathbf{N})_{j,j}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Let $t=O\left(\frac{\phi_{max}\sqrt{n}k^{2}\log^{2}(n)}{\epsilon^{2}}\right)$.
Then, construct $\mathbf{R}$ using $t$ rows of $\mathbf{C}$ and set each one
to $\frac{\mathbf{C}_{i,*}}{\sqrt{tp_{i}}}$ with probability $p_{i}$. With
probability at least $1-c$, for any rank-$k$ orthogonal projection
$\mathbf{X}$,

$\|\mathbf{R}-\mathbf{R}\mathbf{X}\|^{2}_{F}=\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{F}\pm
O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$

for a fixed constant $c$.

###### Proof.

Note,
$\mathbf{R}=\SS\mathbf{C}=\SS\mathbf{A}\mathbf{T}+\SS\mathbf{N}\mathbf{T}$,
where $\SS$ and $\mathbf{T}$ are the corresponding sampling matrices. Observe,
$\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{F}=\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{C}^{T}\mathbf{C}(\mathbb{I}-\mathbf{X})\right)$.
Then,

$\begin{split}\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{C}^{T}\mathbf{C}(\mathbb{I}-\mathbf{X})\right)&=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)+\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\right)\\\
&=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}^{T}\right)+\mathrm{Tr}\left(\mathbf{X}^{T}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\mathbf{X}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{X}\mathbf{C}^{T}\mathbf{C}\right)\\\
&=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)+\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)\\\
&=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{C}^{T}\mathbf{C}\mathbf{X}\right)\\\
&=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)-\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})^{T}(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})\mathbf{X}\right)\end{split}$
(5.18)

where we used the fact that for any projection matrix $X=X^{2}$ in addition to
the cyclic property of the trace. Here, for analyzing the cross and tail
terms, we observe that with probability $1-c$,
$\|\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\|_{F}\leq O(1)\|\mathbf{A}\|_{F}$ and
$\|\mathbf{X}(\mathbf{N}\mathbf{T})^{T}\|^{2}_{F}\leq
O(\eta)\|\mathbf{A}\|^{2}_{F}$. Therefore,

$\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})^{T}(\mathbf{A}\mathbf{T}+\mathbf{N}\mathbf{T})\mathbf{X}\right)=\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{X}\right)\pm
O(\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$ (5.19)

Similarly,

$\begin{split}\|\mathbf{R}-\mathbf{R}\mathbf{X}\|^{2}_{F}=\mathrm{Tr}\left((\mathbb{I}-\mathbf{X})\mathbf{R}^{T}\mathbf{R}(\mathbb{I}-\mathbf{X})\right)&=\mathrm{Tr}\left(\mathbf{R}^{T}\mathbf{R}\right)-\mathrm{Tr}\left(\mathbf{X}\mathbf{R}^{T}\mathbf{R}\mathbf{X}\right)\\\
&=\mathrm{Tr}\left(\mathbf{R}^{T}\mathbf{R}\right)-\mathrm{Tr}\left(\mathbf{X}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{X}\right)\pm
O(\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}\end{split}$ (5.20)

Here, we observe $\|\SS\mathbf{A}\mathbf{T}\|^{2}_{F}$ is an unbiased
estimator for $\|\mathbf{A}\|^{2}_{F}$ and
$\|\SS\mathbf{N}\mathbf{T}\|^{2}_{F}$ is an unbiased estimator for
$\|\mathbf{N}\|^{2}_{F}$. Using the same idea as above, we can bound the cross
and tail terms by $O(\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$. Our goal is show
that Equations 5.18 and 5.20 are related up to additive error
$O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$. We first relate
$\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)$ and
$\mathrm{Tr}\left(\mathbf{R}^{T}\mathbf{R}\right)$. Recall,
${\bf\mathbb{E}}\left[\mathrm{Tr}\left(\mathbf{R}^{T}\mathbf{R}\right)\right]={\bf\mathbb{E}}\left[\|\mathbf{R}\|^{2}_{F}\right]=\|\mathbf{C}\|^{2}_{F}=\mathrm{Tr}\left(\mathbf{C}^{T}\mathbf{C}\right)$.
Using a scalar Chernoff bound, we show that with probability at least
$1-1/\textrm{poly}(n)$,
$|\|\mathbf{R}\|^{2}_{F}-\|\mathbf{C}\|^{2}_{F}|\leq\epsilon\|\mathbf{A}\|^{2}_{F}$.
Observe, for all $i\in[t]$,
$\mathbf{R}_{*,i}=\frac{1}{\sqrt{p_{i^{\prime}}t}}\mathbf{C}_{i^{\prime},*}$
for some $i^{\prime}\in[n]$. Then,

$\begin{split}\|\mathbf{R}_{i,*}\|^{2}_{2}=\frac{1}{p_{i^{\prime}}t}\|\mathbf{C}_{i^{\prime},*}\|^{2}_{2}&=\frac{\phi_{max}\sqrt{n}\|\mathbf{A}\|_{F}\epsilon^{2}}{\phi_{max}\sqrt{nk}\log(n)\log(n/\delta)\mathbf{A}_{i^{\prime},i^{\prime}}}\|\mathbf{C}_{i^{\prime},*}\|^{2}_{2}\\\
&\leq\frac{c(1+\eta)\|\mathbf{A}\|_{F}\epsilon^{2}}{\sqrt{k}\log(n/\delta)\mathbf{A}_{i^{\prime},i^{\prime}}}\max\left\\{\|\mathbf{A}_{i^{\prime},*}\|^{2}_{2},\frac{\phi_{\max}\sqrt{n}\|\mathbf{A}\|_{F}\mathbf{A}_{i^{\prime},i^{\prime}}}{t}\right\\}\\\
&\leq\frac{c\epsilon^{2}}{\sqrt{k}\log(n/\delta)}\max\left\\{\|\mathbf{A}\|_{2}\|\mathbf{A}\|_{F},\frac{\|\mathbf{A}\|_{F}^{2}\epsilon^{2}}{\sqrt{k}\log(n/\delta)}\right\\}\\\
&\leq\frac{c\epsilon^{2}}{\sqrt{k}\log(n/\delta)}\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\end{split}$
(5.21)

where we use
$\mathbf{C}_{i^{\prime},*}=(\mathbf{A}\mathbf{T})_{i^{\prime},*}+(\mathbf{N}\mathbf{T})_{i^{\prime},*}$,
$\|(\mathbf{N}\mathbf{T})_{i,*}\|^{2}_{2}\leq(\eta)\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}$
for all $i$ and Lemma 5.8 to bound $\|(\mathbf{A}\mathbf{T})_{i,*}\|^{2}_{2}$.
Therefore,
$\frac{\sqrt{k}\log(n/\delta)}{c\epsilon^{2}\|\mathbf{A}\|^{2}_{F}}\|\mathbf{R}_{i,*}\|^{2}_{2}\in[0,1]$.
Note, $\|\mathbf{R}\|^{2}_{F}$ is an unbiased estimator for
$\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$. Using a Chernoff bound,

$\begin{split}\mbox{\bf
Pr}\left[\|\mathbf{R}\|^{2}_{F}\geq(1+\epsilon)\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\right]&=\mbox{\bf
Pr}\left[\frac{\sqrt{k}\log(n/\delta)}{\epsilon^{2}\|\mathbf{A}\|^{2}_{F}}\|\mathbf{R}\|^{2}_{F}\geq\frac{\sqrt{k}\log(n/\delta)}{\epsilon^{2}}(1+\epsilon)\right]\\\
&\leq\exp\left(-\frac{\sqrt{k}\epsilon^{2}\log(n/\delta)}{\epsilon^{2}}\right)\leq\frac{\delta}{10}\end{split}$
(5.22)

Therefore, with probability at least $1-\delta/10$,
$|\|\mathbf{R}\|^{2}_{F}-\|\mathbf{A}+\mathbf{N}\|^{2}_{F}|\leq\epsilon\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$.
Note, we can then bound
$\|\mathbf{A}+\mathbf{N}\|^{2}_{F}\leq\|\mathbf{A}\|^{2}_{F}+2\sqrt{\eta}\|\mathbf{A}\|^{2}_{F}$.
Therefore,

$|\|\mathbf{R}\|^{2}_{F}-\|\mathbf{A}\|^{2}_{F}|\leq
O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|_{F}$

Recall, by equation 5.10, with probability $\delta/10$,
$\|\mathbf{A}\|^{2}_{F}=(1\pm(\epsilon+2\sqrt{\eta}))\|\mathbf{C}\|^{2}_{F}$
and thus we have that $\|\mathbf{R}\|^{2}_{F}-\|\mathbf{C}\|^{2}_{F}\leq
3\epsilon\|\mathbf{A}\|^{2}_{F}$. We can repeat the above argument to lower
bound $\|\mathbf{R}\|^{2}_{F}$. Therefore, with probability $1-\delta$, we
have

$|\|\mathbf{R}\|^{2}_{F}-\|\mathbf{C}\|^{2}_{F}|\leq
O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$ (5.23)

Next, we relate
$\mathrm{Tr}\left(\mathbf{X}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{X}\right)$
and
$\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{X}\right)$.
Observe, $\mathbf{X}$ is a rank $k$ projection matrix and we can represent it
as $\mathbf{Z}\mathbf{Z}^{T}$, where $\mathbf{Z}\in\mathbb{R}^{n\times k}$ and
has orthonormal columns. By the cyclic property of the trace, we have

$\mathrm{Tr}\left(\mathbf{Z}\mathbf{Z}^{T}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{Z}\mathbf{Z}^{T}\right)=\mathrm{Tr}\left(\mathbf{Z}^{T}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{Z}\right)=\sum_{j\in[k]}\mathbf{Z}^{T}_{*,j}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{Z}_{*,j}$

Similarly,
$\mathrm{Tr}\left(\mathbf{Z}\mathbf{Z}^{T}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{Z}\mathbf{Z}^{T}\right)=\sum_{j\in[k]}\mathbf{Z}^{T}_{*,j}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{Z}_{*,j}$.
By Theorem 5.9 , we have

$\begin{split}\sum_{j\in[k]}\left(\mathbf{Z}^{T}_{*,j}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{Z}_{*,j}\right)=\sum_{j\in[k]}\left(\mathbf{Z}^{T}_{*,j}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{Z}_{*,j}\pm\frac{\epsilon}{k}\|\mathbf{A}\|_{F}^{2}\mathbf{Z}^{T}_{*,j}\mathbf{I}\mathbf{Z}_{*,j}\right)\end{split}$
(5.24)

Since $\mathbf{Z}^{T}_{*,j}\mathbf{Z}_{*,j}=1$ and
$\mathrm{Tr}\left(\mathbf{Z}^{T}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{Z}\right)=\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{X}\right)$,
we obtain

$\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{X}\right)-\epsilon\|\mathbf{A}\|_{F}^{2}\leq\mathrm{Tr}\left(\mathbf{X}(\SS\mathbf{A}\mathbf{T})^{T}(\SS\mathbf{A}\mathbf{T})\mathbf{X}\right)\leq\mathrm{Tr}\left(\mathbf{X}(\mathbf{A}\mathbf{T})^{T}\mathbf{A}\mathbf{T}\mathbf{X}\right)+\epsilon\|\mathbf{A}\|_{F}^{2}$
(5.25)

Combining equations 5.25,5.23, 5.19 and 5.20 with probability $1-c$,

$\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{F}-O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}\leq\|\mathbf{R}-\mathbf{R}\mathbf{X}\|^{2}_{F}\leq\|\mathbf{C}-\mathbf{C}\mathbf{X}\|^{2}_{F}+O(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$

∎

Input: A Matrix $\mathbf{A}+\mathbf{N}$, integer $k$, $\epsilon>0$ and
$\phi_{\max}=\max_{j}\mathbf{A}_{j,j}/(\mathbf{A}+\mathbf{N})_{j,j}$ 1. Let
$t=\frac{c\phi^{2}_{\max}\sqrt{n}k\log^{2}(n)}{\epsilon^{2}}$, for some
constant $c$. Let $q=\\{q_{1},q_{2}\ldots q_{n}\\}$ denote a distribution over
columns of $\mathbf{A}+\mathbf{N}$ such that
$q_{j}=\frac{(\mathbf{A}+\mathbf{N})_{j,j}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Construct a column PCP for $\mathbf{A}+\mathbf{N}$ by sampling $t$ columns of
$\mathbf{A}+\mathbf{N}$ such that each column is set to
$\frac{(\mathbf{A}+\mathbf{N})_{*,j}}{\sqrt{tq_{j}}}$ with probability
$q_{j}$. Let $\mathbf{C}$ be the resulting $n\times t$ matrix that satisfies
the guarantee of Theorem 5.7. 2. Let $p=\\{p_{1},p_{2}\ldots p_{n}\\}$ denote
a distribution over rows of $\mathbf{C}$ such that
$p_{i}=\frac{(\mathbf{A}+\mathbf{N})_{i,i}}{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)}$.
Construct a row PCP for $\mathbf{C}$ by sampling $t$ rows of $\mathbf{C}$ such
that each row is set to $\frac{\mathbf{C}_{i,*}}{\sqrt{tp_{i}}}$ with
probability $p_{i}$. Let $\mathbf{R}$ be the resulting $t\times t$ matrix that
satisfies the guarantee of Theorem 5.10. Sample $\Theta(n)$ entries uniformly
at random from $\mathbf{A}$ and rescale such that
$\widetilde{v}^{2}=\Theta(\|\mathbf{A}\|^{2}_{F})$. 3. Let
$\mu=\phi_{\max}\sqrt{|(\mathbf{A}+\mathbf{N})_{i,i}|\cdot|(\mathbf{A}+\mathbf{N})_{i^{\prime},i^{\prime}}|}$
For all $i\in[t]$, let
$\mathcal{X}_{i}=\sum_{j\in[\epsilon^{3}t/k^{3}]}\mathcal{X}_{i,j}$ such that
$\mathcal{X}_{i,j}=(k^{3}/\epsilon^{3})\mathbf{R}^{2}_{i,i^{\prime}}$, with
probability $1/t$, for all $i^{\prime}\in[t]$. Here, we query the entry
corresponding to $\mathbf{R}_{i,i^{\prime}}$ in $\mathbf{A}+\mathbf{N}$ and
truncate it to $\mu$. Let $\tau=\phi_{\max}^{2}n\widetilde{v}^{2}/t^{2}$. If
$\mathcal{X}_{i}>\tau$, sample row $\mathbf{R}_{i,*}$ with probability $1$.
For the remaining rows, sample $nk/(\epsilon t)$ rows uniformly at random. 4.
Run the sampling algorithm from Frieze-Kannan-Vempala [FKV04] to compute a
$t\times k$ matrix $\SS$ such that
$\|\mathbf{R}-\mathbf{R}\SS\SS^{T}\|^{2}_{F}\leq\|\mathbf{R}-\mathbf{R}_{k}\|^{2}_{F}+\epsilon\|\mathbf{R}\|^{2}_{F}$.
Consider the regression problem $\min_{\mathbf{X}\in\mathcal{R}^{n\times
k}}\|\mathbf{C}-\mathbf{X}\SS^{T}\|^{2}_{F}.$ Sketch the problem using the
leverage scores of $\SS^{T}$, as shown in Lemma 4.4, to obtain a sampling
matrix $\mathbf{E}$ with $O(\frac{k}{\epsilon})$ columns. Compute
$\mathbf{X}_{\mathbf{C}}=\mathrm{argmin}_{\mathbf{X}\in\mathcal{R}^{n\times
k}}\|\mathbf{C}\mathbf{E}-\mathbf{X}\SS^{T}\mathbf{E}\|^{2}_{F}.$ Let
$\mathbf{X}_{\mathbf{C}}\SS^{T}=\mathbf{U}\mathbf{V}^{T}$ be such that
$\mathbf{U}\in\mathbb{R}^{n\times k}$ has orthonormal columns. 5. Consider the
regression problem $\min_{\mathbf{X}\in\mathbb{R}^{k\times
n}}\|\mathbf{A}-\mathbf{U}\mathbf{X}\|^{2}_{F}.$ Sketch the problem as above,
following Lemma 4.4 to obtain a sampling matrix $\mathbf{E}^{\prime}$ with
$O(\frac{k}{\epsilon})$ rows. Compute
$\mathbf{X}_{\mathbf{A}}=\mathrm{argmin}_{\mathbf{X}}\|\mathbf{E}^{\prime}\mathbf{A}-\mathbf{E}^{\prime}\mathbf{U}\mathbf{X}\|^{2}_{F}$
Output: $\mathbf{M}=\mathbf{U}$, $\mathbf{N}^{T}=\mathbf{X}_{\mathbf{A}}$

Full Algorithm. Next, we describe a sublinear time and query robust algorithm
for low-rank approximation of PSD matrices. We show that querying
$\widetilde{O}(\phi^{2}_{\max}nk/\epsilon)$ entries of $\mathbf{A}$ suffices.
While we assume we know $\phi_{\max}$, in practice this need not be the case.
Therefore, given a budget for the total number of queries, denoted by $\beta$,
we can run the algorithm by querying a $\sqrt{\beta}\times\sqrt{\beta}$
submatrix (as described in Algorithm 5.2), but correctness only holds when
$\beta\geq\widetilde{\Theta}(\phi^{2}_{\max}nk/\epsilon)$. Recall, whenever we
read an entry in $(\mathbf{A}+\mathbf{N})_{i,j}$, we can truncate it to
$\phi_{\max}\sqrt{|(\mathbf{A}+\mathbf{N})_{i,i}|\cdot|(\mathbf{A}+\mathbf{N})_{j,j}|}$.
We can compute these thresholds by simply reading the diagonal of
$\mathbf{A}+\mathbf{N}$.

We proceed by constructing column and row projection-cost preserving sketches
of $\mathbf{A}+\mathbf{N}$, to obtain a $t\times t$ matrix $\mathbf{R}$, where
$t=\widetilde{O}(\phi_{\max}\sqrt{n}k^{2}/\epsilon^{2})$. Instead of reading
the entire matrix, we sample $\epsilon^{3}t/k^{3}$ entries in each row of
$\mathbf{R}$, and read these entries. Ideally we would want to estimate
$\ell^{2}_{2}$ norms of rows of $\mathbf{R}$ to then use a result of Frieze-
Kannan-Vempala [FKV04] to show that there exists an $s\times t$ matrix $\SS$
such that the row space of $\SS$ contains a good rank-$k$ approximation, where
$s=c\phi_{\max}^{2}nk/\epsilon t$, for some constant $c$. However, we show
that is it not possible to obtain accurate estimates of the row norms of each
row of $\mathbf{R}$ with high probability.

Instead, we describe a new sampling procedure that ends up sampling rows of
$\mathbf{R}$ with the same probability as Frieze-Kannan-Vempala. Once we
compute a good low-rank approximation for $\mathbf{R}$ we can follow the
approach of [CMM17],[MW17] and [BW18], where we set up two regression
problems, and use fast approximate regression to compute a low rank
approximation for $\mathbf{A}$. The main theorem we prove in this section is
as follows:

######  Theorem 5.11.

(Robust PSD LRA.) Let $k$ be an integer and $\epsilon>\eta>0$. Given a matrix
$\mathbf{A}+\mathbf{N}$, where $\mathbf{A}$ is PSD and $\mathbf{N}$ is a
corruption term such that
$\|\mathbf{N}\|^{2}_{F}\leq\sqrt{\eta}\|\mathbf{A}\|^{2}_{F}$ and for all
$i\in[n]$ $\|\mathbf{N}_{i,*}\|^{2}_{2}\leq c\|\mathbf{A}_{i,*}\|^{2}_{2}$,
for a fixed constant $c$, Algorithm 5.2 samples
$\widetilde{O}\left(\phi^{2}_{\max}nk/\epsilon\right)$ entries in
$\mathbf{A}+\mathbf{N}$ and computes matrices
$\mathbf{M},\mathbf{N}^{T}\in\mathbb{R}^{n\times k}$ such that with
probability at least $99/100$,

$\|\mathbf{A}-\mathbf{M}\mathbf{N}\|^{2}_{F}\leq\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}+(\epsilon+\sqrt{\eta})\|\mathbf{A}\|^{2}_{F}$

We begin with the following simple lemma for approximating the Frobenius norm
:

######  Lemma 5.12.

(Approximating Frobenius Norm.) Given as input an $n\times n$ matrix
$\mathbf{A}+\mathbf{N}$, there exists an algorithm that reads
$O(\phi_{\max}^{2}n)$ entries in $\mathbf{A}$ and outputs an estimator
$\tilde{v}$ such that with probability at least $1-\frac{1}{n^{c}}$,
$\tilde{v}=\Theta(\|\mathbf{A}\|^{2}_{F})$.

###### Proof.

There are multiple ways to see this. Observe, in Theorem 5.10, we show that
sampling $\frac{\phi_{\max}^{2}n\log(n)}{\epsilon^{2}}$ entries results in row
projection-cost preserving sketch $\mathbf{R}$ such that
$\|\mathbf{R}\|^{2}_{F}=(1\pm\epsilon)\|\mathbf{A}+\mathbf{N}\|^{2}_{F}$.
Setting $\epsilon$ to be a small constant suffices. ∎

Next, we provide intuition for why uniformly sampling columns of $\mathbf{R}$
does not suffice for obtaining a sketch that spans a good low rank
approximation. For simplicity, we assume there is no noise ($\eta=0$ and
$\phi_{\max}=1$) and show that our techniques to bound the column norms of
$\mathbf{R}$ results in an estimate that is too large. We note that this lemma
is not required for proving our result, and is just present for intuition.

######  Lemma 5.13.

Let $\eta=0$. Let $\mathbf{R}\in\mathbb{R}^{t\times t}$ be a row projection-
cost preserving sketch for $\mathbf{C}$ as described in Theorem 5.10. For all
$j\in[t]$, with probability at least $1-1/n^{c}$,

$\|\mathbf{R}_{*,j}\|^{2}_{2}\leq
O\left(\log(n)\max\left\\{\|\mathbf{C}_{*,j}\|^{2}_{2},\frac{n\|\mathbf{A}\|^{2}_{F}}{t^{2}}\right\\}\right)=O\left(\log(n)\max\left\\{\frac{\sqrt{n}\|\mathbf{A}\|^{2}_{F}}{t},\frac{n\|\mathbf{A}\|^{2}_{F}}{t^{2}}\right\\}\right)$

where $c$ is a fixed constant.

###### Proof.

Observe, $\|\mathbf{R}_{*,j}\|^{2}_{2}=\sum_{i\in[t]}\mathbf{R}_{i,j}^{2}$,
where
$\mathbf{R}_{i,j}^{2}=\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t\mathbf{A}_{i^{\prime},i^{\prime}}}\mathbf{C}_{i^{\prime},j}^{2}$
with probability
$\frac{\mathbf{A}_{i^{\prime},i^{\prime}}}{\mathrm{Tr}\left(\mathbf{A}\right)}$
for all $i^{\prime}\in[n]$. Then,
${\bf\mathbb{E}}[\|\mathbf{R}_{*,j}\|^{2}_{2}]=\sum^{n}_{i=1}\mathbf{C}^{2}_{i,j}=\|\mathbf{C}_{*,j}\|^{2}_{2}$.
Next, we compute the variance of $\|\mathbf{R}_{*,j}\|^{2}_{2}$. $\mbox{\bf
Var}\left[\|\mathbf{R}_{*,j}\|^{2}_{2}\right]=t\mbox{\bf
Var}\left[\mathbf{R}_{i,j}\right]\leq
t{\bf\mathbb{E}}\left[\mathbf{R}^{4}_{i,j}\right]$. Then,

$\begin{split}t{\bf\mathbb{E}}\left[\mathbf{R}^{4}_{i,j}\right]=\sum_{i^{\prime}\in[n]}\frac{1}{tp_{i^{\prime}}}\mathbf{C}_{i^{\prime},j}^{4}&\leq\sum_{i^{\prime}\in[n]}\frac{\mathrm{Tr}\left(\mathbf{A}\right)^{2}}{t^{2}\mathbf{A}_{i^{\prime},i^{\prime}}\mathbf{A}_{j,j}}\mathbf{A}_{i^{\prime},j}^{2}\mathbf{A}_{i^{\prime},i^{\prime}}\mathbf{A}_{j,j}\\\
&\leq\frac{\mathrm{Tr}\left(\mathbf{A}\right)^{2}}{t^{2}}\|\mathbf{A}_{*,j}\|^{2}_{2}\\\
&=\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\|\mathbf{C}_{*,j}\|^{2}_{2}\\\
&\leq\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}+\|\mathbf{C}_{*,j}\|^{4}_{2}\hskip
28.90755pt\textrm{ [AM-GM]}\\\ \end{split}$

where we use $\mathbf{A}^{2}_{i,j}\leq\mathbf{A}_{i,i}\mathbf{A}_{j,j}$, which
follows from applying Cauchy-Schwarz to
$\langle\mathbf{A}^{1/2}_{i,*},\mathbf{A}^{1/2}_{j,*}\rangle$. Similarly, we
bound $\mathbf{R}^{2}_{i,j}\leq\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}$.
Applying Bernstein’s inequality,

$\begin{split}&\mbox{\bf
Pr}\left[|\|\mathbf{R}_{*,j}\|^{2}_{2}-\|\mathbf{C}_{*,j}\|^{2}_{2}\geq\eta\max\left\\{\|\mathbf{C}_{*,j}\|^{2}_{2},\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right\\}\right]\\\
&\leq
2\exp\left(-\frac{\eta^{2}\max\left\\{\|\mathbf{C}_{*,j}\|^{4}_{2},\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}\right\\}}{\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}+\|\mathbf{C}_{*,j}\|^{4}_{2}+\eta\max\left\\{\frac{\mathrm{Tr}\left(\mathbf{A}\right)\|\mathbf{C}_{*,j}\|^{2}_{2}}{t},\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}\right\\}}\right)\\\
&\leq
2\exp\left(-\frac{\eta\max\left\\{\|\mathbf{C}_{*,j}\|^{4}_{2},\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}\right\\}}{c^{\prime}\left(\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\right)^{2}+c^{\prime}\|\mathbf{C}_{*,j}\|^{4}_{2}}\right)\\\
\end{split}$

where we use the AM-GM inequality on
$\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t}\|\mathbf{C}_{*,j}\|^{2}_{2}$
repeatedly. Setting $\eta=\Omega(\log(n))$ completes the proof. Finally,
observe, for any $j\in[t]$,
$\|\mathbf{C}_{*,j}\|^{2}_{2}=\frac{\mathrm{Tr}\left(\mathbf{A}\right)}{t\mathbf{A}_{j^{\prime},j^{\prime}}}\|\mathbf{A}_{*,j^{\prime}}\|^{2}_{2}$
for some $j^{\prime}\in[n]$. We then use
$\mathrm{Tr}\left(\mathbf{A}\right)\leq\sqrt{n}\|\mathbf{A}\|_{F}$. ∎

It is well-known that to recover a low-rank approximation for $\mathbf{R}$,
one can sample rows of $\mathbf{R}$ proportional to row norm estimates,
denoted by $\mathbf{Y}_{i}$ [FKV04]. As shown in [IVWW19] the following two
conditions are a relaxation of those required in [FKV04], and suffice to
obtain an additive error low-rank approximation :

  1. 1.

For all $i\in[t]$, $\mathcal{Y}_{i}\geq\|\mathbf{R}_{i,*}\|^{2}_{2}$.

  2. 2.

$\sum_{i\in[t]}\mathcal{Y}_{i}\leq\frac{n}{t}\|\mathbf{R}\|^{2}_{F}$

To satisfy the first condition, we need to obtain overestimates for each row.
Since it is not immediately clear how to obtain overestimates for row norms of
$\mathbf{R}$, a naïve approach would be to bias the estimate for each row by
an upper bound on the row norm. However, by Lemma 5.13, a row norm could be as
large as $\sqrt{n}\|\mathbf{A}\|^{2}_{F}/t$. Observe, we cannot afford to bias
the estimator of each row, $\mathcal{Y}_{i}$, by this amount since
$\sum_{i\in[t]}\mathcal{Y}_{i}\geq\sqrt{n}\|\mathbf{A}\|^{2}_{F}\geq\sqrt{n}\|\mathbf{R}\|^{2}_{F}$.
Therefore, we would have to sample $\sqrt{n}k/\epsilon$ rows of $\mathbf{R}$,
resulting in us querying $\Omega(nk^{3}/\epsilon^{3})$ entries in
$\mathbf{A}$, even when $\eta=0$.

An alternative strategy would be to bias the estimator for each row by
$n\|\mathbf{R}\|^{2}_{F}/t^{2}$, as this would satisfy condition 2 above. We
can now hope to detect rows of $\mathbf{R}$ that have norm larger than
$n\|\mathbf{R}\|^{2}_{F}/t^{2}$ by sampling $\epsilon^{3}t/k^{3}$ entries in
each row of $\mathbf{R}$, uniformly at random. Note, this way we can construct
an unbiased estimator for the $\ell^{2}_{2}$ norm of each row. Ideally, we
would want to show a high probability statement for concentration of our row
norm estimates around the expectation. We could then union bound, and obtain
concentration for all $i$ simultaneously.

However, this is not possible since it may be the case that a row of
$\mathbf{R}$ is $\log(n)$-sparse with each entry being large in magnitude. In
this case, uniformly querying the row would not observe any non-zero with good
probability and thus cannot distinguish between such a row and an empty row.
Instead, we settle for a weaker statement, that shows our estimate is accurate
with $o(1)$ probability. All subsequent statements hold for $\eta>0$.

######  Lemma 5.14.

(Estimating large row norms.) Let $\mathbf{R}\in\mathbb{R}^{t\times t}$ be the
row PCP output by Step 2 of Algorithm 5.2. For all $i\in[t]$ let
$\mathcal{X}_{i}=\sum_{j\in[\epsilon^{3}t/k^{3}]}\mathcal{X}_{i,j}$ such that
$\mathcal{X}_{i,j}=\frac{k^{3}\mathbf{R}^{2}_{i,j^{\prime}}}{\epsilon^{3}}$
with probability $\frac{1}{t}$, for all $j^{\prime}\in[t]$. Then, for all
$i\in[t]$,
$\mathcal{X}_{i}=\left(1\pm\frac{1}{10}\right)\|\mathbf{R}_{i,*}\|^{2}_{2}$
with probability at least $\frac{\|\mathbf{R}_{i,*}\|^{2}_{2}k}{\epsilon n}$.

###### Proof.

Observe, $\mathcal{X}_{i}$ is an unbiased estimator of
$\|\mathbf{R}_{i,*}\|^{2}_{2}$ :

${\bf\mathbb{E}}\left[\mathcal{X}_{i}\right]=\frac{\epsilon^{3}t}{k^{3}}{\bf\mathbb{E}}\left[\mathcal{X}_{i,j}\right]=\frac{\epsilon^{3}t}{k^{3}}\sum_{j^{\prime}\in[t]}\frac{k^{3}}{\epsilon^{3}n}\mathbf{R}^{2}_{i,j^{\prime}}=\|\mathbf{R}_{i,*}\|^{2}_{2}$

Next, we compute the variance of $\mathcal{X}_{i}$.

$\begin{split}\mbox{\bf
Var}\left[\mathcal{X}_{i}\right]=\frac{\epsilon^{3}t}{k^{3}}\mbox{\bf
Var}\left[\mathcal{X}_{i,j}\right]&\leq\sum_{j\in[t]}\frac{1}{\epsilon^{3}}\mathbf{R}^{4}_{i,j}\\\
&\leq\sum_{j\in[t]}\frac{k^{3}}{\epsilon^{3}}\mathbf{R}^{2}_{i,j}\left(\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}}{t^{2}(\mathbf{A}+\mathbf{N})_{i,i}(\mathbf{A}+\mathbf{N})_{j,j}}(\mathbf{A}+\mathbf{N})^{2}_{i,j}\right)\\\
&\leq\sum_{j\in[t]}\frac{k^{3}}{\epsilon^{3}}\mathbf{R}^{2}_{i,j}\left(\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}}{t^{2}(\mathbf{A}+\mathbf{N})_{i,i}(\mathbf{A}+\mathbf{N})_{j,j}}(\mathbf{A}_{i,i}\mathbf{A}_{j,j}+\mathbf{N}^{2}_{i,j})\right)\\\
&\leq\sum_{j\in[t]}\frac{k^{3}}{\epsilon^{3}}\mathbf{R}^{2}_{i,j}\left(\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}\phi^{2}_{\max}}{t^{2}}+\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}\phi^{2}_{\max}(\mathbf{A}+\mathbf{N})_{i,i}(\mathbf{A}+\mathbf{N})_{j,j}}{t^{2}(\mathbf{A}+\mathbf{N})_{i,i}(\mathbf{A}+\mathbf{N})_{j,j}}\right)\\\
&\leq\sum_{j\in[t]}\frac{k^{3}}{\epsilon^{3}}\mathbf{R}^{2}_{i,j}\left(\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}\phi^{2}_{\max}}{t^{2}}\right)\leq
O\left(\frac{\epsilon\|\mathbf{A}\|^{2}_{F}}{k}\|\mathbf{R}_{i,*}\|^{2}_{2}\right)\end{split}$
(5.26)

Here, we use that
$\mathbf{N}^{2}_{i,j}\leq\phi^{2}_{\max}(\mathbf{A}+\mathbf{N})_{i,i}(\mathbf{A}+\mathbf{N})_{j,j}$,
which follows from our truncation procedure. Further, using
$t=\phi_{\max}\sqrt{n}k^{2}/\epsilon^{2}$ and
$\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)\leq\sqrt{n}\|\mathbf{A}\|_{F}+\sqrt{\eta
n}\|\mathbf{A}\|_{F}$, we can bound

$\frac{\mathrm{Tr}\left(\mathbf{A}+\mathbf{N}\right)^{2}\phi^{2}_{\max}}{t^{2}}\leq
O\left(\frac{\epsilon\|\mathbf{A}\|^{2}_{F}}{k}\right)$

Further, using the same argument as above

(5.27)
$\mathcal{X}_{i,j}\leq\frac{k^{3}}{\epsilon^{3}}\mathbf{R}^{2}_{i,j}\leq
O\left(\frac{\epsilon\|\mathbf{A}\|^{2}_{F}}{k}\right)$

Using Equations 5.26 and 5.27 in Bernstein’s inequality,

$\begin{split}\Pr\left[\big{|}\mathcal{X}_{i}-{\bf\mathbb{E}}[\mathcal{X}_{i}]\big{|}\geq\delta{\bf\mathbb{E}}\left[\mathcal{X}_{i}\right]\right]&\leq\exp\left(-\frac{\delta^{2}\|\mathbf{R}_{i,*}\|^{4}_{2}}{\frac{\epsilon\|\mathbf{A}\|^{2}_{F}}{k}\|\mathbf{R}_{i,*}\|^{2}_{2}+\frac{\delta\epsilon\|\mathbf{A}\|^{2}_{F}}{3k}\|\mathbf{R}_{i,*}\|^{2}_{2}}\right)\\\
&\leq\exp\left(-\frac{\delta^{2}\|\mathbf{R}_{i,*}\|^{2}_{2}k\log^{2}(n)}{\epsilon\|\mathbf{R}\|^{2}_{F}}\right)\end{split}$

where we use that $\|\mathbf{A}\|^{2}_{F}=\Theta(\|\mathbf{R}\|^{2}_{F})$.
Setting $\eta=\frac{1}{10}$,
$\mathcal{X}_{i}=\left(1\pm\frac{1}{10}\right)\|\mathbf{R}_{i,*}\|^{2}_{2}$
with probability at least
$1-\exp\left(-\frac{\|\mathbf{R}_{i,*}\|^{2}_{2}k\log^{2}(n)}{\epsilon\|\mathbf{R}\|^{2}_{F}}\right)$.
Let $\xi_{i}$ be the event that
$\mathcal{X}_{i}=\left(1\pm\frac{1}{10}\right)\|\mathbf{R}_{i,*}\|^{2}_{2}$.
Then, union bounding over $t\leq n$ such events $\xi_{i}$, simultaneously for
all $i$, $\xi_{i}$ is true with probability at least

$1-\exp\left(-\frac{\|\mathbf{R}_{i,*}\|^{2}_{2}k\log(n)}{\epsilon\|\mathbf{R}\|^{2}_{F}}\right)\geq\frac{\|\mathbf{R}_{i,*}\|^{2}_{2}k\log(n)}{\epsilon\|\mathbf{R}\|^{2}_{F}}\qed$

We now have two major challenges: first, the probability with which the
estimators are accurate is too small to even detect all rows with norm larger
than $\phi_{\max}^{2}n\|\mathbf{R}\|^{2}_{F}/t^{2}$, and second, there is no
small query certificate for when an estimator is accurate in estimating the
row norms. Therefore, we cannot even identify the rows where we obtain an
accurate estimate of their norm.

To address the first issue, we make the crucial observation that while we
cannot estimate the norm of each row accurately, we can hope to sample the row
with the same probability as Frieze-Kannan-Vempala [FKV04]. Recall, their
algorithm samples row $\mathbf{R}_{i,*}$ with probability at least
$\|\mathbf{R}_{i,*}\|^{2}_{2}/\|\mathbf{R}\|^{2}_{F}$, which matches the
probability in Lemma 5.14. Therefore, we can focus on designing a weaker
notion of identifiability, that may potentially include extra rows.

We begin by partitioning rows of $\mathbf{R}$ into two sets. Let
$\mathcal{H}=\left\\{i\textrm{ }\big{|}\textrm{
}\|\mathbf{R}_{i,*}\|^{2}_{2}\geq\phi_{\max}^{2}n\widetilde{v}^{2}/t^{2}\right\\}$
be the set of heavy rows and $[t]\setminus\mathcal{H}$ be the remaining rows.
Since with probability at least $1-\frac{1}{\textrm{poly}(n)}$,
$\|\mathbf{R}\|^{2}_{F}=\Theta(\|\mathbf{A}\|^{2}_{F})=\Theta(\widetilde{v}^{2})$,

$|\mathcal{H}|=O(t^{2}/\phi_{\max}^{2}n)=O(k^{4}\log^{4}(n)/\epsilon^{4})$