\section{Proofs omitted from the main body}\label{sec:app}

\subsection{Proof of Claim~\ref{cl:typical-hp-basic} and Claim~\ref{cl:frobenius-norm-bound}}
We will use
\begin{theorem}[Bernstein's inequality]\label{thm:bernstein}
Let $X_1,\ldots, X_n$ be independent zero mean random variables such that $|X_i|\leq L$ for all $i$ with probability $1$, and let $X:=\sum_{i=1}^n X_i$. Then
$$
{\bf Pr}[X>t]<\exp\left(-\frac{\frac1{2}t^2}{\sum_{i=1}^n {\bf E}[X_i^2]+\frac1{3}L t}\right).
$$
\end{theorem}

\begin{proofof}{Claim~\ref{cl:typical-hp-basic}}
\paragraph{Proving (1).} The bound follows by standard concentration inequalities, as we now show. Since the normal distribution is rotationally invariant, we have that
\begin{equation}\label{eq:i4g34g}
X^T(I-M)X=\sum_{i=1}^d (\lambda_i-1)Y_i^2=\mathrm{Tr}(M-I)+\sum_{i=1}^d (\lambda_i-1)(Y_i^2-1),
\end{equation}
where $Y\sim N(0, I_d)$ and $\lambda_i$ are the eigenvalues of $M$.  We now apply Bernstein's inequality (Theorem~\ref{thm:bernstein}) to random variables $(\lambda_i-1)(Y_i^2-1)$ (note that they are zero mean). We also have ${\bf E}[(\lambda_i-1)^2(Y_i^2-1)^2]\leq O((\lambda_i-1)^2)$.
We later combine it with the fact that $|\mathrm{Tr}(I-M)|\leq \gamma\leq \frac1{2}\cdot \frac1{100}$ for all $S\in {\mathcal E}(\gamma)$ to obtain the result. We also have $|(\lambda_i-1)Y_i|\leq ||I-M||_F C\sqrt{\log n}\leq  \gamma\cdot C\sqrt{\log n}$ for all $i$ with probability at least $1-n^{-40}/4$ as long as $C>0$ is larger than an absolute constant. We thus have by applying Theorem~\ref{thm:bernstein} to random variables clipped at $\gamma C \sqrt{\log n}$ in
magnitude, which we denote by event $\mathcal{F}$, to conclude for all $t\geq 0$,
$$
{\bf Pr}[\sum_{i=1}^d (\lambda_i-1)(Y_i^2-1)>t \mid \mathcal{F}]<2\exp\left(-\frac{\frac1{2}t^2}{O(\sum_{i=1}^n (\lambda_i-1)^2)+(\frac1{3} \gamma C\sqrt{\log n}) t}\right).
$$
Note the random variables are still independent and zero-mean conditioned on $\mathcal{F}$, and
${\bf E}[(\lambda_i-1)^2(Y_i^2-1)^2]\leq O((\lambda_i-1)^2)$ continues to hold,
since the clipping changes the expectation by at most a factor of $(1+O(n^{-40}))$.
By a union bound we can remove the conditioning on $\mathcal{F}$,
$$
{\bf Pr}[\sum_{i=1}^d (\lambda_i-1)(Y_i^2-1)>t]<2\exp\left(-\frac{\frac1{2}t^2}{O(\sum_{i=1}^n (\lambda_i-1)^2)+(\frac1{3} \gamma C\sqrt{\log n}) t}\right) + \frac{n^{-40}}{4}.
$$
Setting $t=\frac1{100}$, and using the fact that $\sum_i (\lambda_i-1)^2=||I-M||_F^2\leq \gamma^2$, we get
\begin{eqnarray*}
{\bf Pr}[\sum_{i=1}^d (\lambda_i-1)(Y_i^2-1) >\frac1{2}\cdot \frac1{100}] & < & 2\exp\left(-\frac{\frac1{2}(\frac1{2}\cdot \frac1{100})^2}{O(\gamma^2)+(\frac1{3}\cdot (\frac1{2}\cdot \frac1{100}) \gamma C\sqrt{\log n})}\right) + \frac{n^{-40}}{4}\\
& =& \exp(-\Omega(1/(\gamma \sqrt{\log n}))) + \frac{n^{-40}}{4}\\
& < & \frac{n^{-40}}{2},
\end{eqnarray*}
since $\gamma\leq 1/\log^2 n$ by assumption, for a sufficiently large $n$. Combining this with~\eqref{eq:i4g34g}, we get, using the fact that $|\mathrm{Tr}(I-M)|\leq \gamma<\frac1{2}\cdot\frac1{100}$  for $S\in {\mathcal E}(\gamma)$ that
$$
{\bf Pr}[X^T(I-M)X>\frac1{100}]\leq {\bf Pr}[|\sum_{i=1}^d (\lambda_i-1)(Y_i^2-1)|>\frac1{2}\frac1{100}]<n^{-40}/2,
$$
as required.

We also have
$$
X^T(I-M)^2X=\sum_{i=1}^d (\lambda_i-1)^2Y_i^2\leq ||I-M||_F^2\cdot \max_{i\in [d]} |Y_i|^2\leq O(\log n)\cdot ||I-M||_F^2=O(\log n\gamma^2)\leq \frac1{100}
$$
with probability at least $1-n^{-40}/2$ by standard properties of Gaussian random variables. Putting the two estimates together and taking a union bound over the failure events now shows that ${\bf Pr}_{X\sim N(0, I_d)}[X\not \in {\mathcal{T}}(S, U)]<n^{-40}$, as required.

\paragraph{Proving (2).}  Recall that  ${\mathcal{T}}(S, U)=\left\{x\in \mathbb{R}^d: |x^T(I-M)x|\leq \frac1{100}\text{~and~}x^T(I-M)^2x\leq \frac1{100}\right\}$.
For any $S'$ we have that  $X\sim N(0, M')$, where $M'=(S'U)^TS'U$, so $X=M'^{1/2}Y$, where $Y=N(0, I_d)$. We thus have
\begin{equation*}
\begin{split}
X^T(I-M)X=(M'^{1/2}Y)^T(I-M)(M'^{1/2}Y)=Y^TM'^{1/2}(I-M)M'^{1/2}Y.
\end{split}
\end{equation*}

We now show that
\begin{equation}\label{eq:y-bound-1}
\begin{split}
{\bf Pr}_{Y\sim N(0, I_d)}\left[\left|Y^TM'^{1/2}(I-M)M'^{1/2}Y\right|>\frac1{100}\right]<1/n^{20}
\end{split}
\end{equation}

