Microsoft Research, Bangalore, India amitdesh@microsoft.com(Optional) IIT
Mandi, H.P<EMAIL_ADDRESS>Deshpande and
Pratap [100]Replace ccsdesc macro with valid one

###### Acknowledgements.

I want to thank …John Q. Open and Joan R. Access 2 42nd Conference on Very
Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little
Whinging, United Kingdom 42 23

# On Subspace Approximation and Subset Selection in Fewer Passes by MCMC
Sampling

Amit Deshpande  Rameshwar Pratap

###### Abstract

We consider the problem of subset selection for $\ell_{p}$ subspace
approximation, i.e., given $n$ points in $d$ dimensions, we need to pick a
small, representative subset of the given points such that its span gives
$(1+\epsilon)$ approximation to the best $k$-dimensional subspace that
minimizes the sum of $p$-th powers of distances of all the points to this
subspace. Sampling-based subset selection techniques require adaptive sampling
iterations with multiple passes over the data. Matrix sketching techniques
give a single-pass $(1+\epsilon)$ approximation for $\ell_{p}$ subspace
approximation but require additional passes for subset selection.

In this work, we propose an MCMC algorithm to reduce the number of passes
required by previous subset selection algorithms based on adaptive sampling.
For $p=2$, our algorithm gives subset selection of nearly optimal size in only
$2$ passes, whereas the number of passes required in previous work depend on
$k$. Our algorithm picks a subset of size $\mathrm{poly}(k/\epsilon)$ that
gives $(1+\epsilon)$ approximation to the optimal subspace. The running time
of the algorithm is $nd+d\leavevmode\nobreak\ \mathrm{poly}(k/\epsilon)$. We
extend our results to the case when outliers are present in the datasets, and
suggest a two pass algorithm for the same. Our ideas also extend to give a
reduction in the number of passes required by adaptive sampling algorithms for
$\ell_{p}$ subspace approximation and subset selection, for $p\geq 2$.

###### keywords:

Low-rank approximation, dimensionality reduction, sketching, sampling.

###### category:

##  1 Introduction

Computing subspace approximation of large, high-dimensional input data is one
of the most fundamental problems in data science and randomized numerical
linear algebra. Given a dataset
$\mathcal{X}=\\{x_{i}\\}_{i=1}^{n}:x_{i}\in\mathbb{R}^{d}$; where $n$ and $d$
are large, a positive integer $1<k\ll d$, and $1\leq p<\infty$, the problem of
$\ell_{p}$ subspace approximation is to find a $k$ dimensional linear subspace
$V$ of $\mathbb{R}^{d}$ that minimizes the sum of $p$-th powers of the
distances of all the points in the dataset to the subspace $V$, that is,

$\mathrm{err}_{p}(\mathcal{X},V):=\sum_{i=1}^{n}d(x_{i},V)^{p}.$

This subspace approximation problem can also be seen as a dimensionality
reduction as it compresses the data dimension. The subspace approximation
problem for $p=2$ (also known as low-rank matrix approximation) is well
studied and can be solved exactly in time $O(\min\\{n^{2}d,nd^{2}\\})$ using
the Singular value decomposition (SVD). However, computing exact SVD may not
be practical when $n$ and $d$ are large. To overcome this, several faster
algorithms have been proposed that closely approximate the optimal results
obtained via SVD decomposition. We mention a few such notable results as
follows. Frieze, Kannan, and Vempala [18] suggest computing low-rank
approximation that gives an additive approximation in time
$O(nd\cdot\mathrm{poly}(k,1/\epsilon))$ by sampling a subset of points with
probability proportional to their squared lengths. This was later improved in
[16, 14, 13] to give a multiplicative approximation guarantee by modifying and
generalizing the squared-length sampling to sample multiple points adaptively
over multiple passes. This line of work [18, 16, 14, 13] sample
$\mathrm{poly}((k/\epsilon)^{p})$ points, with the guarantee that their span
contains a $k$-dimensional subspace that gives $(1+\epsilon)$ approximation to
the optimum, with high probability. These sampling results are also known as
column subset selection for low-rank approximation. Low-rank approximation
based on row and column subset selection is more interpretable and
advantageous as argued in [17, 27, 29, 26, 23]. However, a limitation of most
row and column subset selection algorithms that give multiple approximation
guarantee is that they require multiple passes over the input matrix to
perform multiple adaptive rounds of sampling, which can be impractical when
$n$ and $d$ are large.

Another line of work follows deterministic sketching based techniques [24, 20,
19, 9], requires one passes over the data, and offers multiplicative
approximation guarantee. The work due to [28, 8] gives randomized sketching
for multiplicative approximation guarantee. However, a limitation of these
results is that they don’t provide subset selection. In this work, we focus on
the problem of achieving a multiplicative approximation guarantee for
$\ell_{p}$ norm via subset selection and simultaneously aim to minimize the
number of passes over the input required by the adaptive sampling. We
summarise our contributions as follows:

###  1.1 Our results:

Our main contribution lies in minimizing the number of rounds required by the
adaptive sampling to sample a subset of points whose span contains a $k$
dimensional subspace that offer multiplicative approximation for the
$\ell_{p}$ error. Our main ingredient is a carefully designed MCMC sampling
distribution that ensures that the implied probability of sampling a point
using MCMC distribution is sufficiently close to that of adaptive sampling
distribution, and as a consequence, the $\ell_{p}$ error corresponding to
these two sampling distributions is sufficiently close. We summarise our key
contribution as follows:

  * •

For $p=2$, whereas previous subset selection for nearly optimal approximation
required $O(k\log k)$ passes by adaptive sampling [16] or $O(\log k)$ passes
by a combination of approximate volume sampling and adaptive sampling [13],
our MCMC sampling algorithm can achieve the same in only $2$ passes over the
data. We sample a set of $\mathrm{poly}(k/\epsilon)$ points whose span
contains a $k$ dimensional subspace that offers $(1+\epsilon)$-multiplicative
approximation to the optimal. The running time of our algorithm is
$nd+d\cdot\mathrm{poly}(k/\epsilon)$.

  * •

For $p=2$, our results generalize to subspace approximation with outliers, and
offer a similar multiplicative approximation guarantee. This is an improvement
over the recently proposed algorithms [12, 11] by reducing their number of
passes from $O(k\log k)$ to $2$.

  * •

Our ideas extend to $\ell_{p}$ subspace approximation, for $p\geq 2$, and give
a significant reduction in the number of passes required by adaptive sampling
algorithms for subspace approximation and subset selection.

##  2 Previous work

We broadly split the baselines to compare with our proposal in the following
subsections.

###  2.1 Subset selection

