Proof. First, let $\boldsymbol{U}\in\mathbb{R}^{n \times d}$ be any matrix with orthonormal columns with the same columnspace as $\boldsymbol{A}$ (e.g. the $\boldsymbol{U}$ matrix in the SVD of $\boldsymbol{A}$). Then, for any $\mathbf{x}\in\mathbb{R}^d$ we have a one-to-one map to a vector $\mathbf{y}\in\mathbb{R}^d$ such that $\boldsymbol{A}\mathbf{x}=\boldsymbol{U}\mathbf{y}$. So, we need to show that $$\begin{aligned} (1-\varepsilon)\|\boldsymbol{U}\mathbf{y}\|_2^2 \leq \|\boldsymbol{S}\boldsymbol{U}\mathbf{y}\|_2^2 \leq (1+\varepsilon)\|\boldsymbol{U}\mathbf{y}\|_2^2 && \forall\mathbf{y}\in\mathbb{R}^d \end{aligned}$$ Next, we expand the $\ell_2$ norms: $$\begin{aligned} (1-\varepsilon)\mathbf{y}^\intercal\boldsymbol{U}^\intercal\boldsymbol{U}\mathbf{y} \leq \mathbf{y}^\intercal\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}\mathbf{y} \leq (1+\varepsilon)\mathbf{y}^\intercal\boldsymbol{U}^\intercal\boldsymbol{U}\mathbf{y} && \forall\mathbf{y}\in\mathbb{R}^d \end{aligned}$$ Note that $\boldsymbol{U}^\intercal\boldsymbol{U}=\boldsymbol{I}$ by definition, so we get $$\begin{aligned} (1-\varepsilon)\mathbf{y}^\intercal\mathbf{y} \leq \mathbf{y}^\intercal\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}\mathbf{y} \leq (1+\varepsilon)\mathbf{y}^\intercal\mathbf{y} && \forall\mathbf{y}\in\mathbb{R}^d \end{aligned}$$ For $\mathbf{y}=0$, the claim trivially holds, so assuming $\mathbf{y}\neq0$ we divide by $\mathbf{y}^\intercal\mathbf{y}$ on both sides: $$\begin{aligned} (1-\varepsilon) \leq \frac{\mathbf{y}^\intercal\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}\mathbf{y}}{\mathbf{y}^\intercal\mathbf{y}} \leq (1+\varepsilon) && \forall\mathbf{y}\in\mathbb{R}^d \end{aligned}$$ By the Courant–Fischer-Weyl Min-Max Principle, this is equivalent to guaranteeing that $$\begin{aligned} 1-\varepsilon \leq \lambda_i(\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}) \leq 1+\varepsilon && \forall i\in[d] \end{aligned}$$ And rearranging the claim, this becomes $$\begin{aligned} \left|\lambda_i(\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}) - 1\right| \leq \varepsilon && \forall i\in[d] \end{aligned}$$ Or, equivalently,

Proof. First, we let $\mathbf{r}_i$ denote row $i$ of $\boldsymbol{S}$:

We can equivalently define $\mathbf{r}$ entrywise, with an indicator variable: $[\mathbf{r}_i]_j = \frac1{\sqrt{k p_j}} \chi_{[s_i = j]}$. By the outer-product form of matrix-matrix multiplication, note that

So, it suffices to analyze the expected value of $\mathbf{r}_1\mathbf{r}_1^\intercal$. In particular, note that $\mathbf{r}_1\mathbf{r}_1^\intercal$ is a diagonal matrix with entries $\frac1{k p_j} \chi_{[s_i = j]}$. This lets us compute the expected value of an arbitrary diagonal entry of $\mathbf{r}_1\mathbf{r}_1^\intercal$ then:

And so, we have $\mathbb{E}[\mathbf{r}_1\mathbf{r}_1^\intercal] = \frac1k\boldsymbol{I}$, and thus $\mathbb{E}[\boldsymbol{S}^\intercal\boldsymbol{S}] = k\mathbb{E}[\mathbf{r}_1\mathbf{r}_1^\intercal]=\boldsymbol{I}$.

Proof. We now decompose $\boldsymbol{I}-\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U} = \frac1k\sum_{i=1}^k \boldsymbol{R}_i$ for some matrices $\boldsymbol{R}_i$. First, note that the $i^{th}$ row of $\boldsymbol{S}\boldsymbol{U}$ is $\frac{1}{\sqrt{k p_{s_i}}} \mathbf{u}_{s_i}$, where $\mathbf{u}_j$ denotes the $j^{th}$ row of $\boldsymbol{U}$. In particular, by the outer-product view of matrix-matrix products, note that

