Algorithm

# Learning a Latent Simplex in Input-Sparsity Time

Ainesh Bakshi
Carnegie Mellon University
<EMAIL_ADDRESS>Chiranjib Bhattacharyya
Indian Institute of Science
<EMAIL_ADDRESS>Ravi Kannan
Microsoft Research India
<EMAIL_ADDRESS>David P. Woodruff
Carnegie Mellon University
<EMAIL_ADDRESS>Samson Zhou
Carnegie Mellon University
<EMAIL_ADDRESS>
###### Abstract

We consider the problem of learning a latent $k$-vertex simplex
$\mathcal{K}\subset\mathbb{R}^{d}$, given access to
$\mathbf{A}\in\mathbb{R}^{d\times n}$, which can be viewed as a data matrix
with $n$ points that are obtained by randomly perturbing latent points in the
simplex $\mathcal{K}$ (potentially beyond $\mathcal{K}$). A large class of
latent variable models, such as adversarial clustering, mixed membership
stochastic block models, and topic models can be cast as learning a latent
simplex. Bhattacharyya and Kannan (SODA, 2020) give an algorithm for learning
such a latent simplex in time roughly $O(k\cdot\textsf{nnz}(\mathbf{A}))$,
where $\textsf{nnz}(\mathbf{A})$ is the number of non-zeros in $\mathbf{A}$.
We show that the dependence on $k$ in the running time is unnecessary given a
natural assumption about the mass of the top $k$ singular values of
$\mathbf{A}$, which holds in many of these applications. Further, we show this
assumption is necessary, as otherwise an algorithm for learning a latent
simplex would imply an algorithmic breakthrough for spectral low rank
approximation.

At a high level, Bhattacharyya and Kannan provide an adaptive algorithm that
makes $k$ matrix-vector product queries to $\mathbf{A}$ and each query is a
function of all queries preceding it. Since each matrix-vector product
requires $\textsf{nnz}(\mathbf{A})$ time, their overall running time appears
unavoidable. Instead, we obtain a low-rank approximation to $\mathbf{A}$ in
input-sparsity time and show that the column space thus obtained has small
$\sin\Theta$ (angular) distance to the right top-$k$ singular space of
$\mathbf{A}$. Our algorithm then selects $k$ points in the low-rank subspace
with the largest inner product (in absolute value) with $k$ carefully chosen
random vectors. By working in the low-rank subspace, we avoid reading the
entire matrix in each iteration and thus circumvent the
$\Theta(k\cdot\textsf{nnz}(\mathbf{A}))$ running time.

##  1 Introduction

We study the problem of learning $k$ vertices
$\mathbf{M}_{*,1},\ldots,\mathbf{M}_{*,k}$ of a latent $k$-dimensional simplex
$\mathcal{K}$ in $\mathbb{R}^{d}$ using $n$ data points generated from
$\mathcal{K}$ and then possibly perturbed by a stochastic, deterministic, or
adversarial source before given to the algorithm. In particular, the resulting
points observed as input data could be heavily perturbed so that the initial
points may no longer be discernible or they could be outside the simplex
$\mathcal{K}$. Recent work of Bhattacharyya and Kannan [BK20b] unifies several
stochastic models for unsupervised learning problems, including $k$-means
clustering [CG92, GH+96, Web03, WT10, Dua20], topic models [BJ03, SG07, BL06a,
Ble12, AGH+13a], mixed membership stochastic block models [ABFX08, MJG09,
XFS+10, FSX09, ABEF14, LAW16, FXC16] and Non-negative Matrix Factorization
[AGH+13b, GV14, Gil20] under the problem of learning a latent simplex. In
general, identifying the latent simplex can be computationally intractable.
However many special applications do not require the full generality. For
example, in a mixture model like Gaussian mixtures, the data is assumed to be
generated from a convex combination of density functions. Thus, it may be
possible to efficiently approximately learn the latent simplex given certain
distributional properties in these models.

Indeed, Bhattacharyya and Kannan showed that given certain reasonable
geometric assumptions that are typically satisfied for real-world instances of
Latent Dirichlet Allocation, Stochastic Block Models and Clustering, there
exists an $\widetilde{O}(k\cdot\textsf{nnz}(\mathbf{A}))$ 111Throughout the
paper we use the notation $\widetilde{O}$ to suppress poly-logarithmic
factors. time algorithm for recovering the vertices of the underlying simplex.
We show that, given an additional natural assumption, we can remove the
dependency on $k$ and obtain a true input sparsity time algorithm. We begin by
defining the model along with our new assumption:

######  Definition 1.1 (Latent Simplex Model).

Let $\mathbf{M}$ be a $d\times k$ matrix such that
$\mathbf{M}_{*,1},\mathbf{M}_{*,2},\ldots,\mathbf{M}_{*,k}\in\mathbb{R}^{d}$
denote the vertices of a $k$-simplex, $\mathcal{K}$. Let $\mathbf{P}$ be a
$d\times n$ matrix such that
$\mathbf{P}_{*,1},\mathbf{P}_{*,2}\ldots\mathbf{P}_{*,n}\in\mathbb{R}^{d}$ are
$n$ points in the convex hull of $\mathcal{K}$. Given $\sigma>0$, we observe a
$d\times n$ matrix $\mathbf{A}$, such that
$\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$. Further, we make the
following assumptions on the data generation process:

  1. 1.

Well-Separateness.  For all $\ell\in[k]$, $\mathbf{M}_{*,\ell}$ has non-
trivial mass in the orthogonal complement of the span of the remaining
vectors, i.e., for all $\ell\in[k]$,
$|\textrm{Proj}(\mathbf{M}_{*,\ell},\textrm{Null}(\mathbf{M}\setminus\mathbf{M}_{*,\ell}))|\geq\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$
where $\textrm{Proj}(x,U)$ denotes the orthogonal projection of $x$ to the
subspace $U$ and $\mathbf{M}\setminus\mathbf{M}_{*,\ell}$ is the matrix
$\mathbf{M}$ with the $\ell$-th column removed.

  2. 2.

Proximate Latent Points.  Given $\delta\in(0,1)$, for all $\ell\in[k]$, there
exists a set $\mathcal{S}_{\ell}\subseteq[n]$ such that
$|\mathcal{S}_{\ell}|\geq\delta n$ and for all $j\in\mathcal{S}_{\ell}$,
$\|\mathbf{M}_{*,\ell}-\mathbf{P}_{*,j}\|_{2}\leq 4\sigma/\delta$.

  3. 3.

Spectrally Bounded Perturbation. The spectrum of $\mathbf{A}-\mathbf{P}$ is
bounded, i.e., for a sufficiently large constant $c$,
$\sigma/\sqrt{\delta}\leq\alpha^{2}\min_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}/ck^{9}$.

  4. 4.

Significant Singular Values. Let
$\mathbf{A}=\sum_{i\in[d]}\sigma_{i}u_{i}v_{i}^{T}$ be the singular value
decomposition and let
$0<\phi\leq\textsf{nnz}(\mathbf{A})/(n\cdot\textrm{poly}(k))$. We assume that
for all $i\in[k]$, $\sigma_{i}>\phi\cdot\sigma_{k+1}$ and
$\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}\leq\phi\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}$.

These assumptions are natural across many interesting applications; see
Section 2 for more details. [BK20b] introduced the Well-Separateness (1),
Proximate Latent Points (2) and Spectrally Bounded Perturbation (3)
assumptions. We include an additional Significant Singular Values assumption
(4), which is crucial for obtaining a faster running time; we discuss this in
more detail below. Our main algorithmic result can then be stated as follows:

######  Theorem 1.2 (Learning a Latent Simplex in Input-Sparsity Time).

Given $k\geq 2$ and $\mathbf{A}\in\mathbb{R}^{d\times n}$ from the Latent
Simplex Model (Definition 1.1), there exists an algorithm that runs in
$\widetilde{O}\left(\textsf{nnz}(\mathbf{A})+(n+d)\textrm{poly}(k/\phi)\right)$
time to output subsets
$\mathbf{A}_{\mathcal{R}_{1}},\ldots,\mathbf{A}_{\mathcal{R}_{k}}$ such that
upon permuting the columns of $\mathbf{M}$, with probability at least
$1-1/\Omega(\sqrt{k})$, for all $\ell\in[k]$, we have
$\|\mathbf{A}_{\mathcal{R}_{\ell}}-\mathbf{M}_{*,\ell}\|_{2}\leq
300k^{4}\sigma/(\alpha\sqrt{\delta})$.

Our result implies faster algorithms for various stochastic models that can be
formulated as special cases of the Latent Simplex Model, including Latent
Dirichlet Allocation for Topic Modeling, Mixed Membership Stochastic Block
Models and Adversarial Clustering. We summarize the connections to these
applications below. We describe our algorithm and provide an outline to our
analysis; we defer all formal proofs to the supplementary material.

##  2 Connection to Stochastic Models

We first formalize the connection between the Latent Simplex Model (Definition
1.1) and numerous stochastic models. In particular, we show that topic models
like Latent Dirichlet Allocation (LDA), Stochastic Block Models and
Adversarial Clustering can be viewed as special cases of the Latent Simplex
Model. We also show how our assumptions are natural in each of these
applications.

###  2.1 Topic Models

Probabilistic Topic Models attempt to identify abstract topics in a collection
of documents by discovering latent semantic structure [BJ03, BL06b, HBB10,
ZAX12, Ble12]. Each document in the corpus is represented by a bag-of-words
vectorization with the corresponding word frequencies. The standard
statistical assumption is that the generative process for the corpus is a
joint probability distribution over both the observed and hidden random
variables. The hidden random variables can be interpreted as representative
documents for each topic. The goal is to then design algorithms that can learn
the underlying topics. The topics can be viewed geometrically as $k$ latent
vectors
$\mathbf{M}_{*,1},\mathbf{M}_{*,2},\ldots,\mathbf{M}_{*,k}\in\mathbb{R}^{d}$,
where $d$ is the size of the dictionary and $\mathbf{M}_{i,\ell}$ is the
expected frequency of word $i$ in topic $\ell$. Since each vector
$\mathbf{M}_{*,\ell}$ represents a probability distribution,
$\sum_{i}\mathbf{M}_{i,\ell}=1$. Let $\mathbf{M}$ be the corresponding
$d\times k$ matrix. One important stochastic model is Latent Dirichlet
Allocation (LDA) [BNJ03], where each document consists of $m$ words is
generated as follows :

  * •

For all $\ell\in[k]$, we pick topic weights
$\mathbf{W}_{j,\ell}\sim\textsf{Dir}(1/k)$, where $\textsf{Dir}(1/k)$ is the
Dirichlet distribution over the unit simplex. The topic distribution of
document $j$ is decided by the topic weights, $\mathbf{W}_{j,\ell}$, and given
by
$\mathbf{P}_{*,j}=\sum_{\ell\in[k]}\mathbf{W}_{j,\ell}\cdot\mathbf{M}_{*,\ell}$,
where $\mathbf{P}_{*,j}$ are latent points.

  * •

We then generate the $j$-th document with $m$ words by taking i.i.d. samples
from $\textsf{Mult}(\mathbf{P}_{*,j})$, the multinomial distribution with
$\mathbf{P}_{*,j}$ as the probability vector. The resulting document observed
is denoted by the vector $\mathbf{A}_{*,j}$, where for all $i\in[d]$
$\mathbf{A}_{i,j}=\frac{1}{m}\sum_{t=1}^{m}\mathbf{X}^{(t)}_{ij},$, such that
$\mathbf{X}^{(t)}_{ij}\sim\textsf{Bern}(\mathbf{P}_{ij})$, where
$\mathbf{X}^{(t)}_{ij}=1$ if the $i$-th word was chosen in the $t$-th draw
while generating the $j$-th document, and $0$ otherwise.

The data generation process of LDA can be viewed as a special case of the
Latent Simplex Model, where the $j$-th document is the data point
$\mathbf{A}_{*,j}$ generated from the stochastic vector $\mathbf{P}_{*,j}$, a
point in the simplex $\mathcal{K}$. The vertices of the simplex are the $k$
topic vectors $\mathbf{M}_{*,1},\ldots,\mathbf{M}_{*,k}$; the goal is then to
recover the vertices of $\mathcal{K}$. [BK20b] remark that the Well-
Separateness condition holds for LDA if we assume a Dirichlet prior on
$\mathbf{M}$. We note that while $\mathcal{K}$ is a $k$-dimensional simplex,
$d\ll k$ and the observed points need not lie inside the simplex. On the
contrary, [BK20b] show that the data often lies significantly outside of
$\mathcal{K}$. However, they show that the smoothed simplex obtained by taking
the averages of all $\delta n$ sized subsets of observed points results in a
polytope $K_{\mathcal{S}}$ that is close to $\mathcal{K}$.

We formally justify our assumptions below.

######  Lemma 2.1 (LDA as a Latent Simplex).

Given $\mathbf{A},\mathbf{P},\mathbf{M}$ following the LDA model as described
above, such that for all $\ell\in[k]$,
$\|\mathbf{M}_{*,\ell}\|_{2}=\Omega(1)$, $m,n=\Omega(\textrm{poly}(k/\alpha))$
and $\delta=c\sigma/\sqrt{k}$, assumptions (2),(3) and (4) from Definition 1.1
are satisfied with high probability.

###### Proof.