We first suggest baselines for $p=2$. Frieze, Kannan, and Vempala [18] suggest
a sampling algorithm that picks points proportional to their squared norm
(called squared-length sampling) and offers the guarantee that the span of
$\mathrm{poly}(k/\epsilon)$ sampled points contains a $k$-dimensional subspace
which offers additive approximation guarantee to the optimal $k$-dimensional
subspace. However, their additive error is essentially $\epsilon$ times the
Frobenius norm of input points, which can be arbitrarily large as compared to
the true error. This result was strengthened by Deshpande and Vempala [16] by
following squared-length sampling in an adaptive manner. They show that a
subset of $\mathrm{poly}(k/\epsilon)$ points sampled using their distribution
gives a multiplicative approximation guarantee. However, a limitation of their
approach is that it requires taking $O(k\log k)$ passes over the input to
generate the sampling distribution. Another way to achieve the multiplicative
approximation guarantee was proposed by doing volume sampling [14], and then
following adaptive sampling in $O(k\log k)$ rounds [16]. The running time of
their algorithm is $O(\mathrm{nnz}(\mathcal{X})\cdot k/\epsilon)$. The result
due to Guruswami et. al. [21] show that sampling $O(k/\epsilon)$ points by
volume sampling gives a bi-criteria $(1+\epsilon)$ approximation to the
optimal subspace. The result due to [15] extends the above for $p\neq 2$, and
suggests multiplicative subspace approximation. They first perform approximate
volume sampling that gives $k!(k+1)$ multiplicative guarantee. Then they
follow an adaptive sampling of $O(k\log k)$ rounds, and sample a subset of
$\tilde{O}(k^{2}(k/\epsilon)^{p+1})$ with the guarantee that their span gives
$(1+\epsilon)$ approximation, with high probability. Their running time is
$\tilde{O}(nd\cdot k^{3}(k/\epsilon)^{p+1})$. The first step of [15] mentioned
above was recently improved to to $(k+1)$ by [7]. This was further
strengthened to $O((k+1)^{1/p})$ for $p\in(1,2)$ and $O({(k+1)}^{1-1/p})$ for
$p\geq 2$ due to [10]. Of course, here also, adaptive sampling of $O(k\log k)$
rounds need to perform in order to achieve $(1+\epsilon)$ multiplicative
approximation. An advantage of these results is that they perform subset
selection for subspace approximation, whereas the downside is that they
require a large number of passes over the input to offer the multiplicative
approximation guarantee.

###  2.2 Frequent directions and sketching

Liberty’s deterministic matrix sketching [24] suggests additive rank $k$
approximation guarantee by taking $1$-pass over the data stream. A subsequent
work due to Ghashami et.al.[20] provide a faster, deterministic algorithm that
runs in $O\left(nd\cdot\text{poly}(k/\epsilon)\right)$ time and gives a
multiplicative $(1+\epsilon)$-approximation to the optimum. A faster algorithm
with running time $O(nd\cdot(k/\epsilon)^{2})$ time that offers the same
guarantee was provided in [19]. An advantage of these results is that they are
deterministic and require only one pass over the data. However, a major
limitation of these results is that they work only for $p=2$, can not perform
subset selection, and also do not extend when outliers are present in the
datasets. Recently proposed work [9] extends the above mentioned deterministic
sketching results for $p\neq 2$. Their Theorem $4.2$ suggests a one pass
deterministic sketching for the $\ell_{p}$ (with $p\neq 2,\infty$) subspace
approximation in streaming settings. The running time of their algorithm is
$\mathrm{poly}(n^{\gamma},d)$ with the update time $O(n^{\gamma}d)$, and
offers $1/d^{\gamma}$ approximation factor, where $\gamma\in(0,1)$ is a
constant. Again limitation of this result is that they do not provide subset
selection. Further Theorem $5.1$ of their result suggest an $\ell_{1}$
subspace approximation algorithm that offer $\mathrm{poly}(k)$ approximation
factor, with update time $\mathrm{poly}(n,d)$ and space
$n^{\gamma}\mathrm{poly}(d)$. The $\ell_{1}$ distance is known to be robust to
the outliers and these results can potentially be used to give $\ell_{p}$
subspace approximation with outliers. However, they don’t provide any concrete
theoretical guarantee on this statement. Whereas our results extend to
$\ell_{p}$ subspace approximation with outliers under the assumption that
error in inliers over $\ell_{p}$ norm is at least a constant fraction of
$\ell_{p}$ error over all the points.

There is another line of work based on the randomized sketching based
techniques. Exploiting the random projection-based techniques [28] suggests
$(1+\epsilon)$ multiplicative approximation in running time
$O(\mathrm{nnz}(X)\cdot\text{poly}(k/\epsilon))$. This was later improved by
Clarkson and Woodruff [8] that offers the same multiplicative guarantee in a
faster running time $O(\text{nnz}(X)+(n+d)\cdot\text{poly}(k/\epsilon))$.
Again the advantage of these results is that they require only one pass over
the input but they can not perform subset selection, and also not known to be
robust.

###  2.3 Robust subspace approximation

Our subspace approximation with outliers results can be seen as an improvement
over the work due to Deshpande and Pratap [12, 11] in the sense that it
requires the lesser number passes over the dataset to offer multiplicative
approximation guarantee over the inliers. For $p=2$, they require $O(k\log k)$
passes over the datasets whereas we require only two number of passes over the
input. Both these results require the assumption on the datasets that
$\ell_{p}$ error over inliers is at least a constant fraction of $\ell_{p}$
error over all the points (see Equation (5)). Bhaskara and Kumar [5] suggest a
bicriteria approximation algorithm for subspace space approximation with
outliers for $p=2$. However, their results require a stronger assumption on
the datasets called rank-$k$ condition, discard a large number of outliers
than the optimal solution, and require an initial guess on the optimal error
over inliers for their algorithm. Moreover, they don’t provide subset
selection. Hardt and Moitra [22] considered a related problem called robust
subspace recovery and gave an efficient algorithm for the problem under a
strong assumption on the data that requires any $d$ or fewer outliers to be
linearly independent.

The MCMC sampling has also been explored in the context of $k$-means
clustering. The $D^{2}$-sampling proposed by Arthur and Vassilvitskii [2]
adaptively samples $k$ points – one point in each passes over the input, and
the sampled points give $O(\log k)$ approximation with respect to the optimal
clustering solution. The results due to [4, 3] suggest generating MCMC
sampling distribution by taking only one pass over the input that closely
approximates the desired $D^{2}$ sampling distribution, and offer close to the
optimal clustering solution.

##  3 Background

$\ell_{p}$ subspace approximation with outliers: Given a set of points
$\mathcal{X}=\\{x_{i}\\}_{i=1}^{n}\in\mathbb{R}^{d}$, an integer $1\leq k\leq
d$, $1\leq p<\infty$, and an upper bound on the fraction of outliers
$0\leq\beta\leq 1$, the problem is to find a $k$-dimensional linear subspace
$V$ that minimizes the sum of $p$-th powers of distances of the $(1-\beta)n$
points nearest to it. If $N_{\beta}(V)\subseteq[n]$ denotes the set of the
indices of the nearest $(1-\beta)n$ points to $V$ among
$x_{1},x_{2},\dotsc,x_{n}$, then we want to minimize the following:
$\sum_{i\in N_{\beta}(V)}d(x_{i},V)^{p}.$

##  4 Subspace approximation in fewer passes by MCMC sampling