Let $Q:=M'^{1/2}(I-M)M'^{1/2}$, and let $1-\tilde \lambda_i, i=1,\ldots, d$ denote the eigenvalues of $Q$. We have
$$
Y^TM'^{1/2}(I-M)M'^{1/2}Y=\sum_{i=1}^d (1-\tilde \lambda_i) Z_i^2,
$$
where $Z\sim N(0, I_d)$. Note that
\begin{equation}\label{eq:trace-bound}
\begin{split}
|\sum_{i=1}^d (1-\tilde \lambda_i)|&=|\mathrm{Tr}(Q)|=|\mathrm{Tr}(M'^{1/2}(I-M)M'^{1/2})|\\
&=|\mathrm{Tr}(M'(I-M))|=|\mathrm{Tr}((I-(I-M'))(I-M))|\\
&\leq |\mathrm{Tr}(I-M)|+|\mathrm{Tr}\left((I-M')\left(I-M\right)\right)|\\
&=\gamma+|\mathrm{Tr}\left((I-M')\left(I-M\right)\right)|\text{~~~~~(since $|\mathrm{Tr}(I-M)|\leq \gamma$ for all $S\in {\mathcal E}(\gamma)$)}\\
&\leq \gamma+||I-M'||_F\cdot ||M-I||_F \text{~~~~(by von Neumann and Cauchy-Schwarz inequalities)}\\
&\leq \gamma+ \gamma^2
\end{split}
\end{equation}
We thus have
\begin{equation}
\begin{split}
Y^TM'^{1/2}(I-M)M'^{1/2}Y&=\sum_{i=1}^d (1-\tilde \lambda_i) Z_i^2\\
&=\sum_{i=1}^d (1-\tilde \lambda_i)+\sum_{i=1}^d (1-\tilde \lambda_i) (Z_i^2-1)\\
\end{split}
\end{equation}

We now use a calculation analogous to the above for {\bf (1)} to show that $|\sum_{i=1}^d (1-\tilde \lambda_i) (Z_i^2-1)|\leq \frac1{2}\cdot \frac1{100}$ with probability at least $1-n^{-40}/4$. Indeed, we first verify that
the variance is bounded by
\begin{eqnarray}\label{eq:gvarc}
  O(\sum_{i=1}^d (1-\tilde \lambda_i)^2) & = & O(||Q||_F^2) \notag \\
  & = & O(||M'^{1/2}(I-M)M'^{1/2}||_F^2)\notag \\
  & \leq & O(||M'||_2^2) ||I-M||_F^2 \text{~~~~~(by sub-multiplicativity)} \notag\\
  & \leq & O((||I||_2 + ||M'-I||_F)^2) ||I-M||_F^2 \notag\\
  & \leq& O(||I-M||_F^2) \notag\\
  & = & O(\gamma^2).
\end{eqnarray}
We also have
\begin{eqnarray*}
  |(1-\tilde \lambda_i)Y_i| & \leq & ||Q||_F C \sqrt{\log n}\\
  & \leq & ||M'||_2 ||I-M||_F C \sqrt{\log n}\text{~~~~~~(by sub-multiplicativity)}\\
  & \leq & (||I||_2 + ||M'-I||_F)||I-M||_F C \sqrt{\log n}\\
  & \leq & 2 ||I-M||_F C \sqrt{\log n}\\
  &\leq & 2 \gamma\cdot C\sqrt{\log n},
\end{eqnarray*}
for all $i$ with probability at least $1-1/n^{40}/5$ as long as $C>0$ is larger than an absolute constant. We thus have by Theorem~\ref{thm:bernstein} (applied to clipped variables and then
unclipping by a union bound as in ({\bf 1}))
for all $t\geq 0$ that
$$
{\bf Pr}[|Y^TM'^{1/2}(I-M)M'^{1/2}Y-\sum_{i=1}^d (1-\tilde \lambda_i)|>t]<\exp\left(-\frac{\frac1{2}t^2}{O(\sum_{i=1}^n (1-\tilde \lambda_i)^2)+(\frac1{3} 2\gamma C\sqrt{\log n}) t}\right) + n^{-40}/5.
$$
Setting $t=\frac1{2}\frac1{100}$, and using the upper bound $O(\sum_i (1-\tilde \lambda_i)^2)=O(\gamma^2)$ obtained in~\eqref{eq:gvarc}, we get
\begin{equation*}
\begin{split}
{\bf Pr}[|Y^TM'^{1/2}(I-M)M'^{1/2}Y-\sum_{i=1}^d (1-\tilde \lambda_i)|>\frac1{2}\cdot\frac1{100}]&<\exp\left(-\frac{\frac1{2}(\frac1{2}\cdot\frac1{100})^2}{C\gamma^2+(\frac1{3}\cdot \frac1{2}\frac1{100} \gamma C\sqrt{\log n})}\right) + n^{-40}/5\\
&=\exp(-\Omega(1/(\gamma \sqrt{\log n}))) + n^{-40}/5 <n^{-40}/4
\end{split}
\end{equation*}
since $\gamma\leq 1/\log^2 n$ by assumption, for a sufficiently large $n$. Since $|\sum_{i=1}^d (1-\tilde \lambda_i)|\leq \gamma+2\gamma^2\leq \frac1{2}\cdot \frac1{100}$ by~\eqref{eq:trace-bound}, we get by triangle inequality that
$$
{\bf Pr}_{X\sim N(0, M')}[|X^T(I-M)X|>\frac1{100}]\leq n^{-40}/4.
$$

Similarly to {\bf (1)} above, we have, when $X\sim N(0, M'), X=M'^{1/2} Y, Y\sim N(0, I_d)$,
\begin{equation*}
\begin{split}
X^T(I-M)^2X&=Y^TM'^{1/2}(I-M)^2M'^{1/2}Y=\sum_{i=1}^d \tilde \tau_i Z_i^2\\
&\leq \mathrm{Tr}(M'^{1/2}(I-M)^2M^{1/2})\cdot \max_{i\in [d]} Z_i^2\\
&\leq O(\log n)\cdot \mathrm{Tr}(M'^{1/2}(I-M)^2M'^{1/2})
\end{split}
\end{equation*}
with probability at least $1-n^{-40}/2$ over the choice of $X$, as $\max_{i\in [d]} Z_i^2\leq C\log n$ with high probability if $C$ is a sufficiently large constant by standard properties of Gaussian random variables. Since $\mathrm{Tr}(M'^{1/2}(I-M)^2M'^{1/2})=\mathrm{Tr}(M'(I-M)^2)\leq 2 ||I-M||_F^2$ (as $\gamma<1/\log^2 n<1/3$ by assumption of the lemma), we get
\begin{equation*}
\begin{split}
X^T(I-M)^2X&\leq O(\log n)\cdot \mathrm{Tr}(M'^{1/2}(I-M)^2M'^{1/2})\leq O(\log n)\cdot \gamma^2\leq \frac1{100} \text{~~~~(since $\gamma<1/\log^2 n$)}
\end{split}
\end{equation*}
with probability at least $1-n^{-40}/4$. A union bound over the failure events yields ${\bf Pr}_{X\sim N(0, M')}[X\not \in {\mathcal{T}}(S, U)]<n^{-40}$, as required.

This completes the proof.
\end{proofof}

\begin{proofof}{Lemma~\ref{lm:ratio-bound-cond}}
By assumption that $S\in {\mathcal E}(\gamma)$ we have that $||I-M||_2\leq \gamma$, so Taylor expansion is valid and gives

$$
\frac1{2}x^Tx-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M=-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+R(x),
$$
where for all $x\in {\mathcal{T}}(S, U)$  one has $R(x)\leq \sum_{k\geq 2} x^T(I-M)^2x+\mathrm{Tr}(I-M)^k$.

We have by Lemma~\ref{lm:lmcimf2} that $R(x)\leq C (x^T(I-M)^2x+||I-M||_F^2)$ for an absolute constant $C>0$, for all $x\in {\mathcal{T}}(S, U)$ and $S\in {\mathcal E}(\gamma)$. We thus have
\begin{equation}\label{eq:0kg43gg4ger}
\begin{split}
&e^{-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-C(x^T(I-M)^2x+||I-M||_F^2)}\\
&\leq e^{-\frac1{2}x^Tx+\frac1{2}\mathrm{Tr}(I-M)-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M}\\
&\leq e^{-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+C(x^T(I-M)^2x+||I-M||_F^2)}
\end{split}
\end{equation}
for all such $M$ and $x$.

We now Taylor expand $e^{-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+A(x^T(I-M)^2x+||I-M||_F^2)}$, where $A$ is any constant (positive or negative), getting
\begin{equation}\label{eq:231hjhiFMD}
\begin{split}
&e^{-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+A(x^T(I-M)^2x+||I-M||_F^2)}\\
&=\sum_{k\geq 1}\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+A(x^T(I-M)^2x+||I-M||_F^2)\right)^k/k!.
\end{split}
\end{equation}

For $k=2$ we have
\begin{equation}\label{eq:90fggd3dxXFS1233}
\begin{split}
&\left|\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+x^T(I-M)^2x+||I-M||_F^2\right)^2/2+\frac1{8}x^T(I-M)x\cdot \mathrm{Tr}(I-M)\right|\\
&\leq C\left((x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2\right),\\
\end{split}
\end{equation}
where we used the fact $|x^T(I-M)x|\leq \frac1{100}$ for $x\in {\mathcal{T}}(S, U)$ and $|\mathrm{Tr}(I-M)|\leq \gamma<\frac1{100}$ for $S\in {\mathcal E}(\gamma)$.

For all $k\geq 3$ we use the bound
\begin{equation}\label{eq:90fggd3dxXFS}
\begin{split}
&|\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+x^T(I-M)^2x+||I-M||_F^2\right)^k|\\
&\leq \left(|x^T(I-M)x|+\frac1{2}|\mathrm{Tr}(I-M)|+x^T(I-M)^2x+||I-M||_F^2\right)^k\\
&\leq \left(|x^T(I-M)x|+\frac1{2}|\mathrm{Tr}(I-M)|+x^T(I-M)^2x+||I-M||_F^2\right)^3\\
&\leq C((x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2),\\
\end{split}
\end{equation}
where we used the bound  $|x^T(I-M)x|+\frac1{2}|\mathrm{Tr}(I-M)|+x^T(I-M)^2x+||I-M||_F^2\leq 1$ to go from the second line to the third, and the last line follows from the observation that every term in the expansion of
$$
\left(|x^T(I-M)x|+\frac1{2}|\mathrm{Tr}(I-M)|+x^T(I-M)^2x+||I-M||_F^2\right)^3
$$ contains either at least a square of one of the first two terms or at least one of the last two.

\if 0
where we used the fact that $|x^T(I-M)x|+x^T(I-M)^2x+||I-M||_F^2\leq 1/2$ for all $S\in {\mathcal E}(\gamma)$ and $x\in {\mathcal{T}}(S, U)$.  Indeed, one has $||I-M||_F\leq \gamma<1/(C\log n)<1/100$ assumption on $\gamma$, $|x^T(I-M)x|\leq \frac1{100}$ and $x^T(I-M)^2x\leq \frac1{100}$ by definition of ${\mathcal{T}}(S, U)$. Similarly, we get
\begin{equation*}
\begin{split}
&|x^T(I-M)x|\cdot \left(|x^T(I-M)x|+x^T(I-M)^2x+||I-M||_F^2\right)^{k-1}\\
&= |x^T(I-M)x\cdot \left(|x^T(I-M)x|+x^T(I-M)^2x+||I-M||_F^2\right)\cdot \left(|x^T(I-M)x|+x^T(I-M)^2x+||I-M||_F^2\right)^{k-2}|\\
&\leq  (x^T(I-M)x)^2 +(\mathrm{Tr}(I-M))^2+ x^T(I-M)^2x+||I-M||_F^2,
\end{split}
\end{equation*}
where we again used the fact that $|x^T(I-M)x|+x^T(I-M)^2x+|I-M||_F^2\leq 1/2$ for all $S\in {\mathcal E}(\gamma)$ and $x\in {\mathcal{T}}(S, U)$. Putting these bounds together, we get
$$
|\left(x^T(I-M)x+x^T(I-M)^2x+||I-M||_F^2\right)^k|\leq C((x^T(I-M)x)^2+ x^T(I-M)^2x+||I-M||_F^2)
$$
for an absolute constant $C>0$.
\fi
Substituting these bounds into~\eqref{eq:231hjhiFMD}, we get
\begin{equation*}
\begin{split}
&e^{-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+A(x^T(I-M)^2x+||I-M||_F^2)}\\
&=\sum_{k\geq 1}\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+A(x^T(I-M)^2x+||I-M||_F^2)\right)^k/k!\\
&\leq -\frac1{2} x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-\frac1{8}x^T(I-M)x\cdot \mathrm{Tr}(I-M)\\
&+C((x^T(I-M)x)^2 + x^T(I-M)^2x+\mathrm{Tr}(I-M)^2+||I-M||_F^2)\text{~~~~(for a constant $C>0$ that may depend on $A$)}\\
&+\sum_{k\geq 3} (A+1)^k ((x^T(I-M)x)^2 +\mathrm{Tr}(I-M)^2+ x^T(I-M)^2x+||I-M||_F^2)/k!\\
&\leq -\frac1{2} x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)+C''(x^T(I-M)^2x+(\mathrm{Tr}(I-M))^2+x^T(I-M)x^2+||I-M||_F^2)\\
\end{split}
\end{equation*}
for an absolute constant $C''>0$. The provides the upper bound in the claimed result. The lower bound is provided by a similar calculation, which we omit.
\end{proofof}

\begin{proofof}{Lemma~\ref{lm:conditioning}}
Since ${\bf E}[(Z-1)^2]\leq \epsilon$ by assumption of the lemma, for any event ${\mathcal E}$ one has ${\bf E}[(Z-1)^2\cdot \mathbf{I}_{\bar {\mathcal E}}]\leq \epsilon$, where $\mathbf{I}_{\bar {\mathcal E}}$ is the indicator of $\bar {\mathcal E}$, the complement of ${\mathcal E}$. This also means that
$$
{\bf E}[(Z-1)^2|\bar {\mathcal E}]\leq \epsilon/{\bf Pr}[\bar {\mathcal E}].
$$

On the other hand, by Jensen's inequality
\begin{equation*}
\begin{split}
{\bf E}[|Z-1||\bar {\mathcal E}]&\leq \left({\bf E}[(Z-1)^2|\bar {\mathcal E}]\right)^{1/2},\\
\end{split}
\end{equation*}
and putting these two bounds together we get
\begin{equation*}
\begin{split}
{\bf E}[|Z-1|\cdot {\bf I}[\bar {\mathcal E}]]&={\bf E}[|Z-1| |\bar {\mathcal E}]\cdot {\bf Pr}[\bar {\mathcal E}]\leq {\bf Pr}[\bar {\mathcal E}]\cdot \left({\bf E}[(Z-1)^2|\bar {\mathcal E}]\right)^{1/2}\leq {\bf Pr}[\bar {\mathcal E}]\cdot \left(\epsilon/{\bf Pr}[\bar {\mathcal E}]\right)^{1/2}=\sqrt{\epsilon\cdot {\bf Pr}[\bar {\mathcal E}]}.\\
\end{split}
\end{equation*}
This means that
\begin{equation*}
\begin{split}
\left|{\bf E}[Z]-{\bf E}[Z|{\mathcal E}]\right|&\leq \left|{\bf E}[Z]-\frac1{{\bf Pr}[{\mathcal E}]}{\bf E}[Z\cdot {\bf I}_{{\mathcal E}}]\right|\\
&\leq \left|{\bf E}[Z]-\frac1{{\bf Pr}[{\mathcal E}]}{\bf E}[Z]+\frac1{{\bf Pr}[{\mathcal E}]}{\bf E}[Z\cdot {\bf I}_{\bar {\mathcal E}}]\right|\\
&\leq {\bf E}[Z]\left(\frac1{1-{\bf Pr}[\bar {\mathcal E}]}-1\right)+\left|\frac1{{\bf Pr}[{\mathcal E}]}{\bf E}[Z\cdot {\bf I}_{\bar {\mathcal E}}]\right|\\
&\leq {\bf E}[Z]\cdot 2{\bf Pr}[\bar {\mathcal E}]+2{\bf E}[Z\cdot {\bf I}_{\bar {\mathcal E}}]\text{~~~~(since $\frac1{1-x}-1\leq 2x$ for $x\in (0, 1/2)$)}\\
&\leq {\bf E}[Z]\cdot 2{\bf Pr}[\bar {\mathcal E}]+2({\bf Pr}[\bar {\mathcal E}]+{\bf E}[|Z-1|\cdot {\bf I}_{\bar {\mathcal E}}])\\
&\leq 2(1+{\bf E}[Z]){\bf Pr}[\bar {\mathcal E}]+2\sqrt{\epsilon {\bf Pr}[\bar {\mathcal E}]}.
\end{split}
\end{equation*}
\end{proofof}

\subsection{Proofs of moment bounds (Lemma~\ref{lm:frobenius-norm} and Lemma~\ref{lm:variance-bound})}\label{sec:moment-bounds}

\begin{proofof}{Lemma~\ref{lm:frobenius-norm} and Lemma~\ref{lm:variance-bound}}
We start by noting that for every $i, j\in [1:d]$  the matrix $M=U^TS^TSU$ satisfies
\begin{equation*}
\begin{split}
M_{ij}&=\sum_{r=1}^B \sum_{a=1}^n\sum_{b=1}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j} \\
&= \sum_{a=1}^n U_{a, i}  U_{a, j} \left(\sum_{r=1}^BS_{r, a}^2\right) +\sum_{r=1}^B\sum_{a=1}^n\sum_{b=1, b\neq a}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j}\\
&= \delta_{i, j} +\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j},\\
\end{split}
\end{equation*}
where $\delta_{i, j}$ equals $1$ if $i=j$ and equals $0$ otherwise. We thus have, for every $i, j\in [1:d]$, that
\begin{equation*}
\begin{split}
(M-I)_{ij}&=\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j},\\
\end{split}
\end{equation*}
which in particular means that
\begin{equation}\label{eq:eq:3}
\begin{split}
\mathrm{Tr}(I-M)=-\sum_{i}(M-I)_{ii}&=-\sum_i\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, i},\\
&=-\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a} S_{r, b} \cdot U_a U_b^T,\\
\end{split}
\end{equation}
(note that it immediately follows that ${\bf E}_S[\mathrm{Tr}(I-M)]=0$, as ${\bf E}_S[S_{r, a} S_{r, b}]=0$ for $a\neq b$)
and
\begin{equation}\label{eq:eq:4}
\begin{split}
x^T(I-M)x&=-\sum_{ij} (M-I)_{ij} x_i x_j=-\sum_{i, j}\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j} x_i x_j\\
&=-\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n S_{r, a} S_{r, b} (Ux)_a (U x)_b\\
\end{split}
\end{equation}
(note that it immediately follows that ${\bf E}_S[x^T(I-M)x]=0$ for all $x$, as ${\bf E}_S[S_{r, a} S_{r, b}]=0$ for $a\neq b$).

We also have
\begin{equation*}
\begin{split}
(M-I)^2_{ij}&=\sum_{r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{r'=1}^B\sum_{\substack{c, d=1,\\c\neq d}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j} S_{r', c}U_{c, i}  S_{r', d} U_{d, j}\\
\end{split}
\end{equation*}
and hence
\begin{equation}\label{eq:eq:1}
\begin{split}
||I-M||_F^2&=\sum_{ij} (M-I)^2_{ij}=\sum_{ij} \sum_{r=1}^B \sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{r'=1}^B\sum_{\substack{c, d=1,\\c\neq d}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j} S_{r', c}U_{c, i}  S_{r', d} U_{d, j}\\
&=\sum_{r=1}^B \sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{r'=1}^B\sum_{\substack{c, d=1,\\c\neq d}}^n S_{r, a} S_{r, b} S_{r', c} S_{r', d} (\sum_i U_{a, i}  U_{c, i}) (\sum_j U_{b, j}   U_{d, j})\\
&=\sum_{r=1}^B \sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{r'=1}^B\sum_{\substack{c, d=1,\\c\neq d}}^n S_{r, a} S_{r, b} S_{r', c} S_{r', d} \cdot U_{a}U_{c}^T \cdot U_{b}  U_{d}^T\\
&=\sum_{r_1=1}^B \sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{r_2=1}^B\sum_{\substack{a_2, b_2=1,\\a_2\neq b_2}}^n S_{r_1, a_1} S_{r_1, b_1} S_{r_2, a_2} S_{r_2, b_2} \cdot U_{a_1}U_{a_2}^T \cdot U_{b_1}  U_{b_2}^T\\
\end{split}
\end{equation}

We also need
\begin{equation}\label{eq:eq:2}
\begin{split}
x^T(I-M)^2x&=||(I-M)x||_2^2=\sum_{i=1}^d \left(\sum_{j=1}^d (I-M)_{ij}x_j\right)^2\\
&=\sum_{i=1}^d \sum_{j=1}^d \sum_{\bar j=1}^d  x_jx_{\bar j}\cdot \sum_{r=1}^B\sum_{\bar r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{\substack{\bar a, \bar b=1,\\\bar a\neq \bar b}}^n S_{r, a}U_{a, i}  S_{r, b} U_{b, j}\cdot S_{\bar r, \bar a}U_{\bar a, i}  S_{\bar r, \bar b} U_{\bar b, \bar j}\\
&=\sum_{r=1}^B\sum_{\bar r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{\substack{\bar a, \bar b=1,\\\bar a\neq \bar b}}^n S_{r, a}  S_{r, b} S_{\bar r, \bar a}    S_{\bar r, \bar b}\cdot  (\sum_{i=1}^d  U_{a, i}U_{\bar a, i})(\sum_{j=1}^d  U_{b, j} x_j) (\sum_{\bar j} U_{\bar b, \bar j} x_{\bar j})\\
&=\sum_{r=1}^B\sum_{\bar r=1}^B\sum_{\substack{a, b=1,\\a\neq b}}^n \sum_{\substack{\bar a, \bar b=1,\\\bar a\neq \bar b}}^n S_{r, a}  S_{r, b} S_{\bar r, \bar a}    S_{\bar r, \bar b}\cdot  U_{a}U_{\bar a}^T\cdot (U x)_b (Ux)_{\bar b}\\
&=\sum_{r_1=1}^B\sum_{r_2=1}^B\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2}\cdot  U_{a_1}U_{a_2}^T\cdot (U x)_{b_1} (Ux)_{b_2}
\end{split}
\end{equation}

\paragraph{Bounding ${\bf E}_S[||I-M||_F^2], {\bf E}_S[(x^T(I-M)x)^2], {\bf E}_S[x^T(I-M)^2x], {\bf E}_S[(x^T(I-M)x) \mathrm{Tr}(I-M)], {\bf E}_S[\mathrm{Tr}(I-M)^2]$}
We first note that for for any $r_1, r_2$ and $a_1\neq b_1, a_2\neq b_2$ the quantity
$$
{\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2}]
$$
is only nonzero when $r_1=r_2$ and $\{a_1, b_1, a_2, b_2\}$ contains two distinct elements, each with multiplicity $2$  (let ${\bf I}_*(\{a_q, b_q\}_{q=1}^2)$ denote the indicator of the latter condition). In that case one has ${\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2}]=1/B^2$. Note that the expression above appears in
all of ${\bf E}_S[(x^T(I-M)x)^2], {\bf E}_S[x^T(I-M)^2x], {\bf E}_S[(x^T(I-M)x) \mathrm{Tr}(I-M)], {\bf E}_S[(\mathrm{Tr}(I-M))^2]$. Specifically, all of these expressions can be written as
\begin{equation*}
\begin{split}
&\sum_{r_1=1}^B\sum_{r_2=1}^B\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2} S_{r_2, b_2}]\\
&\cdot  (U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H},
\end{split}
\end{equation*}
where $A,B, C, D, E, F, G, H\in \{0, 1\}$ and $A+B+C+D+E+F+G+H=2$.  We thus have

\begin{equation*}
\begin{split}
&|\sum_{r_1=1}^B\sum_{r_2=1}^B\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2} S_{r_2, b_2}]\cdot\\
&\cdot  (U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}]|\\
&\leq \frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf I}_*(\{a_q, b_q\}_{q=1}^2) |U_{a_1}U_{a_2}^T|^{A} |U_{b_1}U_{b_2}^T|^{B}\cdot |(U x)_{a_1} (Ux)_{a_2}|^{C} |(U x)_{b_1} (Ux)_{b_2}|^{D}\cdot \\
&\cdot |(U x)_{a_1} (Ux)_{b_1}|^{E} |U_{a_1} U_{b_1}^T|^{F}\cdot |(U x)_{a_2} (Ux)_{b_2}|^{G} |U_{a_2} U_{b_2}^T|^{H}.\\
\end{split}
\end{equation*}
We have $|U_{a}U_{b}^T|\leq ||U_{a}||_2 \cdot ||U_b||_2$ by Cauchy-Schwarz, and $|(U x)_{a}|\leq ||U_{a}||_2\cdot O(\sqrt{\log n})$ since $x\in {\mathcal{T}}^*$ by assumption of the lemma, so
\begin{equation*}
\begin{split}
&\frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf I}_*(\{a_q, b_q\}_{q=1}^2)|U_{a_1}U_{a_2}^T|^{A} |U_{b_1}U_{b_2}^T|^{B}\cdot |(U x)_{a_1} (Ux)_{a_2}|^{C} |(U x)_{b_1} (Ux)_{b_2}|^{D}\cdot |(U x)_{a_1} (Ux)_{b_1}|^{E} |U_{a_2} U_{b_2}^T|^{F}\\
&\leq (O(\log n))^{C+D+E+G}\frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf I}_*(\{a_q, b_q\}_{q=1}^2)(||U_{a_1}||_2 ||U_{a_2}||_2)^{A} \cdot (||U_{b_1}||_2 ||U_{b_2}||_2)^{B}\cdot (||U_{a_1}||_2 ||U_{a_2}||_2)^{C}\\
&\cdot (||U_{b_1}||_2||U_{b_2}||_2)^{D}\cdot (||U_{a_1}||_2 ||U||_{b_1}||_2)^{E} (||U_{a_1}||_2 ||U_{b_1}||_2)^{F}\cdot (||U_{a_2}||_2||U||_{b_2}||_2)^{G} (||U_{a_2}||_2 ||U_{b_2}||_2)^{H}.\\
\end{split}
\end{equation*}

Since we are only summing over $\{a_1, a_2, b_1, b_2\}$ that contain two distinct elements, we have
\begin{equation*}
\begin{split}
&(O(\log n))^{C+D+E+G}\frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n {\bf I}_*(\{a_q, b_q\}_{q=1}^2)(||U_{a_1}||_2 ||U_{a_2}||_2)^{A} \cdot (||U_{b_1}||_2 ||U_{b_2}||_2)^{B}\cdot (||U_{a_1}||_2 ||U_{a_2}||_2)^{C}\\
&\cdot (||U_{b_1}||_2||U_{b_2}||_2)^{D}\cdot (||U_{a_1}||_2 ||U||_{b_1}||_2)^{E} (||U_{a_1}||_2 ||U_{b_1}||_2)^{F}\cdot (||U_{a_2}||_2||U||_{b_2}||_2)^{G} (||U_{a_2}||_2 ||U_{b_2}||_2)^{H}\\
&\leq (O(\log n))^{C+D+E+G}\frac{1}{B}\sum_{\substack{a_1, b_1=1}}^n ||U_{a_1}||^2_2 ||U_{a_2}||^2_2\\
&\leq (O(\log n))^{C+D+E+G}\frac{1}{B}(\sum_{\substack{a_1=1}}^n ||U_{a_1}||^2_2)^2\\
&\leq (O(\log n))^{C+D+E+G}\frac{d^2}{B},
\end{split}
\end{equation*}
where we used the fact that $\sum_a ||U_a|_2^2=d$. Noting that $C+D+E+G=0$ for ${\bf E}_S[||I-M||_F^2]$ and $C+D+E+G=1$ for ${\bf E}_S[x^T(I-M)x \mathrm{Tr}(I-M)]$ completes the proof.

\paragraph{Bounding ${\bf E}_S[(x^T(I-M)x)^2 \mathrm{Tr}(I-M)], {\bf E}_S[x^T(I-M)^2x\cdot \mathrm{Tr}(I-M)], {\bf E}_S[||I-M||_F^2\cdot \mathrm{Tr}(I-M)], {\bf E}_S[(x^T(I-M)x)^2 \cdot x^T(I-M)x], {\bf E}_S[x^T(I-M)^2x\cdot x^T(I-M)x], {\bf E}_S[||I-M||_F^2\cdot x^T(I-M)x]$}
All of the above expressions can be written as
\begin{equation*}
\begin{split}
&\sum_{r_1=1}^B\sum_{r_2=1}^B\sum_{r_3=1}^B\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n {\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2} S_{r_2, b_2} S_{r_3, a_3} S_{r_3, b_3}]\\
&\cdot  (U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}\\
& \cdot ((U x)_{a_3} (Ux)_{b_3})^{I} (U_{a_3} U_{b_3}^T)^{J}
\end{split}
\end{equation*}
where $A, B, C\ldots$ are in $\{0, 1\}$ and $A+B+C+D+E+F+G+H+I+J=3$.

We first note that for for any $r_1, r_2, r_3$ and $a_1\neq b_1, a_2\neq b_2, a_3\neq b_3$ the quantity
$$
{\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2} S_{r_3, a_3}    S_{r_3, b_3}]
$$
is only nonzero when $r_1=r_2=r_3$ and $\{a_1, b_1, a_2, b_2, a_3, b_3\}$ contains three distinct elements, each with multiplicity $2$. Let ${\bf I}_*(\{a_q, b_q\}_{q=1}^3)$ denote the indicator of the latter condition. In that case one has ${\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2} S_{r_3, a_3}    S_{r_3, b_3}]=1/B^3$. Note we cannot have $a_1 = a_2 = a_3$ and $b_1 = b_2 = b_3$ since the expectation is $0$ in that case.

Similarly to the above, it thus suffices to bound
\begin{equation*}
\begin{split}
&\frac1{B^2}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n  {\bf I}_*(\{a_q, b_q\}_{q=1}^3)\\
&\cdot  | (U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}\\
& \cdot ((U x)_{a_3} (Ux)_{b_3})^{I} (U_{a_3} U_{b_3}^T)^{J}|\\
&\leq (O(\log n))^{C+D+E+G+I}\frac1{B^2}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n  {\bf I}_*(\{a_q, b_q\}_{q=1}^3) \cdot \\
&\cdot  (||U_{a_1}||_2 ||U_{a_2}||_2)^{A}(||U_{b_1}||_2 ||U_{b_2}||_2)^{B}\cdot (||U_{a_1}||_2 ||U_{a_2}||_2)^{C} (||U_{b_1}||_2 ||U_{b_2}||_2)^{D}\cdot (||U_{a_1}||_2 ||U_{b_1}||_2)^{E} (||U_{a_1}||_2 ||U_{b_1}||_2)^{F}\\
&\cdot (||U_{a_2}||_2 ||U_{b_2}||_2)^{G} (||U_{a_2}||_2 ||U_{b_2}||_2)^{H}\cdot (||U_{a_3}||_2 ||U_{b_3}||_2)^{I} (||U_{a_3}||_2 ||U_{b_3}||_2)^{J}\\
\end{split}
\end{equation*}
where we used Cauchy-Schwarz and the assumption that $x\in {\mathcal{T}}^*$ (and hence $x$ is not correlated with any of the rows of $U$ too much), as above.

Since we are only summing over $\{a_1, a_2, a_3, b_1, b_2, b_3\}$ that contain three distinct elements, the expression above is upper bounded by
\begin{equation*}
\begin{split}
&(O(\log n))^{C+D+E+G+I}\frac1{B^2}\sum_{\substack{a, c, b}}^n ||U_{a}||^2_2 ||U_{b}||^2_2 ||U_{c}||^2_2\\
&\leq (O(\log n))^{C+D+E+G+I}\frac{d^3}{B^2}\\
&\leq (O(\log n))^2\frac{d^2}{B},
\end{split}
\end{equation*}
where we used the fact that $\sum_a ||U_a|_2^2=d$ and that in all cases, $C + D + E + G + I \leq 2$.

\paragraph{Bounding ${\bf E}_S[((x^T(I-M)x)^2+ x^T(I-M)^2x+||I-M||_F^2+(\mathrm{Tr}(I-M))^2)^2]$ and ${\bf E}_S[x^T(I-M)x \cdot\mathrm{Tr}(I-M)\cdot ((x^T(I-M)x)^2+ x^T(I-M)^2x+||I-M||_F^2+(\mathrm{Tr}(I-M))^2)]$}
All of the pairwise products arising in the expansion of the above expressions can be written as
\begin{equation*}
\begin{split}
&\sum_{r_1=1}^B\sum_{r_2=1}^B\sum_{r_3=1}^B\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n\sum_{\substack{a_4, b_4=1,\\ a_4\neq b_4}}^n {\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2} S_{r_2, b_2} S_{r_3, a_3} S_{r_3, b_3} S_{r_4, a_4} S_{r_4, b_4}]\\
&\cdot   (U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}\\
&\cdot   (U_{a_3}U_{a_4}^T)^{A'}(U_{b_3}U_{b_4}^T)^{B'}\cdot ((U x)_{a_3} (Ux)_{a_4})^{C'} ((U x)_{b_3} (Ux)_{b_4})^{D'}\cdot ((U x)_{a_3} (Ux)_{b_3})^{E'} (U_{a_3} U_{b_3}^T)^{F'}\cdot ((U x)_{a_4} (Ux)_{b_4})^{G'} (U_{a_4} U_{b_4}^T)^{H'},\
\end{split}
\end{equation*}
where $A, B, C, D, E, F, G, H, A', B', C', D', E', F', G', H' \in \{0, 1\}$ and add up to $4$.