Assumptions (2) and (3) follow from Lemma 7.1 in [BK20b]. By Claim 8.1 in
[BK20b], $\sigma_{k}(\mathbf{A})\geq
c\alpha\sqrt{\delta/k}\min_{\ell}\mathbf{M}_{*,\ell}$. Each column of
$\mathbf{A}$ sums to $1$, so $\|\mathbf{A}\|^{2}_{F}=O(n)$ and
$\sigma_{k}(\mathbf{A})\geq\alpha\sqrt{\delta/k}\|\mathbf{A}\|_{F}$. Since
$\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$ by definition of $\sigma$,
and $\mathbf{P}$ consists of $n$ point in the convex hull of $k$ points and
thus $\sigma_{k+1}(\mathbf{P})=0$, we have
$\sigma_{k+1}(\mathbf{A})\leq\sigma_{k+1}(\mathbf{P})+\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}\leq\sigma\|\mathbf{A}\|_{F}$.
Thus if $\sigma\leq\alpha\sqrt{\delta}/\textrm{poly}(k)$ for a large enough
$\textrm{poly}(k)$, our Significant Singular Values assumption holds. ∎

###  2.2 Mixed Membership Stochastic Block Models

The Stochastic Block Model is a well-studied stochastic model for generating
random graphs, where the vertices are partitioned into $k$ communities and
edges within each community are more likely to occur than edges across
communities. Given communities $C_{1},C_{2},\ldots C_{k}$, there exists a
$k\times k$ symmetric latent matrix ${\bf B}$, where,
$\mathbf{B}_{\ell_{1},\ell_{2}}$ is the probability that there exists an edge
between vertices in $C_{\ell_{1}}$ and $C_{\ell_{2}}$. The MMBM can be
formalized as the following stochastic process:

  * •

For $j\in[n]$, vertex $j$ picks a probability vector
$\mathbf{W}_{*,j}\in\mathbb{R}^{k}$ representing community membership
probabilities that sum to $1$, i.e., $\mathbf{W}_{i,j}\sim\textsf{Dir}(1/k)$
for all $i\in[k]$.

  * •

For all pairs $(j_{1},j_{2})\in[n]$, vertex $j_{1}$ picks a community
$\ell_{1}$ proportional to $\textsf{Mult}(\mathbf{W}_{*,j_{1}})$ and $j_{2}$
picks a community $\ell_{2}$ proportional to
$\textsf{Mult}(\mathbf{W}_{*,j_{2}})$. The edge $(j_{1},j_{2})$ is included in
the graph with probability $\mathbf{B}_{\ell_{1},\ell_{2}}$. Since
$\sum_{\ell_{1},\ell_{2}}\mathbf{W}_{\ell_{1},j_{1}}\mathbf{B}_{\ell_{1},\ell_{2}}\mathbf{W}_{\ell_{2},j_{2}}$
represents the edge probability of the edge $(j_{1},j_{2})$, the latent
variable matrix $\mathbf{P}$ of edge probabilities can be represented as
$\mathbf{P}=\mathbf{W}^{T}\mathbf{B}\mathbf{W}^{T}$.

However, our reduction is not straightforward since now ${\bf P}$ depends
quadratically on ${\bf W}$ and the only polynomial time algorithms for ${\bf
B}$ directly rely on semidefinite programming. Further, they require non-
degeneracy assumptions in order to compute a tensor decomposition provably in
polynomial time [AGHK14, HS17]. However, we can pose the problem of recovery
of the $k$ underlying communities differently and first pick at random a
subset $V_{1}\subset[n]$ of $d$ vertices and represent the $\ell$-th community
by a $d$-dimensional vector that represents the probabilities of vertices in
$[n]\setminus V_{1}$ belonging to community $\ell$ and having an edge with
each of the $d$ vertices in $V_{1}$. We now define $\mathbf{W}_{(1)}$ to be a
$k\times d$ matrix representing the fractional membership of weights of
vertices in $V_{1}$ and $\mathbf{W}_{(2)}$ to be the analogous $k\times n$
matrix for vertices in $[n]\setminus V_{1}$. Observe that the probability
matrix $\mathbf{P}$ can now be represented as
$\mathbf{W}^{T}_{(1)}\mathbf{B}\mathbf{W}_{(2)}$.

The reduction to the Latent Simplex Model can now be stated as follows: given
a data matrix $\mathbf{A}$ which is the adjacency matrix of the community
graph, and the latent variable matrix $\mathbf{P}$, recover the simplex ${\bf
M}=\mathbf{W}_{(1)}^{T}\mathbf{B}$. Further, [ABFX08] assumes that each column
of ${\bf W}_{(2)}$ is picked from the Dirichlet distribution with parameter
$1/k$. Combined with tools from random matrix theory [Ver10], [BK20b] (Lemma
7.2) shows that the Proximate Latent Points and Spectrally Bounded assumptions
hold for Stochastic Block Models. As for the Significant Singular Values
assumption, it is satisfied when $\sigma$ is a small enough polynomial in $k$.

##### Justifying Significant Singular Values.

We give the following further justification for assumption (4) in Section 6: a
faster algorithm only using the assumptions appearing in [BK20b] would imply
an algorithmic breakthrough for spectral low-rank approximation and partially
resolve the first open question of [Woo14].

######  Theorem 2.2 (Spectral LRA and Learning a Simplex (informal)).

There exists a distribution over instances such that learning a latent simplex
in $o(nnz(\mathbf{A})\cdot k)$ time with good probability implies a constant
factor spectral low-rank approximation algorithm in the same running time.

###  2.3 Adversarial Clustering

We consider clustering problems that arise naturally from stochastic mixture
models such as Gaussian, Mallows, categorical and so on [SK01, VW04, LB11,
CSV17, DKS18, LM18]. We can then formulate such a clustering problem in the
Latent Simplex Model as follows: Given $n$ data points
$\mathbf{A}_{*,1},\mathbf{A}_{*,2},\ldots,\mathbf{A}_{*,n}\in\mathbb{R}^{d}$,
such that the data is a mixture of $k$ distinct clusters,
$\mathbf{C}_{1},\mathbf{C}_{2},\ldots,\mathbf{C}_{k}$, with means
$\mathbf{M}_{*,1},\mathbf{M}_{*,2},\ldots,\mathbf{M}_{*,k}$, the goal is to
approximately learn the means. Further, we can set the $n$ latent vectors
$\mathbf{P}_{*,j}$ to denote the mean of the cluster point $\mathbf{A}_{*,j}$
belongs to, and thus
$\mathbf{P}_{*,j}\in\\{\mathbf{M}_{*,1},\mathbf{M}_{*,2},\ldots,\mathbf{M}_{*,k}\\}$.
Prior work of [KK10] and [AS12] shows that if the minimum cluster size if
$\delta n$ and for all $\ell\neq\ell^{\prime}$,
$\|\mathbf{M}_{*,\ell}-\mathbf{M}_{*,\ell^{\prime}}\|\geq
ck\frac{\sigma}{\sqrt{\delta}}$ the $\mathbf{M}_{*,\ell}$ can be found within
error $O(\sqrt{k}\sigma/\sqrt{\delta})$.

However, the aforementioned algorithms are not robust to adversarial
perturbations. Therefore, we describe the perturbations we can handle in the
Latent Simplex Model. The adversarial model is the same as the one considered
in [BK20b]. The adversary is allowed to selected a subset $S_{\ell}$ of each
cluster $\mathbf{C}_{\ell}$ of cardinality at most $\delta n$ and perturb each
point $\mathbf{A}_{*,j}$ for $j\in S_{\ell}$ by $\Delta_{j}$ such that :

  * •

$\mathbf{P}_{*,j}+\Delta_{j}$ is still in the Convex Hull of $\text{
}\mathbf{M}_{*,1},\mathbf{M}_{*,2},\ldots,\mathbf{M}_{*,k}$

  * •

The norm of the perturbation is bounded, i.e., $|\Delta_{j}|_{2}\leq
4\sigma/\sqrt{\delta}$.

Intuitively, the adversary can move a $1-\delta$ fraction of the data points
in each cluster an arbitrary amount towards the convex hull of the means of
the remaining clusters. For the remaining $\delta n$, the perturbation should
have norm at most $O(\sigma/\sqrt{\delta})$. The goal is to still learn the
means $\mathbf{M}_{*,\ell}$ approximately. [BK20b] shows that the
aforementioned model satisfies Well-Separateness, Proximate Latent Points and
Spectrally Bounded Perturbations assumptions. The proof for the Significant
Singular Values assumption follows from Lemma 2.1. We note that there has been
a flurry of recent progress on adversarial clustering in the strong
contamination model, where the input data points are sampled from a mixture of
Gaussians distribution and the adversary can corrupt a small fraction of the
samples arbitrarily [DKS18, HL18, KSS18, DHKK20, BK20a]. In our setting, there
is no distribution assumption on the data points but the adversary is
constrained as the norm of the perturbation is bounded.

##  3 Preliminaries

We use $n,d,$ and $k$ to denote the number of data points, the number of
dimensions of the space and the number of vertices of $\mathcal{K}$
respectively. We use the notation $\mathbf{A}_{*,j}$ to denote the $j$-th
column of matrix ${\bf A}$. For $\mathbf{A}\in\mathbb{R}^{d\times n}$ with
rank $r$, its singular value decomposition, denoted by
$\texttt{SVD}(\mathbf{A})=\mathbf{U}\mathbf{\Sigma}\mathbf{V}^{T}$, guarantees
that $\mathbf{U}$ is a $d\times r$ matrix with orthonormal columns,
$\mathbf{V}^{T}$ is an $r\times n$ matrix with orthonormal rows and
$\mathbf{\Sigma}$ is an $r\times r$ diagonal matrix. The diagonal entries of
$\mathbf{\Sigma}$ are the singular values of $\mathbf{A}$, denoted by
$\sigma_{1}\geq\sigma_{2}\geq\ldots\geq\sigma_{r}$. Given an integer $k\leq
r$, we define the truncated singular value decomposition of $\mathbf{A}$ that
zeros out all but the top $k$ singular values of $\mathbf{A}$, i.e.,
$\mathbf{A}_{k}=\mathbf{U}\mathbf{\Sigma}_{k}\mathbf{V}^{T}$, where
$\mathbf{\Sigma}_{k}$ has only $k$ non-zero entries along the diagonal. It is
well-known that the truncated SVD computes the best rank-$k$ approximation to
$\mathbf{A}$ under the Frobenius norm, i.e.,
$\mathbf{A}_{k}=\min_{\textrm{rank}(\mathbf{X})\leq
k}\|\mathbf{A}-\mathbf{X}\|_{F}$. Given an orthonormal basis $\mathbf{U}$ for
a subspace, we use $\mathbf{P}_{\mathbf{U}}=\mathbf{U}\mathbf{U}^{T}$ to
denote the projection matrix corresponding to the subspace. We consider the
following notion of subspace distance:

######  Definition 3.1 ($\sin\Theta$ Distance).

For any two subspaces $\mathbf{R}$, $\SS$ of $\mathbb{R}^{d}$, the
$\sin\Theta$ distance between $\mathbf{R}$ and $\SS$ is defined as

$\begin{split}\sin\Theta(\mathbf{R},\SS)=\underset{u\in\mathbf{R}}{\max}\,\underset{v\in\SS}{\min}\sin\theta(u,v)=\underset{u\in\mathbf{R},|u|=1}{\max}\underset{v\in\SS}{\min}\|u-v\|.\end{split}$

We use the notion of spectral low-rank approximation to obtain a compact
representation of the input and compute matrix-vector products efficiently. We
also require the notion of mixed spectral-Frobenius low-rank approximation.
This guarantee is weaker than spectral-low rank approximation but admits
faster algorithms and has been recently used in several sublinear time
algorithms [MW17, BCW20].

######  Definition 3.2 (Spectral Low-rank Approximation, Spectral-Frobenius
Low-rank Approximation).

Given a matrix $\mathbf{A}$, an integer $k$ and $\epsilon>0$, a rank-$k$
matrix $\mathbf{B}$ satisfies a relative-error spectral low-rank approximation
guarantee if
$\|\mathbf{A}-\mathbf{B}\|^{2}_{2}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}$.
$\mathbf{B}$ satisfies a mixed spectral-Frobenius low-rank approximation
guarantee if

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

##  4 Technical Overview

In this section, we provide an overview of our algorithmic techniques and
discuss the main challenges we overcome to obtain an input-sparsity time
algorithm.

##### Our Techniques.

The starting point in [BK20b] is that the smoothened polytope, obtained by
averaging points in the data matrix $\mathbf{A}$ is itself close to the latent
points in the convex hull of $\mathcal{K}$ in operator norm. This fact is
captured by the following lemma:

######  Lemma 4.1 (Subset Smoothing).

For any $\mathcal{S}\subset[n]$, let $\mathbf{A}_{\mathcal{S}}$ be a vector
obtained by averaging the columns of $\mathbf{A}$ indexed by $\mathcal{S}$ and
define $\mathbf{P}_{\mathcal{S}}$ similarly. Then for
$\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$, we have
$\|\mathbf{A}_{\mathcal{S}}-\mathbf{P}_{\mathcal{S}}\|_{2}\leq\sigma\sqrt{n/|\mathcal{S}|}$.

Our main insight is that we can approximately optimize a linear function on
the smoothed polytope by working with a rank-$k$ spectral approximation to
$\mathbf{A}$ instead. Geometrically, this implies that while the smoothed
polytope is perhaps $d$-dimensional, projecting it onto the $k$-dimensional
space spanned by the top-$k$ singular values of the data matrix $\mathbf{A}$
suffices to recover the latent $k$-simplex, $\mathcal{K}$. This is surprising
since the data matrix can contain points significantly far from the latent
polytope. Further, this approach presents several challenges: we do not have
access to the left singular space of $\mathbf{A}$ and even if we are provided
this subspace exactly, it is unclear why it spans a set of points that
approximate vertices of $\mathcal{K}$. Finally, the points obtained by
smoothing the projected polytope have no immediate relation to points in the
smoothed high-dimensional polytope considered by [BK20b].