We present the pseudocode of our algorithm in Algorithm 1. Our algorithm
starts with an initial subset $S_{0}$ and then uses it as a _pivot_ subset to
approximate subsequent iterations of adaptive sampling in a single pass by an
MCMC sampling procedure. In other words, $l$ iterations of adaptive sampling,
with $t$ i.i.d. points to be picked in each iteration, requires $l$ passes
over the data $\mathcal{X}$ to update the set w.r.t. which we need to do
adaptive sampling. Our MCMC sampling algorithm uses a pivot subset and a
random walk to approximate the distribution over $l$ iterations using only a
single pass, for any $l$. Using the right choice of parameters $t,l$ and the
length of the random walk $m$, we can do subset selection of near-optimal size
for $\ell_{p}$ subspace approximation without requiring a large number of
passes over the data. The number of passes required in previous randomized
algorithm for subset selection depend on $l$, and we remove this dependence by
MCMC sampling.

Input: Data set of $n$ points $\mathcal{X}\subseteq\mathbb{R}^{d}$; a positive
integer $k\leq d$; real-valued parameters $\epsilon,\alpha>0$; positive
integer parameters $t,l,m$

Output: $S_{0}\cup A_{1}\cup A_{2}\cup\dotsc\cup A_{l}$

Sample a subset $S_{0}$ of $k$ point from $\mathcal{X}$ using
$\alpha$-approximate volume sampling, i.e., the probability of picking any
subset $S$ is
$\operatorname{Pr}\left(S\right)\leq\frac{\alpha\cdot\mathrm{vol}(\Delta_{S})^{p}}{\sum_{T\;:\;\left|T\right|=k}\mathrm{vol}(\Delta_{T})^{p}},$
where $\Delta({S})$ denotes the simplex formed by the points in $S$ and the
origin.

for  _$i=1,2,\dotsc,l$_ do

Sample $x\in\mathcal{X}$ with probability $q(x)$, where
$q(x)=\dfrac{1}{2}\dfrac{d(x,\operatorname{span}\left(S_{0}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S_{0})}+\dfrac{1}{2\left|\mathcal{X}\right|}$.

Let $p(x)=\dfrac{d(x,\operatorname{span}\left(S_{0}\cup A_{1}\cup\dotsc\cup
A_{i-1}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
A_{1}\cup\dotsc\cup A_{i-1})}$

while  _$|A_{i}|\leq t$_ do

for  _$j=2,3,\ldots m$_ do

Sample $y\in\mathcal{X}$ with probability $q(y)$.

$p(y)\leftarrow\dfrac{d(y,\operatorname{span}\left(S_{0}\cup
A_{1}\cup\dotsc\cup
A_{i-1}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
A_{1}\cup\dotsc\cup A_{i-1})}$

$\mathrm{Unif}(0,1)$ be a uniform random number in $(0,1)$ interval.

if  _$\dfrac{p(y)q(x)}{p(x)q(y)} >\mathrm{Unif}(0,1)$_ then

$x\leftarrow y$

$p(x)\leftarrow p(y)$

$A_{i}\longleftarrow A_{i}\cup\\{x\\}$

Algorithm 1 Subset selection for $\ell_{p}$ subspace approximation by MCMC
sampling

###  4.1 Expected error over multiple iterations of MCMC sampling

First, let’s set up the notation required to analyze adaptive sampling as well
as the MCMC sampling in Algorithm 1. For any fixed subset
$S\subseteq\mathcal{X}$, we define

$\displaystyle\mathrm{err}_{p}(\mathcal{X},S)$
$\displaystyle=\sum_{x\in\mathcal{X}}d(x,S)^{p},$ $\displaystyle P^{(1)}(T|S)$
$\displaystyle=\prod_{x\in
T}\frac{d(x,\operatorname{span}\left(S\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S)},\qquad\text{for
any subset $T$ of size $t$},$
$\displaystyle\underset{T}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S\cup
T)\right]$
$\displaystyle=\sum_{T\;:\;\left|T\right|=t}P^{(1)}(T\;|\;S)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S\cup T).$

Given a subset $S\subseteq\mathcal{X}$, $P^{(1)}(T\;|\;S)$ denotes the
probability of picking a subset $T\subseteq\mathcal{X}$ of i.i.d. $t$ points
by adaptive sampling w.r.t. $S$. We use $P^{(l)}(T_{1:l}|S)$ to denote the
probability of picking a subset $T_{1:l}=B_{1}\cup B_{2}\cup\dotsc\cup
B_{l}\subseteq\mathcal{X}$ of $tl$ points by $l$ iterative rounds of adaptive
sampling, where in the first round we sample a subset $B_{1}$ consisting of
i.i.d. $t$ points w.r.t. $S$, in the second round we sample a subset $B_{2}$
consisting of i.i.d. $t$ points w.r.t. $S\cup B_{1}$, and so on to pick
$T_{1:l}=B_{1}\cup B_{2}\cup\dotsc\cup B_{l}$ over $l$ iterations. Similarly,
in the context of adaptive sampling, we use $T_{2:l}$ to denote
$B_{2}\cup\dotsc\cup B_{l}$. We abuse the notation
$\underset{T_{1:l}\;|\;S}{\operatorname{E}}\left[\cdot\right]$ to denote the
expectation over $T_{1:l}$ picked in $l$ iterative rounds of adaptive sampling
starting from $S$.

Given a _pivot_ subset $\tilde{S}\subseteq\mathcal{X}$ and another subset
$S\subseteq\mathcal{X}$ such that $\tilde{S}\subseteq S$, consider the
following MCMC sampling with parameters $l,t,m$ that picks $l$ subsets
$A_{1},A_{2},\dotsc,A_{l}$ of $t$ points each. $m$ denotes the number of steps
of a random walk used to pick these points. This sampling can be implemented
in a single pass over $\mathcal{X}$, for any $l,t,m$ and any given subsets
$\tilde{S}\subseteq S$. For $T_{1:l}=A_{1}\cup A_{2}\cup\dotsc\cup A_{l}$ We
use $\tilde{P}^{(l)}_{m}(T_{1:l}\;|\;S)$ to denote the probability of picking
$T_{1:l}$ as the output of the following sampling procedure. Similarly, in the
context of MCMC sampling, we use $T_{2:l}$ to denote $A_{2}\cup\dotsc\cup
A_{l}$. We abuse the notation
$\underset{T_{1:l}\;|\;S}{\operatorname{\tilde{E}}}\left[\cdot\right]$ to
denote the expectation over $T_{1:l}$ picked using the MCMC sampling procedure
starting from $S$ with a pivot subset $\tilde{S}\subseteq S$.

For $i=1,2,\dotsc,l$ do: (1) Sample $x\in\mathcal{X}$ with probability $q(x)$,
where
$q(x)=\dfrac{1}{2}\dfrac{d(x,\operatorname{span}\left(\tilde{S}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},\tilde{S})}+\dfrac{1}{2\left|\mathcal{X}\right|}$.
(2) Let $p(x)=\dfrac{d(x,\operatorname{span}\left(S\cup A_{1}\cup\dotsc\cup
A_{i-1}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S\cup A_{1}\cup\dotsc
A_{i-1})}$. (3) $A_{i}\leftarrow\emptyset$. While $\left|A_{i}\right|\leq t$
do: (a) For $j=2,3,\dotsc,m$ do: (i) Sample $y\in\mathcal{X}$ with probability
$q(y)$,
and let $p(y)=\dfrac{d(y,\operatorname{span}\left(S\cup A_{1}\cup\dotsc\cup
A_{i-1}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S\cup A_{1}\cup\dotsc\cup
A_{i-1})}$. (ii) If $\dfrac{p(y)q(x)}{p(x)q(y)}>\mathrm{Unif}(0,1)$ then
$x\leftarrow y$ and $p(x)\leftarrow p(y)$ (b) $A_{i}\leftarrow
A_{i}\cup\\{x\\}$
Output: $T_{1:l}=A_{1}\cup A_{2}\cup\dotsc\cup A_{l}$.

We require the following additional notation in our analysis of the above MCMC
sampling. We use $\tilde{P}^{(1)}_{m}(T\;|\;S)$ to denote the resulting
distribution over subsets $T$ of size $t$, when we use the above sampling
procedure with $l=1$. We define

$\displaystyle\mathrm{ind}_{p}(\mathcal{X},S)$
$\displaystyle=\mathbbm{1}\left(\mathrm{err}_{p}(\mathcal{X},S)\leq\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\right),$
$\displaystyle\underset{T}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S\cup
T)\right]$
$\displaystyle=\sum_{T\;:\;\left|T\right|=t}\tilde{P}^{(1)}_{m}(T\;|\;S)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S\cup T),$
$\displaystyle\underset{T}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S\cup
T)\right]$
$\displaystyle=\sum_{T\;:\;\left|T\right|=t}\tilde{P}^{(1)}_{m}(T\;|\;S)\leavevmode\nobreak\
\mathrm{ind}_{p}(\mathcal{X},S\cup T).$