We now need to consider two cases.

\paragraph{Case 1:} the number of distinct elements in $\{a_1, b_1, a_2, b_2, a_3, b_3, a_4, b_4\}$ is four, each occurring with multiplicity $2$ (let ${\bf I}_*(\{a_q, b_q\}_{q=1}^4)$ denote the indicator of the latter condition)
Then
$$
{\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2} S_{r_3, a_3}    S_{r_3, b_3}  S_{r_4, a_4} S_{r_4,b_4}]
$$
contributes $1/B^4$. In this case the number of distinct elements in $\{r_1, r_2, r_3, r_4\}$ cannot be larger than $2$.

It thus suffices to bound
\begin{equation*}
\begin{split}
&\frac1{B^2}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n  \sum_{\substack{a_4, b_4=1,\\ a_4\neq b_4}}^n  {\bf I}_*(\{a_q, b_q\}_{q=1}^4) \cdot \\
&\cdot   |(U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}\\
&\cdot   (U_{a_3}U_{a_4}^T)^{A'}(U_{b_3}U_{b_4}^T)^{B'}\cdot ((U x)_{a_3} (Ux)_{a_4})^{C'} ((U x)_{b_3} (Ux)_{b_4})^{D'}\cdot ((U x)_{a_3} (Ux)_{b_3})^{E'} (U_{a_3} U_{b_3}^T)^{F'}\cdot ((U x)_{a_4} (Ux)_{b_4})^{G'} (U_{a_4} U_{b_4}^T)^{H'}|\\
&\leq (O(\log n))^2\frac1{B^2}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n  {\bf I}_*(\{a_q, b_q\}_{q=1}^4) \cdot \\
&\cdot   (||U_{a_1}||_2 ||U_{a_2}||_2)^{A}(||U_{b_1}||_2 ||U_{b_2}||_2)^{B}\cdot (||U||_{a_1} ||U_{a_2}||)^{C} (||U_{b_1}||_2 ||U_{b_2}||_2)^{D}\cdot (||U_{a_1}||_2 ||U_{b_1}||_2)^{E} (||U_{a_1}||_2 ||U_{b_1}||_2)^{F}\\
&\cdot (||U_{a_2}|| ||U_{b_2}||)^{G} (||U_{a_2}||_2 ||U_{b_2}||_2)^{H}\\
&\cdot   (||U_{a_3}||_2||U_{a_4}||_2)^{A'}(||U_{b_3}||_2 ||U_{b_4}||_2)^{B'}\cdot (||U_{a_3}||_2 ||U_{a_4}||_2)^{C'} (||U_{b_3}||_2 ||U_{b_4}||_2)^{D'}\cdot (||U_{a_3}||_2 ||U_{b_3}||_2)^{E'} (||U_{a_3}||_2 ||U_{b_3}||_2)^{F'}\\
&\cdot (||U_{a_4}||_2 ||U_{b_4}||_2)^{G'} (||U_{a_4}||_2 ||U_{b_4}||_2)^{H'}\\
\end{split}
\end{equation*}
where we used Cauchy-Schwarz and the assumption that $x\in {\mathcal{T}}^*$ (and hence $x$ is not correlated with any of the rows of $U$ too much), as above.

Since we are only summing over $\{a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4\}$ that contain three distinct elements, each of multiplicity two, the expression above is upper bounded by
\begin{equation*}
\begin{split}
&(O(\log n))^{2}\frac1{B^2}\sum_{\substack{a, b, c, d}}^n ||U_{a}||^2_2 ||U_{b}||^2_2 ||U_{c}||^2_2||U_{d}||^2_2\\
&\leq (O(\log n))^{2}\frac{d^4}{B^2}\\
&\leq (O(\log n))^2\frac{d^2}{B},
\end{split}
\end{equation*}
where we used the fact that $\sum_a ||U_a|_2^2=d$.

\paragraph{Case 2:} the number of distinct elements in $\{a_1, b_1, a_2, b_2, a_3, b_3, a_4, b_4\}$ is two, each occurring with multiplicity $4$ (let ${\bf I}_*(\{a_q, b_q\}_{q=1}^4)$ denote the indicator of the latter condition)
Then
$$
{\bf E}_S[S_{r_1, a_1}  S_{r_1, b_1} S_{r_2, a_2}    S_{r_2, b_2} S_{r_3, a_3}    S_{r_3, b_3} S_{r_4, a_4} S_{r_4, b_4}]
$$
contributes $1/B^2$. In this case the number of distinct elements in $\{r_1, r_2, r_3, r_4\}$ has to be one, since each column of $S$ has a single non-zero entry and necessarily $a_1 = a_2 = a_3 = a_4$ and $b_1 = b_2 = b_3 = b_4$.

It thus suffices to bound
\begin{equation*}
\begin{split}
&\frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n  \sum_{\substack{a_4, b_4=1,\\ a_4\neq b_4}}^n  {\bf I}_*(\{a_q, b_q\}_{q=1}^4) \cdot \\
&\cdot   |(U_{a_1}U_{a_2}^T)^{A}(U_{b_1}U_{b_2}^T)^{B}\cdot ((U x)_{a_1} (Ux)_{a_2})^{C} ((U x)_{b_1} (Ux)_{b_2})^{D}\cdot ((U x)_{a_1} (Ux)_{b_1})^{E} (U_{a_1} U_{b_1}^T)^{F}\cdot ((U x)_{a_2} (Ux)_{b_2})^{G} (U_{a_2} U_{b_2}^T)^{H}\\
&\cdot   (U_{a_3}U_{a_4}^T)^{A'}(U_{b_3}U_{b_4}^T)^{B'}\cdot ((U x)_{a_3} (Ux)_{a_4})^{C'} ((U x)_{b_3} (Ux)_{b_4})^{D'}\cdot ((U x)_{a_3} (Ux)_{b_3})^{E'} (U_{a_3} U_{b_3}^T)^{F'}\cdot ((U x)_{a_4} (Ux)_{b_4})^{G'} (U_{a_4} U_{b_4}^T)^{H'}|\\
&\leq (O(\log n))^2\frac1{B}\sum_{\substack{a_1, b_1=1,\\a_1\neq b_1}}^n \sum_{\substack{a_2, b_2=1,\\ a_2\neq b_2}}^n   \sum_{\substack{a_3, b_3=1,\\ a_3\neq b_3}}^n \sum_{\substack{a_4, b_4=1,\\ a_4\neq b_4}}^n {\bf I}_*(\{a_q, b_q\}_{q=1}^4) \cdot \\
&\cdot   (||U_{a_1}||_2 ||U_{a_2}||_2)^{A}(||U_{b_1}||_2 ||U_{b_2}||_2)^{B}\cdot (||U||_{a_1} ||U_{a_2}||)^{C} (||U_{b_1}||_2 ||U_{b_2}||_2)^{D}\cdot (||U_{a_1}||_2 ||U_{b_1}||_2)^{E} (||U_{a_1}||_2 ||U_{b_1}||_2)^{F}\\
&\cdot (||U_{a_2}|| ||U_{b_2}||)^{G} (||U_{a_2}||_2 ||U_{b_2}||_2)^{H}\\
&\cdot   (||U_{a_3}||_2||U_{a_4}||_2)^{A'}(||U_{b_3}||_2 ||U_{b_4}||_2)^{B'}\cdot (||U_{a_3}||_2 ||U_{a_4}||_2)^{C'} (||U_{b_3}||_2 ||U_{b_4}||_2)^{D'}\cdot (||U_{a_3}||_2 ||U_{b_3}||_2)^{E'} (||U_{a_3}||_2 ||U_{b_3}||_2)^{F'}\\
&\cdot (||U_{a_4}||_2 ||U_{b_4}||_2)^{G'} (||U_{a_4}||_2 ||U_{b_4}||_2)^{H'}\\
\end{split}
\end{equation*}
where we used Cauchy-Schwarz and the assumption that $x\in {\mathcal{T}}^*$ (and hence $x$ is not correlated with any of the rows of $U$ too much), as above.

Since we are only summing over $\{a_1, a_2, a_3, a_4, b_1, b_2, b_3, b_4\}$ that contain two distinct elements, each of multiplicity four, the expression above is upper bounded by
\begin{equation*}
\begin{split}
&(O(\log n))^{2}\frac1{B}\sum_{\substack{a, b}}^n ||U_{a}||^4_2 ||U_{b}||^4_2\\
&=(O(\log n))^{2}\frac1{B}\sum_{\substack{a, b}}^n ||U_{a}||^2_2 ||U_{b}||^2_2\text{~~~~~~(since $||U_a||_2\leq 1$ for all $a$)}\\
&\leq (O(\log n))^2\frac{d^2}{B},
\end{split}
\end{equation*}
where we used the fact that $\sum_a ||U_a|_2^2=d$.

\end{proofof}

\section{Proof of Theorem~\ref{thm:main}} \label{sec:countsketch}

The main result of this section is

{\noindent{\bf Theorem~\ref{thm:main}} \em (Restated)
There exists an absolute constant $C>0$  such that for every $\delta\in (0, 1)$, every integer $1\leq m\leq n^4$ and every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, if $B\geq \frac1{\delta}C(\log n)^4\cdot d^2\cdot m^{1/2}$,  $S\in \mathbb{R}^{B\times n}$ is a random CountSketch matrix, and $G\in \mathbb{R}^{m\times B}$ and $\tilde G\in \mathbb{R}^{m\times n}$ are matrices of i.i.d. unit variance Gaussians, then the total variation distance between the joint distribution $G S U$ and $\tilde GU$ is less than $\delta$.
}

\begin{remark}
Note that we restrict the range of values of $m$ in Theorem~\ref{thm:main} to $[1:n^4]$. This is because if $m>n^4$, the theorem requires $B\gg \frac1{\delta}n^2$, at which  point the CountSketch matrix $S$ becomes an isometry of $\mathbb{R}^n$ with high probability and the theorem follows immediately. At the same time restricting $m$ to be bounded by a small polynomial of $n$ simplifies the proof of Theorem~\ref{thm:main}  notationally.
\end{remark}

Recall that a CountSketch matrix $S\in \mathbb{R}^{B\times n}$ is a matrix all of whose columns have exactly one nonzero in a random location, and the value of the nonzero element is independently chosen to be $-1$ or $+1$. All random choices are made independently. Throughout this section we denote the number of rows in the CountSketch matrix by $B$. Note that the matrix $S$ is a random variable. Let $G$ denote an $m\times B$ matrix of independent Gaussians. For an $n\times d$ matrix $U$ with orthonormal columns let  $q:\mathbb{R}^d\to \mathbb{R}_+$ denote the p.d.f. of the random variable $G_1 S U$, where $G_1$ is the first row of $G$ (all rows have the same distribution and are independent). We note that $G_1SU$ is a mixture of Gaussians. Indeed, for any fixed $S$ the distribution of $G_1SU$ is normal with covariance matrix $(G_1SU)^T(G_1SU)=U^TS^TSU$. We denote the distribution of $G_1SU$ given $S$ by
$$
q_S(x):=\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}.
$$
Throughout this section we use the notation $M:=U^TS^TSU$. Note that since $S$ is a random variable, $M$ is as well. With this notation in place we have for any $x\in \mathbb{R}^d$
\begin{equation}\label{eq:def-q}
q(x)={\bf E}_S\left[q_S(x)\right].
\end{equation}
Let $p:\mathbb{R}^d\to \mathbb{R}_+$ denote the pdf of the isotropic Gaussian distribution, i.e. for all $x\in \mathbb{R}^d$
\begin{equation}
p(x)=\frac1{\sqrt{(2\pi)^d}}e^{-\frac1{2}x^Tx}.
\end{equation}

Before giving a proof of Theorem~\ref{thm:main}, which is somewhat involved, we give a simple proof of a weaker version of the theorem, where the number of buckets $B$ of our CountSketch matrix is required to be $\approx \frac1{\delta} d^2 m$ as opposed to $\approx \frac1{\delta} d^2 \sqrt{m}$:

\begin{theorem}\label{thm:simple}
There exists an absolute constant $C>0$  such that for every $\delta\in (0, 1)$, every integer $m\geq 1$ and every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns if $B\geq \frac1{\delta^2}C d^2\cdot m$,  $S\in \mathbb{R}^{B\times n}$ is a random CountSketch matrix, and $G\in \mathbb{R}^{m\times B}$ and $\tilde G\in \mathbb{R}^{m\times n}$ are matrices of i.i.d. unit variance Gaussians, then the total variation distance between the joint distribution $G S U$ and $\tilde GU$ is less than $\delta$.
\end{theorem}

We will use the following measures of distance between two distribution in the proof of our main theorem (Theorem~\ref{thm:main}) as well as the proof of Theorem~\ref{thm:simple}.
\begin{definition}[Kullback-Leibler divergence]
The Kullback-Leibler (KL) divergence between two random variables $P, Q$ with probability density functions $p(x), q(x)\in \mathbb{R}^d$ is given by $D_{KL}(P||Q)=\int_{\mathbb{R}^d} p(x)\ln \frac{p(x)}{q(x)}dx$
\end{definition}

\begin{definition}[Total variation distance]
The total variation distance between two random variables $P, Q$ with probability density functions $p(x), q(x)\in \mathbb{R}^d$ is given by $D_{TV}(P, Q)=\frac1{2}\int_{\mathbb{R}^d} |p(x)-q(x)|dx$.
\end{definition}
\begin{theorem}[Pinsker's inequality]
For any two random variables $P, Q$ with probability density functions $p(x), q(x)\in \mathbb{R}^d$ one has $D_{TV}(P, Q)\leq \sqrt{\frac1{2}D_{KL}(P||Q)}$.
\end{theorem}

The proof of Theorem~\ref{thm:simple} uses the following simple claim.
\begin{claim}[KL divergence between multivariate Gaussians]\label{cl:kl-basic}
Let $X\sim N(0, I_d)$ and $Y\sim N(0, \Sigma)$. Then $D_{KL}(X || Y)=\frac1{2}\mathrm{Tr}(\Sigma^{-1}-I)+\frac1{2}\ln \det \Sigma$.
\end{claim}
\begin{proof}
One has
\begin{equation*}
\begin{split}
D_{KL}(X || Y)&={\bf E}_{X\sim N(0, I_d)}[-\frac1{2}X^TX+\frac1{2}X^T\Sigma^{-1}X+\frac1{2}\ln \det \Sigma]\\
&={\bf E}_{X\sim N(0, I_d)}[\frac1{2}X^T(\Sigma^{-1}-I)X+\frac1{2}\ln \det \Sigma]\\
&=\frac{1}{2}{\bf E}_{X\sim N(0, I_d)}[\mathrm{Tr}((\Sigma^{-1}-I)XX^T)] + \frac{1}{2} \ln \det \Sigma\\
&=\frac1{2}\mathrm{Tr}(\Sigma^{-1}-I)+\frac1{2}\ln \det \Sigma,\\
\end{split}
\end{equation*}
where we used the fact that for a vector $X$ of independent Gaussians of unit variance one has ${\bf E}_X[X^TAX]=\mathrm{Tr}(A)$ for any symmetric $A$ (by rotational invariance of the Gaussian distribution).
\end{proof}

We can now give

\begin{proofof}{Theorem~\ref{thm:simple}}
One has by Lemma~\ref{lm:frobenius-norm}, {\bf (1)} (see below; this is a standard property of the CountSketch matrix) that for any $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, and $B\geq 1$, if $S$ is a random CountSketch matrix and $M=U^TS^TSU$, then  ${\bf E}_S[||M-I||_F^2]=O(d^2/B)$. By Markov's inequality ${\bf Pr}_S[||I-M||_F>(2/\delta)\cdot O(d^2/B)]<\delta/2$. Let ${\mathcal E}$ denote the event that $||I-M||_F \leq (2/\delta)\cdot O(d^2/B)$. We condition on ${\mathcal E}$ in what follows. Since $B\geq \frac1{\delta^3} Cd^2 m$ for a sufficiently large absolute constant $C>1$, we have, conditioned on ${\mathcal E}$, that
\begin{equation}\label{eq:fnim-bound}
||I-M||_F^2\leq (2/\delta)\cdot O(d^2/B)=(2/\delta)\cdot \delta^3/(Cm)\leq 2\delta^2/(Cm).
\end{equation}
Note that in particular we have $||I-M|| \leq ||I-M||_F < 1/2$ conditioned on ${\mathcal E}$  as long as $C>1$ is larger than an absolute constant.

By Claim~\ref{cl:kl-basic} we have $D_{KL}(X || Y)=\frac1{2}\mathrm{Tr}(I-\Sigma^{-1})+\frac1{2} \ln \det \Sigma$. We now use Taylor expansions of matrix inverse and $\log \det$ provided by Claim~\ref{cl:1} and Claim~\ref{cl:2} (see below) to obtain

\begin{eqnarray}\label{eq:fsggrg}
D_{KL}(X || Y)&=&\frac1{2}\mathrm{Tr}(M^{-1}-I)+\frac1{2}\ln \det M \notag \\
&=&\frac1{2}\mathrm{Tr}\left(\sum_{k\geq 1} (I-M)^k\right)+\frac1{2}\sum_{k\geq 1} \left(-\mathrm{Tr}((I-M)^k)/k\right) \notag \\
&=&\frac1{2}\mathrm{Tr}\left(\sum_{k\geq 2} (I-M)^k\right)+\frac1{2}\sum_{k\geq 2} \left(-\mathrm{Tr}((I-M)^k)/k\right)\notag \\%\text{~~~~~(since $\mathrm{Tr}(I-M)=0$ for all $S$)} \notag \\
&=&O(\mathrm{Tr}((I-M)^2))\text{~~~~~~~~~~~~(since $||I-M||_2\leq ||I-M||_F < 1/2$)} \notag \\
&=&O(||I-M||_F^2) \notag \\
&=&O(2\delta^2/(Cm))\text{~~~~~~~~~~~(by~\eqref{eq:fnim-bound})}\notag \\
&\leq& (\delta/4)^2/m
\end{eqnarray}
as long as $C>1$ is larger than an absolute constant. This shows that for every $S\in {\mathcal E}$ one has $D_{KL}(p||q_S)\leq (\delta/4)^2/m$, and thus $D_{KL}(p||\tilde q|{\mathcal E}])\leq (\delta/4)^2/m$, where we let $\tilde q(x):={\bf E}_S[q_S(x)|{\mathcal E}]$.