We would like to begin by computing a spectral low-rank approximation
(Definition 3.2) for $\mathbf{A}$. Since a low-rank approximation to
$\mathbf{A}$ can be represented in factored form $\mathbf{Y}\mathbf{Z}^{T}$,
where $\mathbf{Y}$ is $d\times k$ and $\mathbf{Z}^{T}$ is $k\times n$, any
matrix-vector product of the form $\mathbf{Y}\mathbf{Z}^{T}\cdot x$ only
requires $(n+d)k$ time. Thus optimizing a linear function $k$ times over a
smoothed low-rank polytope requires only $(n+d)k^{2}$ time, circumventing the
previous bound of $k\cdot\textsf{nnz}(\mathbf{A})$. However, the best known
algorithm for spectral low-rank approximation (Theorem 1 in [MM15]) requires
$\widetilde{O}(\textsf{nnz}(\mathbf{A})\cdot k/\sqrt{\epsilon})$ time and thus
provides no improvement. A natural direction to pursue is then to compute a
Frobenius low-rank approximation (which requires $\textsf{nnz}(\mathbf{A})$
time) for $\mathbf{A}$ and use this as our proxy. However, a Frobenius low-
rank approximation is too coarse to obtain a subspace that is close to the
top-$k$ singular vectors of $\mathbf{A}$.

Instead we compute a mixed spectral-Frobenius low-rank approximation (see
Definition 3.2) that runs in $O(\textsf{nnz}(A)+dk^{2})$ time, but the
resulting error guarantee is weaker. In particular, it incurs an additive
$\epsilon\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}/k$ term. Here, we use the
assumption we introduced (the Significant Singular Value assumption) to show
that the low-rank matrix obtained from this algorithm also satisfies a
relative-error spectral low-rank approximation guarantee. The next challenge
is that the aforementioned guarantee only bounds the spectral norm of
$\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}$ in terms of the $(k+1)$-st singular
value of $\mathbf{A}$. This guarantee does not relate how close the subspaces
spanned by the columns and rows of the low-rank approximation are to the
top-$k$ singular space of $\mathbf{A}$.

A key technical contribution of our work is thus to prove that the subspaces
obtained via spectral low-rank approximation are close to the true left and
right top-$k$ singular space in angular ($\sin\Theta$) distance. We note that
such a guarantee is crucial to approximately optimize a linear function over
$\mathbf{A}$. Further, this result provides an intriguing connection between
spectral low-rank approximation and power iteration. It is well known that
power iteration suffices to obtain a subspace that is close to the top-$k$
subspace of a matrix in $\sin\Theta$ distance, which at first glance appears
much stronger than spectral low-rank approximation. However, our work implies
that it suffices to compute a spectral low-rank approximation, which provides
a succinct representation of the data matrix and can be computed faster than
power iteration in several natural settings.

Input: A matrix $\mathbf{A}\in\mathbb{R}^{d\times n}$, integer $k$, and
$\epsilon>0$. 1. Using the algorithm from Lemma 5.1, compute rank-$k$ matrices
$\mathbf{Y},\mathbf{Z}$ such that $\mathbf{Y}\mathbf{Z}^{T}$ is a spectral
low-rank approximation to $\mathbf{A}$, i.e.,
$\|\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}\|^{2}_{2}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}$.
2. Let $\mathcal{S}=\\{\emptyset\\}$. For each $t\in[k]$, (a) Let
$\mathbf{U}_{t}$ be an orthonormal basis for the vectors in $\mathcal{S}$. (b)
Compute the projection matrix
$\mathbf{P}_{t}=\mathbf{U}_{t}\mathbf{U}_{t}^{T}$ that projects onto the row
span of $\mathcal{S}$. (c) Let $g\sim\mathcal{N}(0,\mathbf{I}_{k})$ and let
${\bf
u}_{t}=g\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{t})\mathbf{Y}\mathbf{Z}^{T}$
be a random vector in $\mathbb{R}^{n}$. Compute $\mathcal{R}_{t}\subset[n]$, a
subset of $\delta n$ indices corresponding to the largest coordinates of ${\bf
u}_{t}$ in absolute value. (d) Let $\mathbf{A}_{\mathcal{R}_{t}}$ be the
average of the columns of $\mathbf{A}$ indexed by $\mathcal{R}_{t}$. Update
$\mathcal{S}=\mathcal{S}\cup\mathbf{A}_{R_{t}}$. Output: The set of vectors
$\mathbf{A}_{{\mathcal{R}_{1}}},\mathbf{A}_{\mathcal{R}_{2}},\ldots,\mathbf{A}_{\mathcal{R}_{k}}$
as our approximation to the vertices of the latent $k$-simplex $\mathcal{K}$.

In the context of learning the latent simplex, given a spectral low-rank
approximation, $\mathbf{Y}\mathbf{Z}^{T}$, we first restrict to the column
span of $\mathbf{Y}$, which w.l.o.g. has orthonormal columns, and iteratively
generate $k$ vectors in this subspace. In the first iteration, we generate a
random vector $g\mathbf{Y}^{T}$ and compute
$g\mathbf{Y}^{T}\mathbf{Y}\mathbf{Z}^{T}$. We then consider the largest
$\delta n$ indices of $g\mathbf{Y}^{T}\mathbf{Y}\mathbf{Z}^{T}$. While the
resulting vector does not have strong provable guarantees, we show that
averaging the columns of $\mathbf{A}$ corresponding to these indices results
in a vector, $\mathbf{A}_{\mathcal{R}_{1}}$, which intuitively corresponds to
efficiently optimizing a linear function over a low-rank approximation to the
smoothened polytope, where the smoothened polytope is obtained by averaging
over all subsets of $\delta n$ data points. Our next contribution is to show
that $\mathbf{A}_{\mathcal{R}_{1}}$ obtained by the aforementioned algorithmic
process is indeed close to a vertex of $\mathcal{K}$.

To obtain an approximation to the remaining vertices of $\mathcal{K}$, we
consider the following iterative process: in the $t$-th iteration, consider
the subspace $\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{t})$, where
$(\mathbf{I}-\mathbf{P}_{t})$ is the projection onto the orthogonal complement
of the span of
$\mathbf{A}_{\mathcal{R}_{1}},\mathbf{A}_{\mathcal{R}_{2}}\ldots\mathbf{A}_{\mathcal{R}_{t-1}}$.
Then generate a random vector $g\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{t})$,
and compute the largest $\delta n$ coordinates of
$g\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{t})\mathbf{Y}\mathbf{Z}^{T}$. Average
the corresponding columns of $\mathbf{A}$ to obtain
$\mathbf{A}_{\mathcal{R}_{t}}$ and output this vector. We prove that after
iterating $k$ times, the vectors
$\mathbf{A}_{\mathcal{R}_{1}},\mathbf{A}_{\mathcal{R}_{1}},\ldots\mathbf{A}_{\mathcal{R}_{k}}$
approximate all the vertices of the latent simplex $\mathcal{K}$ within the
desired accuracy and running time.

In contrast, prior work of [BK20b] uses power iteration to approximate the
left top-$k$ singular space $\mathbf{U}_{k}$ of $\mathbf{A}$ using a subspace
$\widehat{\mathbf{V}}$ that is $\textrm{poly}(\alpha/k)$ close in $\sin\Theta$
distance. Each step of the power iteration uses
$O(\textsf{nnz}(\mathbf{A})+dk^{2})$ time and is repeated $\log(d)$ times.
Next, they pick a random vector $u_{1}$ in the subspace spanned
$\widehat{\mathbf{V}}$ and compute
$\mathbf{A}_{\mathcal{R}_{1}}=\operatorname*{argmax}_{\mathcal{S}:|\mathcal{S}|=\delta
n}|u_{1}\cdot\mathbf{A}_{\mathcal{S}}|$, using the resulting vector as an
approximation to some vertex $\mathbf{M}_{*,1}$.

They then repeat the above algorithm $k$ times and in the $i$-th iteration,
they pick $u_{i}$ to be a uniformly random direction in the $k-i$ dimensional
subspace constructed as follows: let $\widetilde{\mathbf{V}}_{i-1}$ be an
orthonormal basis for
$\mathbf{A}_{\mathcal{R}_{1}},\mathbf{A}_{\mathcal{R}_{2}},\ldots,\mathbf{A}_{\mathcal{R}_{i-1}}$.
Intuitively, this corresponds to sampling a random vector from the subspace
orthogonal to the set of vertex approximations picked thus far. The resulting
$k$ vectors $\mathbf{A}_{\mathcal{R}_{1}},\ldots,\mathbf{A}_{\mathcal{R}_{k}}$
are the approximation to the vertices of the latent simplex. Since they
directly optimize over the smoothened polytope, the correctness analysis is
more straightforward.

However, each iteration of the algorithm requires optimizing a linear function
over the smoothened polytope and in particular requires computing
$u_{i}\cdot\mathbf{A}$, and thus, the overall running time is dominated by
$k\cdot\textsf{nnz}(\mathbf{A})$. Since the latent simplex satisfies the Well-
Separateness condition, the inner product with a random direction is maximized
by a unique vertex. Intuitively, it appears necessary to project away from the
set of vectors obtained up to the $i$-th iteration in order to learn new
vertices of $\mathcal{K}$. The inherently iterative nature of the algorithm
combined with matrix-vector product lower bounds indicates that the new
algorithmic ideas we introduce are in fact necessary.

##  5 Full Analysis

In this section, we analyze Algorithm 4 and show that it outputs a set of $k$
vectors that approximate the vertices of the latent simplex $K$. Formally, the
main theorem we prove is as follows:

Theorem 1.2 (Restated.) Given input data $\mathbf{A}$ from the Latent Simplex
Model, there exists Algorithm 4 that takes
$\widetilde{O}\left(\textsf{nnz}(\mathbf{A})+(n+d)\textrm{poly}(k)\right)$
time to output $k$ vectors $\mathcal{R}_{1},\ldots,\mathcal{R}_{k}$ such that
upon permuting the columns of $\mathbf{M}$, for all $\ell\in[k]$, we have

$\|\mathcal{R}_{\ell}-\mathbf{M}_{*,\ell}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}},$

with probability at least $1-\frac{1}{\Omega(\sqrt{k})}$.

We start with a spectral low-rank approximation for $\mathbf{A}$. We then use
the right factor as an approximation to
$\mathbf{\Sigma}_{k}\mathbf{V}_{k}^{T}$ and the left factor as an
approximation to $\mathbf{U}_{k}$.

######  Lemma 5.1.

(Input-Sparsity Spectral LRA [CEM+15, CMM17].) Given a matrix
$\mathbf{A}\in\mathbb{R}^{d\times n}$, $\epsilon,\delta>0$ and
$k\in\mathbb{N}$, there exists an algorithm that outputs matrices
$\mathbf{Y},\mathbf{Z}$, such that with probability at least $1-\delta$,
$\|\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}\|^{2}_{2}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$,
in time
$\widetilde{O}\left(\textsf{nnz}(\mathbf{A})+(n+d)\textrm{poly}(k/\epsilon\delta)\right)$.

Under the Significant Singular Values condition (4), setting $\epsilon=\phi$
in Lemma 5.1 implies with probability $99/100$,

$\frac{1}{\textrm{poly}(k)}\sum^{n}_{i=k+1}\sigma^{2}_{i}=\frac{1}{\textrm{poly}(k)}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}\leq\sigma^{2}_{k+1}=\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}$
(1)

and thus $\|\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}\|^{2}_{2}\leq
2\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}$. Further, the aforementioned lemma
implies such a matrix $\mathbf{Y}\mathbf{Z}^{T}$ can be computed in
$\widetilde{O}\left(\textsf{nnz}(\mathbf{A})+(n+d)\textrm{poly}(k/\phi)\right)$
time. Thus the Well-Separateness condition immediately implies that the
algorithm from Lemma 5.1 is a spectral low-rank approximation.

Next, we show that if $\mathbf{Y}\mathbf{Z}^{T}$ is a good rank $k$ spectral
approximation to $\mathbf{A}$, then the subspace spanned by the columns of
$\mathbf{Y}$ must be close to the column span of $\mathbf{U}_{k}$, the top-$k$
left singular vectors of $\mathbf{A}$. In fact, the subspace $\mathbf{Y}$
obtained via spectral low-rank approximation is a good approximation to the
subspace $\mathbf{U}_{k}$ in angular distance. The appropriate measure of
angular distance between subspaces can be formalized as the principal angle
between the subspaces and the corresponding $\sin\Theta$ function. Wedin
[Wed72] bounded the $\sin\Theta$ between the SVD subspace of a matrix and the
SVD subspace of a slight perturbation of the matrix.

######  Theorem 5.2 (Wedin’s $\sin\Theta$ theorem [Wed72]).

Let $\mathbf{R},\SS\in\mathbb{R}^{d\times n}$ and $0<m\leq\ell$ be integers.
Let $\mathbf{R}_{m}$ and $\mathcal{S}\sigma_{\ell}$ denote the subspaces
spanned by the top $m$ singular vectors of $\mathbf{R}$ and top $\ell$
singular vectors of $\SS$, respectively. Suppose
$\gamma=\sigma_{m}(\mathbf{R})-\sigma_{\ell+1}(\SS)$. Then

$\sin\Theta(\mathbf{R}_{m},\mathcal{S}\sigma_{\ell})\leq\frac{\|\mathbf{R}-\SS\|_{2}}{\gamma}.$