Lemma 4.1 below shows that for any subset $S\subseteq\mathcal{X}$ that
contains the pivot subset $\tilde{S}$ used for MCMC sampling, either
$\mathrm{err}_{p}(\mathcal{X},S)$ is small compared to
$\mathrm{err}_{p}(\mathcal{X},\tilde{S})$ or the adaptive sampling
distribution w.r.t. $S$ is closely approximated in total variation distance by
the MCMC sampling procedure with the pivot subset $\tilde{S}$.

######  Lemma 4.1.

Let $\epsilon_{1},\epsilon_{2}\in(0,1)$ and $\tilde{S}\subseteq
S\subseteq\mathcal{X}$. Then for $m\geq
1+\frac{2}{\epsilon_{1}}\log\tfrac{1}{\epsilon_{2}}$, either
$\mathrm{err}_{p}(\mathcal{X},S)\leq\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$ or
$\left\|P^{(1)}(\cdot\;|\;S)-\tilde{P}^{(1)}_{m}(\cdot\;|\;S)\right\|_{TV}\leq\epsilon_{2}t$.

######  Proof 4.2.

Consider the $l=1,t=1$ case of the above MCMC sampling procedure. In this
case, the procedure outputs only one element of $\mathcal{X}$. This random
element is picked by $m$ steps of the following random walk. We first pick $x$
with probability $q(x)$, then we sample a $y$ with probability $q(y)$, we
compute $p(x),p(y)$ and sample a number uniformly at random from the interval
$(0,1)$, and if $p(y)q(x)/p(x)q(y)>\mathrm{Unif}(0,1)$, then the random walk
moves from $x$ to $y$ and updates $p(x)$ as $p(y)$. Observe that the
stationary distribution of the above random walk is the adaptive sampling
distribution w.r.t. $S$ given by
$p(x)=d(x,\operatorname{span}\left(S\right))^{p}/\mathrm{err}_{p}(\mathcal{X},S)$.
Using Corollary $1$ of [6], the total variation distance after $m$ steps of
the random walk is bounded by

$\left(1-\frac{1}{\gamma}\right)^{m-1}\leq
e^{-(m-1)/\gamma}\leq\epsilon_{2},\quad\text{where
$\gamma=\max_{x\in\mathcal{X}}\frac{p(x)}{q(x)}$}.$

The above bound is at most $\epsilon_{2}$ if we choose to run the random walk
for $m\geq 1+\gamma\log\frac{1}{\epsilon_{2}}$ steps. Now suppose
$\mathrm{err}_{p}(\mathcal{X},S)>\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$. Then, for any $x\in\mathcal{X}$

$\frac{p(x)}{q(x)}=\dfrac{\dfrac{d(x,\operatorname{span}\left(S\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},S)}}{\dfrac{1}{2}\dfrac{d(x,\operatorname{span}\left(\tilde{S}\right))^{p}}{\mathrm{err}_{p}(\mathcal{X},\tilde{S})}+\dfrac{1}{2\left|\mathcal{X}\right|}}\leq\dfrac{2\leavevmode\nobreak\
d(x,\operatorname{span}\left(S\right))^{p}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})}{d(x,\operatorname{span}\left(\tilde{S}\right))^{p}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S)}\leq\frac{2}{\epsilon_{1}},$

using $\tilde{S}\subseteq S$ and the above assumption
$\mathrm{err}_{p}(\mathcal{X},S)>\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$. Therefore,
$m>\frac{2}{\epsilon_{1}}\log\frac{1}{\epsilon_{2}}$ ensures that $m$ steps of
the random walk gives a distribution within total variation distance
$\epsilon_{2}$ from the adaptive sampling distribution for picking a single
point.

Note that for $t>1$ both the adaptive sampling and the MCMC sampling procedure
pick an i.i.d. sample of $t$ points, so the total variation distance is
additive in $t$, which means

$\left\|P^{(1)}(\cdot\;|\;S)-\tilde{P}^{(1)}_{m}(\cdot\;|\;S)\right\|_{TV}\leq\epsilon_{2}t,$

assuming $\mathrm{err}_{p}(\mathcal{X},S)>\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$. This completes the proof the lemma.

Now Lemma 4.3 analyzes the effect of starting with an initial subset $S_{0}$
and using the same $S_{0}$ as a pivot subset for doing the MCMC sampling for
$l$ subsequent iterations of adaptive sampling, where we pick $t$ i.i.d.
points in each iteration using $t$ independent random walks of $m$ steps.
Lemma 4.3 shows that the expected error for subspace approximation after doing
the $l$ iterations of adaptive sampling is not too far from the expected error
for subspace approximation after replacing the $l$ iterations with MCMC
sampling.

######  Lemma 4.3.

For any subset $S_{0}\subseteq\mathcal{X}$, any
$\epsilon_{1},\epsilon_{2}\in(0,1)$ and any positive integers $t,l,m$ with
$m\geq 1+\frac{2}{\epsilon_{2}}\log\frac{1}{\epsilon_{1}}$,

$\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\left(\epsilon_{1}+\epsilon_{2}tl\right)\mathrm{err}_{p}(\mathcal{X},S_{0}).$

######  Proof 4.4.

We show a slightly stronger inequality than the one given above, i.e., for any
$S_{0}$ such that $\tilde{S}\subseteq S_{0}$,

$\displaystyle\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\left(\epsilon_{1}\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\epsilon_{2}tl\right)\mathrm{err}_{p}(\mathcal{X},\tilde{S}).$