We now observe that the vectors $(G_i SU)_{i=1}^m$ and $(\tilde G_i U)_{i=1}^m$ are vectors of independent samples from distributions $q(x)$ and $p(x)$ respectively. We denote the corresponding product distributions by $q^m$ and $p^m$. Since the good event ${\mathcal E}$ constructed above occurs with probability at least $1-\delta/2$, it suffices to consider the distributions $\tilde q(x)$ and $p(x)$, as
\begin{equation*}
D_{TV}(q^m, p^m)\leq {\bf Pr}[\bar {\mathcal E}]+D_{TV}(q^m, p^m|{\mathcal E})={\bf Pr}[\bar {\mathcal E}]+D_{TV}(\tilde q^m, p^m),
\end{equation*}
where $D_{TV}(q^m, p^m| {\mathcal E})=D_{TV}(\tilde q^m, p^m)$ stands for the total variation distance between the distribution of $(\tilde G_i U)_{i=1}^m$ and the distribution of $(G_i SU)_{i=1}^m$ conditioned on $S\in {\mathcal E}$.
We can now use the estimate from~\eqref{eq:fsggrg} to get
\begin{equation*}
\begin{split}
D_{TV}(\tilde q^m, p^m)&\leq \sqrt{\frac1{2}D_{KL}(p^m || \tilde q^m)}\text{~~~~(by Pinsker's inequality)}\\
&=\sqrt{\frac{m}{2}D_{KL}(p|| \tilde q)}\text{~~~~(by additivity of KL divergence over product spaces)}\\
&\leq \sqrt{\frac{m}{2}\cdot (\delta/4)^2 /m}\text{~~~~(by ~\eqref{eq:fsggrg})}\\
&\leq \delta/4.
\end{split}
\end{equation*}

\end{proofof}

The main source of hardness in proving the stronger result provided by Theorem~\ref{thm:main} comes from the fact that unlike the setting of Theorem~\ref{thm:simple}, where most elements in the mixture are close to isotropic Gaussians in KL divergence, in the setting of Theorem~\ref{thm:main} most elements of the mixture are too far from isotropic Gaussians to establish our result directly (this can be seen by verifying that the bounds of Theorem~\ref{thm:simple} on the KL divergence of $q_S$ to $p$ are essentially tight).  Thus, the main technical challenge in proving Theorem~\ref{thm:main} consists of analyzing the effect of averaging over random CountSketch matrices that is involved in the definition of $q(x)$ in~\eqref{eq:def-q}. The core technical result behind the proof of Theorem~\ref{thm:main} is Lemma~\ref{lm:main}, stated below. Ideally, we would like a lemma that states that the ratio of the pdfs $q(x)/p(x)$ is very close to $1$ for `typical' values of $x$ (for appropriate definition of a set of 'typical' $x$). Unfortunately, it is not clear how to achieve this result for the distribution $q(x)$ defined in~\eqref{eq:def-q}. The problem is that some choices of CountSketch matrices $S$ may lead to degenerate Gaussian distributions that are hard to analyze. For example, when $S$ is not a subspace embedding, the matrix $M$ may even be rank-deficient, and the inverse $M^{-1}$ is then ill-defined. To avoid these issues, we work with an alternative definition. Specifically, instead of averaging the distributions $\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}$ over all CountSketch matrices, we define a high probability event ${\mathcal E}$ in the space of matrices $S$ (see Lemma~\ref{lm:main} for the definition) and reason about the modified distribution $\tilde q(x)$ defined as
\begin{equation}\label{eq:def-q-tilde}
\tilde q(x)={\bf E}_S\left[\left.\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\right|{\mathcal E}\right].
\end{equation}
For technical reasons it turns out to be useful to define yet another distribution
\begin{equation}\label{eq:def-q-prime}
q'(x)={\bf E}_S\left[\left.\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]+\xi\cdot p(x),
\end{equation}
where $\xi={\bf E}_S\left[\left.{\bf Pr}_{X\sim q_S}[X\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]\leq  n^{-20}$ and for each $S\in {\mathcal E}$ and $U$ with orthonormal columns the set ${\mathcal{T}}(S, U)$ (see Definition~\ref{def:typical}) is an appropriately defined set of  $x\in \mathbb{R}^d$ that are `typical' for $S$ and $U$.  We first note that $q'$ is indeed the p.d.f. of a distribution. First, it is clear that $q'(x)\geq 0$ for all $x$. Second, we have
\begin{equation*}
\begin{split}
\int_{\mathbb{R}^d} q'(x)dx&=\int_{\mathbb{R}^d} {\bf E}_S\left[\left.\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]+\xi\cdot \int_{\mathbb{R}^d} p(x)dx\\
&=1-\int_{\mathbb{R}^d} {\bf E}_S\left[\left.\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]+\xi\\
&=1-{\bf E}_S\left[\left.\int_{\mathbb{R}^d} \frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\not \in {\mathcal{T}}(S, U)]dx\right|{\mathcal E}\right]+\xi\\
&=1-{\bf E}_S\left[\left.\int_{\mathbb{R}^d\setminus {\mathcal{T}}(S, U)} \frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}dx\right|{\mathcal E}\right]+\xi\\
&=1-{\bf E}_S\left[\left.{\bf Pr}_{X\sim q_S}[X\not \in  {\mathcal{T}}(S, U)] \right|{\mathcal E}\right]+\xi\\
&=1,\text{~~~~~(by definition of $\xi$)}\\
\end{split}
\end{equation*}
as required.

As we show below, the total variation distance between $q'$ and $\tilde q$ is a small $n^{-10}$, so working with $q'$ suffices. The main argument of our proof shows that the distribution $q'(x)$ is close to $p(x)$ for `typical' $x\in \mathbb{R}^d$. Then since $q'$ is close to $\tilde q$ and the event ${\mathcal E}$ occurs with high probability, this suffices for a proof of Theorem~\ref{thm:main}. Formally, the core technical result behind the proof of Theorem~\ref{thm:main} is