Bhattacharyya and Kannan [BK20b] use Wedin’s $\sin\Theta$ theorem to measure
the distance between the subspace $\mathbf{U}_{k}$ spanned by the top $k$ left
singular vectors of $\mathbf{A}$ and the subspace returned by their iterative
subspace power method. Since we create the sketch $\mathbf{Y}$ for
$\mathbf{U}_{k}$, we would instead like to argue that $\mathbf{Y}$ and
$\mathbf{U}_{k}$ are close in $\sin\Theta$ distance.

######  Lemma 5.3 (Proximity of Subspace Projections).

Let $\mathbf{Y}$ be defined as in Algorithm 4 and let $\mathbf{U}_{k}$ be the
subspace spanned by the top $k$ left singular vectors of $\mathbf{A}$. Let
$\mathbf{P}_{\mathbf{Y}}$ and $\mathbf{P}_{\mathbf{U}_{k}}$ be the $d\times d$
projection matrices onto the row span of $\mathbf{Y}$ and $\mathbf{U}_{k}$.
Then
$\|\mathbf{P}_{\mathbf{Y}}-\mathbf{P}_{\mathbf{U}_{k}}\|_{2}\leq\frac{1}{1000k^{10}}$.

###### Proof.

Suppose by way of contradiction that
$\|\mathbf{P}_{\mathbf{Y}}-\mathbf{P}_{\mathbf{U}_{k}}\|_{2}\geq\frac{1}{1000k^{10}}$.
Note that since $\mathbf{Y}$ and $\mathbf{U}_{k}$ are each orthonormal
matrices with rank $k$, then

$\|\mathbf{U}_{k}\mathbf{U}_{k}^{T}-\mathbf{Y}\mathbf{Y}^{T}\|_{F}^{2}\geq\|\mathbf{U}_{k}\mathbf{U}_{k}^{T}-\mathbf{Y}\mathbf{Y}^{T}\|_{2}^{2}\geq\frac{1}{(1000k^{10})^{2}}$

so that

$\begin{split}\|\mathbf{U}_{k}\mathbf{U}_{k}^{T}-\mathbf{Y}\mathbf{Y}^{T}\|_{F}^{2}&=\|\mathbf{U}_{k}\|_{F}^{2}+\|\mathbf{Y}\|_{F}^{2}-2\|\mathbf{U}_{k}\mathbf{Y}^{T}\|_{F}^{2}\\\
&=2k-2\|\mathbf{U}_{k}\mathbf{Y}^{T}\|_{F}^{2}\geq\frac{1}{(1000k^{10})^{2}}\end{split}$

Hence, $\|\mathbf{U}_{k}\mathbf{Y}^{T}\|_{F}^{2}\leq
k-\frac{1}{(1000k^{10})^{2}}$. Now we would like to show for the sake of
contradiction that $\|\mathbf{A}-\mathbf{P}_{\mathbf{Y}}\mathbf{A}\|_{2}$ is
large. Thus, for the singular value decomposition
$\mathbf{A}=\mathbf{U}\Sigma\mathbf{V}^{T}$, we write

$\begin{split}\|\mathbf{A}-\mathbf{P}_{\mathbf{Y}}\mathbf{A}\|_{2}&=\|\mathbf{U}^{T}\Sigma-\mathbf{Y}\mathbf{Y}^{T}\mathbf{U}^{T}\Sigma\|_{2}\\\
&\geq\|\mathbf{U}_{k}\mathbf{U}^{T}\Sigma-\mathbf{U}_{k}\mathbf{Y}\mathbf{Y}^{T}\mathbf{U}^{T}\Sigma\|_{2}\end{split}$

since $\|\mathbf{U}_{k}\|_{2}\leq\|\mathbf{U}\|_{2}\leq 1$. Thus, there exist
matrices $\mathbf{C}_{1},\mathbf{C}_{2}$ such that

$\mathbf{U}_{k}\mathbf{U}^{T}\Sigma-\mathbf{U}_{k}\mathbf{Y}\mathbf{Y}^{T}\mathbf{U}^{T}\Sigma=\begin{bmatrix}\mathbf{C}_{1}&\mathbf{C}_{2}\end{bmatrix}\begin{bmatrix}\Sigma_{k}&0\\\
0&\Sigma_{n-k}\\\ \end{bmatrix},$

where $\Sigma_{k}$ is the diagonal matrix consisting of the top $k$ singular
values of $\mathbf{A}$ and $\Sigma_{n-k}$ is the diagonal matrix consisting of
the bottom $n-k$ singular values of $\mathbf{A}$. Now we know that one of the
top $k$ eigenvalues of
$\mathbf{U}_{k}^{T}\mathbf{Y}\mathbf{Y}^{T}\mathbf{U}_{k}$ is at most
$1-\frac{1}{(1000k^{10})^{2}}$. Thus, one of the top $k$ eigenvalues of
$\mathbf{I}_{k}-\mathbf{C}_{1}$ is at least $\frac{1}{(1000k^{10})^{2}}$. In
particular, let $\lambda$ be such an eigenvalue and let ${\bf x}$ be the
corresponding unit eigenvector of $\mathbf{I}-\mathbf{C}_{1}$. Then we have

$\displaystyle\|\mathbf{U}_{k}\mathbf{U}^{T}\Sigma-\mathbf{U}_{k}\mathbf{Y}\mathbf{Y}^{T}\mathbf{U}^{T}\Sigma\|_{2}$
$\displaystyle\geq\|(\mathbf{I}-\mathbf{C}_{1})\Sigma_{k}{\bf
x}\|_{2}\geq\sigma_{k}(\mathbf{A})\lambda\geq\frac{1}{(1000k^{10})^{2}}\sigma_{k}(\mathbf{A}).$

Since the Significant Singular Values assumption implies that
$\frac{1}{(1000k^{10})^{2}}\sigma_{k}(\mathbf{A})>(1+\epsilon)\sigma_{k+1}(\mathbf{A})$,
this implies that
$\|\mathbf{A}-\mathbf{P}_{\mathbf{Y}}\mathbf{A}\|_{2}>(1+\epsilon)\sigma_{k+1}(\mathbf{A})$,
which contradicts the assumption that $\mathbf{Y}$ is a good low-rank
approximation to $\mathbf{A}$. Thus we have
$\|\mathbf{P}_{\mathbf{Y}}-\mathbf{P}_{\mathbf{U}_{k}}\|_{2}\leq\frac{1}{1000k^{10}}$,
as desired. ∎

Our analysis proceeds via induction on the number of iterations performed by
the algorithm. Suppose our algorithm has selected $t$ points from our
approximation of the top $k$ subspace and these points are reasonably close to
$i$ points of the $k$-simplex. In the $(t+1)$-st iteration, we again bound the
$\sin\Theta$ distance between $\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{t})$,
which corresponds to our approximation of the top $k$ subspace projected away
from the selected vectors, and the actual $k$-simplex projected away from the
corresponding points closest to our selected vectors. This argues that we can
continue selecting random vectors in the subspace spanned by
$\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{t})$ as a close approximation to random
vectors in $\mathbf{M}(\mathbf{I}-\mathbf{P}_{t})$.

We first bound the $k$-th singular values of the simplex vertices
($\mathbf{M}$) and latent variables ($\mathbf{P}$), leveraging the Well-
Separateness and Spectrally Bounded Perturbations assumptions.

######  Lemma 5.4 (Claim 8.1 in [BK20b]).

If the underlying points $\mathbf{M}$ follow the Well-Separateness and
Spectrally Bounded Perturbation assumptions, then

$\sigma_{k}(\mathbf{M})\geq\frac{1000k^{8.5}}{\alpha^{2}}\frac{\sigma}{\sqrt{\delta}},\qquad\sigma_{k}(\mathbf{P})\geq\frac{995k^{8.5}\sqrt{n}}{\alpha^{2}}\sigma.$

We can then upper bound $\sin\Theta$ distance between $\mathbf{Y}$ and
$\mathbf{U}_{k}$ as follows:

######  Corollary 5.5.

Let $\mathbf{Y}$ be defined as in Algorithm 4 and let $\mathbf{U}_{k}$ be the
subspace spanned by the top $k$ left singular vectors of $\mathbf{A}$. Then
$\sin\Theta(\mathbf{Y},\mathbf{U}_{k})\leq\frac{1}{1000k^{10}}$.

###### Proof.

By setting $m=k=\ell$ in Theorem 5.2, we have

$\begin{split}\sin\Theta(\mathbf{Y},\mathbf{U}_{k})&=\sin\Theta(\mathbf{P}_{\mathbf{Y}},\mathbf{P}_{\mathbf{U}_{k}})\\\
&\leq\frac{\|\mathbf{P}_{\mathbf{Y}}-\mathbf{P}_{\mathbf{U}_{k}}\|_{2}}{\sigma_{k}(\mathbf{Y})-\sigma_{k+1}(\mathbf{U}_{k})}.\end{split}$

By definition of $\sigma$, we have that
$\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$. Thus, Lemma 5.4 implies
that $\sigma_{k}(\mathbf{A})\gg 1$. Since $\mathbf{Y}$ has rank $k$, we have
$\sigma_{k+1}(\mathbf{Y})=0$. By Lemma 5.3,
$\sin\Theta(\mathbf{Y},\mathbf{U}_{k})\leq\|\mathbf{P}_{\mathbf{Y}}-\mathbf{P}_{\mathbf{U}_{k}}\|_{2}\leq\frac{1}{1000k^{10}}$.
∎

They also showed that vectors in $\mathbf{U}_{k}$ are close to the subspace
$\mathbf{M}$:

######  Lemma 5.6.

[BK20b] Let $\mathbf{U}_{k}$ be the subspace spanned by the top $k$ left
singular vectors of $\mathbf{A}$ and let $\mathbf{R}$ be any $k$-dimensional
subspace of $\mathbb{R}^{d}$ with
$\sin\Theta(\mathbf{U}_{k},\mathbf{R})\leq\frac{\alpha^{2}}{1001k^{9}}$. Let
$\mathbf{M}$ be the underlying latent $k$-simplex. Then for each unit vector
${\bf x}\in\mathbf{R}$, there exists a vector ${\bf
y}\in\textbf{Span}\left(\mathbf{M}\right)$ with $\|{\bf x}-{\bf
y}\|_{2}\leq\frac{\alpha^{2}}{500k^{8.5}}$.

Since we have $\sin\Theta(\mathbf{Y},\mathbf{U}_{k})\leq\frac{1}{1000k^{10}}$
from Corollary 5.5, then it follows from Lemma 5.6 and the triangle inequality
of $\sin\Theta$ distance that vectors in $\mathbf{Y}_{k}$ are close to the
subspace $\mathbf{M}$:

######  Corollary 5.7.

Let $\mathbf{Y}$ be defined as in Algorithm 4 and let $\mathbf{R}$ be any
$k$-dimensional subspace of $\mathbb{R}^{d}$ with

$\sin\Theta(\mathbf{Y},\mathbf{R})\leq\frac{\alpha^{2}}{1000k^{9}}.$

Let $\mathbf{M}$ be the underlying latent $k$-simplex. Then for each unit
vector ${\bf x}\in\mathbf{R}$, there exists a vector ${\bf
y}\in\textbf{Span}\left(\mathbf{M}\right)$ with $\|{\bf x}-{\bf
y}\|_{2}\leq\frac{\alpha^{2}}{500k^{8.5}}$.

We then use the following structural result between the first $r$ points
selected by Algorithm 4 and the closest $r$ points in the latent $k$-simplex
$\mathbf{M}$.

######  Lemma 5.8 (Equation 10.21 in [BK20b]).

For $r\in[k]$ let $\mathcal{R}_{1},\ldots,\mathcal{R}_{k}\in\mathbb{R}^{d}$ be
points such that there exist distinct $\ell_{1},\ldots,\ell_{r}\subseteq[n]$
with

$\|\mathcal{R}_{i}-\mathbf{M}_{*,\ell_{i}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$

Let $\widehat{\mathbf{A}}=\mathcal{R}_{1}\circ\ldots\circ\mathcal{R}_{t}$ and
$\widehat{\mathbf{M}}=\mathbf{M}_{*,\ell_{1}}\circ\ldots\circ\mathbf{M}_{*,\ell_{r}}$.
Then

$\|\widehat{\mathbf{M}}-\widehat{\mathbf{A}}\|_{2}\leq\frac{k^{4.5}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.$

###### Proof.

Note that the claim follows immediately from the hypothesis and applying the
Cauchy-Schwarz inequality. ∎

We first bound the $\sin\Theta$ distance between
$\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$
and $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$. This essentially says that we
can work in the subspace $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ rather
than
$\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$
and we will not incur too much error.

Next, we prove our lemma relating angular distance of the subspace obtained in
the $i$-th iteration of the algorithm
($\mathbf{Y}(\mathbf{I}-\mathbf{P}_{i})$) to the optimal subspace
($\mathbf{M}(\mathbf{I}-\mathbf{P}_{i})$).

######  Lemma 5.9 (Angular Distance between Subspaces.).

For some $r\in[k]$, let
$\widehat{\mathbf{M}}=\mathbf{M}_{*,\ell_{1}}\circ\ldots\circ\mathbf{M}_{*,\ell_{r}}$
be the matrix with $r$ columns corresponding to vertices of the latent
$k$-simplex $\mathbf{M}$ closest to the first $r$ points selected by Algorithm
4, $\mathbf{A}_{\mathcal{R}_{1}},\ldots,\mathbf{A}_{\mathcal{R}_{r}}$,
respectively. Suppose
$\|\mathbf{A}_{\mathcal{R}_{i}}-\mathbf{M}_{*,\ell_{i}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$
for each $i\in[r]$. Let $\mathbf{P}_{r}$ be the projection matrix orthogonal
to $\mathbf{A}_{\mathcal{R}_{1}},\ldots,\mathbf{A}_{\mathcal{R}_{r}}$. Then,

$\displaystyle\sin\Theta\left(\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r}),\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})\right)$
$\displaystyle\leq\frac{\alpha}{100k^{4}}$
$\displaystyle\sin\Theta\left(\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}}),\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})\right)$
$\displaystyle\leq\frac{\alpha}{100k^{4}}.$