Which then motivates us to let $\boldsymbol{R}_i \;{\vcentcolon=}\; \boldsymbol{I} - \frac{1}{p_{s_i}} \mathbf{u}_{s_i}\mathbf{u}_{s_i}^\intercal$ (notice $k$ is dropped from the denominator) be our iid matrices.

• By the above equation, we know that $\frac1k\sum_{i=1}^k\boldsymbol{R}_i = \boldsymbol{I}-\boldsymbol{U}^\intercal\boldsymbol{S}^\intercal\boldsymbol{S}\boldsymbol{U}$.

• $\mathbb{E}[\boldsymbol{R}] = \boldsymbol{I} - \sum_{j=1}^n p_j \frac1{p_j}\mathbf{u}_j\mathbf{u}_j^\intercal = \boldsymbol{I} - \sum_{j=1}^n \mathbf{u}_j\mathbf{u}_j^\intercal = \boldsymbol{0}$

• For all $j\in[n]$, $\|\boldsymbol{R}\|_2 \leq \|\boldsymbol{I}\|_2 + \frac1{p_j}\|\mathbf{u}_j\mathbf{u}_j^\intercal\|_2 = 1 + \frac{d}{\|\mathbf{u}_j\|_2^2} \|\mathbf{u}_j\|_2^2 = 1 + d$ (using Lemma 3 Part 4 from here)

• We verify the variance term $\|\mathbb{E}[\boldsymbol{R}^2]\|_2 = (d-1)\boldsymbol{I}$ below:

And so, by the Matrix Bernstein bound,

Plugging in $k = O(\frac{d \log(\frac d\delta)}{\varepsilon^2})$ makes the right hand side term at most $\delta$, completing the proof.

Proof. This proof almost exactly matches that of Theorem 1, except we bound a couple terms from the Matrix Bernstein a little differently:

• $\|\boldsymbol{R}\|_2 \leq \|\boldsymbol{I}\|_2 + \frac1{p_j}\|\mathbf{u}_j\mathbf{u}_j^\intercal\|_2 = 1 + \frac{\tilde d}{\tilde\tau_i} \|\mathbf{u}_j\|_2^2 = 1 + \frac{\tilde d}{\tilde \tau_i} \tau_i \leq 1 + \tilde d$

• And the variance analysis:

$$\begin{aligned} \mathbb{E}[\boldsymbol{R}^2] &= \mathbb{E}[\boldsymbol{I} - \tfrac2{p_j} \mathbf{u}_j\mathbf{u}_j^\intercal + \tfrac1{p_j^2} \mathbf{u}_j\mathbf{u}_j^\intercal\mathbf{u}_j\mathbf{u}_j^\intercal] \\ &= \boldsymbol{I} - 2\boldsymbol{I} + \mathbb{E}[\tfrac1{p_j^2} \mathbf{u}_j\mathbf{u}_j^\intercal\mathbf{u}_j\mathbf{u}_j^\intercal] \\ &= \boldsymbol{I} - 2\boldsymbol{I} + \sum_{j=1}^n[p_j \tfrac1{p_j^2} \mathbf{u}_j\mathbf{u}_j^\intercal\mathbf{u}_j\mathbf{u}_j^\intercal] \\ &= \boldsymbol{I} - 2\boldsymbol{I} + \sum_{j=1}^n[\tfrac1{p_j} \|\mathbf{u}_j\|_2^2 \mathbf{u}_j\mathbf{u}_j^\intercal] \\ &= \boldsymbol{I} - 2\boldsymbol{I} + \sum_{j=1}^n[\tfrac{\tilde d}{\tilde\tau_i} \tau_i \mathbf{u}_j\mathbf{u}_j^\intercal] \\ &\leq \boldsymbol{I} - 2\boldsymbol{I} + \tilde d\sum_{j=1}^n[\mathbf{u}_j\mathbf{u}_j^\intercal] \\ &= \boldsymbol{I} - 2\boldsymbol{I} + \tilde d\boldsymbol{I} \\ &= (\tilde d-1)\boldsymbol{I} \end{aligned}$$ From which the result follows by Matrix Bernstein.