\begin{lemma}\label{lm:main}
There exists an absolute constant $C>0$  such that for every $\delta\in (0, 1)$ and every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns if $B\geq \frac1{\delta}C(\log n)^4d^2$ there exists a set ${\mathcal E}$ of CountSketch matrices and a  subset ${\mathcal{T}}^*\subseteq \mathbb{R}^d$ that satisfies ${\bf Pr}_{X\sim p}[X\not \in {\mathcal{T}}^*]\leq n^{-10}$ and ${\bf Pr}_{X\sim \tilde q}[X\not \in {\mathcal{T}}^*]\leq n^{-10}$ such that if  $S\in \mathbb{R}^{B\times n}$ is a random CountSketch matrix, then {\bf (1)} ${\bf Pr}_S[{\mathcal E}]\geq 1-\delta/3$,  and {\bf (2)} for all $x\in {\mathcal{T}}^*$ one has
$$
\left|\frac{q'(x)}{p(x)}-1\right|\leq O((d^2 \log^4 n)/B)+O(n^{-10}).
$$
\end{lemma}

We now prove Theorem~\ref{thm:main} assuming Lemma~\ref{lm:main}
and Claim~\ref{cl:typical-hp}. After this, we then prove
Lemma~\ref{lm:main} and Claim~\ref{cl:typical-hp}. We now give

\begin{proofof}{Theorem~\ref{thm:main}}
The proof relies on the observation that the vectors $(G_i SU)_{i=1}^m$ and $(\tilde G_i U)_{i=1}^m$ are vectors of independent samples from distributions $q(x)$ and $p(x)$ respectively. We denote the corresponding product distributions by $q^m$ and $p^m$. Since the good event ${\mathcal E}$ constructed in Lemma~\ref{lm:main} occurs with probability at least $1-\delta/3$, it suffices to consider the distributions $\tilde q(x)$ and $p(x)$, as
\begin{equation}\label{eq:dtv-step1}
D_{TV}(q^m, p^m)\leq {\bf Pr}[\bar {\mathcal E}]+D_{TV}(\tilde q^m, p^m| {\mathcal E}),
\end{equation}
where $D_{TV}(\tilde q^m, p^m| {\mathcal E})$ stands for the total variation distance between the distribution of $(\tilde G_i U)_{i=1}^m$ and the distribution of $(G_i SU)_{i=1}^m$ conditioned on $S\in {\mathcal E}$. Further, we have by the triangle inequality
\begin{equation}\label{eq:dtv-step2}
D_{TV}(\tilde q^m, p^m| {\mathcal E})\leq D_{TV}((q')^m, p^m| {\mathcal E})+D_{TV}(\tilde q^m, (q')^m| {\mathcal E})\leq D_{TV}((q')^m, p^m| {\mathcal E})+m\cdot n^{-10},
\end{equation}
since $D_{TV}(\tilde q^m, (q')^m| {\mathcal E})\leq m D_{TV}(\tilde q, q'| {\mathcal E})\leq m n^{-10}$, where $ D_{TV}(\tilde q, q'| {\mathcal E})\leq n^{-10}$ by Claim~\ref{cl:typical-hp} below.

We first prove, using Lemma~\ref{lm:main}, that the KL divergence between $p(x)$ and $q'(x)$ restricted to the set ${\mathcal{T}}^*$ (whose existence is guaranteed by Lemma~\ref{lm:main}) is bounded by $O(((d\log n)^2/B)^2)$. Specifically, let
\begin{equation}\label{eq:p-star-def}
p_*(x):=\left\{
\begin{array}{cc}
p(x)/{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]&\text{~~if~~}x\in {\mathcal{T}}^*\\
0&\text{o.w.}
\end{array}
\right.
\end{equation}
and
\begin{equation}\label{eq:q-star-def}
q'_*(x):=\left\{
\begin{array}{cc}
 q'(x)/{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]&\text{~~if~~}x\in {\mathcal{T}}^*\\
0&\text{o.w.}
\end{array}
\right.
\end{equation}
Since ${\mathcal{T}}^*$ occurs with  probability at least $1-1/n^{10}$ under both $\tilde q(x)$ and $p(x)$ by Lemma~\ref{lm:t-star}, it suffices to bound the total variation distance between the product of $m$ independent copies of $q'_*(x)$ and $m$ independent copies of $p_*(x)$. Specifically,
\begin{equation}\label{eq:dtv-step3}
\begin{split}
D_{TV}((q')^m, p^m| {\mathcal E})&\leq D_{TV}((q'_*)^m, p_*^m| ({\mathcal{T}}^*)^m)+m{\bf Pr}[q'(\mathbf{R}^d\setminus {\mathcal{T}}^*)]+m{\bf Pr}[p(\mathbb{R}^d\setminus {\mathcal{T}}^*)]\\
&\leq D_{TV}((q'_*)^m, p_*^m)+2m n^{-10},  \text{~~~~~(by Lemma~\ref{lm:t-star})}\\
\end{split}
\end{equation}
where we used the fact that $q'_*$ and $p_*$ are supported on ${\mathcal{T}}^*$.  Note that both distributions are still product distributions. By Pinkser's inequality and the product structure  we thus get
\begin{equation}\label{eq:pon23gfg}
\begin{split}
D_{TV}((q'_*)^m, p_*^m)&\leq \sqrt{\frac1{2}D_{KL}((q'_*)^m || p_*^m)}\text{~~~~(by Pinsker's inequality)}\\
&=\sqrt{\frac{m}{2}D_{KL}(q'_*|| p_*)}\text{~~~~(by additivity of KL divergence over product spaces)}\\
\end{split}
\end{equation}

In what follows we bound $D_{KL}(q'_*|| p_*)$. By Lemma~\ref{lm:main} we have for every $x\in {\mathcal{T}}^*$ that
\begin{equation}\label{eq:l2}
|q'(x)/p(x)-1|\leq O((d^2 \log^4 n)/B)+O(n^{-10}),
\end{equation}
so
\begin{equation*}
\begin{split}
|q'_*(x)/p_*(x)-1|&=\left|(q'(x)/p(x))\cdot \frac{{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]}{{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]}-1\right|=\frac{{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]}{{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]}\cdot \left|(q'(x)/p(x))-\frac{{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]}{{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]}\right|\\
&\leq\frac{{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]}{{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]}\cdot \left(\left|q'(x)/p(x)-1\right|+\left|1-\frac{{\bf Pr}_{X\sim p}[{\mathcal{T}}^*]}{{\bf Pr}_{X\sim q'}[{\mathcal{T}}^*]}\right|\right)\\
&=(1+O(n^{-10}))\cdot \left(\left|q'(x)/p(x)-1\right|+O(n^{-10})\right)\\
&=O((d^2 \log^4 n)/B)+O(n^{-10}).\text{~~~~~(by ~\eqref{eq:l2})}
\end{split}
\end{equation*}
 Since $B\geq \frac1{\delta}C d^2 \log^4 n$ for a sufficiently large constant $C>0$ by assumption of the theorem, we get that
 $$
 O((d^2\log^4 n)/B)+O(n^{-10})<O(1/C)+O(n^{-10})<1/2.
 $$
 We thus get, using the bound $|1/(1+x)-1|\leq 2|x|$ for $|x|\leq 1/2$,
\begin{equation}\label{eq:2tfdf}
\begin{split}
|p_*(x)/q'_*(x)-1|&=\left|\frac1{q'_*(x)/p_*(x)}-1\right|=\left|\frac1{1+(q_*'(x)/p_*(x)-1)}-1\right|\\
&=O\left(\left|q_*'(x)/p_*(x)-1\right|\right)\\
&=O((d^2 \log^4 n)/B)+O(n^{-10})
\end{split}
\end{equation}
 We now use the fact that $|\ln(1+x)-x|\leq 2x^2$ for all $x\in (-1/10, 1/10)$ to upper bound $D_{KL}(q'_*|| p_*)$. Specifically, we have
\begin{equation}\label{eq:ib2tgg}
\begin{split}
D_{KL}(q'_*|| p_*)={\bf E}_{X\sim q'_*}[\ln (q'_*(X)/p_*(X))]&\leq -{\bf E}_{X\sim q'_*}[\ln (p_*(X)/q'_*(X))]\\
&\leq -{\bf E}_{X\sim q'_*}[(p_*(x)/q'_*(x)-1)-(p_*(x)/q'_*(x)-1)^2]\\
&\leq -{\bf E}_{X\sim q'_*}[p_*(x)/q'_*(x)-1]+{\bf E}_{X\sim q'_*}[(p_*(x)/q'_*(x)-1)^2]\\
& = -(1-1) + {\bf E}_{X\sim q'_*}[(p_*(x)/q'_*(x)-1)^2]\\
&={\bf E}_{X\sim q'_*}[(p_*(x)/q'_*(x)-1)^2]\\
&=O(((d^2 \log^4 n)/B)^2+n^{-10}) \text{~~~~~~(by~\eqref{eq:2tfdf})}\\
\end{split}
\end{equation}
Since $B\geq \frac1{\delta}C(\log n)^4d^2\cdot m^{1/2}$ for a sufficiently large constant $C>0$ by assumption of the theorem, substituting the bound of~\eqref{eq:ib2tgg} into~\eqref{eq:pon23gfg}, we get
\begin{equation*}
\begin{split}
D_{TV}((q'_*)^m, p_*^m)&\leq \sqrt{\frac{m}{2}D_{KL}(q'_*|| p_*)}\leq \sqrt{\frac{m}{2}\cdot O(((d^2 \log^4 n)/B)^2+n^{-10})} \leq \sqrt{\frac{m}{2}\cdot \delta^2/(8m)}\leq \delta/2.\\
\end{split}
\end{equation*}

Putting this together with ~\eqref{eq:dtv-step3},~\eqref{eq:dtv-step2} and~\eqref{eq:dtv-step1} using the assumption that $m\leq n^4$ gives the result.
\end{proofof}

The rest of the section is devoted to proving Lemma~\ref{lm:main}, i.e.  bounding
\begin{equation}\label{eq:org-ratio}
\begin{split}
q'(x)/p(x)&={\bf E}_S\left[\left.\exp\left(\frac1{2}x^Tx-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]+\xi,
\end{split}
\end{equation}
where $\xi={\bf E}_S\left[\left.{\bf Pr}_{X\sim q_S}[X\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}\right]\leq n^{-20}$, for `typical' $x$ sampled from the Gaussian distribution (i.e. $x\in {\mathcal{T}}^*$ -- see formal definition below).

\paragraph{Organization.} The rest of this section is organized as follows. We start by defining the set ${\mathcal E}$ of `nice' CountSketch matrices in section~\ref{sec:e-def}, and proving that a random CountSketch matrix is likely to be `nice'. We will in fact define a parameterized set ${\mathcal E}(\gamma)$ in terms of a parameter $\gamma$. In section~\ref{sec:t-sets} we define, for each matrix $U$ (which can be thought of as fixed throughout our analysis) with orthonormal columns and CountSketch matrix $S$, a set ${\mathcal{T}}(S, U)$ of $x\in \mathbb{R}^d$ that are `typical' for $S$ and $U$. The ratio of pdfs in~\eqref{eq:org-ratio} can be approximated well by a Taylor expansion {\bf for such `typical' $x\in {\mathcal{T}}(S, U)$}. These Taylor expansions are developed in section~\ref{sec:taylor-basic} and form the basis of our proof. Unfortunately, these Taylor expansions are valid only for $x\in {\mathcal{T}}(S, U)$, i.e. for $x$ that are `typical' with respect to a given $S$. To complete the proof, we need to construct a universal `typical' set ${\mathcal{T}}^*(U, \gamma)$ of $x\in \mathbb{R}^d$, again parameterized in terms of a parameter $\gamma$, that will allow for approximation via Taylor expansions for {\bf all $x\in {\mathcal{T}}^*(U, \gamma)$ and $S\in {\mathcal E}(\gamma)$}. We construct such a set ${\mathcal{T}}^*(U, \gamma)$ in section~\ref{sec:t-star}. Finally, the proof of Lemma~\ref{lm:main} is given in section~\ref{sec:main-lemma-proof}.

\subsection{Typical set ${\mathcal E}$ of CountSketch matrices and its properties}\label{sec:e-def}

Our analysis of~\eqref{eq:org-ratio} starts by Taylor expanding $M^{-1}$ and $\det M$ around the identity matrix. We now state the Taylor expansions, and the define a (family of) high probability events ${\mathcal E}(\gamma)$ (equivalently, sets of  `typical' CountSketch matrices) such that the Taylor expansions are valid for matrices $M\in {\mathcal E}(\gamma)$ for all sufficiently small $\gamma$.\footnote{Note that we use the notation $S\in {\mathcal E}(\gamma)$ and $M\in {\mathcal E}(\gamma)$ interchangeably. This is fine since $M=U^TS^TSU$ and the matrix $U$ is fixed.}  The Taylor expansions that we use are given by
\begin{claim}\label{cl:1}
For any matrix $M$ with $||I-M||<1/2$ one has $M^{-1}=(I-(I-M))^{-1}=\sum_{k\geq 0} (I-M)^k$.
\end{claim}
\begin{claim}\label{cl:2}
For any matrix $M$ with $||I-M||<1/2$ one has $\log \det M=\log\det (I-(I-M))=\sum_{k\geq 1} -\mathrm{Tr}((I-M)^k)/k.$
\end{claim}

For a parameter $\gamma\in (0, 1)$ that we will later set to $1/\text{poly}(\log n)$, define  event ${\mathcal E}(\gamma)$ as
\begin{equation}\label{eq:def-e}
{\mathcal E}(\gamma):=\left\{||I-M||^2_F\leq \gamma^2 \text{~~~and~~~}|\mathrm{Tr}(I-M)|\leq \gamma\right\}.
\end{equation}
The events ${\mathcal E}(\gamma)$ occur with high probability even for fairly small $\gamma$ as long as $B$ is sufficiently large:
\begin{claim}\label{cl:prob-e}
For any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, any $B \times n$ CountSketch matrix $S$ we have
${\bf Pr}[{\mathcal E}(\gamma)]\geq 1-3(d/\gamma)^2/B$.
\end{claim}
\begin{proof}
By Lemma~\ref{lm:frobenius-norm} below, we have ${\bf E}_S[||I-M||_F^2]\leq 2d^2/B$. Applying Markov's inequality to $||I-M||_F^2$, we get
$$
{\bf Pr}[||I-M||_F^2\geq \gamma^2]\leq {\bf Pr}[||I-M||_F^2\geq \gamma^2 (B/(2d^2))\cdot {\bf E}[||I-M||_F^2]]\leq 2(d/\gamma)^2/B
$$
as required.

We also have by Lemma~\ref{lm:frobenius-norm} (fifth bound) that ${\bf E}_S[(\mathrm{Tr}(I-M))^2]\leq d^2/B$. Applying Markov's inequality to $(\mathrm{Tr}(I-M))^2$, we get
$$
{\bf Pr}[|\mathrm{Tr}(I-M)|\geq \gamma]={\bf Pr}[(\mathrm{Tr}(I-M))^2\geq \gamma^2]\leq {\bf Pr}[(\mathrm{Tr}(I-M))^2\geq \gamma^2 (B/(d^2))\cdot {\bf E}[(\mathrm{Tr}(I-M))^2]]\leq (d/\gamma)^2/B.
$$
A union bound over the two events gives the result.
\end{proof}

\subsection{Typical sets ${\mathcal{T}}(S, U)$ and their properties}\label{sec:t-sets}

In order to construct a single typical set ${\mathcal{T}}^*$, we will need the following simple definitions of sets ${\mathcal{T}}(S, U)$  of $x\in \mathbb{R}^d$ that are `typical' for a given CountSketch matrix (as opposed to the set ${\mathcal{T}}^*$ whose existence is guaranteed by Lemma~\ref{lm:main}, which contains $x$ that are `typical' for {\bf all matrices $S\in {\mathcal E}$ simultaneously}).
We will use
\begin{definition}[Typical $x$]\label{def:typical}
For any orthonormal matrix $U\in \mathbb{R}^{n\times d}$ and CountSketch matrix $S$ we define
\begin{equation*}
\begin{split}
{\mathcal{T}}(S, U)&:=\left\{x\in \mathbb{R}^d: |x^T(I-M)x|\leq \frac1{100}\text{~~and~~}|x^T(I-M)^2x|\leq \frac1{100}\right\},
\end{split}
\end{equation*}
\end{definition}

The following claim will be useful in what follows.  Its (simple) proof is given in Section~\ref{sec:app}:
\begin{claim}\label{cl:frobenius-norm-bound}
For any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns and any CountSketch matrix $S\in \mathbb{R}^{B\times n}$ one has $||I-M||_F^2\leq 4n^3$.
\end{claim}

The following claim is crucial to our analysis. A detailed proof is given in Section~\ref{sec:app}.
\begin{claim}\label{cl:typical-hp-basic}
For any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, every $\gamma\leq 1/\log^2 n$, every CountSketch matrix $S\in {\mathcal E}(\gamma)$ one has
{\bf (1)} ${\bf Pr}_{X\sim N(0, I_d)}[X\not \in {\mathcal{T}}(S, U)]<n^{-40}$ and {\bf (2)} for any CountSketch matrix $S'\in {\mathcal E}(\gamma)$, $M'=U^TS'^TS'U$ one has ${\bf Pr}_{X\sim N(0, M')}[X\not \in {\mathcal{T}}(S, U)]<n^{-40}$ for sufficiently large $n$.
\end{claim}

Using the claim above we get
\begin{claim}\label{cl:typical-hp}
The total variation distance between $\tilde q$ (defined in~\eqref{eq:def-q-tilde}) and $q'$ (defined in~\eqref{eq:def-q-prime}) is at most $n^{-10}$. Further, $\xi \leq n^{-40}$.
\end{claim}
\begin{proof}
We have
\begin{equation*}
\begin{split}
D_{TV}(\tilde q, q')&\leq 2\xi\leq 2\int_{\mathbb{R}^d} {\bf E}_S\left[\left.\frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]dx\\
&=2{\bf E}_S\left[\left.\int_{\mathbb{R}^d} \frac1{\sqrt{(2\pi)^d \det M}}e^{-\frac1{2}x^TM^{-1}x}\cdot \mathbf{I}[x\not \in {\mathcal{T}}(S, U)]dx\right|{\mathcal E}(\gamma)\right]\\
&=2{\bf E}_S\left[\left.{\bf Pr}_{X\sim N(0, M)}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]\\
&\leq 2n^{-40}\leq n^{-10}\text{~~~~~~~~(by Claim~\ref{cl:typical-hp-basic})}
\end{split}
\end{equation*}
as required.
\end{proof}

\subsection{Basic Taylor expansions}\label{sec:taylor-basic}
In this section we define the basic Taylor expansions of $\tilde q(x)/p(x)$ that form the foundation of our analysis. Our analysis of~\eqref{eq:org-ratio} proceeds by first Taylor expanding $M^{-1}$ and $\det M$ around the identity matrix using Claims~\ref{cl:1} and~\ref{cl:2}, which is valid since for any $S\in {\mathcal E}(\gamma)$ for $\gamma<1/2$ one has $||I-M||_2\leq ||I-M||_F\leq 1/2$. This gives

\begin{equation}\label{eq:org-ratio-taylor}
\begin{split}
\tilde q(x)/p(x)&={\bf E}_S\left[\left.\exp\left(\frac1{2}x^Tx-\frac1{2}\left(\sum_{k\geq 0} x^T(I-M)^kx\right)+\frac1{2}\sum_{k\geq 1} \mathrm{Tr}((I-M)^k)/k\right)\right|{\mathcal E}\right]\\
&={\bf E}_S\left[\left.\exp\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-\frac1{2}\sum_{k\geq 2} \left(x^T(I-M)^kx-\mathrm{Tr}((I-M)^k)/k\right)\right)\right|{\mathcal E}\right]\\
&={\bf E}_S\left[\left.\exp\left(-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-R(x)\right)\right|{\mathcal E}\right],\\
\end{split}
\end{equation}
where $R(x):=\frac1{2}\sum_{k\geq 2} \left(x^T(I-M)^kx-\mathrm{Tr}((I-M)^k)/k\right)$.

The rationale behind the definition of ${\mathcal E}(\gamma)$ is that for all $S\in {\mathcal E}(\gamma)$ the residual $R(x)$ above is (essentially) dominated by the quadratic terms, i.e. $||I-M||_F^2$ and $x^T(I-M)^2x$ (for `typical' values of $x$ -- see Lemma~\ref{lm:lmcimf2} below), i.e. we can truncate the Taylor expansion to the first and second terms and control the error. This is made formal by the following three lemmas.

\begin{lemma}\label{lm:higher-moments-tr-bound}
For every $\gamma\in (0, 1)$, conditioned on $\mathcal{E}(\gamma)$ we have
 $\mathrm{Tr}((I-M)^k)\leq \gamma^{k-2}\cdot ||I-M||_F^2$ for all $k\geq 2$.
\end{lemma}
\begin{proof}
$|\mathrm{Tr}((I-M)^k)|\leq ||I-M||_2^{k-2}\cdot \mathrm{Tr}((I-M)^2)\leq ||I-M||_F^{k-2}\cdot ||I-M||_F^2\leq \gamma^k$ as required, since $||A||_2\leq ||A||_F$ and $\mathrm{Tr} (A^TA)=||A||_F^2$ for all $A\in \mathbb{R}^{d\times d}$.
\end{proof}

\begin{lemma}\label{lm:higher-moments-x}
For any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, any $\gamma\in (0, 1/2)$, for any $x\in \mathbb{R}^d$ one has, for any CountSketch matrix $S\in {\mathcal E}(\gamma)$,
$x^T(I-M)^kx\leq \gamma^{k-2} x^T(I-M)^2x$ for any $k\geq 2$.
\end{lemma}
\begin{proof}
We have, for any $x\in \mathbb{R}^d$ and any $S\in {\mathcal E}(\gamma)$
$|x^T(I-M)^kx|\leq ||I-M||_2^{k-2}\cdot x^T(I-M)^2x\leq \gamma^{k-2}\cdot x^T(I-M)^2x$, as $||I-M||_2\leq ||I-M||_F$.

\end{proof}

\begin{lemma}\label{lm:lmcimf2}
For any $\gamma\in (0, 1/2)$, any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, any CountSketch matrix $S\in {\mathcal E}(\gamma)$ and any $x\in {\mathcal{T}}(S, U)$ one has
$$
|R(x)|\leq \sum_{k\geq 2} |x^T(I-M)^kx|+|\mathrm{Tr}((I-M)^k)|/k\leq C||I-M||_F^2+ Cx^T(I-M)^2x,
$$
where $C>0$ is an absolute constant.
\end{lemma}
\begin{proof}
We have by combining Lemma~\ref{lm:higher-moments-tr-bound} and Lemma~\ref{lm:higher-moments-x}
\begin{equation*}
\begin{split}
\sum_{k\geq 2} |x^T(I-M)^kx|+|\mathrm{Tr}((I-M)^k)|/k&\leq \sum_{k\geq 2} [\gamma^{k-2} x^T(I-M)^2x+\gamma^{k-2}\cdot ||I-M||_F^2/k]\\
&\leq  C(x^T(I-M)^2x+||I-M||_F^2)
\end{split}
\end{equation*}
for an absolute constant $C'>0$, as $\gamma<1/2$ by assumption of the lemma.
\end{proof}

\subsection{Constructing the universal set ${\mathcal{T}}^*(U, \gamma)$ of typical $x$}\label{sec:t-star}

The main result of this section is the following lemma:

\begin{lemma}\label{lm:t-star}
For every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, for every $\gamma\in (0, 1/\log^2 n)$ and any $\delta>0$ if
\begin{equation*}
\begin{split}
{\mathcal{T}}^*(U, \gamma):=\left\{x\in \mathbb{R}^d\text{~s.t.~}\right.&||x||_\infty\leq C\sqrt{\log  n} \text{~and~}\\
&|(U x)_a|\leq O(\sqrt{\log n}) ||U_a||_2\text{~for all ~}a\in [n]\text{~~and}\\
&\left.{\bf E}_S\left[\left.\mathbf{I}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]<1/n^{25}.\right\},
\end{split}
\end{equation*}
then {\bf (a)} ${\bf Pr}_{X\sim N(0, I_d)}[X\in {\mathcal{T}}^*(U, \gamma)]\geq 1-n^{-10}$ and {\bf (b)} ${\bf Pr}_{X\sim \tilde q}[X\in {\mathcal{T}}^*(U, \gamma)]\geq 1-n^{-10}$.
\end{lemma}

Note that the lemma guarantees the existence of a universal set ${\mathcal{T}}^*\subseteq \mathbb{R}^d$ that captures most of the probability mass of both the normal distribution $N(0, I_d)$ and the mixture $\tilde q$.

\begin{proofof}{Lemma~\ref{lm:t-star}}

Let
$$
{\mathcal{T}}^*_1:=\{x\in \mathbb{R}^d: {\bf E}_S\left[\left.\mathbf{I}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]<1/n^{25}\}.
$$
$$
{\mathcal{T}}^*_2:=\{x\in \mathbb{R}^d: ||x||_\infty\leq C\sqrt{\log n}\}.
$$
$$
{\mathcal{T}}^*_3:=\{x\in \mathbb{R}^d: |(Ux)_a|\leq C\sqrt{\log n} ||U_a||_2 \textrm{ for all }a \in [n]\}.
$$

We  prove that ${\mathcal{T}}^*_i, i=1,2, 3$ occur with high probability under both distributions. As we show below, the result then follows by a union bound.

\paragraph{Showing that ${\mathcal{T}}^*_1$ occurs with high probability.} We first show that ${\mathcal{T}}_1^*$ occurs with high probability under the isotropic Gaussian distribution $X\sim N(0, I_d)$, and then show that it also occurs with high probability under the mixture of Gaussians distribution $\tilde q$. In both cases the proof proceeds by applying Claim~\ref{cl:typical-hp-basic} followed by Markov's inequality.

\paragraph{Step 1: bounding ${\bf Pr}_{X\sim N(0, I_d)} [{\mathcal{T}}^*_1]$.} We have by Claim~\ref{cl:typical-hp-basic}, {\bf (1)} that ${\bf Pr}_{X\sim N(0, I_d)}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]]<n^{-40}$, and hence
\begin{equation*}
\begin{split}
&{\bf E}_S\left[\left.{\bf E}_{X\sim N(0, I_d)}\left[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]\right]\right|{\mathcal E}(\gamma)\right]<1/n^{40},
\end{split}
\end{equation*}
implying that ${\bf E}_{X\sim N(0, I_d)}\left[{\bf E}_S\left[\left.\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]\right]\right|{\mathcal E}(\gamma)\right]<1/n^{40}$. We thus get by Markov's inequality
that ${\bf Pr}_{X\sim N(0, I_d)}[{\mathcal{T}}^*_1]\geq 1-n^{-15}$.

\paragraph{Step 2: bounding ${\bf Pr}_{X\sim \tilde q} [{\mathcal{T}}^*_1]$.} We have by Claim~\ref{cl:typical-hp-basic}, {\bf (2)} that for any $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, any pair of matrices $S, S'\in {\mathcal E}(\gamma)$, if $M'=U^TS^TSU$, then ${\bf Pr}_{X\sim N(0, M')}[X\not \in {\mathcal{T}}(S, U)]<n^{-40}$. We thus have
\begin{equation*}
\begin{split}
{\bf E}_{X\sim \tilde q}[{\bf E}_{S}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]|{\mathcal E}(\gamma)]]&={\bf E}_{S'}\left[\left.{\bf E}_{X\sim q_{S'}}[{\bf E}_{S}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]]|{\mathcal E}(\gamma)]\right|{\mathcal E}(\gamma)\right]\\
&={\bf E}_{S}\left[\left.{\bf E}_{S'}[{\bf E}_{X\sim q_{S'}}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]]|{\mathcal E}(\gamma)]\right|{\mathcal E}(\gamma)\right]\\
&={\bf E}_{S}\left[\left.{\bf Pr}_{X\sim \tilde q}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]]\right|{\mathcal E}(\gamma)\right]\\
&\leq n^{-40}.
\end{split}
\end{equation*}

By Markov's inequality applied to the expression in the first line we thus have
$$
{\bf Pr}_{X\sim \tilde q}[{\bf E}_{S}[\mathbf{I}[X\not \in {\mathcal{T}}(S, U)]|{\mathcal E}(\gamma)]>n^{-25}]<n^{-15}.
$$

\paragraph{Showing that ${\mathcal{T}}_2^*$ occurs with high probability.} The fact that
$$
{\bf Pr}_{X\sim N(0, I_d)} \left[||X||_\infty\leq C\sqrt{\log n}\right]\geq 1-n^{-40}
$$
follows by standard properties of Gaussian random variables.
Thus, it remains to show that  ${\mathcal{T}}_2^*$ occurs with high probability under $X\sim \tilde q$. For any $U\in \mathbb{R}^{n\times d}$ and $S\in {\mathcal E}(\gamma)$ we now prove that for $M=U^TS^TSU$
\begin{equation}\label{eq:irgrgwgwgcc}
\begin{split}
{\bf Pr}_{X\sim N(0, M)} \left[||X||_\infty\leq C\sqrt{\log n}\right]\geq 1-n^{-40}
\end{split}
\end{equation}
It is convenient to let $X=M^{1/2}Y$, where $Y\sim N(0, I_d)$ is a vector of independent Gaussians of unit variance. Then we need to bound
\begin{equation*}
\begin{split}
{\bf Pr}_{X\sim N(0, M)} \left[||X||_\infty\geq C\sqrt{\log n}\right]={\bf Pr}_{Y\sim N(0, I_d)} \left[||M^{1/2}Y||_\infty\geq C\sqrt{\log n}\right]\\
\end{split}
\end{equation*}
By $2$-stability of the Gaussian distribution we have that for each $i=1,\ldots, d$ the random variable $(M^{1/2}Y)_i$ is Gaussian with variance at most $||M^{1/2}||_F^2$, which we bound by
\begin{equation*}
\begin{split}
||M^{1/2}||_F&=||(I+(M-I))^{1/2}||_F=\left|\left|\sum_{t=0}^\infty {1/2 \choose t} (I-M)^t\right|\right|_F\\
&\leq \sum_{t=0}^\infty  \left|{1/2 \choose t}\right|\cdot \left|\left| (I-M)^t\right|\right|_F\\
&\leq \sum_{t=0}^\infty  \left|{1/2 \choose t}\right|\cdot ||I-M||_F^t\\
&\leq \sum_{t=0}^\infty  ||I-M||_F^t\\
&\leq \sum_{t=0}^\infty  (1/2)^t\\
&\leq 2\\
\end{split}
\end{equation*}
Thus, for each $i\in [n]$ the random variable $(M^{1/2}Y)_i$ is Gaussian with variance at most $4$, and~\eqref{eq:irgrgwgwgcc} follows by standard properties of Gaussian random variables as long as $C>0$ is a sufficiently large constant.

\paragraph{Showing that ${\mathcal{T}}_3^*$ occurs with high probability.} The fact that
$$
{\bf Pr}_{X\sim N(0, I_d)} \left[|(UX)_a|\leq C\sqrt{\log n}\cdot ||U_a||_2\text{~~for all~}a\in [n]\right]\geq 1-n^{-40}
$$
follows by standard properties of Gaussian random variables and a union bound over all $a\in [n]$.

Thus, it remains to show that  ${\mathcal{T}}_3^*$ occurs with high probability under $X\sim \tilde q$. For any $U\in \mathbb{R}^{n\times d}$ and $S\in {\mathcal E}(\gamma)$ we now prove that for $M=U^TS^TSU$
\begin{equation*}
\begin{split}
{\bf Pr}_{X\sim N(0, M)} \left[|(UX)_a|\leq C\sqrt{\log n}||U_a||_2\text{~~for all~}a\in [n]\right]\geq 1-n^{-40}
\end{split}
\end{equation*}
It is convenient to let $X=M^{1/2}Y$, where $Y\sim N(0, I_d)$ is a vector of independent Gaussians of unit variance. Then we need to bound, for each $a\in [n]$
\begin{equation*}
\begin{split}
{\bf Pr}_{X\sim N(0, M)} \left[|(UX)_a|\geq C\sqrt{\log n}||U_a||_2\right]={\bf Pr}_{Y\sim N(0, I_d)} \left[|(UM^{1/2}Y)_a|\geq C\sqrt{\log n}||U_a||_2\right]\\
\end{split}
\end{equation*}
By $2$-stability of the Gaussian distribution we have that for each $a=1,\ldots, n$ the random variable $U_a M^{1/2}Y$ is Gaussian with variance at most $||U_a M^{1/2}||_2^2 \leq 4||U_a||_F^2$ (since $\gamma<1/\log^2 n$ by assumption of the lemma), and hence the result follows by standard properties of Gaussian random variables and a union bound.

Finally, we let ${\mathcal{T}}^*:={\mathcal{T}}_1^*\cap {\mathcal{T}}_2^*\cap {\mathcal{T}}_3^*$. By a union bound applied to the bounds above we have that ${\mathcal{T}}^*$ occurs with probability at least $1-n^{-10}$ under both distributions, as required.
\end{proofof}

\subsection{Proof of Lemma~\ref{lm:main}}\label{sec:main-lemma-proof}

We first prove
\begin{lemma}\label{lm:ratio-bound-cond}
There exists an absolute constant $C>0$ such that for every $\gamma\in (0, 1/\log n)$, any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns and any CountSketch matrix $S\in {\mathcal E}(\gamma)$ and $x\in {\mathcal{T}}(S, U)$ one has, letting
$$
L(x):=-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-\frac1{8}x^T(I-M)x\cdot \mathrm{Tr}(I-M)
$$
and
$$
Q(x):=((x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2),
$$
that
\begin{equation*}
\begin{split}
&\left|1+L(x)-\exp\left(\frac1{2}x^Tx-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M\right)\right|\leq C\cdot Q(x).
\end{split}
\end{equation*}
\end{lemma}
The proof is given in section~\ref{sec:app}.

We will need the following two lemmas, whose proofs are provided in section~\ref{sec:moment-bounds}
\begin{lemma}\label{lm:frobenius-norm}
For any $U\in \mathbb{R}^{n\times d}$ with orthonormal columns, and $B\geq 1$, if $S$ is a random CountSketch matrix and $M=U^TS^TSU$, then
\begin{description}
\item[(1)] ${\bf E}_S[||M-I||_F^2] \leq 2d^2/B$
\item[(2)] for all $x\in {\mathcal{T}}^*$ one has ${\bf E}_S[x^T(I-M)^2x]=O(d^2(\log^2 n)/B)$
\item[(3)] for all $x\in {\mathcal{T}}^*$ one has ${\bf E}_S[(x^T(I-M)x)^2]=O(d^2(\log^2 n)/B)$
\item[(4)] for all $x\in {\mathcal{T}}^*$ one has ${\bf E}_S[(x^T(I-M)x)\cdot \mathrm{Tr}(I-M)]=O(d^2(\log n)/B)$
\item[(5)] one has ${\bf E}_S[(\mathrm{Tr}(I-M))^2]=O(d^2/B)$
\end{description}

\end{lemma}
and

\begin{lemma}[Variance bound]\label{lm:variance-bound}
For any matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns if $\gamma\in (0, 1/2)$ and ${\mathcal{T}}^*(U, \gamma)\subseteq \mathbb{R}^d$ is as defined in Lemma~\ref{lm:t-star}, then for any $x\in {\mathcal{T}}^*(U, \gamma)$ one has, for
$$
L(x):=-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-\frac1{8}x^T(I-M)x\cdot \mathrm{Tr}(I-M)
$$
and
$$
Q(x):=((x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2),
$$
that for any constant $C$
\begin{equation*}
\begin{split}
&{\bf E}_S\left[\left(L(x)+C\cdot Q(x)\right)^2\right]=O(d^2(\log^2 n)/B),
\end{split}
\end{equation*}
where $S$ is a uniformly random CountSketch matrix and $M=U^TS^TSU$.
\end{lemma}

We will use the following lemma, whose proof is given in section~\ref{sec:app}:
\begin{lemma}\label{lm:conditioning}
  For any random variable $Z$ and any event ${\mathcal E}$ with $\Pr[{\mathcal E}] \geq 1/2$,
  if $\epsilon:={\bf E}[(Z-1)^2]$, then
$$
\left|{\bf E}[Z]-{\bf E}[Z|{\mathcal E}]\right|\leq 2(1+{\bf E}[Z]){\bf Pr}[\bar {\mathcal E}]+2\sqrt{\epsilon {\bf Pr}[\bar {\mathcal E}]}.
$$
\end{lemma}

Equipped with the bounds above, we can now prove Lemma~\ref{lm:main}:

{{\bf \noindent Lemma~\ref{lm:main}} (Restated) \em There exists an absolute constant $C>0$  such that for every $\delta\in (0, 1)$ and every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns if $B\geq \frac1{\delta}C(\log n)^4d^2$ there exists a set ${\mathcal E}$ of CountSketch matrices and a  subset ${\mathcal{T}}^*\subseteq \mathbb{R}^d$ that satisfies ${\bf Pr}_{X\sim p}[X\not \in {\mathcal{T}}^*]\leq n^{-10}$ and ${\bf Pr}_{X\sim \tilde q}[X\not \in {\mathcal{T}}^*]\leq n^{-10}$ such that if  $S\in \mathbb{R}^{B\times n}$ is a random CountSketch matrix, then {\bf (1)} ${\bf Pr}_S[{\mathcal E}]\geq 1-\delta/3$,  and {\bf (2)} for all $x\in {\mathcal{T}}^*$ one has
$$
\left|\frac{q'(x)}{p(x)}-1\right|\leq O((d^2 \log^4 n)/B)+O(n^{-10}).
$$

}
\begin{proof}
Let ${\mathcal{T}}^*(U, \gamma)\subseteq \mathbb{R}^d$ be as defined in Lemma~\ref{lm:t-star}, and let $\gamma:=1/\log^2 n$. Let ${\mathcal E}:={\mathcal E}(\gamma)$, and note that ${\bf Pr}[{\mathcal E}]\geq 1-\delta/3$ by Claim~\ref{cl:prob-e} as long as $C$ is a large enough constant, as required.

We now bound
$$
\frac{q'(x)}{p(x)}={\bf E}_S\left[\left.\frac{q_S(x)}{p(x)}\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]+\xi,
$$
for $x\in {\mathcal{T}}^*(U, \gamma)$, where $\xi={\bf E}_S[{\bf Pr}_{X\sim q_S}[X\in {\mathcal{T}}(S, U)]]\leq n^{-40}$ by definition and Claim~\ref{cl:typical-hp}, {\bf (2)}. For each $S\in {\mathcal E}(\gamma)$ and $x\in {\mathcal{T}}(S, U)$ we have by Lemma~\ref{lm:ratio-bound-cond}
\begin{equation*}
\begin{split}
&\left|\frac{q_S(x)}{p(x)}-(1+L(x))\right|=\left|\exp\left(\frac1{2}x^Tx-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M\right)-(1+L(x))\right|\leq C\cdot Q(x),
\end{split}
\end{equation*}
where
$$
L(x):=-\frac1{2}x^T(I-M)x+\frac1{2}\mathrm{Tr}(I-M)-\frac1{8}x^T(I-M)x\cdot \mathrm{Tr}(I-M)
$$
denotes the `linear' term and
$$
Q(x):=(x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2
$$
denotes the `quadratic' term.

Taking expectations, we get
\begin{equation*}
\begin{split}
&{\bf E}_S\left[\left.\left(L(x)-C\cdot Q(x)\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]\\
&\leq {\bf E}_S\left[\left.\left(\exp\left(\frac1{2}x^Tx-\frac1{2}x^TM^{-1}x-\frac1{2}\log \det M\right)-1\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]\\
&\leq {\bf E}_S\left[\left.\left(L(x)+C\cdot Q(x)\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right].
\end{split}
\end{equation*}

Thus, it suffices to show that
$$
|{\bf E}_S\left[\left.\left(L(x)\pm C\cdot Q(x)\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]|=O((Cd\log n)^2/B) + O(n^{-10}),
$$
 which we do now. We only provide the analysis for the case when the sign in front of the constant $C$ is a plus, as the other part is analogous.

We first show that removing the multiplier $\mathbf{I}[x\in {\mathcal{T}}(S, U)]$ from the equation above only changes the expectation slightly.
Specifically, note that
\begin{equation}\label{eq:diff-2}
\begin{split}
&\left|{\bf E}_S\left[\left.\left(L(x)+C\cdot Q(x)\right)\cdot \mathbf{I}[x\in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]-{\bf E}_S\left[\left.L(x)+C\cdot Q(x)\right|{\mathcal E}(\gamma)\right]\right|\\
&\leq {\bf E}_S\left[\left.\left|L(x)+C\cdot Q(x)\right|\cdot \mathbf{I}[x\not\in  {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right].
\end{split}
\end{equation}
By Claim ~\ref{cl:frobenius-norm-bound} we have $||I-M||_F^2\leq 4n^3$ for all $S$ and  $U$, so every element of the matrix $I-M$ is upper bounded by $2n^2$. Similarly, we have $||(I-M)^2||_F\leq ||I-M||_F^2$, and so every element of $(I-M)^2$ is upper bounded by $4n^3$. Thus, for any $x\in {\mathcal{T}}^*(U, \gamma)$ one has
\begin{equation*}
\begin{split}
&|L(x)+CQ(x)|\\
&\leq (|x^T(I-M)x|+|\mathrm{Tr}(I-M)|+|x^T(I-M)x\cdot \mathrm{Tr}(I-M)|\\
&+C((x^T(I-M)x)^2+(\mathrm{Tr}(I-M))^2+x^T(I-M)^2x+||I-M||_F^2))\\
&=O(\log n) (2n^2 d^2+d\cdot (2n^2)+(2n^2)^2 d^3+(2n^2d^2)^2+(d\cdot 2n^2)^2+4n^4 d^2+4n^3)\leq n^{10}\\
\end{split}
\end{equation*}
as long as $n$ is sufficiently large, where we used the fact that $||x||_\infty\leq O(\sqrt{\log n})$ for all $x\in {\mathcal{T}}^*(U, \gamma)$.

Furthermore,  by Lemma~\ref{lm:t-star} we have for $x\in {\mathcal{T}}^*(U, \gamma)$ that
$$
{\bf E}_S\left[\left.\mathbf{I}[x\not \in {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]<1/n^{25}.
$$

Substituting these two bounds into~\eqref{eq:diff-2},  we get
\begin{equation}\label{eq:diff-3}
\begin{split}
&{\bf E}_S\left[\left.\left|L(x)+C\cdot Q(x)\right|\cdot \mathbf{I}[x\not\in  {\mathcal{T}}(S, U)]\right|{\mathcal E}(\gamma)\right]\leq n^{-10}
\end{split}
\end{equation}

so it remains to bound
\begin{equation*}
\begin{split}
{\bf E}_S\left[\left.L(x)+C\cdot Q(x)\right|{\mathcal E}(\gamma)\right].
\end{split}
\end{equation*}

We bound the expectation above by relating it to the corresponding unconditional expectation. Let $Z:=1+(L(x)+C\cdot Q(x))$, and note that
\begin{equation}\label{eq:z-exp}
{\bf E}_S[Z]=1-{\bf E}_S[\frac1{8}x^T(I-M)x \cdot \mathrm{Tr}(I-M)]+C\cdot{\bf E}_S[Q(x)]=1+O((C\log n)^2d^2/B)
\end{equation}
by Lemma~\ref{lm:frobenius-norm}. Let $\epsilon:={\bf E}_S[(Z-1)^2]$. We note that by Lemma~\ref{lm:variance-bound} that $\epsilon\leq O(d^2 (\log^2 n)/B)$, and hence since ${\mathcal E}(\gamma) \geq 1/2$ by
Claim \ref{cl:prob-e}, by Lemma~\ref{lm:conditioning} we have
$$
\left|{\bf E}[Z]-{\bf E}[Z|{\mathcal E}(\gamma)]\right|\leq 2(1+{\bf E}[Z]){\bf Pr}[\bar {\mathcal E}(\gamma)]+2\sqrt{\epsilon {\bf Pr}[\bar {\mathcal E}(\gamma)]}.
$$
Since ${\bf Pr}[\bar {\mathcal E}(\gamma)]\leq  3(d/\gamma)^2/B$ by Claim~\ref{cl:prob-e} and using the assumption that $B\geq (\log^2 n)d^2$, we get
\begin{equation}\label{eq:z-exp-delta}
\left|{\bf E}[Z]-{\bf E}[Z|{\mathcal E}(\gamma)]\right|\leq O((d/\gamma)^2/B)+2\sqrt{O(d^2\log^2 n/B)\cdot (d/\gamma)^2/B)}=O((\frac1{\gamma^2}+\frac1{\gamma}\log n)d^2/B)=O((d/\gamma)^2/B),
\end{equation}
where we used the assumption that $\gamma\leq 1/\log^2 n$. Combining ~\eqref{eq:z-exp-delta},~\eqref{eq:z-exp} with~\eqref{eq:diff-2} and~\eqref{eq:diff-3}, we get
\begin{equation*}
\left|\frac{q'(x)}{p(x)}-1\right|= \left|{\bf E}_S\left[\left.\frac{q(x)}{p(x)}\cdot \mathbf{I}[x\in {\mathcal{T}}(U, S)]\right|{\mathcal E}(\gamma)\right]+\xi-1\right|\leq O((d^2 \log^4 n)/B)+O(1/n^{10}).
\end{equation*}

\end{proof}

\section{Introduction}
\label{sec:intro}
One approach to handle high dimensional data, often in the form of a matrix,
is to first project the data to a much lower dimensional subspace.
This is an example of sketching and the last decade has seen a systematic study of this approach.
A linear sketch of a matrix replaces the original matrix by a smaller matrix
which is often obtained by a random projection of the original
matrix~ (see, e.g., \cite{woodruff2014sketching} for a survey).
Random projections have been successfully applied to speed up least squares regression and have been implemented with
remarkable success~\cite{avron2010blendenpik}.
This is impressive considering the fact that these solvers have been highly optimized
over the last few decades, exploiting both algorithmic improvements and machine dependent optimizations.

Many of these works rely on {\it fast projection matrices}, such as the Subsampled Randomized Hadamard Transform
or the CountSketch, the latter being particularly well-suited for sparse data (see, e.g., \cite{woodruff2014sketching}
and references therein). However, there are certain applications for which multiplying by a Gaussian matrix is
the only way that is known to reduce the dimensionality of the data. This arises mainly because the application
requires rotational symmetry, which is often not preserved by other fast transforms, or because additional properties,
such as spreading out a sparse vector to a vector with non-spiky elements, do not hold for transforms like
CountSketch (some of these hold for the Fast Hadamard Transform, but the latter are not known to be able to exploit sparsity). We give
two such applications below, one to nonnegative matrix factorization (NMF), and one to support vector machines (SVM).

\subsection{Our Results}
{\bf A New Randomized Transform.}
In this work we propose a new randomized transform $T$, which we call the CountGauss. It is simply a product of a
CountSketch matrix and a Gaussian matrix.
That is, given an $n \times d$ matrix $X$ which we would like to
multiply by an $m \times n$ matrix $\tilde G$ of Gaussians, we instead let $T = G \cdot S$, where $S$ is a
$B \times d$ CountSketch matrix
where $B = \tilde{O}(d^{2}m^{.5})$, and $\tilde G$ is an $m \times B$ matrix of i.i.d.
Gaussians.
Recall that a CountSketch matrix $S$ satisfies that each column of $S$ has only a single non-zero
entry chosen in a uniformly random position. That non-zero is $1$ with probability $1/2$, and $-1$ with
probability $1/2$. The columns of $S$ are independent of each other.
Importantly, computing $S \cdot X$ can be done in $O(\textrm{nnz}(X))$ time, and this significantly reduces
the number of rows of $X$. Then computing $G \cdot (S \cdot X)$ can now be done in $\tilde{O}(m^{1.5} d^{3})$ time.
While such a composition of matrices has been used before in the context of subspace embeddings for regression,
see, e.g., \cite{cw13}, here we show a new property of this composition - the distribution of $G \cdot S \cdot X$
looks like the distribution of $\tilde G \cdot X$! Formally, the statistical distance between the two distributions
is smaller than any positive constant.

{\it Therefore, in any application which uses $\tilde G \cdot X$, if we replace
$\tilde G \cdot X$ with $G \cdot S \cdot X$,
then if $p$ is the success probability of the old algorithm, then the success probability
of the new algorithm is at least $p - \delta$, where $\delta > 0$ is an arbitrarily small constant.}

We now give applications.
\\\\
{\bf Non-negative Matrix Factorization.}
Learning low rank structures and representations is a fundamental problem in machine learning.
With the rise of data-driven decision making, many businesses, government agencies,
and scientific laboratories are collecting increasingly
large amounts of data each day.
For instance, the large Hadron Collider (LHC)
experiments represent about $150$ million sensors acquiring around $40$ million samples
per second. Even working with $0.001$ percent of the sensor data, the data flow from all four
LHC experiments is around $25$ petabytes per day~\cite{brumfiel2011down}.
This means the traditional approach of storing the data, and then processing it
later, may be infeasible.
One approach would be to subsample the incoming streams. However, we may lose valuable
information in the form of infrequent events.

We use our transform to solve the nonnegative matrix factorization (NMF) problem.
Previous approaches~\cite{damle2014random,benson2014scalable,tepper2015compressed}
have used random matrices for the projection. However, these approaches can be slow if the
dimensionality of the data is high since they rely on multiplying by Gaussian matrices,
e.g., for natural images or structural Magnetic Resonance
Imaging brain scans. Recent work by Smola et al.~\cite{le2013fastfood} have shown that
sometimes dense random Gaussian matrices can be replaced by faster transforms,
and moreover, each row of the transform is equally likely to be in any
direction on the unit sphere. To show the correctness of the NMF algorithm, however,
we need a much stronger property than this, namely that any small
subset of rows of the transform has the property that its product with
a fixed matrix $X$ has low variation distance to the distribution of a product
of a Gaussian matrix with $X$. These latter properties, of having a fast transform with
{\it equal representation of directions on the sphere},
do not seem to have been exploited in the context of NMF. Our transformation, since it
has low variation distance to multiplying by a Gaussian matrix, directly applies here and
we can use existing analysis.

We note that the classical way of speeding up Gaussian
transforms via the Fast Hadamard or Fast Fourier Transform (see, e.g., \cite{t11})
do not work in this context, since they miss large sections of the sphere, and we provide
a formal counterexample in Section~\ref{sec:counterexample}. Intuitively, while it is fine to miss directions along large
sections of the sphere to approximate the norm of a vector,
it is not fine to miss directions for NMF, where the corresponding
polytope partitions the sphere into a small number of caps, and each cap should have a random
direction chosen from it.
\\\\
{\bf Support Vector Machines.}
We also apply random projections to the support vector machines (SVM) problem.
Previously, the CountSketch (CW)~\cite{clarkson2013count} projection and random Gaussian (RG) projection
have been applied to the linear SVM problem.
Despite Countsketch being much faster than the
Gaussian projection, the overall running time of projection together with the SVM solver was similar
for both
projections~\cite{paul2014random}, since the training of the projected data was faster when using
Gaussian projections. Our projection combines the CW matrix with
a smaller Gaussian matrix thereby getting the best of both worlds --- similar projection
time as CountSketch and similar
Gaussian properties of RG that are useful for SVM.
\\\\
{\bf Experiments.}
We empirically validate our results for both NMF and SVM applications.
For NMF, we give an experimental evaluation by comparing with state-of-the-art algorithms
such as SPA~\cite{gillis2014fast}, XRAY~\cite{kumar2013fast}, na\"ive random projections~\cite{damle2014random} ,
structured Gaussian random projections~\cite{tepper2015compressed}, and Tall-Skinny QR
factorization~\cite{benson2014scalable} for NMF problems with applications to breast cancer,
flow cytometry, and climate data.
Also, we show experimental speedups using our projection when combined with linear SVM solvers
 for document classification problems~\cite{paul2014random}.

\section{A New Randomized Transform}\label{sec:newTransform}
A CountSketch matrix $S\in \mathbb{R}^{B\times n}$ is a matrix all of whose rows have exactly one nonzero in a uniformly random location, and the value of the nonzero element is independently chosen to be $-1$ or $+1$ with equal probability. We denote the number of rows in the CountSketch matrix by $B$.

We prove the next theorem, which gives the formal guarantees of our new transform.
\begin{theorem}\label{thm:main}
There exists an absolute constant $C>0$  such that for every $\delta\in (0, 1)$, every integer $m\geq 1$ and every matrix $U\in \mathbb{R}^{n\times d}$ with orthonormal columns if $B\geq \frac1{\delta}C(\log n)^4\cdot d^2\cdot m^{1/2}$,  $S\in \mathbb{R}^{B\times n}$ is a random CountSketch matrix, and $G\in \mathbb{R}^{m\times B}$ and $\tilde G\in \mathbb{R}^{m\times n}$ are matrices of i.i.d. unit variance Gaussians, then the total variation distance between the joint distribution $G S U$ and $\tilde GU$ is less than $\delta$.
\end{theorem}
The proof is given in Section~\ref{sec:countsketch}.
We note that Theorem~\ref{thm:main} applies to matrices $U$ with orthonormal columns. This is sufficient for applying our transform to an arbitrary matrix $X$, since we can write $X=UR$, where the columns of $U$ form an orthonormal basis for the range of $X$, and apply the theorem to $U$.
Since $G\cdot S\cdot U$ is close the $\tilde G\cdot U$ in total variation distance, $G\cdot S\cdot UR=G\cdot S\cdot X$ is close to $\tilde G\cdot UR=\tilde G\cdot X$ in total variation distance as well.
We note that the role of $d$ and $n$ in Theorem~\ref{thm:main} is swapped in comparison to our notation for application to NMF below. The notation in Theorem~\ref{thm:main} is more consistent with the numerical linear algebra literature, and we thus prefer to state the theorem in this form.

In Section~\ref{sec:countsketch} of our paper we also first present a weaker version of Theorem \ref{thm:main} (see Theorem~\ref{thm:simple})
which establishes exactly the same guarantees but instead with $B \geq \frac{C}{\delta^2} \cdot d^2 \cdot m$. This version has a much simpler proof.

We first present the intuition behind the simpler version of Theorem \ref{thm:main}. Consider the distribution of the first row of the two matrices, namely $\tilde G U$ versus $G SU$. Both random variables are Gaussians in dimension $d$, but while the former is an ideal isotropic Gaussian, the latter, despite being Gaussian, has correlated entries. The correlations between the entries are due to the fact that the CountSketch matrix $S$ is not a perfect isometry: the correlation is given exactly by $U^TS^TSU$, which is the identity in expectation, but not for most realizations of $S$. In order to show that these two distributions are close in total variation distance, it would suffice to argue that the covariance matrix $U^TS^TSU$ is sufficiently close to the identity. This is exactly how the proof of the simpler version of Theorem \ref{thm:main} proceeds, which fixes an $S$ for which $U^TS^TSU$ is sufficiently close to the identity, using a so-called ``approximate matrix product'' theorem in the linear algebra community. After fixing such an $S$,
one can use that the rows of $G \cdot S$ and the rows of $\tilde{G}$ are independent, and then bound the variation distance between individual rows of $G \cdot S$ and of $\tilde{G}$. For the latter, it is convenient to work with Kullback-Leibler divergence (KL divergence) which is additive over product spaces; here we bound the KL divergence betwee a standard multivariate Gaussian and one with covariance matrix $U^TS^TSU$.

While this works for the simpler version of Theorem \ref{thm:main}, it can be seen that since we need to ensure that the {\bf joint} distribution of $\tilde G U$ is close to the joint distribution of $G S U$ for most choices of $S$, we would need to set $B$ to be at least $\approx d^2 m$ as opposed to $d^2 \sqrt{m}$, as in our bound in Theorem \ref{thm:main}. The idea behind the stronger result is to crucially use the fact that the distribution of $GSU$ is a mixture of Gaussians with varying covariance matrices. When $B\approx d^2\sqrt{m}$, one can see that most Gaussians $GSU$ in the mixture are too far in distribution from $\tilde GU$. However, we show that these differences that exist for {\bf most} choices of the CountSketch matrix $S$ cancel out {\bf on average}. While mixtures of Gaussians with varying means and fixed covariance structure have been analyzed in the literature, to the best of our knowledge our analysis is the first to handle nontrivial mixtures with changing covariance.

\section{Preliminaries for the Applications}\label{sec:prelim}
A few applications of our new randomized transform are NMF and SVM, which we now formally define.
\subsection{Nonnegative Matrix Factorization}
Given a nonnegative matrix $X$ of size $d \times n$, we would like to approximate it as a product of nonnegative matrices as follows:
$X \approx WH,$
where $W$ is of size $d \times k$ and $H$ is $k \times n$.
This problem was studied by Paatero and Tapper~\cite{paatero1994positive} under the name of positive matrix factorization and gained a wider popularity through the work of Lee and Seung~\cite{lee2001algorithms}.
NMF arises in a wide range of problems and application domains
such as curve resolution in chemometrics and document clustering; further references can be found in~\cite{arora2012computing}.
Various extensions to the original model to incorporate domain knowledge such as sparsity, orthogonality~\cite{ding2006orthogonal}, and under-approximation~\cite{gillis2010using} have also been studied.
Commonly used measures of approximation include the Frobenius norm, Itakuro-Saito (IS), and Bregman divergence with applications in image processing, speech and music analysis~\cite{yilmaz2011generalised} among other places.
Typical algorithms use alternating minimization to solve the non-convex objective function arising from NMF.

Until recently, the complexity of the NMF problem was unknown. Vavasis established that the NMF problem is NP-hard~\cite{vavasis2009complexity}. However, if the data satisfies the separability condition, a condition
introduced by Donoho and Stodden~\cite{donoho2003separable},
then tractable algorithms exist and have been recently proposed by Arora et al.~\cite{arora2012computing,recht2012factoring}.
Formally, a nonnegative matrix $X$ is $k$-separable if it satisfies the following condition:
$X = X_{I} H$,
where $I$ is an index set of size $k$
corresponding to the columns of the data matrix $X$.
Geometrically, this assumption implies that the columns of $X$
lie in a cone generated by the $k$ selected
columns of $X$ indexed by $I$.
One can view these $k$ selected columns as the extreme points of a polytope containing all other columns.
In practice, $k$ is much smaller than both $d$ and $n$. We will assume $k$-separability.

Given $X_{I}$, one can solve for $X$ by solving a nonnegative
least squares problem \cite{damle2014random},
and therefore our focus is on finding $X_{I}$, or equivalently, the index
set $I$ of extreme points of the point cloud formed by the columns of $X$.

To understand the guarantees of our algorithm, we define a few geometric notions also
used in \cite{damle2014random}, which we refer to for more background.
The {\it normal cone}
of a convex set $C$ at a point $x$ is the cone
$$N_C(x) = \{w \in \mathbb{R}^d \mid w^T(y-x) \leq 0 \textrm{ for
any } y \in C\},$$
that is, it is the cone defined by the outward normals of supporting hyperplanes at the point
$x$. One can define a measure $\omega(K)$ on any cone $K$, which for full-dimensional
cones $K$ satisfies $\omega(K) = \Pr[\theta \in K \cap S^{d-1}]$ where $\theta$ is a uniformly
random point on the sphere $S^{d-1}$ in $d$ dimensions. This measure is known as the
{\it solid angle} of $K$. For any convex polytope $C$,
if $P$ is the set of its extreme points,
then $\sum_{p \in P} \omega(N_C(p)) = 1,$
that is, the solid angles of the normal cones at the extreme points sum to $1$.
If we label the points $p_i \in P$, we will use the shorthand
$\omega_i = \omega(N_C(p_i))$.

A key property we will use is that for a unit vector $u$ and a convex set $C$,
the maximum inner product of $u$ with any point $p \in C$ is
achieved by an extreme point $p$ of $C$. Moreover, the maximum
is achieved by the extreme point $p$ precisely when $u \in N_C(p)$.
This follows since the inner product with a fixed vector $u$ is a linear function,
which is maximized by an extreme point for any convex set. These conditions also
hold if we replace maximum with minimum.

Our results, as in \cite{damle2014random}, depend on the condition number
$\kappa = \frac{1}{k \log \left (\frac{1}{\max_i 1- 2\omega_i} \right )}.$
The larger $\kappa$ is, the more pointed the polytope defined by the columns
of $X$ is, whereas if $\kappa$ is small, the polytope has ``fatter'' vertices.

\subsection{Support Vector Machines}
Given a dataset of samples and labels $\{x_i,y_i\}_{i=1}^N$ where $x_i$ corresponds to sample $i$ and $y_i$ the
corresponding label belonging to one of two classes denoted by $\{-1, 1\}$, we would like to find a maximum-margin hyperplane that separates
the two classes.
The primal form for the linear SVM problem is as follows:
\begin{align}
\min_{w} \frac{1}{2} \|w\|_2^2 + \frac{C}{N} \sum_{i=1}^N \max(0, 1 - y_i \langle w, x_i \rangle)
\end{align}
where $C$ is soft-margin parameter which allows for mis-classfication errors in the dataset and $w$ is
the maximum-margin hyperplane that we are learning from the data.
The dual form for the linear SVM problem is given as follows:
\begin{align}
\max_{0 \le \alpha \le C} 1^T \alpha - \frac{1}{2} \alpha^T Y X X^T Y \alpha
\end{align}

Previously~\cite{paul2014random} have shown that the margin (hyperplane) and minimum enclosing ball of the
original data is preserved after projection up to a multiplicative factor. However, in their original formulation
it is possible to just replace all points with zero to achieve the same guarantee.
We strengthen the theorems by requiring that the projected data
upper bound the objective of the original data. The details are given in Section~\ref{sec:svm-theorem}.

\section{Application to NMF}
We consider the separable NMF problem as defined in Section \ref{sec:prelim}.
We first review an algorithm proposed by Damle and Sun~\cite{damle2014random}.
Their algorithm involves the computation of $\tilde GX$ where $\tilde G$
is of dimensions $m \times d$ for a parameter $m$, and the element-wise
entries are distributed as $N(0,1)$.
Notice that we need to first compute the $m \times d$ random matrix $\tilde G$
which
is itself dense. We also need to compute the matrix product $\tilde GX$
with the input data. This is computationally expensive and is of the order
$O(mnd)$ in practice. Fast matrix multiplication routines
~\cite{cw90,w12} can be used in theory, but the time will still be
at least $k^{\omega-2}nd$, where $\omega \approx 2.376$ is the exponent of fast matrix
multiplication.
Instead, we propose to use our new transform
to
significantly speed up the computations for extracting the
extreme points in the dataset.
Note that both approaches are easily amenable to distributed-data settings by simply sharing
the seed of the random number generator which allows identical matrix transformations on all the computational nodes.
Our new algorithm is called \textbf{C}ount \textbf{G}auss NMF or \textbf{CountGauss} and is as follows:
\begin{algorithm}
    \caption{$\textrm{\textbf{C}ount\textbf{G}auss NMF (\textbf{CG})}$}
\label{alg:sketchNMF}
Initialize the index sets $I_{max},I_{min}$ to empty.\\
\begin{enumerate}
\item Let $T=G \cdot S$ where $G$ is an $m \times B$
matrix of i.i.d Gaussians, and $S$ is a $B \times d$ CountSketch
matrix. Here $B = Cn^{2}m^{.5} \log^4 n / \delta$.
\item Compute the product $Z = TX$.
\item Find the indices which give the maximum and
minimum across each row of $Z$ corresponding to $I_{max},I_{min}$
\end{enumerate}
\end{algorithm}
Instead of using Gaussian random matrices for the projection, we approximate them by the following projection
matrix $T=G \cdot S,$ where the matrices are defined in
Algorithm \ref{alg:sketchNMF}.

Consider the convex polytope defined by the columns of $X$ and their
negations. As defined in Section \ref{sec:prelim}, we assume
$k$-separability, namely, that there are $k$ columns of $X$, indexed by $I$,
for which $X = X_I H$ for a nonnegative matrix $H$. The columns
of $X_I$ are the extreme
points of a convex polytope $C$. By definition of an extreme point of a
convex polytope, the indices found in step 3 of
Algorithm \ref{alg:sketchNMF} belong to the index set $I$.

Damle and Sun show the following.
\begin{theorem}(Theorem 3.3 of \cite{damle2014random})\label{thm:damleMain}
Consider a modification to Algorithm \ref{alg:sketchNMF} in which we
replace $T$ by an $m \times d$ matrix of i.i.d. $N(0,1)$ random variables,
where $m = \kappa k \log(\frac{k}{\delta})$,
where recall $\kappa = \frac{1}{k \max_i 1-2\omega_i}$ is the condition number.
Then the probability that
the output $I_{min} \cup I_{max}$ of Algorithm \ref{alg:sketchNMF} contains
the index set $I$ of extreme points of $X$ is at least $1-\delta$.
\end{theorem}

Using Theorem \ref{thm:main}, we analyze the performance of
Algorithm \ref{alg:sketchNMF}.

\begin{theorem}\label{thm:algAnalysis}
Let $\delta > 0$ be given.
Suppose in Algorithm \ref{alg:sketchNMF} we set
the parameter $m = \kappa k \log(\frac{k}{\delta})$, where
$\kappa = \frac{1}{k \max_i 1-2\omega_i}$ is the condition number, and choose $B\geq \frac1{\delta}C(\log d)^4\cdot n^2\cdot m^{1/2}$ for a sufficiently large constant $C>1$ as per Theorem~\ref{thm:main}.
Then the probability that
the output $I_{min} \cup I_{max}$ of Algorithm \ref{alg:sketchNMF} contains
the index set $I$ of extreme points of $X$ is at least $1-2\delta$.
\end{theorem}
\begin{proof}
Let $I$ be the index set of extreme points of the polytope defined by
the columns of $X$. By definition of an extreme point,
in each iteration of step 4 of the algorithm, we
add an index $i \in I$ to $I_{max}$ and an index $j \in I$ to $I_{min}$ (since we are taking
the inner product with a linear function).
Therefore, the behavior of Algorithm \ref{alg:sketchNMF} is the same
if we instead, in each invocation of step 2, compute the product
$Z = T X_I$.

By our assumption on $m$, since $X_I$ is a $d \times k$ matrix we may
apply Theorem \ref{thm:main}, with the role of $n$ and $d$ in that theorem swapped,
to obtain that the variation
distance of the distributions of $T X_I$ and $\tilde G X_I$ is at most
$1 - \delta$, where $\tilde G$ is a matrix of i.i.d. $N(0,1)$ random
variables. Therefore, we can apply Theorem \ref{thm:damleMain} to conclude by a union bound that
the output of Algorithm \ref{alg:sketchNMF} contains the set $I$ with probability
at least $1-2\delta$.
\end{proof}
We obtain the same guarantee as Theorem \ref{thm:damleMain} with considerably faster computation time.
Indeed, our
matrix product $TX$ can be computed in
$O(\textrm{nnz}(X)) + \tilde{O}(m^{1.5}n^{3})$ time using our transform $T$,
as opposed to the $O(dnm)$ time needed in
\cite{damle2014random} to compute the product $ \tilde{G} X$ for a matrix
 $\tilde{G}$ of i.i.d. Gaussians. This is significant when $d$ is very large.

{\bf Distributed Environments:} Our results naturally provide
solutions to NMF in a distributed environment
in which the columns of $X$ are partitioned across multiple servers.
Indeed, the servers can agree upon a short random seed of length $O(d)$ words
to generate $T$. Each server can then compute its local sets
$I_{max},I_{min}$, and send them to a coordinator who can find the global
maxima and minima.

\iffalse
\subsection{Subspace embeddings for non-separable NMF algorithms}
Here we note a simple application of
the theory of subspace embeddings to alternating-minimization based
NMF algorithms \cite{wl10}, which apply even in the non-separable case.
In this case, one seeks to find nonnegative factors $\bm{W}$ and $\bm{H}$ to
minimize $\|\bm{X} - \bm{W}\bm{H}\|_F^2$, where $\bm{W}$ is $d \times r$ and $\bm{H}$ is $r \times n$.
One fixes $\bm{W}$, then solves for $\bm{H}$ by solving a constrained least squares regression problem. One then fixes
the newly found $\bm{H}$, and solves for $\bm{W}$ by solving a constrained least squares regression problem. This process
repeats until a suitably good solution is found. Note that there is not a convergence guarantee, as in
general the problem is NP-hard.

In \cite{wl10} the alternating minimization
is sped up by instead minimizing $\|\bm{R} \bm{X} - \bm{R} \bm{W}\bm{H}\|_F^2$
at each step, where $\bm{R}$ is a Gaussian or Fast Hadamard Transform. Using the recent work of Clarkson
and Woodruff \cite{cw13}, $\bm{R}$ may be chosen to be a CountSketch matrix, since the only
property used in \cite{wl10} is that $\bm{R}$ is a subspace embedding, namely,
that $\|\bm{R} \bm{X} \bm{X}^T \bm{R}^T - \bm{I}\|_2 < \epsilon$
(see Theorem 2.6 of \cite{woodruff2014sketching} for a simpler proof). Moreover, $\bm{R} \cdot \bm{X}$
is computable in $O(\textrm{nnz}(\bm{X}))$ time.
\fi
\begin{figure*}[ht!]
\includegraphics[width=0.47\linewidth]{clean_gauss.pdf}
\hfill
\includegraphics[width=0.42\linewidth]{clean_countgauss.pdf}
\caption{The fraction of trials in which the CG algorithm correctly extracted all ``k' extreme
    points. For each value of $k$ and $m$, we generated $500$ matrices such that data matrix is of size $1000 \times 500$ and
shown is how often we successfully recovered the original anchors (black indicates success). (Left) We contrast gaussian random projections (GP) with (right) our algorithm countGauss. Note that we recover the anchors with a similar success rate as GP.}
\label{fig:exact_recover}
\end{figure*}
\begin{figure*}[ht!]
\begin{center}
\includegraphics[width=0.97\linewidth]{noise_gauss.pdf}
\includegraphics[width=0.98\linewidth]{noise_countgauss.pdf}
\end{center}
\caption{We show the scree plots at $20$ noise levels
and notice that there are sharp transitions at $20$ corresponding to the rank of the data. (Top) Gaussian random projections and (bottom) our algorithm countGauss are applied to the dataset. For each
noise value in $\{0.01, 0.02, 0.03, 0.05, 0.08, 0.12, 0.22, 0.36, 0.6,1\}$, we generate $100$ datasets. At higher noise levels, we note that
both the algorithms GP and CG have most of the features active and there is no longer a sharp transition at $20$.}
\label{fig:noise_recover}
\end{figure*}

\section{Other Related work}
Over the last couple of years, many approaches have been proposed to solve the separable-NMF problem. \\
\textbf{XRAY}
Selects the anchors one at a time by expanding a cone until all columnds in the dataset are contained in it. At each step, XRAY finds the datapoint (column) which maximizes the inner product with the current residual matrix. It then computes the
residual matrix corresponding to the new set of anchor points~\cite{kumar2013fast}.\\
\textbf{SPA}
Successive projection algorithm~\cite{araujo2001successive,gillis2014fast} is a family of recursive algorithms where the projections are given by strongly convex functions. \\
\textbf{TSQR}
Use tall and thin QR factorization when the number of rows/features is really large~\cite{benson2014scalable}.
This approach is especially attractive when the number of features is really large ($\gg 10^6$) and number of samples
is small ($<10^5$).\\
\textbf{SC}
In~\cite{tepper2015compressed}, an algorithm similar to the one proposed by Damle and Sun
~\cite{damle2014random} is proposed.
The
difference is that instead of choosing a Gaussian or FastFood projection matrix, the projection is chosen
to be a matrix which depends on $X$ (data dependent projection), namely, one that is found via the subspace power
iteration (see Figure 3 of \cite{tepper2015compressed}). This approach is expensive in the case of distributed settings
since the projection matrix depends on all the samples.
\begin{figure}[ht!]
\begin{center}

    \includegraphics[width=0.97\linewidth]{breast.pdf}
\end{center}
\caption{Relative reconstructive error as function of anchors selected by the two algorithms CountGauss and GP are shown.
They are remarkably similar.}
\label{fig:breast_comp}
\end{figure}
\begin{figure}[ht!]
\includegraphics[width=0.47\linewidth]{gauss_flow.pdf}
\hfill
\includegraphics[width=0.47\linewidth]{countgauss_flow.pdf}
\caption{Coefficient matrices $H$ are shown for the two algorithms GP and CountGauss for the flow cytometry data when $k$ is
set to $16$. The coefficients tend to be clustered near the diagonal as has been previously observed.}
\label{fig:flow}
\end{figure}
\begin{figure*}[ht!]
    \begin{minipage}[b]{0.6\linewidth}
    \includegraphics[width=1\linewidth]{test_air_mon_time_new.pdf}

 (A) \qquad      Running times using CountGauss (comp==CG)
\end{minipage}
\begin{minipage}[b]{0.6\linewidth}
\includegraphics[width=1\linewidth]{test_air_mon_error_new.pdf}\\
(B)  \qquad     Relative error using CG
\end{minipage}
\caption{Extracting columns with CG versus using QR factorization. Note that the QR-based methods
are optimized for tall-and-skinny matrices and tend to do poorly for fat matrices. Note that CG (and SC) tends to perform
well since it is based on random projections and is at least an order of magnitude faster than QR-based methods.}
\label{fig:climate}
\end{figure*}

\begin{table*}[ht!]
\begin{center}
\begin{tabular}{|l| c|| c | c || c | c|| c | c || c|| r|| }
\hline
      \multicolumn{2}{|c||}{Test}   &     \multicolumn{2}{c||}{Proj}       &     \multicolumn{2}{c||}{SVMf}    &   \multicolumn{2}{c||}{Margin}   &  Proj &  Algo \\
\hline
  mean  &  std &    mean &   std  &  mean &    std  &   mean &    std  &  & \\
\hline
 17.92 & 11.29  &  0.0000 &  0.0000 &  0.89 &  0.38  &  2.1057 &  3.9391 &  full & full \\
 24.71 & 12.60  &  0.0086 &  0.0042 &  0.38 &  0.19  &  1.6792 &  3.5714 &   128 & countSketch \\
 25.27 & 13.08  &  0.0216 &  0.0047 &  \textbf{0.16} &  \textbf{0.11}  &  1.6277 &  3.5634 &   128 & countGauss  \\
 25.07 & 13.20  &  0.3676 &  0.1569 &  0.49 &  0.20  &  1.7143 &  3.7143 &   128 &         RG  \\
\hline
 17.92 & 11.29  &  0.0000 &  0.0000 &  0.89 &  0.38  &  2.1057 &  3.9391 &  full & full        \\
 22.56 & 12.42  &  0.0082 &  0.0036 &  0.54 &  0.21  &  1.8778 &  3.6709 &   256 & countSketch \\
 24.34 & 12.23  &  0.0565 &  0.0091 &  \textbf{0.21} &  \textbf{0.07}  &  1.8722 &  3.7389 &   256 & countGauss \\
 23.66 & 12.86  &  0.8178 &  0.3286 &  0.98 &  0.35  &  1.8895 &  3.6747 &   256 &         RG \\
\hline
 17.92 & 11.29  &  0.0000 &  0.0000 &  0.89 &  0.38  &  2.1057 &  3.9391 &  full & full       \\
 21.31 & 11.92  &  0.0075 &  0.0032 &  0.72 &  0.28  &  1.9914 &  3.7989 &   512 & countSketch\\
 22.11 & 12.89  &  0.1865 &  0.0228 &  \textbf{0.45} &  \textbf{0.11}  &  1.9893 &  3.8453 &   512 & countGauss\\
 22.42 & 12.37  &  1.6057 &  0.6437 &  1.88 &  0.67  &  2.0148 &  3.9014 &   512 &         RG\\
\hline
\end{tabular}
\caption{We applied CountGauss (CG), CountSketch (CW) and Random Gaussian (RG) on the TechTC300 dataset consisting of
$295$ pairs of data matrices and show the resulting mean and standard deviation for the resulting parameters such as
projection time, SVMf time (projection + SVM training time), margin (gamma) and testing error. The results are shown
over $10$-fold cross validation with $4$ repetitions and $3$ runs over the random projection matrices. Note that the mean running times
for our algorithm CG (highlighted) is faster than both CW and RG inspite of slower projection time than CW.}
\end{center}
\end{table*}
\section{Experiments}
We show experiments validating our projection operator countGauss (CG) for NMF problems on various synthetic and real-world datasets.
Also, we apply CG on the SVM problem for the TechTC300 datasets. In all our experiments\footnote{\url{https://github.com/marinkaz/nimfa}}, we set $B=5m$.
\\
{\bf Synthetic datasets.}
Similar to Damle and Sun~\cite{damle2014random}, we generate the data as follows:
We set a grid of tuples $(k, m)$ such that $m/k \approx \log k$. For each tuple, we generate $500$ separable
datasets, say X, such that they are of size $1000 \times 500$ and have nonnegative rank $k$.
Set matrix $U$ with i.i.d. samples from the uniform random distribution in $[0,1]$ of size $d \times k$.
Also, generate matrix $V$ with the identity matrix for the top $k$ indices and the rest with i.i.d samples from the uniform
distribution. Normalize each row of the matrix $V$ to unit norm and compute the matrix product $X = U\trans{V}$.
From Figure~\ref{fig:exact_recover}, we see that the CountGauss algorithm also requires $O(k\log k)$ optimizations to find all $k$ extreme points with high probability.
We also test the algorithm in the noisy case. For that, we  generate $U$ of size $1000 \times 20$ with uniform entries in $[0,1]$ and
and set the first $20$ columns of data matrix $X$ to $U$.
The remaining $190$ columns of $X$ are set to the midpoints of the $k(k+1)/2$-dimensional faces of the polytope with extreme points chosen by
the first $20$ columns of $X$. Now, we add Gaussian noise to $X$ with noise level $\sigma$ which creates many spurious
extreme points. The resulting scree plot is shown in Figure~\ref{fig:exact_recover}.
\\
{\bf Flow cytometry.}
The flow cytometry (FC) data represents abundances of fluorescent molecules labeling antibodies
that bind to specific targets on the surface of blood cells. A more detailed description of
the dataset can be found in~\cite{benson2014scalable}.
The measurements are represented as the data matrix A of size $40000 \times 5$.
Since they study pairwise interactions in the data, the Kronecker product, $X = A\otimes A$ is formed which is of size
$40000^2 \times 5^2$.

For this dataset, we exploit the data structure as follows. For some arbitrary input vector $g$, we know that
$A \otimes A g = \trans{A} G A$ where $g=\textrm{vec}(G)$. For each random projection,
we can compute the matrix-matrix product $AG$ very efficiently and in fact do not even need to generate the matrix $G$.
For our algorithm, we do not need to
explicitly compute the kronecker product and the complete NMF problem, including anchor selection and learning the weight coefficients,
can be solved in a couple of seconds on an off-the-shelf desktop. As we can see from Figure~\ref{fig:flow} the results are pretty consistent from prior work~\cite{benson2014scalable}.
The weight matrix $H$ still maintains a diagonal-like structure as previously observed.
\\
{\bf Gene expression breast cancer dataset.}
We utilize the hereditary breast cancer dataset collected by Hedenfalk et al. (2001) which consists of
the expression levels of $3226$ genes on $22$ samples from breast cancer patients.
The patients consist of three groups: 7 patients with a BRCA1 mutation, 8 samples with a BRCA2
mutation4, and 7 additional patients with sporadic cancers. It was analyzed using separable NMF in~\cite{damle2014random} and we similarly preprocess
the dataset by exponentiating to make the log- expression levels nonnegative and normalize the columns.
The size of the data matrix is $3222 \times 22$.
The result of applying our algorithm CG and GP are shown in Figure~\ref{fig:breast_comp}.
Notice that we get similar reconstruction error as GP while we vary the number of anchors.
\iffalse
\subsection{Movie dataset: Elephant Dreams}
We also experiment with the open-source movie ``Elephant Dreams'' used in~\cite{tepper2015compressed}.
The movie is approximately $11$ minutes long with $15961$ frames and was processed at the following resolution:
$360p$ --- $640 \times 360$ and the HDF5 file occupies approximately $43$GB.
We extract representative frames from the video clip of $120$ frames which was previously analyzed~\cite{tepper2015compressed}.
Using $6,15$ representative frames we obtain a relative error of $0.37,0.31$ comparable to that of $0.42,0.30$ which were obtained in~\cite{tepper2015compressed}.
$6$ representative scenes and the activation matrix are shown in Figure~\ref{fig:movie}.
\fi
\\
{\bf Climate Dataset.}
We obtained a climate dataset which was analyzed in~\cite{tepper2015compressed}. The data size is $10512 \times 23742$.
First we present the running times and reconstruction error when using SC versus QR-based algorithms and then show the corresponding results when using CG algorithm in Figure~\ref{fig:climate}. Note that CG (and SC) which is based on random projections is an order-of-magnitude faster compared to QR factorization methods.
\\
{\bf SVM TechTC-300 Dataset.}
We obtained the TechTC-300 dataset which is a comprehensive directory of the web. There are $295$-pairs of categories which provides a rich framework for running SVM experiments~\cite{paul2014random}.
Each data matrix has $10,000 - 40,000$ words and $150-280$ documents. LIBSVM was used with a linear kernel and soft-margin parameter $C$ set to $500$ for all experiments and we set
the projections to $128, 256,$ and $512$.
The results are summarized in the Table 1.

\input{countsketch.tex}

\input{app.tex}

\section{A counterexample for Fast Hadamard Transforms}\label{sec:counterexample}
\begin{figure}[h!]
    \begin{center}
    \includegraphics[width=0.7\linewidth]{neg_anchor.pdf}
    \end{center}
    \caption{Illustrative example with $5$ points corresponding the vertices of a pentagon inscribed in a unit circle.
    The normal cone at $(0,1)$ is not covered by any of the vectors in $\{-1\sqrt{2},+1\sqrt{2}\}^2$.}
    \label{fig:illus_anchor}
\end{figure}
A natural alternative
transform to try would be the $m \times d$ Subsampled Randomized Hadamard Transform
(SRHT) (see the references in Theorem 7 of \cite{woodruff2014sketching}),
which has the form $V = P \cdot H \cdot D$, where
$P$ is a diagonal matrix with a random subset of $m$ diagonal entries
equal to $1$, and the remaining equal to $0$, $H$ is the Hadamard transform,
and $D$ is a diagonal matrix with random signs along the diagonal. Like
FastFood, the SRHT
can be applied to a $d$-dimensional vector in $O(d \log d)$ time. Note
that each row of $V$ is in the set $\{-1/\sqrt{d}, +1/\sqrt{d}\}$.

An illustrative counterexample would be to consider a pentagon inscribed in a unit circle~\ref{fig:illus_anchor} with one
point $p$ at $(0,1)$. Each extreme point then receives $1/5$ of the circumference of the enclosing circle and so to be in
the normal cone at $p$, one needs to have an angle in $[3\pi/10,7\pi/10]$. Hence, the second coordinate ("y") needs to have
magnitude at least $\sin(3\pi/10)$ which is larger than $1\sqrt{2}$ and so a vector in $\{-1\sqrt{2},+1\sqrt{2}\}^2$ will
never be in it.
Generalizing this to $d$-dimensions, we could consider a convex set $C$ entirely supported on the first $2$ coordinates
(so $0$ on the remaining coordinates). Further, we have that $C$ is a pentagon with one extreme point equal
to $(0,1,\ldots, 0)$. Now we require the second coordinate to have magnitude at least $\sin(3\pi/10)$ which is larger
than $1\sqrt{d}$ and therefore a vector in $\{-1\sqrt{d}, +1\sqrt{d}\}^d$ will never be in it.
With probability $\approx 0.16$, a random point on
the sphere will have $x_1 > 1/\sqrt{d}$ (this corresponds to one standard deviation
of an $N(0, 1/d)$ random variable), which means $\omega(N_C(p)) \approx 0.16$,
yet {\it no row of $V$} will be in $N_C(p)$, which means that even
if the condition number $\kappa$ is constant, an algorithm using the SRHT in place
of the FastFood transform will fail with probability $1$.

\section{SVM with Random Projections }\label{sec:svm-theorem}

We require the following stronger theorem for the SVM problem~\cite{paul2014random}. \\
\begin{theorem}{Let $\epsilon \in (0, \frac{1}{2}]$ be an accuracy parameter and let $R \in \mathbb{R}^{d \times r}$ be a matrix satisfying
$\|V^T V - V^T R R^T V\|_2 \le \epsilon$
	where $V \in \mathbb{R}^{d\times \rho}$ be the orthonormal (columns) matrix of right singular vectors obtained from the SVD of $X$.
Let $\gamma^{*}$ and $\tilde{\gamma}^*$ be the
margins obtained by solving the SVM problems using data matrices $X$ and $X R$ respectively. Then \\
\begin{center}
	$ (1-\epsilon) \gamma^{*2} \le \tilde{\gamma}^{*2} \le ( 1 + \epsilon) \gamma^{*2}$
\end{center}}
\end{theorem}
\begin{proof}
We will follow a similar structure from Paul et al~\cite{paul2014random}. Let us denote by $ E  := V^T V  - V^T R R^T V$ and for optimal solution vectors $\alpha^*$, $\tilde{\alpha}^*$ the dual SVM objectives are given by:
\begin{align}
Z_{\textrm{opt}} &= 1^T \alpha^{*} - \frac{1}{2} \alpha^{*T} Y X X^{T} Y \alpha^{*} \\
\tilde{Z}_{\textrm{opt}} &= 1^T \tilde{\alpha}^{*} - \frac{1}{2} \tilde{\alpha}^{*T} Y X R R^{T} X^{T} Y \tilde{\alpha}^{*}
\end{align}

Let us first consider the objective function at the optimal vector $\alpha$ of the original problem:
\begin{align}
\label{eq:zorig}
\nonumber
Z_{\textrm{opt}} &= 1^T \alpha^{*} - \frac{1}{2} \alpha^{*T} Y X X^{T} Y \alpha^{*} \\
\nonumber
                 &= 1^T \alpha^{*} - \frac{1}{2} \alpha^{*T} Y U \Sigma V^{T} R R^{T} V \Sigma U^{T} Y \alpha^{*}
                    - \frac{1}{2} \alpha^{*T} Y U \Sigma E \Sigma U^{T} Y \alpha^{*} \\
                 &\ge \tilde{Z}_{\textrm{opt}}  - \frac{1}{2} \tilde{\alpha}^{*T} Y U \Sigma E \Sigma U^{T} Y \tilde{\alpha}^{*}
\end{align}
where we substituted the vector $\tilde{\alpha}^*$ in the objective and utilize the fact that it is smaller than the optimal value.
Next, we consider the projected problem and lower-bound it as follows:
\begin{align}
\label{eq:zproj}
\nonumber
\tilde{Z}_{\textrm{opt}} &= 1^T \tilde{\alpha}^{*} - \frac{1}{2} \tilde{\alpha}^{*T} Y X R R^{T} X^{T} Y \tilde{\alpha}^{*} \\
\nonumber
                 &= 1^T \tilde{\alpha}^{*} - \frac{1}{2} \tilde{\alpha}^{*T} Y U \Sigma V^{T} V \Sigma U^{T} Y \tilde{\alpha}^{*}
                    - \frac{1}{2} \tilde{\alpha}^{*T} Y U \Sigma (-E) \Sigma U^{T} Y \tilde{\alpha}^{*} \\
                 &\ge Z_{\textrm{opt}}  - \frac{1}{2} \tilde{\alpha}^{*T} Y U \Sigma (-E) \Sigma U^{T} Y \tilde{\alpha}^{*}
\end{align}
where we substituted the vector $\alpha^*$ in the objective as before and utilize the fact that it is smaller than the optimal value.
By sub-multiplicativity, we have by using the fact $V^T V = I$:
\begin{align}
\label{eq:submult}
\frac{1}{2} z^T Y U \Sigma G \Sigma U^T  Y z &\le \frac{1}{2} \|z^T Y U \Sigma\| \cdot \|G\|_2 \cdot \|  \Sigma U^T Y z\| \\
                                              & =  \frac{1}{2} \|G\|_2 \cdot \|z^T Y X\|_2^2
\end{align}
for any vector $z$ and matrix $G$.
Let us bound the following second-order term:
\begin{align*}
| z^T Y X R R^{T} X^T Y z  - z^T Y X X^T Y z| &= | z^T Y U \Sigma (V^T R R^T V  - V^T V) \Sigma U^T Y z| \\
                   &= | z^T Y U \Sigma (-E) \Sigma U^T Y z | \\
                   &\le \|E\|_2 \cdot \| z^T Y U \Sigma \|_2^2 \\
                   &= \|E\|_2 \cdot \| z^T Y X \|_2^2
\end{align*}
for any vector $z$. This gives us the following useful inequality:
\begin{align}
\label{eq:ineqobj}
\| z^T Y X \|_2^2 \le \frac{1}{1 - \|E\|_2} \|z^T Y X R\|_2^2
\end{align}

Combining~\eqref{eq:zorig},~\eqref{eq:zproj},~\eqref{eq:submult}, and~\eqref{eq:ineqobj} for $z \in (\alpha, \tilde{\alpha})$ and $G \in (-E, E)$, we have the
following bounds:
\begin{align}
\nonumber
\tilde{Z}_{\textrm{opt}} &\ge Z_{\textrm{opt}} - \frac{1}{2} \|E\|_2 \cdot \|\alpha^{*T} Y X\|_2^2 \\
\nonumber
                    &= Z_{\textrm{opt}} - \|E\|_2\cdot Z_{\textrm{opt}} \\
                    &= (1 - \|E\|_2) Z_{\textrm{opt}}\\
\nonumber
Z_{\textrm{opt}} &\ge \tilde{Z}_{\textrm{opt}} - \frac{1}{2} \|E\|_2 \cdot \|\tilde{\alpha}^{*T} Y X \|_2^2 \\
\nonumber
                   &\ge  \tilde{Z}_{\textrm{opt}} - \frac{\|E\|_2}{1 - \|E\|_2}  \frac{\|\tilde{\alpha}^{*T} Y X R \|_2^2}{2} \\
\nonumber
                 &= \tilde{Z}_{\textrm{opt}} - \frac{\|E\|_2}{1 - \|E\|_2} \tilde{Z}_{\textrm{opt}} \\
                 &= ( 1  - \frac{\|E\|_2}{1 - \|E\|_2} ) \tilde{Z}_{\textrm{opt}}
\end{align}
The bounds follow by using the following relations,
$Z_{\textrm{opt}} = \frac{1}{2 \gamma^{*2}}$ and $\tilde{Z}_{\textrm{opt}} = \frac{1}{2 \tilde{\gamma}^{*2}}$:
\begin{align}
(1 - \frac{\|E\|}{1 - \|E\|_2}) \gamma^{*2} \le \tilde{\gamma}^{*2} \le \frac{1}{1 - \|E\|_2} \gamma^{*2}
\end{align}
Notice that we cannot now trivially project the data to zero ($XR$ to the zero matrix) which would have been acceptable if we had the used the weaker version of theorem as stated in~\cite{paul2014random}.
\end{proof}

\section{Discussion}
 We have presented an efficient way to multiply by a Gaussian matrix, without actually computing the dense
 matrix product. Theorem~\ref{thm:main} provides our theoretical guarantees on this much faster transform,
 showing it has low variation distance to multiplication by a dense Gaussian matrix.
 \iffalse
We refer the reader to the full version of our paper for the formal proof of Theorem~\ref{thm:main}.
\fi

 Our transform is useful in a surprising number of applications --- here we apply our transform to NMF and SVM.
 The classical way of speeding up Gaussian transforms via the Fast Hadamard or FFT does not work in our setting since it misses large sections of the sphere.

 Our experiments on synthetic and real-world datasets for NMF showed that
 the results obtained by our algorithm were on par with the state-of-the-art NMF algorithms such as
 SC, XRAY and SPA. In particular, for synthetic problems, we showed similar anchor recovery performance as random projection (GP) of
Damle and Sun~\cite{damle2014random} both in the noiseless and noisy cases. Also, the performance was remarkably similar to  GP when applied on the breast cancer dataset and also picked up activation patterns which might be of biological interest as previously noted in flow cytometry problems.
 Experiments on document classification tasks using the popular SVM formulation revealed that the new projection leads to faster
 SVM solutions than previous methods. Previously, it was shown that while CountSketch led to faster projection times it did not lead to overall
 faster training time and was in fact was found to be slower than random Gaussian projections (RG). Our new countGauss projection fixes this by sacrificing projection time compared to countSketch projection but leads to an overall faster SVM training time and thereby beats both random Gaussian and CountSketch-based SVM algorithms~\cite{paul2014random}.
 We note that in practice for SVM, solution accuracy may be of critical importance rather than computation time and in these
 scenarios random projection based algorithms can be used to explore the optimal settings of the SVM parameters such as soft-margin.
 In our experiments (not shown) we noticed that these lead to faster training times while not sacrificing test accuracy.

\section*{Acknowledgements}
Vamsi P. would like to acknowledge support from the following grant: NSF-IIP-1346452 and also RDI$^2$ at Rutgers University where this work was initiated. David W. would like to acknowledge the support from XDATA program of the Defense Advanced Research Projects Agency (DARPA), administered through Air Force Research Laboratory contract FA8750-12-C-0323.