###### Proof.

Let ${\bf y}\in\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ be a unit vector. By
Corollary 5.7, there exists ${\bf x}\in\textbf{Span}\left(\mathbf{M}\right)$
with

$\|{\bf x}-{\bf y}\|_{2}\leq\frac{\alpha^{2}}{500k^{8.5}}.$ (2)

Let ${\bf z}={\bf x}-\widehat{\mathbf{M}}\widehat{\mathbf{M}}^{\dagger}{\bf
x}$ be the component of ${\bf x}$ in $\mbox{Null}(\widehat{\mathbf{M}})$. Note
that $\widehat{\mathbf{M}}\widehat{\mathbf{M}}^{\dagger}$ is a projection
matrix and thus
$\|\widehat{\mathbf{M}}\widehat{\mathbf{M}}^{\dagger}\|_{2}\leq 1$. Then we
have

$\displaystyle\|{\bf x}-{\bf z}\|_{2}$
$\displaystyle\leq\|\widehat{\mathbf{M}}\widehat{\mathbf{M}}^{\dagger}({\bf
x}-{\bf y})\|_{2}+\|\widehat{\mathbf{M}}\widehat{\mathbf{M}}^{\dagger}{\bf
y}\|_{2}$ $\displaystyle\leq\|{\bf x}-{\bf
y}\|_{2}+\|\widehat{\mathbf{M}}(\widehat{\mathbf{M}}^{T}\widehat{\mathbf{M}})^{-1}(\widehat{\mathbf{M}}^{T}-\widehat{\mathbf{A}}^{T}){\bf
y}\|_{2}$

where $\widehat{\mathbf{A}}=\mathcal{R}_{1}\circ\ldots\circ\mathcal{R}_{t}$ so
that $\widehat{\mathbf{A}}^{T}{\bf y}=0$ since $\mathbf{P}_{r}$ projects away
from $\widehat{\mathbf{A}}$. We also have
$\|\widehat{\mathbf{M}}(\widehat{\mathbf{M}}^{T}\widehat{\mathbf{M}})^{-1}\|_{2}=\frac{1}{\sigma_{r}(\widehat{\mathbf{M}})}$.
Thus by (2) and Lemma 5.8, we have

$\begin{split}\|{\bf x}-{\bf z}\|_{2}&\leq\|{\bf x}-{\bf
y}\|_{2}+\frac{1}{\sigma_{r}(\widehat{\mathbf{M}})}\|(\widehat{\mathbf{M}}^{T}-\widehat{\mathbf{A}}^{T}){\bf
y}\|_{2}\\\
&\leq\frac{\alpha^{2}}{500k^{8.5}}+\frac{k^{4.5}\sigma}{\alpha\sqrt{\delta}\sigma_{k}(\widehat{\mathbf{M}})}.\end{split}$

Hence by the triangle inequality and Lemma 5.4, we have $\|{\bf y}-{\bf
z}\|_{2}\leq\frac{\alpha}{100k^{4}}$. Since ${\bf
y}\in\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ and ${\bf
z}\in\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$,
then by definition of the $\sin\Theta$ distance, it follows that

$\sin\Theta\left(\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r}),\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})\right)\leq\frac{\alpha}{100k^{4}},$

proving the first part of the claim.

To prove the second half of the claim, it suffices to show that the dimension
of $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ is $k-r$, since
$\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$
has dimension $k-r$ and the $\sin\Theta$ distance is symmetric between two
subspaces of the same dimension. By construction, $\mathbf{Y}$ has dimension
$k$ so that $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ has dimension at least
$k-r$. But if $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ has dimension larger
than $k-r$, then there exists a set of orthonormal vectors ${\bf
u}_{1},\ldots,{\bf u}_{k-r+1}\in\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$. By
the first part of the claim and the definition of the $\sin\Theta$ distance,
there exists a set of corresponding vectors ${\bf v}_{1},\ldots,{\bf
v}_{k-r+1}\in\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$
such that $\|{\bf u}_{i}-{\bf v}_{j}\|_{2}<\frac{\alpha}{100k^{4}}$. But then
for $a\neq b$, we have by the triangle inequality and the fact that ${\bf
u}_{a}\cdot{\bf u}_{b}=0$,

$\begin{split}|{\bf v}_{a}\cdot{\bf v}_{b}|&\leq|{\bf u}_{a}\cdot{\bf
u}_{b}|+|({\bf v}_{a}-{\bf u}_{a})\cdot{\bf u}_{b}|+|{\bf v}_{a}\cdot({\bf
v}_{b}-{\bf u}_{b})|\\\ &\leq\frac{\alpha}{50k^{4}}\end{split}$

Similarly, since ${\bf u}_{a}\cdot{\bf u}_{a}=1$, we have

$\begin{split}|{\bf v}_{a}\cdot{\bf v}_{a}|&\geq|{\bf u}_{a}\cdot{\bf
u}_{a}|-|({\bf v}_{a}-{\bf u}_{a})\cdot{\bf u}_{a}|-|{\bf v}_{a}\cdot({\bf
v}_{a}-{\bf u}_{a})|\\\ &\geq 1-\frac{\alpha}{50k^{4}}.\end{split}$

Thus if $\mathbf{V}={\bf v}_{1}\circ\ldots\circ{\bf
v}_{k-r+1}\in\mathbb{R}^{d\times k-r+1}$ is formed by concatenating the
vectors ${\bf v}_{1},\ldots,{\bf v}_{k-r+1}$, then $\mathbf{V}^{T}\mathbf{V}$
is diagonally-dominant. Hence, $\mathbf{V}^{T}\mathbf{V}$ is nonsingular, so
${\bf v}_{1},\ldots,{\bf v}_{k-r+1}$ must be linearly independent vectors in
$\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}})$,
which contradicts the fact that its dimension is $k-r$. Therefore, the
dimension of $\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})$ must be $k-r$, and so
$\sin\Theta\left(\textbf{Span}\left(\mathbf{M}\right)\cap\mbox{Null}(\widehat{\mathbf{M}}),\mathbf{Y}(\mathbf{I}_{d}-\mathbf{P}_{r})\right)\leq\frac{\alpha}{100k^{4}}$.
∎

We now recall a structural lemma from [BK20b].

######  Lemma 5.10 (Claim 10.1 in [BK20b]).

Let $a,b\notin\\{\ell_{1},\ldots,\ell_{r}\\}$ be distinct indices. Then

$\|\mbox{Proj}(\mathbf{M}_{*,a}-\mathbf{M}_{*,b},\mbox{Null}(\widehat{\mathbf{M}})\|_{2}\geq\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}.$

Now we need to show that our algorithm is (1) well-defined and (2) preserves
the invariant that the $(i+1)$-st point sampled from
$\mathbf{Y}^{T}(\mathbf{I}-\mathbf{P}_{i})$ will also be reasonably close to
some different point of the $k$-simplex. We show the selected procedure is
well-defined in Lemma 5.11 by arguing that there exists a unique solution to
the maximization problem.

######  Lemma 5.11 (Optimization is Well-Defined).

Let ${\bf u}\in\mathbb{R}^{d}$ be a random unit vector in the space of
$\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})$, where $\mathbf{P}_{r}$ is the
orthogonal projection to
$\mathbf{A}_{\mathcal{R}_{1}},\ldots,\mathbf{A}_{\mathcal{R}_{r}}$. Then there
exists a constant $c>0$ so that with probability at least $1-c/{k^{1.5}}$:

  1. 1.

For all distinct $a,b\notin\\{\ell_{1},\ldots,\ell_{r}\\}$, then $|{\bf
u}\cdot(\mathbf{M}_{*,a}-\mathbf{M}_{*,b})|\geq\frac{0.097}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$.

  2. 2.

For all $a\notin\\{\ell_{1},\ldots,\ell_{r}\\}$, then $|{\bf
u}\cdot\mathbf{M}_{*,a}|\geq\frac{0.0989}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$.

###### Proof.

For $a\notin\\{\ell_{1},\ldots,\ell_{r}\\}$, let ${\bf p}_{a}$ be the
projection of $\mathbf{M}_{*,a}$ onto $\mbox{Null}(\widehat{\mathbf{M}})$ and
${\bf q}_{a}$ be the projection of $\mathbf{M}_{*,a}$ onto
$\textbf{Span}\left(\widehat{\mathbf{M}}\right)$. By the Well-Separateness
assumption, we have $\|{\bf
p}_{a}\|_{2}\geq\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$. Let ${\bf
w}_{a}$ be defined so that ${\bf q}_{a}=\widehat{\mathbf{M}}{\bf w}_{a}$.
Since $\|{\bf q}_{a}\|_{2}\leq\|\mathbf{M}_{*,a}\|_{2}$ and
$\sigma_{r}(\widehat{\mathbf{M}})\leq\sigma_{k}(\mathbf{M})$, then Lemma 5.4
gives

$\|{\bf w}_{a}\|_{2}\leq\frac{\|{\bf
q}_{a}\|_{2}}{\sigma_{r}(\widehat{\mathbf{M}})}\leq\frac{\|\mathbf{M}_{*,a}\|_{2}\alpha^{2}}{1000k^{8.5}}\frac{\sqrt{\delta}}{\sigma}.$
(3)

Since $\widehat{\mathbf{A}}{\bf u}=0$, we can also write

$\begin{split}{\bf u}\cdot\mathbf{M}_{*,a}&={\bf u}\cdot{\bf p}_{a}+{\bf
u}\cdot{\bf q}_{a}\\\ &={\bf u}\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))+{\bf
u}^{T}(\widehat{\mathbf{M}}-\widehat{\mathbf{A}}){\bf w}_{a}.\end{split}$

By Lemma 5.8, (3), and normalizing so that $\|{\bf u}\|_{2}=1$, we have

$\begin{split}|{\bf u}\cdot(\mathbf{M}_{*,a}-\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})))|&\leq\|\widehat{\mathbf{M}}-\widehat{\mathbf{A}}\|_{2}\|{\bf
w}_{a}\|_{2}\\\
&\leq\frac{\alpha\|\mathbf{M}_{*,a}\|_{2}}{1000k^{4}}.\end{split}$ (4)

The same holds for ${\bf u}\cdot(\mathbf{M}_{*,a}-\mathbf{M}_{*,b})$, so that

$\begin{split}&|{\bf u}\cdot(\mathbf{M}_{*,a}-\mathbf{M}_{*,b})-{\bf
u}\cdot\mbox{Proj}({\bf p}_{a}-{\bf
p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|\\\
&\leq\frac{\|\mathbf{M}_{*,a}-\mathbf{M}_{*,b}\|_{2}\alpha}{1000k^{4}}.\end{split}$
(5)

Let $\mathcal{E}$ be the event that:

  1. 1.

For all $a$, $|{\bf u}\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|\geq\frac{1}{10k^{4}}\|\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}$.

  2. 2.

For all $a\neq b$, $|{\bf u}\cdot\mbox{Proj}({\bf p}_{a}-{\bf
p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|\geq\frac{1}{10k^{4}}\|\mbox{Proj}({\bf
p}_{a}-{\bf p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}$.

Note that $|{\bf u}\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|\geq\frac{1}{10k^{4}}\|\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}$ holds as long as
${\bf u}\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\neq 0$. Since the volume
of the set $\\{{\bf x}\in\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}):{\bf
u}\cdot{\bf x}=0\\}$ is at most $\sqrt{k}$ times the volume of the unit ball
$\\{{\bf x}\in\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}):\|{\bf
x}\|_{2}=1\\}$, then by taking a union bound over at most $k^{2}$ indices, it
follows that $\mathcal{E}$ holds with probability at least
$1-\frac{1}{k^{1.5}}$.

By Lemma 5.9, there exists ${\bf
p}^{\prime}_{a}\in\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})$ such that
$\|{\bf p}^{\prime}_{a}-{\bf p}_{a}\|_{2}\leq\frac{\alpha\|{\bf
p}_{a}\|_{2}}{100k^{4}}$. Hence for $k\geq 2$, $\|{\bf p}_{a}-\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}\leq\frac{\alpha\|{\bf
p}_{a}\|_{2}}{100k^{4}}\leq\frac{\|{\bf p}_{a}\|_{2}}{1600}$. This implies
$\|\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}\geq 0.999\|{\bf
p}_{a}\|_{2}$. Then conditioning on $\mathcal{E}$,

$\begin{split}|{\bf u}\cdot\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|&\geq\frac{\|\mbox{Proj}({\bf
p}_{a},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}}{10k^{4}}\\\
&\geq\frac{0.999\|{\bf p}_{a}\|_{2}}{10k^{4}}\\\
&\geq\frac{0.999\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}}{10k^{4}},\end{split}$

where the last inequality follows since $\|{\bf
p}_{a}\|_{2}\geq\|\mbox{Proj}(\mathbf{M}_{*,a},\mbox{Null}(\mathbf{M}\setminus\mathbf{M}_{*,a}))\|_{2}\geq\alpha\max_{\ell}\mathbf{M}_{*,\ell}$
by the Well-Separateness assumption. Hence by (4), it follows that for all
$a\notin\\{\ell_{1},\ldots,\ell_{r}\\}$,

$\begin{split}|{\bf u}\cdot\mathbf{M}_{*,a}|&\geq|{\bf u}*\mbox{Proj}({\bf
u},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))-\frac{\alpha\|\mathbf{M}_{*,a}\|_{2}}{1000k^{4}}\\\
&\geq\frac{0.0989\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}}{k^{4}},\end{split}$