The special case $S_{0}=\tilde{S}$ gives the lemma. We prove the above-
mentioned stronger statement by induction on $l$. For $l=0$, the above
inequality holds trivially. Now assuming induction hypothesis, the above holds
true for $l-1$ iterations (instead of $l$) starting with any subset
$S_{1}=S_{0}\cup A\subseteq\mathcal{X}$ because $\tilde{S}\subseteq
S_{0}\subseteq S_{1}$.

$\displaystyle\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$
$\displaystyle=\underset{S_{1}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]\right]$
$\displaystyle=\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=1}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$
$\displaystyle\qquad\qquad+\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right].$ (1)

If $\mathrm{ind}_{p}(\mathcal{X},S_{1})=1$ then
$\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\leq\mathrm{err}_{p}(\mathcal{X},S_{1})\leq\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S_{0})$, so the first part of the above sum can
be bounded as follows.

$\displaystyle\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=1}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\leq\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S_{0})\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=1}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right].$ (2)

Now, the second part can be bounded as follows.

$\displaystyle\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$
$\displaystyle=\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$
$\displaystyle\leq\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\cdot$
$\displaystyle\qquad\left(\underset{T_{2:l}\;|\;S_{1}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]+\left(\epsilon_{1}\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]+\epsilon_{2}t(l-1)\right)\mathrm{err}_{p}(\mathcal{X},\tilde{S})\right)$
by applying the induction hypothesis to $(l-1)$ iterations starting from
$S_{1}$
$\displaystyle\leq\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}P^{(1)}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{2}t(l-1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})$
$\displaystyle\qquad+\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\left|\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})-P^{(1)}(S_{1}\;|\;S_{0})\right|\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$
$\displaystyle\leq\sum_{S_{1}}P^{(1)}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{2}t(l-1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})+\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\left|\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})-P^{(1)}(S_{1}\;|\;S_{0})\right|\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$ $\displaystyle\qquad+\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{2}t(l-1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})+\left\|\tilde{P}^{(1)}(\cdot\;|\;S_{0})-P^{(1)}(\cdot\;|\;S_{0})\right\|_{TV}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$ (3)
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$ $\displaystyle\qquad+\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}\;:\;\mathrm{ind}_{p}(\mathcal{X},S_{1})=0}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{2}t(l-1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})+\epsilon_{2}t\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S}),$ (4)

using Lemma 4.1 about the total variation distance between $P^{(1)}$ and
$\tilde{P}^{(1)}$ distributions. Plugging the bounds $\eqref{eq:part-1-ind}$
and $\eqref{eq:part-2-ind}$ into $\eqref{eq:parts-by-ind}$, we get

$\displaystyle\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\epsilon_{1}\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})\leavevmode\nobreak\
\sum_{S_{1}}\tilde{P}^{(1)}_{m}(S_{1}\;|\;S_{0})\leavevmode\nobreak\
\underset{T_{2:l}\;|\;S_{1}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{1}\cup
T_{2:l})\right]$ $\displaystyle\qquad+\epsilon_{2}t(l-1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})+\epsilon_{2}t\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$
$\displaystyle=\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\left(\epsilon_{1}\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{ind}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\epsilon_{2}tl\right)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S})$
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\left(\epsilon_{1}+\epsilon_{2}tl\right)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},\tilde{S}),$

which completes the proof of Lemma 4.3.

###  4.2 Near-optimal subset selection for $\ell_{2}$ subspace approximation
in $2$ passes by MCMC sampling

######  Proposition 4.5.

Let $k$ be any positive integer and let $\epsilon\in(0,1)$. Let $S_{0}$ be any
subset $S_{0}\subseteq\mathcal{X}$. If $S_{l}=S_{0}\cup T_{1:l}$ be obtained
by starting from $S_{0}$ and doing adaptive sampling in $l$ iterations, where
in each iteration we add $t$ points from $\mathcal{X}$, then we have
$\left|S_{l}\right|=\left|S_{0}\right|+tl$ and

$\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{2}(\mathcal{X},S_{0}\cup
T_{1:l})\right]\leq\left(1+\frac{2k}{t}\right)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})+\left(\frac{k}{t}\right)^{l}\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},S_{0}),$

where $V^{*}$ minimizes $\mathrm{err}_{2}(\mathcal{X},V)$ over all linear
subspaces $V$ of dimension $k$.

######  Proof 4.6.

Follows directly from Corollary 1 in [16].

Now we state a slight modification of Theorem 1.3 from [14]. The original
theorem gives $(k+1)$ approximation guarantee for exact volume sampling, in
expectation. Proposition 4.7 below modifies it to say that
$\alpha$-approximate volume sampling gives $\alpha(k+1)$ approximation
guarantee, in expectation.

######  Proposition 4.7.

(Immediate from Theorem 1.3, [14]) If $S_{0}\subseteq\mathcal{X}$ is a random
subset of size $k$ picked according to $\alpha$-approximate volume sampling
probability, i.e.,

then $\mathrm{err}_{2}(\mathcal{X},S_{0})$ is at most
$\alpha(k+1)\leavevmode\nobreak\ \mathrm{err}_{p}(\mathcal{X},V^{*})$, in
expectation, where $V^{*}$ minimizes $\mathrm{err}_{2}(\mathcal{X},V)$ over
all linear subspaces $V$ of dimension $k$..

Theorem 4.8 and Theorem 4.10 essentially show that the MCMC sampling in
Algorithm 1 requires only $2$ passes to approximately implement the multiple
passes of adaptive sampling. Moreover, using the guarantee in Lemma 4.3, we
get a nearly-optimal subset selection for the $p=2$ case of subspace
approximation in only $2$ passes.

######  Theorem 4.8.

Let $k$ be any positive integer and let $\epsilon\in(0,1)$. Let $S_{0}$ be a
subset of $k$ points sampled from $\mathcal{X}$ using $\alpha$-approximate
volume sampling for $p=2$. Let $S_{l}=S_{0}\cup T_{1:l}$ be obtained by
starting from $S_{0}$ and doing $l$ iterations of MCMC sampling, where in each
iteration we add $t$ points from $\mathcal{X}$ by running $t$ independent
random walks for $m$ steps each. Then for $t=8k/\epsilon$,
$l=\log(2\alpha(k+1)/\epsilon)/\log(8/\epsilon)$ and $m\geq
1+128k\alpha\log^{2}(2\alpha/\epsilon)/\epsilon^{2}\log(8/\epsilon)$, we have

$\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{2}(\mathcal{X},S_{0}\cup
T_{1:l})\right]\leq(1+\epsilon)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*}),$

where $V^{*}$ minimizes $\mathrm{err}_{2}(\mathcal{X},V)$ over all linear
subspaces $V$ of dimension $k$.

######  Proof 4.9.

We use the following setting of parameters $t,l,\epsilon_{1},\epsilon_{2},m$
as functions of $k,\epsilon,\alpha$.

$\displaystyle t$ $\displaystyle=\frac{8k}{\epsilon},\qquad
l=\frac{\log(2\alpha(k+1)/\epsilon)}{\log(8/\epsilon)},\qquad\epsilon_{1}=\frac{\epsilon}{8\alpha(k+1)},\qquad\text{and}$
$\displaystyle\epsilon_{2}$
$\displaystyle=\frac{\epsilon}{8tl\alpha(k+1)}=\frac{\epsilon^{2}\log(8/\epsilon)}{64k(k+1)\alpha\log(2\alpha/\epsilon)},$
$\displaystyle m$
$\displaystyle=1+\frac{2}{\epsilon_{2}}\log\frac{1}{\epsilon_{1}}=1+\frac{128k(k+1)\alpha\log^{2}(2\alpha/\epsilon)}{\epsilon^{2}\log(8/\epsilon)}$