which proves the second half of the claim.

To prove the first half of the claim, note that conditioned on $\mathcal{E}$,
then (5) implies

$\begin{split}|{\bf u}\cdot(\mathbf{M}_{*,a}-\mathbf{M}_{*,b})|&\geq|{\bf
u}\cdot\mbox{Proj}({\bf p}_{a}-{\bf
p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))|\\\
&-\frac{\|\mathbf{M}_{*,a}-\mathbf{M}_{*,b}\|_{2}\alpha}{1000k^{4}}\\\
&\geq\frac{\|\mbox{Proj}({\bf p}_{a}-{\bf
p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}}{10k^{4}}\\\
&-\frac{\|\mathbf{M}_{*,a}-\mathbf{M}_{*,b}\|_{2}\alpha}{1000k^{4}}.\end{split}$

By Lemma 5.9, there exists ${\bf
v}\in\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})$ such that $\|{\bf v}-({\bf
p}_{a}-{\bf p}_{b})\|_{2}\leq\frac{\alpha\|{\bf p}_{a}-{\bf
p}_{b}\|_{2}}{100k^{4}}$. Thus, $\|\mbox{Proj}({\bf p}_{a}-{\bf
p}_{b},\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r}))\|_{2}\geq 0.99\|{\bf
p}_{a}\|_{2}\geq 0.99\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$, by Lemma
5.10. Since
$\frac{\|\mathbf{M}_{*,a}-\mathbf{M}_{*,b}\|_{2}\alpha}{1000k^{4}}\leq\frac{2\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}}{1000k^{4}}$,
it follows that $|{\bf
u}\cdot(\mathbf{M}_{*,a}-\mathbf{M}_{*,b})|\geq\frac{0.097}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$.
∎

We next show that the selected index is not among the previously selected
indices. Thus, we obtain a new index at each iteration, which implies that we
only need $k$ iterations.

######  Lemma 5.12.

Let
$\widehat{\mathbf{M}}=\mathbf{M}_{*,\ell_{1}}\circ\ldots\circ\mathbf{M}_{*,\ell_{r}}$
be the $r$ points in the latent $k$-simplex $\mathbf{M}$ closest to the first
$r$ points selected by Algorithm 4, $\mathcal{R}_{1},\ldots,\mathcal{R}_{r}$,
respectively. Suppose

$\|\mathcal{R}_{i}-\mathbf{M}_{*,\ell_{i}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$

for each $i\in[r]$. Let ${\bf u}\in\mathbb{R}^{d}$ be a random unit vector in
the space of $\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})$, where
$\mathbf{P}_{r}$ is the orthogonal projection to
$\mathcal{R}_{1},\ldots,\mathcal{R}_{r}$. Let

$\ell_{r+1}=\begin{cases}\operatorname*{argmax}_{\ell}{\bf
u}\cdot\mathbf{M}_{*,\ell}\qquad\text{if }{\bf u}\cdot\mathcal{R}_{r+1}\geq
0\\\ \operatorname*{argmin}_{\ell}{\bf
u}\cdot\mathbf{M}_{*,\ell}\qquad\text{if }{\bf
u}\cdot\mathcal{R}_{r+1}<0\end{cases}.$

Then $\ell_{r+1}\notin\\{\ell_{1},\ldots,\ell_{r}\\}$.

###### Proof.

We consider the case ${\bf u}\cdot\mathcal{R}_{r+1}\geq 0$ as the analysis for
the case ${\bf u}\cdot\mathcal{R}_{r+1}<0$ is symmetric. Let
$\ell_{r+1}=\operatorname*{argmax}_{\ell}{\bf u}\cdot\mathbf{M}_{*,\ell}$.
Suppose by way of contradiction that
$\ell_{r+1}\in\\{\ell_{1},\ldots,\ell_{r}\\}$. Without loss of generality, let
$\ell_{r+1}=\ell_{1}$. Since
$\|\mathcal{R}_{1}-\mathbf{M}_{*,\ell_{1}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$
and ${\bf u}\cdot\mathcal{R}_{1}$, then

${\bf u}\cdot\mathbf{M}_{*,\ell_{i}}\|_{2}\leq{\bf
u}\cdot\mathcal{R}_{i}+\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}=\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.$

Since $\ell_{1}=\operatorname*{argmax}_{\ell}{\bf u}\cdot\mathbf{M}_{*,\ell}$,
then ${\bf u}\cdot\mathbf{M}_{*,\ell}\leq{\bf u}\cdot\mathbf{M}_{*,\ell_{1}}$
for all $\ell$. Thus ${\bf
u}\cdot\mathbf{P}_{*,S}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$
for any set of indices $S\subseteq[n]$ inside the convex hull of $\mathbf{M}$.
In conjunction, Lemma 5.13 implies

${\bf u}\cdot\mathbf{A}_{*,\mathcal{R}_{r+1}}\leq{\bf
u}\cdot\mathbf{P}_{*,\mathcal{R}_{r+1}}+\frac{\sigma}{\sqrt{\delta}}\leq\left(\frac{300k^{4}}{\alpha}+1\right)\frac{\sigma}{\sqrt{\delta}}.$
(6)

Recall that by Lemma 5.1,
$\|\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}\|^{2}_{2}\leq(1+\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}+\frac{\epsilon}{k}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$
and thus
$\|\mathbf{A}-\mathbf{Y}\mathbf{Z}^{T}\|\leq(1+2\epsilon)\|\mathbf{A}-\mathbf{A}_{k}\|_{2}$,
given the Significant Singular Values assumption. Since
$\mathbf{A}_{*,\mathcal{R}_{r+1}}$ is a subset of $\delta n$ columns of
$\mathbf{A}$ and $\mathcal{R}_{r+1}$ is a subset of $\delta n$ columns of
$\mathbf{Y}$, then for $\epsilon<1$,

$\displaystyle{\bf u}\cdot\mathcal{R}_{r+1}$ $\displaystyle\leq{\bf
u}\cdot\mathbf{A}_{*,\mathcal{R}_{r+1}}+{\bf
u}\cdot(\mathcal{R}_{r+1}-\mathbf{A}_{*,\mathcal{R}_{r+1}})$
$\displaystyle\leq\left(\frac{300k^{4}}{\alpha}+1\right)\frac{\sigma}{\sqrt{\delta}}+\frac{3}{\sqrt{\delta
n}}\|\mathbf{A}-\mathbf{A}_{k}\|_{2},$

where the last step follows from (6) and applying the Cauchy-Schwarz
inequality and the fact that ${\bf u}$ is a unit vector. Since $\mathbf{P}$
has rank $k$ and $\mathbf{A}_{k}$ is the best rank $k$ approximation to
$\mathbf{A}$, then
$\|\mathbf{A}-\mathbf{A}_{k}\|_{2}\leq\|\mathbf{A}-\mathbf{P}\|_{2}$ so that

$\displaystyle{\bf u}\cdot\mathcal{R}_{r+1}$
$\displaystyle\leq\left(\frac{300k^{4}}{\alpha}+1\right)\frac{\sigma}{\sqrt{\delta}}+\frac{3}{\sqrt{\delta
n}}\|\mathbf{A}-\mathbf{P}\|_{2},$
$\displaystyle\leq\left(\frac{300k^{4}}{\alpha}+1\right)\frac{\sigma}{\sqrt{\delta}}+\frac{3\sigma}{\sqrt{\delta}}$
(7)
$\displaystyle=\left(\frac{300k^{4}}{\alpha}+4\right)\frac{\sigma}{\sqrt{\delta}},$
(8)

since $\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$ by definition of
$\sigma$. However for $t\notin\\{\ell_{1},\ldots,\ell_{r}\\}$, Lemma 5.13 and
the Proximate Latent Points assumption imply the existence of a set
$\sigma_{t}$ of $\delta n$ columns such that

$\begin{split}|{\bf u}\cdot\mathbf{A}_{*,\sigma_{t}}|&\geq|{\bf
u}\cdot\mathbf{P}_{*,\sigma_{t}}|-\frac{\sigma}{\sqrt{\delta}}\\\ &\geq|{\bf
u}\cdot\mathbf{M}_{*,t}|-\frac{5\sigma}{\sqrt{\delta}}\\\
&\geq\frac{0.0989}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}-\frac{5\sigma}{\sqrt{\delta}},\end{split}$
(9)

where the last step follows from Lemma 5.11. Moreover, $\sigma_{t}$ has
$\delta n$ columns, so again by applying the Cauchy-Schwarz inequality and the
fact that ${\bf u}$ is a unit vector, we have

$\begin{split}|{\bf
u}\cdot(\mathbf{A}_{*,\sigma_{t}}-\mathbf{Y}_{*,\sigma_{t}})|&\leq\frac{1}{\sqrt{\delta
n}}\|\mathbf{A}-\mathbf{A}_{k}\|_{2}\\\ &\leq\frac{1}{\sqrt{\delta
n}}\|\mathbf{A}-\mathbf{P}\|_{2}\leq\frac{3\sigma}{\sqrt{\delta}}.\end{split}$
(10)

where the last two inequalities come from the fact that $\mathbf{P}$ has rank
$k$ and $\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$ by definition of
$\sigma$.

Thus from (9) and (10),

$\begin{split}|{\bf u}\cdot\mathbf{Y}_{*,\sigma_{t}}|&\geq|{\bf
u}\cdot\mathbf{A}_{*,\sigma_{t}}|-|{\bf
u}\cdot(\mathbf{A}_{*,\sigma_{t}}-\mathbf{Y}_{*,\sigma_{t}})|\\\
&\geq\frac{0.0989}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}-\frac{8\sigma}{\sqrt{\delta}}.\end{split}$

However by the Spectrally Bounded Perturbation assumption, we have $|{\bf
u}\cdot\mathbf{Y}_{*,\sigma_{t}}|\geq\frac{2400k^{5}}{\alpha}\frac{\sigma}{\sqrt{\delta}}-\frac{8\sigma}{\sqrt{\delta}}$,
which contradicts the maximality of $\mathcal{R}_{r+1}$ in (8). Therefore, it
holds that $\ell_{r+1}\notin\\{\ell_{1},\ldots,\ell_{r}\\}$. ∎

Before showing that the selected index completes the inductive step, we recall
the following:

######  Lemma 5.13 (Lemma 3.1 in [BK20b]).

For a subset $S\subseteq[n]$, let $\mathbf{A}_{*,S}=\frac{1}{|S|}\sum_{i\in
S}\mathbf{A}_{*,i}$. For all $S\subseteq[n]$,
$|\mathbf{A}_{*,S}-\mathbf{P}_{*,S}|\leq\sigma\sqrt{n/|S|}$.

We then show that the algorithm preserves the aforementioned invariant by
showing that the unique solution $\mathbf{A}_{\mathcal{R}_{i}}$ cannot
correspond to one of the vertices of the $k$-simplex that have been found in
the first $i$ rounds, thus proving that we find a solution
$\mathbf{A}_{\mathcal{R}_{i}}$ that corresponds to a new vertex of
$\mathbf{M}$. We then show $\mathbf{A}_{\mathcal{R}_{i}}$ is close to the new
vertex of $\mathbf{M}$, preserving the inductive hypothesis.

######  Lemma 5.14 (Recovery Guarantees).

Let
$\widehat{\mathbf{M}}=\mathbf{M}_{*,\ell_{1}}\circ\ldots\circ\mathbf{M}_{*,\ell_{r}}$
be the $r$ points in the latent $k$-simplex $\mathbf{M}$ closest to the first
$r$ points selected by Algorithm 4, $\mathcal{R}_{1},\ldots,\mathcal{R}_{r}$,
respectively. Suppose

$\|\mathcal{R}_{i}-\mathbf{M}_{*,\ell_{i}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$

for each $i\in[r]$. Let ${\bf u}\in\mathbb{R}^{d}$ be a random unit vector in
the space of $\mathbf{Y}^{T}(\mathbf{I}_{d}-\mathbf{P}_{r})$, where
$\mathbf{P}_{r}$ is the orthogonal projection to
$\mathcal{R}_{1},\ldots,\mathcal{R}_{r}$. Let

$\ell_{r+1}=\begin{cases}\operatorname*{argmax}_{\ell}{\bf
u}\cdot\mathbf{M}_{*,\ell}\qquad\text{if }{\bf u}\cdot\mathcal{R}_{r+1}\geq
0\\\ \operatorname*{argmin}_{\ell}{\bf
u}\cdot\mathbf{M}_{*,\ell}\qquad\text{if }{\bf
u}\cdot\mathcal{R}_{r+1}<0\end{cases}.$

Then

$\|\mathcal{R}_{r+1}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.$

###### Proof.

We consider the case ${\bf u}\cdot\mathcal{R}_{r+1}\geq 0$ as the analysis for
the case ${\bf u}\cdot\mathcal{R}_{r+1}<0$ is symmetric. Let
$\ell_{r+1}=\operatorname*{argmax}_{\ell}{\bf u}\cdot\mathbf{M}_{*,\ell}$. By
Lemma 5.12, we have $\ell_{r+1}\notin\\{\ell_{1},\ldots,\ell_{r}\\}$. Thus
applying Lemma 5.11,

${\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}\geq\frac{0.0989}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|.$
(11)

By the Proximate Latent Points assumption, there exists a set
$\sigma_{\ell_{r+1}}$ of size $\delta n$ so that
$\|\mathbf{P}_{*,j}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}\leq\frac{4\sigma}{\sqrt{\delta}}$
for all $j\in\sigma_{\ell_{r+1}}$ so that
$\|\mathbf{P}_{*,\sigma_{\ell_{r+1}}}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}\leq\frac{4\sigma}{\sqrt{\delta}}$.
Then by Lemma 5.13,

${\bf u}\cdot\mathbf{A}_{*,\sigma_{\ell_{r+1}}}\geq{\bf
u}\cdot\mathbf{P}_{*,\sigma_{\ell_{r+1}}}-\frac{\sigma}{\sqrt{\delta}}\geq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{5\sigma}{\sqrt{\delta}}.$

By the same reasoning as 10, we have
$\|\mathcal{R}_{r+1}-\mathbf{A}_{*,\sigma_{\ell_{r+1}}}\|_{2}\leq\frac{3\sigma}{\sqrt{\delta}}$
and thus,

${\bf u}\cdot\mathcal{R}_{r+1}\geq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{8\sigma}{\sqrt{\delta}}.$ (12)

Now for any $a\notin\\{\ell_{1},\ldots,\ell_{r+1}\\}$, Lemma 5.11 says

${\bf u}\cdot\mathbf{M}_{*,a}\leq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{0.097}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}.$
(13)

Similarly, for $a\in\\{\ell_{1},\ldots,\ell_{r}\\}$, we have
$\|\mathcal{R}_{a}-\mathbf{M}_{*,a}\|\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$
by the inductive hypothesis. Since ${\bf u}\cdot\mathcal{R}_{a}=0$, then

$\displaystyle{\bf u}\cdot\mathbf{M}_{*,a}$ $\displaystyle\leq{\bf
u}\cdot\mathcal{R}_{a}+\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}=\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$
$\displaystyle\leq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{0.0989}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|$
$\displaystyle+\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}$

by (11). Thus by the Spectrally Bounded Perturbation assumption,

${\bf u}\cdot\mathbf{M}_{*,a}\leq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{0.097}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|$
(14)

Since $\mathbf{P}_{*,\mathcal{R}_{r+1}}$ is a convex combination of the
columns of $\mathbf{M}$, there exists a vector ${\bf w}$ such that
$\mathbf{P}_{*,\mathcal{R}_{r+1}}=\mathbf{M}{\bf w}$. Then by the same
reasoning as 10 and Lemma 5.13,

$\displaystyle{\bf u}\cdot\mathcal{R}_{r+1}$ $\displaystyle\leq{\bf
u}\cdot\mathbf{A}_{*,\mathcal{R}_{r+1}}+\frac{3\sigma}{\sqrt{\delta}}\leq{\bf
u}\cdot\mathbf{P}_{*,\mathcal{R}_{r+1}}+\frac{3\sigma}{\sqrt{\delta}}+\frac{4\sigma}{\sqrt{\delta}}$
$\displaystyle\leq w_{\ell_{r+1}}({\bf u}\cdot\mathbf{M}_{*,\ell_{r+1}})+$
$\displaystyle\sum_{a\neq\ell_{r+1}}w_{a}\left(({\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{0.097}{k^{4}}\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}\right)$
$\displaystyle+\frac{4\sigma}{\sqrt{\delta}},$

where the last line follows from decomposing $\mathbf{M}$ and applying (13)
and (14) to $\mathbf{M}_{*,a}$ for $a\neq\ell_{r+1}$. Hence,

$\displaystyle{\bf u}\cdot\mathcal{R}_{r+1}$ $\displaystyle\leq{\bf
u}\cdot\mathbf{M}_{*,\ell_{r+1}}-\frac{0.097\alpha\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}(1-w_{\ell_{r+1}})}{k^{4}}$
$\displaystyle+\frac{4\sigma}{\sqrt{\delta}}.$

Combining with (12), we have

$(1-w_{\ell_{r+1}})\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}\leq\frac{12\sigma}{\sqrt{\delta}}\frac{k^{4}}{0.097\alpha}\leq\frac{124k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.$

Thus,

$\displaystyle\|\mathbf{P}_{*,\mathcal{R}_{r+1}}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}$
$\displaystyle=\|(w_{\ell_{r+1}}-1)\mathbf{M}_{*,\ell_{r+1}}$
$\displaystyle+\sum_{a\neq\ell_{r+1}}w_{a}\mathbf{M}_{*,a}\|$
$\displaystyle\leq\sum_{a\neq\ell_{r+1}}w_{a}\|\mathbf{M}_{*,\ell_{r+1}}-\mathbf{M}_{*,a}\|_{2}$
$\displaystyle\leq 2(1-w_{\ell_{r+1}})\max_{\ell}\|\mathbf{M}_{*,\ell}\|_{2}$
$\displaystyle\leq\frac{248k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.$

Finally from the triangle inequality and Lemma 5.13, we have

$\begin{split}\|\mathcal{R}_{r+1}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}&\leq\|\mathcal{R}_{r+1}-\mathbf{P}_{*,\mathcal{R}_{r+1}}\|_{2}\\\
&+\|\mathbf{P}_{*,\mathcal{R}_{r+1}}-\mathbf{M}_{*,\ell_{r+1}}\|_{2}\\\
&\leq\frac{3\sigma}{\sqrt{\delta}}+\frac{248k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}\\\
&\leq\frac{300k^{4}}{\alpha}\frac{\sigma}{\sqrt{\delta}}.\end{split}$

∎

##  6 Connection to Spectral Low-Rank Approximation

In this section, we show that learning a latent simplex is closely related to
computing a spectral low-rank approximation. Spectral low-rank approximation
is a fundamental primitive for algorithm design and numerical linear algebra
and the best known algorithm for computing a $(1+\epsilon)$-approximation is
$O(\textsf{nnz}(\mathbf{A})\cdot k)$ [MM15]. A major open question in
randomized linear algebra is to determine whether the dependence on $k$ in the
running time is necessary for spectral low-rank approximation.

We show that for a candidate hard distribution over the input, determined by a
Stochastic Block Model (with appropriate parameters) satisfying Well-
Separateness1, Proximate Latent Points2 and Spectrally Bounded Perturbations3,
an algorithm for learning a latent simplex requiring
$o(\textsf{nnz}(\mathbf{A})\cdot k)$ time also recovers a spectral low-rank
approximation for the input. One way to interpret this statement is that
improving the running time for learning a latent simplex under the same
assumptions as [BK20b] would likely lead to a major algorithmic breakthrough
for spectral low-rank approximation.

######  Theorem 6.1 (Spectral LRA to Latent Simplex).

Given $k\in[n]$, let $\mathcal{S}_{1},\mathcal{S}_{2}\ldots,\mathcal{S}_{k}$
be a partition of $[n]$ such that for all $\ell\in[k]$,
$|\mathcal{S}_{\ell}|=n/k$. Consider a stochastic block model with $k$
communities, $\mathcal{S}_{1},\ldots,\mathcal{S}_{k}$ such that for all
$i\in\mathcal{S}_{\ell}$ and $j\in\mathcal{S}_{\ell^{\prime}}$, the
probability of an edge $(i,j)$ is $p=\textrm{poly}(k)/n^{1/8}$ when
$\ell=\ell^{\prime}$ and $q=p/10$ otherwise. Let $\mathbf{A}$ be a matrix
drawn from the aforementioned model such that $\mathbf{A}_{i,j}=1$ if there
exists an edge between $(i,j)$ and $0$ otherwise. Then any algorithm that
learns the simplex also recovers a rank $k$ matrix $\mathbf{B}$ such that
$\|\mathbf{A}-\mathbf{B}\|^{2}_{2}\leq\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{2}+\frac{1}{n^{1/3}}\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}$.

###### Proof.

Let $\mathbf{P}_{\mathbf{B}}$ be the projection matrix onto the column span of
the output matrix $\mathbf{B}$. We show that
$\mathbf{A}-\mathbf{P}_{\mathbf{B}}$ is a good mixed spectral-Frobenius low-
rank approximation to $\mathbf{A}$.

$\displaystyle\|\mathbf{A}-\mathbf{P}_{\mathbf{B}}\mathbf{A}\|_{2}$
$\displaystyle\leq\|\mathbf{A}-\mathbf{P}+\mathbf{P}\|_{2}\|\mathbf{I}-\mathbf{P}_{\mathbf{B}}\|_{2}$
$\displaystyle\leq\|\mathbf{A}-\mathbf{P}\|_{2}\|\mathbf{I}-\mathbf{P}_{\mathbf{B}}\|_{2}+\mathbf{P}\|_{2}\|\mathbf{I}-\mathbf{P}_{\mathbf{B}}\|_{2}$
$\displaystyle\leq\|\mathbf{A}-\mathbf{P}\|_{2}+\|\mathbf{P}\|_{2}\|\mathbf{I}-\mathbf{P}_{\mathbf{B}}\|_{2}.$

From the definition of $\sigma$, we have
$\|\mathbf{A}-\mathbf{P}\|_{2}\leq\sigma\sqrt{n}$. For the specific stochastic
block model, we have $\sigma\leq\sqrt{p(1-p)}$, e.g., see [Awa17]. Moreover,
the algorithm of [BK20b] guarantees specifically in their Theorem 7.2 that
$\|\mathbf{I}-\mathbf{P}_{\mathbf{B}}\|_{2}\leq\frac{C_{1}k^{4.5}d^{1/8}}{n^{1/4}}$
for some constant $C_{1}>0$. Since $\|\mathbf{P}\|_{F}\geq\|\mathbf{P}\|_{2}$
and $\|\mathbf{P}\|_{F}^{2}\leq C_{2}p^{2}nd$ for some constant $C_{2}>0$ with
high probability, then we have

$\displaystyle\|\mathbf{A}-\mathbf{P}_{\mathbf{B}}\mathbf{A}\|_{2}$
$\displaystyle\leq\sqrt{p(1-p)n}+\frac{C_{1}k^{4.5}d^{1/8}\sqrt{C_{2}p^{2}nd}}{n^{1/4}}$
$\displaystyle\leq\sqrt{pn}+C_{1}pk^{4.5}d^{5/8}\sqrt{C_{2}}n^{1/4}.$

On the other hand, we have
$\|\mathbf{A}-\mathbf{A}_{k}\|^{2}_{F}\geq\|\mathbf{A}\|^{2}_{F}-k\|\mathbf{A}\|^{2}_{2}$.
As before, we have $\|\mathbf{P}\|_{2}\leq p\sqrt{C_{2}nd}$, so that

$\|\mathbf{A}\|_{2}\leq\|\mathbf{P}\|_{2}+\|\mathbf{A}-\mathbf{P}\|_{2}\leq
p\sqrt{C_{2}nd}+\sqrt{p(1-p)n}.$

Moreover, we have $\|\mathbf{A}\|_{F}\geq C_{3}\sqrt{qnd}$ for some constant
$C_{3}>0$ with high probability. Hence for $q>C_{4}p^{2}$ with a sufficiently
high constant $C_{4}$, we have

$\|\mathbf{A}-\mathbf{A}_{k}\|_{F}^{2}\geq C_{5}qnd,$

for some $C_{5}>0$. Let $p=O(q)$ and $d=n^{1/C}$ for some constant $C\geq 3$
so that $k^{4.5}d^{5/8}=o(n^{1/4})$. Since
$\|\mathbf{A}-\mathbf{P}_{\mathbf{B}}\mathbf{A}\|^{2}_{2}\leq C_{6}pn$ for
some constant $C_{6}$, then

$\displaystyle\|\mathbf{A}-\mathbf{P}_{\mathbf{B}}\mathbf{A}\|^{2}_{2}$
$\displaystyle\leq
C_{6}pn\leq\frac{C_{5}}{n^{1/C}}qnd=O\left(\frac{1}{n^{1/C}}\right)\|\mathbf{A}-\mathbf{A}_{k}\|_{F}^{2}$
$\displaystyle\leq\|\mathbf{A}-\mathbf{A}_{k}\|_{2}^{2}+O\left(\frac{1}{n^{1/C}}\right)\|\mathbf{A}-\mathbf{A}_{k}\|_{F}^{2}.$

Taking $C=3$ gives the desired claim. ∎

##  7 Empirical Evaluation

In this section, we describe a series of experiments that demonstrate the
advantage of our algorithm, performed in Python 3.6.9 on an Intel Core
i7-8700K 3.70 GHz CPU with 12 cores and 64GB DDR4 memory, using an Nvidia
Geforce GTX 1080 Ti 11GB GPU, on both synthetic and real-world data. Whereas
previous work requires computing the top $k$ subspace as a pre-processing
step, our main improvement is that we only require a crude approximation. Thus
we compared the running times for finding the top $k$ subspace as required by
[BK20b] to finding a mixed spectral-Frobenius approximation using an input
sparsity algorithm, as required by our algorithm. For the former, we use the
svds method from the sparse scipy linalg package optimized by LAPACK. For the
latter, [CEM+15, CMM17] show that using a sparse CountSketch matrix [CW13,
MM13, NN13], i.e., a matrix with $O(k^{2})$ columns and a single nonzero entry
in each row that is in a random location and is a random sign, suffices to
obtain a mixed spectral-Frobenius guarantee; we evaluate such a matrix with
exactly $k^{2}$ columns. Across all parameters and datasets, the input
sparsity procedure used by our algorithm significantly outperforms the
optimized power iteration methods required by [BK20b].

Synthetic Data. Since our theoretical results are most interesting when $k\ll
d\ll n$, we set $n=50000$, $d=1000$, $k\in\\{20,50,100\\}$ and generate a
random $d\times n$ matrix $\mathbf{A}$ that consists of independent entries
that are each $1$ with probability
$p\in\left\\{\frac{1}{500},\frac{1}{2000},\frac{1}{5000}\right\\}$ and $0$
with probability $1-p$. In Figure 1, we report the average running time of
both algorithms, among $5$ independent runs for each choice of $p$ and $k$.