We have

$\displaystyle\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]$
$\displaystyle\leq\underset{T_{1:l}\;|\;S_{0}}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S_{0}\cup
T_{1:l})\right]+\left(\epsilon_{1}+\epsilon_{2}tl\right)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},S_{0})$ by Lemma 4.3 and $m\geq
1+\frac{2}{\epsilon_{2}}\log\frac{1}{\epsilon_{1}}$
$\displaystyle\leq\left(1+\frac{2k}{t}\right)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})+\left(\frac{k}{t}\right)^{l}\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},S_{0})+\left(\epsilon_{1}+\epsilon_{2}tl\right)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},S_{0})$ by Proposition 4.5
$\displaystyle\leq\left(1+\frac{\epsilon}{4}\right)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})+\frac{\epsilon}{2\alpha(k+1)}\alpha(k+1)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})$
$\displaystyle\qquad\qquad+\left(\frac{\epsilon}{8\alpha(k+1)}+\frac{\epsilon}{8\alpha(k+1)}\right)\alpha(k+1)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})$ by Proposition 4.7 and plugging in
$t,l,\epsilon_{1},\epsilon_{2}$
$\displaystyle\leq\left(1+\frac{\epsilon}{4}\right)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})+\frac{\epsilon}{2}\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})+\frac{\epsilon}{4}\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*})$
$\displaystyle\leq(1+\epsilon)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*}).$

It is known (Proposition 1 in [16]) that picking a subset of size $k$ from
$\mathcal{X}$ by adaptive sampling in $k$ iterations, with $1$ point per
iteration, gives $\alpha$-approximate volume sampling with
$\alpha=k!=2^{O(k\log k)}$. Theorem 4.8 can be used to reduce the number of
passes required in [16] for a $(1+\epsilon)$-approximation from $O(k\log k)$
to $k+1$. Now we show that if we use a single-pass MCMC algorithm for
$\alpha$-approximate volume sampling for a suitable $\alpha$, then the entire
Algorithm 1 can be implemented in only two passes.

######  Theorem 4.10.

Let $k$ be any positive integer and let $\epsilon\in(0,1)$. Algorithm 1 can be
implemented in $2$ passes over $\mathcal{X}$, with $\alpha$-approximate volume
sampling to pick a subset $S_{0}$ of size $k$ taking one pass over
$\mathcal{X}$ and the remaining MCMC procedure with $S_{0}$ as its pivot
subset taking another pass. Setting $t,l,m$ as $t=8k/\epsilon$,
$l=\log(2/\epsilon)/\log(8/\epsilon)$ and $m\geq
1+128k\log^{2}(2(k+2)/\epsilon)/\epsilon^{2}\log(8/\epsilon)$, the algorithm
picks a subset of $tl=O(k\log k/\epsilon)$ points given by $T_{1:l}=A_{1}\cup
A_{2}\cup\dotsc\cup A_{l}$ such that

$\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\mathrm{err}_{2}(\mathcal{X},S_{0}\cup
T_{1:l})\right]\leq(1+\epsilon)\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},V^{*}),$

where $V^{*}$ minimizes $\mathrm{err}_{2}(\mathcal{X},V)$ over all linear
subspaces $V$ of dimension $k$. This gives a near-optimal $O(k\log
k/\epsilon)$-sized subset selection with $(1+\epsilon)$ approximation
guarantee in only $2$ passes over $\mathcal{X}$. The running time of MCMC
procedure is $d\cdot\mathrm{poly}(k/\epsilon).$

######  Proof 4.11.