Mean Runtime of Algorithms across Parameters | $p=1/500$ | $p=1/2000$ | $p=1/5000$
---|---|---|---
Top $k$ Subspace, $k=20$ | 35.056s | 29.725s | 16.45s
Input Sparsity Approximation, $k=20$ | 0.595s | 0.329s | 0.83s
Top $k$ Subspace, $k=50$ | 56.146s | 54.613s | 53.213s
Input Sparsity Approximation, $k=50$ | 0.658s | 0.657s | 0.434s
Top $k$ Subspace, $k=100$ | 78.420s | 79.410s | 71.424s
Input Sparsity Approximation, $k=100$ | 0.501s | 0.387s | 0.440s
Figure 1: Mean runtime comparison of algorithms across parameters on synthetic
data.

Social Networks. We also evaluate the algorithms on the email-Eu-core network
dataset of interactions across email data between individuals from a large
European research institution [YBLG17, LKF07] and the com-Youtube dataset of
friendships on the Youtube social network [YL15], both accessed through the
Stanford Network Analysis Project (SNAP). In the former, there are $n=d=1005$
nodes in the adjacency matrix over $25571$ total edges, forming $k=42$
communities. In the latter, there are $1134890$ nodes with $8385$ communities,
from which we extract a $d\times n$ matrix with $n=100000$, $d=1000$ to
represent a bipartite graph, as described in both Section 2.2 and [BK20b]. In
Figure 2, we report the running time of both algorithms across each dataset
among choices of $k\in\\{20,50,100\\}$. We observe that the resulting matrix
has sparsity roughly $1000$, which is consistent with $p\approx\frac{1}{n}$
and is much less than the sparsity parameters tested in our synthetic data.

| email-Eu-core network | com-Youtube
---|---|---
Top $k$ Subspace, $k=20$ | 0.387s | 5.713s
Input Sparsity Approximation, $k=20$ | 0.005s | 0.379s
Top $k$ Subspace, $k=50$ | 0.556s | 16.711s
Input Sparsity Approximation, $k=50$ | 0.003s | 0.373s
Top $k$ Subspace, $k=100$ | 1.281s | 41.788s
Input Sparsity Approximation, $k=100$ | 0.003s | 0.366s
Figure 2: Mean runtime comparison of algorithms across parameters on real-
world data.

Finally, we consider a full end-to-end implementation comparing the runtime
and least squares loss of the top $k$ subspace algorithm and our input
sparsity approximation algorithm over various ranges of the parameter $k$ and
smoothening parameter $\delta n$ on the com-Youtube dataset, from which we
randomly extract an $n\times d$ matrix, with $n=20000$ and $d=1000$ to
represent a bipartite graph. Our results in Figure 3 show that our algorithm
not only significantly outperforms the top $k$ subspace algorithm in runtime,
but also produces solutions with lower least squared loss.

$0$$5$$10$$15$$20$$25$$30$$0$$300$$600$$900$$1{,}200$$1{,}500$$1{,}800$$2{,}100$Number
of communities ($k$), with $\delta n=10$Least Squared Loss

$0$$5$$10$$15$$20$$25$$30$$0$$300$$600$$900$$1{,}200$$1{,}500$$1{,}800$$2{,}100$Smoothening
parameter $(\delta n)$, with $k=20$Least Squared Loss

$0$$5$$10$$15$$20$$25$$30$$0$$1$$2$$3$$4$$5$$6$$7$$8$$9$Number of communities
($k$), with $\delta n=10$Runtime

Figure 3: Comparison of least squares loss by power iteration algorithm (in
blue triangles) and by our algorithm (in red circles), over various ranges of
the parameter $k$ with smoothening parameter $\delta n=10$, and over various
ranges of $\delta n$ with $k=20$, on the com-Youtube dataset. Also runtime
comparison over a range of $k$, with $\delta n=10$.

#### Acknowledgments

A.B., and D. W. were supported by the Office of Naval Research (ONR) grant
N00014-18-1-2562, and the National Science Foundation (NSF) Grant No.
CCF-1815840. D.W and S.Z were supported by National Institute of Health (NIH)
grant 5R01 HG 10798-2 and a Simons Investigator Award.

## References

  * [ABEF14] Edoardo M. Airoldi, David M. Blei, Elena A. Erosheva, and Stephen E. Fienberg.  Introduction to mixed membership models and methods, 2014.
  * [ABFX08] Edoardo M. Airoldi, David M. Blei, Stephen E. Fienberg, and Eric P. Xing.  Mixed membership stochastic blockmodels.  J. Mach. Learn. Res., 9:1981–2014, June 2008.
  * [AGH+13a] Sanjeev Arora, Rong Ge, Yonatan Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu.  A practical algorithm for topic modeling with provable guarantees.  In International Conference on Machine Learning, pages 280–288. PMLR, 2013.
  * [AGH+13b] Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu.  A practical algorithm for topic modeling with provable guarantees.  In Proceedings of the 30th International Conference on Machine Learning, ICML 2013, Atlanta, GA, USA, 16-21 June 2013, 2013.
  * [AGHK14] Animashree Anandkumar, Rong Ge, Daniel J. Hsu, and Sham M. Kakade.  A tensor approach to learning mixed membership community models.  Journal of Machine Learning Research, 15(1):2239–2312, 2014.
  * [AS12] Pranjal Awasthi and Or Sheffet.  Improved spectral-norm bounds for clustering.  CoRR, abs/1206.3204, 2012.
  * [Awa17] Pranjal Awasthi.  Cs 598: Theoretical machine learning lecture notes, 2017.  https://www.cs.rutgers.edu/~pa336/mlt_f17/lec-14.pdf.
  * [BCW20] Ainesh Bakshi, Nadiia Chepurko, and David P Woodruff.  Robust and sample optimal algorithms for psd low rank approximation.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 506–516. IEEE, 2020.
  * [BJ03] David M Blei and Michael I Jordan.  Modeling annotated data.  In Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, pages 127–134, 2003.
  * [BK20a] Ainesh Bakshi and Pravesh Kothari.  Outlier-robust clustering of non-spherical mixtures.  arXiv preprint arXiv:2005.02970, 2020.
  * [BK20b] Chiranjib Bhattacharyya and Ravindran Kannan.  Finding a latent _k_ -simplex in _O_ * (_k_ $\cdot$ nnz(data)) time via subset smoothing.  In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, pages 122–140. SIAM, 2020.
  * [BL06a] David Blei and John Lafferty.  Correlated topic models.  Advances in neural information processing systems, 18:147, 2006\.
  * [BL06b] David M Blei and John D Lafferty.  Dynamic topic models.  In Proceedings of the 23rd international conference on Machine learning, pages 113–120, 2006.
  * [Ble12] David M. Blei.  Probabilistic topic models.  Commun. ACM, 55(4):77–84, 2012.
  * [BNJ03] David Blei, Andrew Ng, and Michael Jordan.  Latent Dirichlet allocation.  Journal of Machine Learning Research, 3:993–1022, 2003.
  * [CEM+15] Michael B Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Madalina Persu.  Dimensionality reduction for k-means clustering and low rank approximation.  In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 163–172. ACM, 2015.
  * [CG92] Gilles Celeux and Gérard Govaert.  A classification em algorithm for clustering and two stochastic versions.  Computational statistics & Data analysis, 14(3):315–332, 1992\.
  * [CMM17] Michael B. Cohen, Cameron Musco, and Christopher Musco.  Input sparsity time low-rank approximation via ridge leverage score sampling.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1758–1777, 2017.
  * [CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47–60, 2017.
  * [CW13] Kenneth L Clarkson and David P Woodruff.  Low rank approximation and regression in input sparsity time.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 81–90. ACM, 2013.
  * [DHKK20] Ilias Diakonikolas, Samuel B Hopkins, Daniel Kane, and Sushrut Karmalkar.  Robustly learning any clusterable mixture of gaussians.  arXiv preprint arXiv:2005.06417, 2020.
  * [DKS18] Ilias Diakonikolas, Daniel M Kane, and Alistair Stewart.  List-decodable robust mean estimation and learning mixtures of spherical gaussians.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1047–1060, 2018.
  * [Dua20] Leo L Duan.  Latent simplex position model: High dimensional multi-view clustering with uncertainty quantification.  Journal of Machine Learning Research, 21(38):1–25, 2020.
  * [FSX09] Wenjie Fu, Le Song, and Eric P Xing.  Dynamic mixed membership blockmodel for evolving networks.  In Proceedings of the 26th annual international conference on machine learning, pages 329–336, 2009.
  * [FXC16] Xuhui Fan, Richard Yi Da Xu, and Longbing Cao.  Copula mixed-membership stochastic block model.  In IJCAI International Joint Conference on Artificial Intelligence, 2016.
  * [GH+96] Zoubin Ghahramani, Geoffrey E Hinton, et al.  The em algorithm for mixtures of factor analyzers.  Technical report, Technical Report CRG-TR-96-1, University of Toronto, 1996.
  * [Gil20] Nicolas Gillis.  Nonnegative Matrix Factorization.  SIAM, 2020.
  * [GV14] Nicolas Gillis and Stephen A. Vavasis.  Fast and robust recursive algorithmsfor separable nonnegative matrix factorization.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 36(4):698–714, 2014.
  * [HBB10] Matthew Hoffman, Francis R Bach, and David M Blei.  Online learning for latent dirichlet allocation.  In advances in neural information processing systems, pages 856–864, 2010.
  * [HL18] Samuel B Hopkins and Jerry Li.  Mixture models, robustness, and sum of squares proofs.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1021–1034, 2018.
  * [HS17] Samuel B. Hopkins and David Steurer.  Efficient bayesian estimation from few samples: Community detection and related problems.  In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 379–390, 2017.
  * [KK10] Amit Kumar and Ravindran Kannan.  Clustering with spectral norm and the k-means algorithm.  FOCS, 2010.
  * [KSS18] Pravesh K Kothari, Jacob Steinhardt, and David Steurer.  Robust moment estimation and improved clustering via sum of squares.  In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 1035–1046, 2018.
  * [LAW16] Wenzhe Li, Sungjin Ahn, and Max Welling.  Scalable mcmc for mixed membership stochastic blockmodels.  In Artificial Intelligence and Statistics, pages 723–731, 2016\.
  * [LB11] Tyler Lu and Craig Boutilier.  Learning mallows models with pairwise preferences, 2011.
  * [LKF07] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos.  Graph evolution: Densification and shrinking diameters.  ACM Trans. Knowl. Discov. Data, 1(1):2, 2007.
  * [LM18] Allen Liu and Ankur Moitra.  Efficiently learning mixtures of mallows models.  In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 627–638. IEEE, 2018.
  * [MJG09] Kurt Miller, Michael I Jordan, and Thomas L Griffiths.  Nonparametric latent feature models for link prediction.  In Advances in neural information processing systems, pages 1276–1284, 2009.
  * [MM13] Xiangrui Meng and Michael W Mahoney.  Low-distortion subspace embeddings in input-sparsity time and applications to robust linear regression.  In Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 91–100. ACM, 2013.
  * [MM15] Cameron Musco and Christopher Musco.  Randomized block krylov methods for stronger and faster approximate singular value decomposition.  In Advances in Neural Information Processing Systems, pages 1396–1404, 2015.
  * [MW17] Cameron Musco and David P Woodruff.  Sublinear time low-rank approximation of positive semidefinite matrices.  In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 672–683. IEEE, 2017.
  * [NN13] Jelani Nelson and Huy L. Nguyen.  OSNAP: faster numerical linear algebra algorithms via sparser subspace embeddings.  In 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 117–126. IEEE Computer Society, 2013.
  * [SG07] Mark Steyvers and Tom Griffiths.  Probabilistic topic models.  Handbook of latent semantic analysis, 427(7):424–440, 2007.
  * [SK01] Arora Sanjeev and Ravi Kannan.  Learning mixtures of arbitrary gaussians.  In Proceedings of the thirty-third annual ACM symposium on Theory of computing, pages 247–257, 2001.
  * [Ver10] Roman Vershynin.  Introduction to the non-asymptotic analysis of random matrices.  arXiv preprint arXiv:1011.3027, 2010.
  * [VW04] Santosh Vempala and Grant Wang.  A spectral algorithm for learning mixture models.  Journal of Computer and System Sciences, 68(4):841–860, 2004.
  * [Web03] Marcus Weber.  Clustering by using a simplex structure.  2003\.
  * [Wed72] Per-Ake Wedin.  Perturbation bounds in connection with singular value decomposition.  BIT Numerical Mathematics, 12(1):99–111, 1972.
  * [Woo14] David P. Woodruff.  Sketching as a tool for numerical linear algebra.  Foundations and Trends® in Theoretical Computer Science, 10(1–2):1–157, 2014.
  * [WT10] Daniela M Witten and Robert Tibshirani.  A framework for feature selection in clustering.  Journal of the American Statistical Association, 105(490):713–726, 2010.
  * [XFS+10] Eric P Xing, Wenjie Fu, Le Song, et al.  A state-space mixed membership blockmodel for dynamic network tomography.  The Annals of Applied Statistics, 4(2):535–566, 2010.
  * [YBLG17] Hao Yin, Austin R. Benson, Jure Leskovec, and David F. Gleich.  Local higher-order graph clustering.  In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 555–564. ACM, 2017\.
  * [YL15] Jaewon Yang and Jure Leskovec.  Defining and evaluating network communities based on ground-truth.  Knowl. Inf. Syst., 42(1):181–213, 2015.
  * [ZAX12] Jun Zhu, Amr Ahmed, and Eric P Xing.  Medlda: maximum margin supervised topic models.  Journal of Machine Learning Research, 13(Aug):2237–2278, 2012.