Anari et al. [1] give an MCMC algorithm to sample approximately from volume
sampling. They start with any subset $S$, pick $i\in S$ and $j\notin S$
uniformly at random, and perform a lazy random walk over $k$-sized subsets,
i.e., move to $T=S\setminus\\{i\\}\cup\\{j\\}$ with probability
$\frac{1}{2}\min\\{1,\frac{\mathrm{vol}(\Delta_{T})^{2}}{\mathrm{vol}(\Delta_{S})^{2}}\\}$,
and with the remaining probability stay at $S$. They show that in
$\text{poly}(n,k,\log(1/\delta\mathrm{vol}(\Delta_{S}))$ steps of the above
random walk starting at $S$, the resulting distribution is within $\delta$
total variation distance from the exact volume sampling distribution. Thus,
using Proposition 4.7 with $\alpha=1$ and adding the error due to total
variation distance, we get that the expected error
$\mathrm{err}_{2}(\mathcal{X},S)$ at the end of
$\text{poly}(n,k,\log(1/\delta\mathrm{vol}(\Delta_{S}))$ steps of the above
random walk is at most $(k+1)\leavevmode\nobreak\
\mathrm{err}_{p}(\mathcal{X},V^{*})+\delta\max_{S\;:\;\left|S\right|=k}\mathrm{err}_{p}(\mathcal{X},S)$,
where $V^{*}$ minimizes $\mathrm{err}_{2}(\mathcal{X},V)$ over all linear
subspaces $V$ of dimension $k$. We choose $\delta$ as follows.

$\delta=\frac{1}{\kappa}=\frac{\sigma_{\min}}{\sigma_{\max}}\leq\frac{\min_{S\;:\;\left|S\right|=k}\mathrm{err}_{p}(\mathcal{X},S)}{\max_{S\;:\;\left|S\right|=k}\mathrm{err}_{p}(\mathcal{X},S)},$

where $\sigma_{\min}$ and $\sigma_{\max}$ are the minimum and the maximum
singular values, respectively, of the $n$-by-$d$ matrix whose rows are all the
points in $\mathcal{X}$, and $\kappa$ is the condition number. Then the
expected error of $\mathrm{err}_{2}(\mathcal{X},S)$ is at most
$(k+2)\leavevmode\nobreak\ \mathrm{err}_{p}(\mathcal{X},V^{*})$. Observe that
$\min_{S\;:\;\left|S\right|=k}\mathrm{vol}(\Delta_{S})^{2}\geq\sigma_{\min}^{k}$.
Note that for the above choice of $\delta$ and any $k$-sized subset
$S\subseteq\mathcal{X}$, we can upper bound
$\log(1/\delta\mathrm{vol}(\Delta_{S})^{2})$ by $O(k\log\kappa)$, where
$\kappa$ is the condition number of the $n$-by-$d$ matrix whose rows are the
points of $\mathcal{X}$. Thus, in total number of
$\text{poly}(n,k,\log\kappa)$ steps of the random walk we get an initial
subset $S_{0}$ with $\mathrm{err}_{2}(\mathcal{X},S_{0})$ upper bounded by
$(k+2)\leavevmode\nobreak\ \mathrm{err}_{2}(\mathcal{X},S^{*})$, in
expectation.

Another alternative to implement approximate volume sampling is to do a
$(1+\epsilon)$ volume-preseving random projection using only one pass over the
given data [25], and then do exact volume sampling on the projected data in
$\mathrm{poly}(k/\epsilon)$ dimensions. This gives another alternative to
obtain the initial subset $S_{0}$.

The rest of the proof using MCMC sampling algorithm starting from $S_{0}$
using the same subset as a pivot is similar to the proof of Theorem 4.8.

The running time of MCMC procedure is $O(tlm\cdot
d(tl)^{2})=d\cdot\mathrm{poly}(k/\epsilon)$, where $d\cdot(tl)^{2}$ is the
time required to project a point onto $\mathrm{span}(S)$, where $S$ is a
subset of $O(tl)$ points of dimension $d$ each.

###  4.3 $(k+1)$-pass subset selection for $\ell_{p}$ subspace approximation
by MCMC sampling

Our results can be extended in a similar manner for $p\geq 2$ by combining our
MCMC sampling algorithm with the initialization $S_{0}$ given by adaptively
sampling $k$ points in $k$ iterations, one point per iteration. Note that the
initialization takes $k$ passes over the data.

######  Theorem 4.12 (Theorem $1$ of [15]).

Let $S_{0}$ be the subset of $k$ points sampled using volume sampling stated
in line 1 of Algorithm 1. Then we have
$\underset{S}{\operatorname{E}}\left[\mathrm{err}_{p}(\mathcal{X},S)^{p}\right]\leq
k!(k+1)^{p}\leavevmode\nobreak\ \mathrm{err}_{p}(\mathcal{X},S^{*})$, where
$S^{*}=\underset{S\;:\;\left|S\right|=k}{\operatorname{argmin}}\leavevmode\nobreak\
\mathrm{err}_{2}(\mathcal{X},S)$.

##  5 $\ell_{2}$ subspace approximation with outliers in two passes by MCMC
sampling

We further extend our results for subspace approximation with outliers
problem, which is essentially finding the optimal subspace only over the
inliers. We define it formally in Section 3. Our result is an improvement of
Theorem $12$ (for $p=2$) of [12] in the sense that we reduce the number of
passes required by the adaptive sampling. Their result requires one assumption
on the input, and we state it as follows. Let
$\mathcal{X}=\\{x_{i}\\}_{i=1}^{n}$ be a set of $n$ points in $d$-dimensional
space, and $S^{*}_{I}$ is the optimal $k$-dimensional subspace over inlier set
(denoted as $I$), then

$\displaystyle\frac{\sum_{i\in
I}d(x_{i},S^{*}_{I})^{2}}{\sum_{i=1}^{n}d(x_{i},S^{*}_{I})^{2}}\geq\lambda,\qquad\text{where\leavevmode\nobreak\
}\lambda\in(0,1),\text{\leavevmode\nobreak\ is a constant.}$ (5)

We state our result as follows:

######  Theorem 5.1.

For any given set of points
$\mathcal{X}=\\{x_{i}\\}_{i=1}^{n}\in\mathbb{R}^{d}$, let $I\subseteq[n]$ be
the set of optimal $(1-\beta)n$ inliers and $S^{*}_{I}$ be the optimal
subspace over inliers that minimizes their squared distance. Let the input
satisfy the condition stated in Equation (5), and $k$ be a positive integer,
and $\epsilon\in(0,1).$ Then Algorithm 1 can be implemented in $2$ passes over
$\mathcal{X}$, with $\alpha$-approximate volume sampling to pick a subset
$S_{0}$ of size $k$ taking one pass over $\mathcal{X}$ and the remaining MCMC
procedure with $S_{0}$ as its pivot subset taking another pass. Setting
$t,l,m$ as $t=O(k/\epsilon)$, $l=O(\log(\alpha
k/\epsilon\lambda)/\log(1/\epsilon))$ and $m\geq 1+O((\alpha
k/\lambda)\log^{2}(\alpha k/\epsilon\lambda)/\epsilon^{2}\log(1/\epsilon))$,
the algorithm picks a subset of $tl=O(k^{2}\log k/\epsilon^{2})$ points given
by $T_{1:l}=A_{1}\cup A_{2}\cup\dotsc\cup A_{l}$ such that

$\underset{T_{1:l}\;|\;S_{0}}{\operatorname{\tilde{E}}}\left[\sum_{j\in
N_{\beta}(S_{0}\cup T_{1:l})}d(x_{j},S_{0}\cup
T_{1:l})^{2}\right]\leq(1+\epsilon)\leavevmode\nobreak\ \sum_{i\in
I}d(x_{i},S^{*}_{I})^{2},$

where
$S^{*}_{I}=\underset{S\;:\;\left|S\right|=k}{\operatorname{argmin}}\leavevmode\nobreak\
\sum_{i\in I}d(x_{i},S)^{2}$, and $N_{\beta}(S_{0}\cup T_{1:l})\subseteq[n]$
denotes the set of the indices of the nearest $(1-\beta)n$ points to
$(S_{0}\cup T_{1:l})$ among $x_{1},x_{2},\dotsc,x_{n}$. This gives a near-
optimal $O(k^{2}\log k/\epsilon^{2})$-sized subset selection with
$(1+\epsilon)$ approximation guarantee over inliers in only $2$ passes over
$\mathcal{X}$.

######  Proof 5.2.

Follows from Theorems $11,12$ of [12] and Theorem 4.8 of this paper.

##  6 Conclusion

We improve upon the previous work on sampling-based subspace approximation and
subset selection algorithms that require adaptive sampling, and hence,
multiple passes over the given data. This renders some of the algorithms based
on adaptive sampling less practical on large data, especially if the number of
passes required depends on the target dimension $k$. Our MCMC sampling
algorithm can significantly reduce the number of passes required in the
various applications of adaptive sampling for $\ell_{p}$ subspace
approximation and subset selection.

## References

  * [1] Nima Anari, Shayan Oveis Gharan, and Alireza Rezaei.  Monte carlo markov chain algorithms for sampling strongly rayleigh distributions and determinantal point processes.  In 29th Annual Conference on Learning Theory (COLT), volume 49, pages 103–115. PMLR, 2016.  URL: http://proceedings.mlr.press/v49/anari16.html.
  * [2] David Arthur and Sergei Vassilvitskii.  k-means++: the advantages of careful seeding.  In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007, pages 1027–1035, 2007.  URL: http://dl.acm.org/citation.cfm?id=1283383.1283494.
  * [3] Olivier Bachem, Mario Lucic, S. Hamed Hassani, and Andreas Krause.  Approximate k-means++ in sublinear time.  In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, pages 1459–1467, 2016.  URL: http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12147.
  * [4] Olivier Bachem, Mario Lucic, Seyed Hamed Hassani, and Andreas Krause.  Fast and provably good seedings for k-means.  In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 55–63, 2016.  URL: https://proceedings.neurips.cc/paper/2016/hash/d67d8ab4f4c10bf22aa353e27879133c-Abstract.html.
  * [5] Aditya Bhaskara and Srivatsan Kumar.  Low rank approximation in the presence of outliers.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA, pages 4:1–4:16, 2018.  URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2018.4, doi:10.4230/LIPIcs.APPROX-RANDOM.2018.4.
  * [6] Haiyan Cai.  Exact bound for the convergence of metropolis chains.  Stochastic Analysis and Applications, 18(1):63–71, 2000.  URL: https://doi.org/10.1080/07362990008809654, arXiv:https://doi.org/10.1080/07362990008809654, doi:10.1080/07362990008809654.
  * [7] Flavio Chierichetti, Sreenivas Gollapudi, Ravi Kumar, Silvio Lattanzi, Rina Panigrahy, and David P. Woodruff.  Algorithms for $\ell_p$ low-rank approximation.  In Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, pages 806–814, 2017.  URL: http://proceedings.mlr.press/v70/chierichetti17a.html.
  * [8] Kenneth L. Clarkson and David P. Woodruff.  Low rank approximation and regression in input sparsity time.  In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pages 81–90, 2013.  URL: https://doi.org/10.1145/2488608.2488620, doi:10.1145/2488608.2488620.
  * [9] Graham Cormode, Charlie Dickens, and David P. Woodruff.  Leveraging well-conditioned bases: Streaming and distributed summaries in minkowski p-norms.  In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, pages 1048–1056, 2018.  URL: http://proceedings.mlr.press/v80/cormode18a.html.
  * [10] Chen Dan, Hong Wang, Hongyang Zhang, Yuchen Zhou, and Pradeep Ravikumar.  Optimal analysis of subset-selection based l_p low-rank approximation.  In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2537–2548, 2019.  URL: https://proceedings.neurips.cc/paper/2019/hash/80a8155eb153025ea1d513d0b2c4b675-Abstract.html.
  * [11] Amit Deshpande and Rameshwar Pratap.  Subspace approximation with outliers.  In Computing and Combinatorics - 26th International Conference, COCOON 2020, Atlanta, GA, USA, August 29-31, 2020, Proceedings, pages 1–13, 2020.  URL: https://doi.org/10.1007/978-3-030-58150-3_1, doi:10.1007/978-3-030-58150-3\\_1.
  * [12] Amit Deshpande and Rameshwar Pratap.  Sampling-based dimension reduction for subspace approximation with outliers.  Theor. Comput. Sci., 858:100–113, 2021.  URL: https://doi.org/10.1016/j.tcs.2021.01.021, doi:10.1016/j.tcs.2021.01.021.
  * [13] Amit Deshpande and Luis Rademacher.  Efficient volume sampling for row/column subset selection.  In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 329–338, 2010.  URL: https://doi.org/10.1109/FOCS.2010.38, doi:10.1109/FOCS.2010.38.
  * [14] Amit Deshpande, Luis Rademacher, Santosh S. Vempala, and Grant Wang.  Matrix approximation and projective clustering via volume sampling.  Theory Comput., 2(12):225–247, 2006.  URL: https://doi.org/10.4086/toc.2006.v002a012, doi:10.4086/toc.2006.v002a012.
  * [15] Amit Deshpande and Kasturi R. Varadarajan.  Sampling-based dimension reduction for subspace approximation.  In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 641–650, 2007\.  URL: https://doi.org/10.1145/1250790.1250884, doi:10.1145/1250790.1250884.
  * [16] Amit Deshpande and Santosh S. Vempala.  Adaptive sampling and fast low-rank matrix approximation.  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Computation, RANDOM 2006, Barcelona, Spain, August 28-30 2006, Proceedings, pages 292–303, 2006.  URL: https://doi.org/10.1007/11830924_28, doi:10.1007/11830924\\_28.
  * [17] Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.  Relative-error CUR matrix decompositions.  SIAM J. Matrix Anal. Appl., 30(2):844–881, 2008.  URL: https://doi.org/10.1137/07070471X, doi:10.1137/07070471X.
  * [18] Alan M. Frieze, Ravi Kannan, and Santosh S. Vempala.  Fast monte-carlo algorithms for finding low-rank approximations.  J. ACM, 51(6):1025–1041, 2004.  URL: https://doi.org/10.1145/1039488.1039494, doi:10.1145/1039488.1039494.
  * [19] Mina Ghashami, Edo Liberty, Jeff M. Phillips, and David P. Woodruff.  Frequent directions: Simple and deterministic matrix sketching.  SIAM J. Comput., 45(5):1762–1792, 2016.  URL: https://doi.org/10.1137/15M1009718, doi:10.1137/15M1009718.
  * [20] Mina Ghashami and Jeff M. Phillips.  Relative errors for deterministic low-rank matrix approximations.  In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 707–717, 2014.  URL: https://doi.org/10.1137/1.9781611973402.53, doi:10.1137/1.9781611973402.53.
  * [21] Venkatesan Guruswami and Ali Kemal Sinop.  Optimal column-based low-rank matrix reconstruction.  In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, January 17-19, 2012, pages 1207–1214, 2012.  URL: https://doi.org/10.1137/1.9781611973099.95, doi:10.1137/1.9781611973099.95.
  * [22] Moritz Hardt and Ankur Moitra.  Algorithms and hardness for robust subspace recovery.  In COLT 2013 - The 26th Annual Conference on Learning Theory, June 12-14, 2013, Princeton University, NJ, USA, pages 354–375, 2013.  URL: http://proceedings.mlr.press/v30/Hardt13.html.
  * [23] Yasutoshi Ida, Sekitoshi Kanai, Yasuhiro Fujiwara, Tomoharu Iwata, Koh Takeuchi, and Hisashi Kashima.  Fast deterministic CUR matrix decomposition with accuracy assurance.  In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 4594–4603. PMLR, 13–18 Jul 2020\.  URL: http://proceedings.mlr.press/v119/ida20a.html.
  * [24] Edo Liberty.  Simple and deterministic matrix sketching.  In The 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2013, Chicago, IL, USA, August 11-14, 2013, pages 581–588, 2013.  URL: https://doi.org/10.1145/2487575.2487623, doi:10.1145/2487575.2487623.
  * [25] Avner Magen and Anastasios Zouzias.  Near optimal dimensionality reductions that preserve volumes.  In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, 11th International Workshop, APPROX 2008, and 12th International Workshop, RANDOM 2008, Boston, MA, USA, August 25-27, 2008\. Proceedings, pages 523–534, 2008.  URL: https://doi.org/10.1007/978-3-540-85363-3_41, doi:10.1007/978-3-540-85363-3\\_41.
  * [26] Michael W Mahoney.  Randomized algorithms for matrices and data.  arXiv preprint arXiv:1104.5557, 2011.
  * [27] Michael W. Mahoney and Petros Drineas.  CUR matrix decompositions for improved data analysis.  Proc. Natl. Acad. Sci. USA, 106(3):697–702, 2009.  URL: https://doi.org/10.1073/pnas.0803205106, doi:10.1073/pnas.0803205106.
  * [28] Tamás Sarlós.  Improved approximation algorithms for large matrices via random projections.  In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 143–152, 2006.  URL: https://doi.org/10.1109/FOCS.2006.37, doi:10.1109/FOCS.2006.37.
  * [29] Shusen Wang and Zhihua Zhang.  Improving CUR matrix decomposition and the nyström approximation via adaptive sampling.  J. Mach. Learn. Res., 14(1):2729–2769, 2013.  URL: http://dl.acm.org/citation.cfm?id=2567748.