# Fitting an ellipsoid to a quadratic number of random points

Afonso S. Bandeira, Antoine Maillard, Shahar Mendelson, Elliot Paquette

###### Abstract

We consider the problem $(\rm P)$ of fitting $n$ standard Gaussian random
vectors in $\mathbb{R}^{d}$ to the boundary of a centered ellipsoid, as
$n,d\to\infty$. This problem is conjectured to have a sharp feasibility
transition: for any $\varepsilon>0$, if $n\leq(1-\varepsilon)d^{2}/4$ then
$(\rm P)$ has a solution with high probability, while $(\rm P)$ has no
solutions with high probability if $n\geq(1+\varepsilon)d^{2}/4$. So far, only
a trivial bound $n\geq d^{2}/2$ is known on the negative side, while the best
results on the positive side assume $n\leq d^{2}/\mathrm{polylog}(d)$. In this
work, we improve over previous approaches using a key result of Bartl &
Mendelson on the concentration of Gram matrices of random vectors under mild
assumptions on their tail behavior. This allows us to give a simple proof that
$(\rm P)$ is feasible with high probability when $n\leq d^{2}/C$, for a
(possibly large) constant $C>0$.

## 1 Introduction

We study the following question: given $n$ vectors in $\mathbb{R}^{d}$
independently sampled from the standard Gaussian measure, when does there
exist an ellipsoid centered at $0$ whose boundary goes through all of the
vectors? This question was raised by [Sau11, SCPW12, SPW13], and has received
significant attention recently [PTVW22, KD22, HKPX23]. We will discuss the
motivations behind this problem and review some of the recent literature in
Section 1.1. In the original series of work of Saunderson&al [Sau11, SCPW12,
SPW13], it was conjectured based on numerical experiments that the ellipsoid
fitting property undergoes a phase transition in the limit $d\to\infty$ for
$n\sim d^{2}/4$. Notably, the threshold $d^{2}/4$ corresponds to the
statistical dimension of the cone of positive semidefinite matrices [Gor88,
ALMT14] (see [PTVW22] for a discussion).

######  Conjecture 1.1 (The ellipsoid fitting conjecture).

Let $n,d\geq 1$, and
$x_{1},\cdots,x_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\mathrm{I}_{d}/d)$.
Let $p(n,d)$ be defined as the probability of existence of a fitting ellipsoid
centered in $0$:

$\displaystyle p(n,d)$
$\displaystyle\coloneqq\mathbb{P}\Big{[}\exists\Sigma\in\mathcal{S}_{d}\,:\,\Sigma\succeq
0\quad\textrm{and}\quad x_{i}^{\top}\Sigma x_{i}=1\quad(\forall
i\in[n])\Big{]}.$

For any $\varepsilon>0$, the following holds:

$\displaystyle\begin{dcases}\limsup_{d\to\infty}\frac{n}{d^{2}}\leq\frac{1-\varepsilon}{4}&\Rightarrow\lim_{d\to\infty}p(n,d)=1,\\\
\liminf_{d\to\infty}\frac{n}{d^{2}}\geq\frac{1+\varepsilon}{4}&\Rightarrow\lim_{d\to\infty}p(n,d)=0.\end{dcases}$

Our main result gives a positive answer to the existence statement of
Conjecture 1.2, up to a constant factor in $n/d^{2}$. We present its proof in
Section 2.

######  Theorem 1.2 (Ellipsoid fitting up to a constant).

Let $n,d\geq 1$, and
$x_{1},\cdots,x_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\mathrm{I}_{d}/d)$.
Given any $\beta\geq 1$, there exist a (small) constant
$\alpha=\alpha(\beta)>0$ and a (large) constant $C=C(\beta)>0$ such that for
$n\leq\alpha d^{2}$:

$\displaystyle\mathbb{P}\left[\exists\Sigma\in\mathcal{S}_{d}\,:\,\Sigma\succeq
0\quad\textrm{and}\quad x_{i}^{\top}\Sigma x_{i}=1\quad(\forall
i\in[n])\right]\geq 1-Cn^{-\beta}.$

From polynomial to exponential probability bounds – While we show a polynomial
lower bound on the probability, as we will notice during the detailing of the
proof, we believe that such a lower bound can be improved to an exponential
lower bound of the type $1-2\exp(-Cd)$, for $n\leq\alpha d^{2}$ and a
universal constant $\alpha>0$. We highlight the principles of this improvement
in the proof, and detail how it would require a slightly deeper dive into the
arguments of the proof of the main result of [BM22]. Since the main conjecture
of ellipsoid fitting only concerns the limit of the probability and not its
scaling, we leave this improvement for future work, and will sometimes use
probability estimates that are not the sharpest possible, but are sufficient
for our goal.

###  1.1 Motivation and related literature

We give here a brief overview of the motivations to consider the ellipsoid
fitting problem, as well as previous results on this conjecture.

Despite the fact that Conjecture 1.1 remains open, the ellipsoid fitting
property is a natural question in random geometry. Notably, if the vectors
$x_{1},\cdots,x_{n}$ satisfy this property, then there is no vector $x_{i}$
lying in the interior of the convex hull of the other vectors $(\pm
x_{j})_{j\neq i}$. Moreover, this problem has several connections with machine
learning and theoretical computer science, which motivated its introduction.
Examples of these connections include the decomposition of a data matrix into
a sum of diagonal and low-rank components [Sau11, SCPW12, SPW13], overcomplete
independent component analysis [PPW+19], or the discrepancy of random matrices
[SCPW12, PTVW22]. Relations to these various problems are discussed more
extensively in the introduction of [PTVW22], to which we refer the interested
reader for more details.

The negative side of the conjecture – A dimension counting argument shows that
ellipsoid fitting is generically not possible if $n>d(d+1)/2$, implying that
the negative part of Conjecture 1.1 is non-trivial only in the range
$d^{2}/4\lesssim n\lesssim d^{2}/2$. Despite the simplicity of this argument,
$d^{2}/2$ is still the best-known bound on the negative side of Conjecture
1.1.

Early results – In the original works that introduced the ellipsoid fitting
conjecture [Sau11, SPW13], it was proven that ellipsoid fitting is feasible
with high probability if $n\lesssim\mathcal{O}(d^{6/5-\varepsilon})$ (for any
$\varepsilon>0$). This bound was improved to
$n\lesssim\mathcal{O}(d^{3/2-\varepsilon})$ in [GJJ+20], where the result was
obtained as a corollary of the proof of a Sum-of-Squares lower bound for the
Sherrington-Kirkpatrick Hamiltonian of statistical physics111In the revised
version of [PTVW22], as well as in [HKPX23], it was noticed that the results
of [GJJ+20] actually hold for
$n\lesssim\mathcal{O}(d^{2}/\mathrm{polylog}(d))$., using a pseudo-calibration
construction.

Comparison with recent work – Our proof is based on an “identity perturbation”
construction, an idea which was described in [PTVW22], and used in [KD22] to
prove that $p(n,d)\to 1$ under the assumption that
$n=\mathcal{O}(d^{2}/\mathrm{polylog}(d))$. On the other hand, [PTVW22] uses a
least-square construction to prove that ellipsoid fitting is possible with
high probability under the similar condition
$n=\mathcal{O}(d^{2}/\mathrm{polylog}(d))$222We note that [PTVW22] was
recently updated to present an alternative proof through the identity
perturbation construction, again under the assumption
$n=\mathcal{O}(d^{2}/\mathrm{polylog}(d))$..

Our proof follows in part the one of [KD22], improving a crucial operator norm
bound thanks to results of [BM22]. As mentioned in [KD22], using a suboptimal
bound on this operator norm was the main limitation that prevented the authors
to prove the existence of a fitting ellipsoid for $n\leq d^{2}/C$. We
emphasize that numerical studies [PTVW22] suggested that the identity
perturbation construction is successful only in the range $n\lesssim
d^{2}/10$, so in order to resolve Conjecture 1.1 (or even just the existence
part) it appears a new idea is needed333Numerical simulations of [PTVW22]
suggest the least-squares approach suffers from the same shortcomings..

Parallel work – As we were finalizing the current manuscript, another proof
that ellipsoid fitting is possible at a quadratic number of points was
proposed [HKPX23]. Like our approach, the proof in [HKPX23] is based on the
identity perturbation construction, but the proof techniques appear to us to
be quite different: [HKPX23] relies on the theory of graph matrices, and as
such strengthens similar arguments presented in [PTVW22] (while our proof can
instead be viewed as a strengthening of the arguments in [KD22]).

More specifically, our approach relies on obtaining a crucial bound on the
operator norm of a kernel Gram matrix by mapping it to the Gram matrix of
flattened rank-one matrices, and using the results of [BM22]. This latter work
showed the concentration of the Gram matrix of i.i.d. vectors
$X_{1},\cdots,X_{n}$ under the assumption that the first moments of the
projections $\langle X,u\rangle$ satisfy (uniformly in $u$) a
$\psi_{\alpha}$-like tail bound for some $\alpha\in(0,2]$.

###  1.2 The dual semidefinite program

Note that ellipsoid fitting belongs to the class of random semidefinite
programs, and as such admits a dual formulation. As we find the dual problem
to have a particularly interesting formulation we include a short expository
snippet to highlight this dual SDP, and the consequences of Theorem 1.2 for
it. Namely, it implies the following corollary.

######  Corollary 1.3 (Dual problem).

Let $n,d\geq 1$, and
$x_{1},\cdots,x_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,\mathrm{I}_{d}/d)$.
Given any $\beta\geq 1$, there exist a (small) constant
$\alpha=\alpha(\beta)>0$ and a (large) constant $C=C(\beta)>0$ such that for
$n\leq\alpha d^{2}$:

$\displaystyle\mathbb{P}\left[\exists
z\in\mathbb{R}^{n}\,:\,\sum_{i=1}^{n}z_{i}=0\textrm{ and
}\lambda_{\max}\left(\sum_{i=1}^{n}z_{i}x_{i}x_{i}^{\top}\right)<0\right]\leq
Cn^{-\beta}.$

Corollary 1.3 rewrites ellipsoid fitting as a problem of “balancing” rank-one
matrices: we show that for $n\leq\alpha d^{2}$ it is impossible to find a
centered balancing of $(x_{i}x_{i}^{\top})$ such that the resulting matrix is
negative definite (nor positive definite as one can always consider $-z$). We
note however that duality doesn’t play any explicit role in the proof of
Theorem 1.2.

Proof of Corollary 1.3 – By weak duality and Theorem 1.2, with probability at
least $1-Cn^{-\beta}$ for $n\leq\alpha(\beta)d^{2}$, we have

$\displaystyle\max_{\begin{subarray}{c}y\in\mathbb{R}^{n}\\\
\sum_{i=1}^{n}y_{i}x_{i}x_{i}^{\top}\preceq\,0\end{subarray}}\sum_{i=1}^{n}y_{i}=0.$

We now condition on this event. Thus for all $y\in\mathbb{R}^{n}$, if $\sum
y_{i}>0$ then $\lambda_{\max}(\sum_{i=1}^{n}y_{i}x_{i}x_{i}^{\top})>0$. Let
$z\in\mathbb{R}^{n}$ such that $\sum_{i=1}^{n}z_{i}=0$. To prove Corollary
1.3, it suffices to show that
$\lambda_{\max}(\sum_{i=1}^{n}z_{i}x_{i}x_{i}^{\top})\geq 0$. Let
$M(z)\coloneqq\sum_{i=1}^{n}z_{i}x_{i}x_{i}^{\top}$. Let $\varepsilon>0$, and
$y_{i}(\varepsilon)\coloneqq z_{i}+\varepsilon$. Since $\sum y_{i}>0$, there
exists $u_{\varepsilon}\in\mathcal{S}^{d-1}$ (the Euclidean unit sphere in
$\mathbb{R}^{d}$) such that
$u_{\varepsilon}^{\top}M(z)u_{\varepsilon}+\varepsilon\sum_{i=1}^{n}\langle
u_{\varepsilon},x_{i}\rangle^{2}>0$. Extracting a converging sub-sequence as
$\varepsilon\to 0$ by compactness, there exists $u\in\mathcal{S}^{d-1}$ with
$u^{\top}M(z)u\geq 0$. $\square$

## 2 Proof of Theorem 1.2

Notation – Positive universal constants are generically denoted as $c_{k}$ or
$C_{k}$, and may vary from line to line. We will explicit possible
dependencies of such constants on relevant parameters when necessary.
$\mathcal{S}_{d}$ denotes the set of $d\times d$ real symmetric matrices,
$\mathrm{I}_{d}$ is the identity matrix, and $\mathbf{1}_{d}$ is the all-ones
vector. $\mathcal{S}^{d-1}$ is the Euclidean unit sphere in $\mathbb{R}^{d}$.

Remark – Since the ellipsoid fitting has a clear monotonocity property with
respect to $n$, we assume without loss of generality in what follows that
$n=\omega(d^{2-\varepsilon})$ for any fixed $\varepsilon>0$. The polynomial
exponent on the probability estimates, of the form $n^{-\beta}$, can be taken
to be arbitrarily large but it will be considered fixed throughout, with
$\beta\geq 1$, and as it will be clear below constants generally depend on
$\beta$.

###  2.1 Identity perturbation ansatz

In the identity perturbation ansatz [PTVW22, KD22], we look for a fitting
ellipsoid $\Sigma\in\mathcal{S}_{d}$ in the form:

$\displaystyle\Sigma=\mathrm{I}_{d}+\sum_{i=1}^{n}q_{i}x_{i}x_{i}^{\top},$ (1)

for some $q\in\mathbb{R}^{n}$. Having $\Sigma\succeq 0$ is thus equivalent to:

$\displaystyle\sum_{i=1}^{n}q_{i}x_{i}x_{i}^{\top}\succeq-\mathrm{I}_{d}.$ (2)

We denote $x_{i}=\sqrt{d_{i}}\omega_{i}$, with
$\omega_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}[\mathcal{S}^{d-1}]$,
and $d_{i}\coloneqq\|x_{i}\|_{2}^{2}$, and we let
$D\coloneqq\mathrm{Diag}(\\{d_{i}\\}_{i=1}^{n})$ and
$\Theta\in\mathbb{R}^{n\times n}$ with
$\Theta_{ij}\coloneqq\langle\omega_{i},\omega_{j}\rangle^{2}$. Note that
$d_{i}$ are i.i.d. variables, independent of the directions $\omega_{i}$.
Plugging the ansatz of eq. (1) into the ellipsoid fitting equations
$x_{i}^{\top}\Sigma x_{i}=1$ yields:

$\displaystyle\mathbf{1}_{n}=D\mathbf{1}_{n}+D\Theta Dq.$

Assuming that $D$ and $\Theta$ are invertible, this equation is solved by:

$\displaystyle q$
$\displaystyle=D^{-1}\Theta^{-1}(D^{-1}\mathbf{1}_{n}-\mathbf{1}_{n}).$

Plugging it back into eq. (2), we see that the identity perturbation ansatz
gives a semidefinite positive solution to the ellipsoid fitting problem if
$\Theta,D$ are invertible, and

$\displaystyle\min_{a\in\mathcal{S}^{d-1}}\sum_{i=1}^{n}\Big{[}\Theta^{-1}(D^{-1}\mathbf{1}_{n}-\mathbf{1}_{n})\Big{]}_{i}\langle
a,\omega_{i}\rangle^{2}\geq-1.$ (3)

###  2.2 Concentration of a kernel Gram matrix

We use the following critical lemma on the concentration of the matrix
$\Theta$ appearing in eq. (3).

######  Lemma 2.1 (Concentration of a kernel Gram matrix).

Let $n,d\geq 1$, and
$\omega_{1},\cdots,\omega_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}[\mathcal{S}^{d-1}]$.
Let $\Theta_{ij}\coloneqq\langle\omega_{i},\omega_{j}\rangle^{2}$. For any
$\beta\geq 1$, there are constants such that, with probability greater than
$1-n^{-\beta}-2\exp(-c_{0}n)$, the following occurs:

$\displaystyle\|\Theta-\mathbb{E}\Theta\|_{\mathrm{op}}$
$\displaystyle\leq\frac{C_{1}}{d}+C_{2}(\beta)\left(\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\right)$
(4)

Notice that
$\mathbb{E}\Theta=(1-1/d)\mathrm{I}_{n}+(1/d)\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$.
This lemma is a consequence of the analysis of [BM22], and is proven in
Section 3.1.

Remark: improving the probability upper bound – A careful analysis of the
proof arguments of [BM22] reveals that in the present case in which the matrix
to control is a Gram matrix of sub-exponential vectors (which will be the case
here as detailed in the proof), the probability estimate could likely be
improved significantly to yield a probability lower bound of $1-2\exp(-cn)$.
We leave for future work to carry out this improvement, and keep a formulation
that follows directly from the results of [BM22].

We get the following corollary:

######  Corollary 2.2 (Concentration of the inverse).

Let $n,d\geq 1$, and
$\omega_{1},\cdots,\omega_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}[\mathcal{S}^{d-1}]$.
Let $\Theta_{ij}\coloneqq\langle\omega_{i},\omega_{j}\rangle^{2}$. For any
$\beta\geq 1$, there exists $\alpha=\alpha(\beta)>0$ and constants such that
if $n\leq\alpha d^{2}$ and $d\geq d_{0}(\beta)$, then with probability at
least $1-n^{-\beta}-2\exp(-c_{0}n)$:

$\displaystyle\left\|\Theta^{-1}-\left(\mathrm{I}_{n}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\right)\right\|_{\mathrm{op}}\leq\frac{C_{1}}{d}+C_{2}(\beta)\sqrt{\frac{n}{d^{2}}}+\frac{d}{n}.$
(5)

In particular, assuming $n=\omega(d)$, for all $\beta\geq 1$ there is
$\alpha=\alpha(\beta)>0$ such that if $n\leq\alpha d^{2}$:

$\displaystyle\mathbb{P}[\|\Theta^{-1}\|_{\mathrm{op}}\leq 2]\geq
1-2n^{-\beta}.$ (6)

Proof of Corollary 2.2 – Note that
$\|\mathbb{E}\Theta-[\mathrm{I}_{n}+(1/d)\mathbf{1}_{n}\mathbf{1}_{n}^{\top}]\|_{\mathrm{op}}=(1/d)$,
so that eq. (4) also holds replacing $\mathbb{E}\Theta$ by
$\mathrm{I}_{n}+(1/d)\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$. We use the
following elementary lemma, proven in Section 3.4.

######  Lemma 2.3.

Let $A,B\in\mathcal{S}_{n}$ two symmetric matrices, such that $B\succ 0$, and
for some $\varepsilon<\lambda_{\min}(B)$ we have
$\|A-B\|_{\mathrm{op}}\leq\varepsilon$. Then

$\displaystyle\|A^{-1}-B^{-1}\|_{\mathrm{op}}\leq\varepsilon\frac{\|B^{-1}\|_{\mathrm{op}}^{2}}{1-\varepsilon\|B^{-1}\|_{\mathrm{op}}}.$

Applying Lemma 2.3 to
$B=\mathrm{I}_{n}+(1/d)\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$, such that
$\lambda_{\min}(B)=1$, and
$B^{-1}=\mathrm{I}_{n}-(d+n)^{-1}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$, gives,
with probability at least $1-n^{-\beta}-2\exp(-c_{0}n)$:

$\displaystyle\left\|\Theta^{-1}-\left(\mathrm{I}_{n}-\frac{1}{n}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\right)\right\|_{\mathrm{op}}$
$\displaystyle\leq\left\|\Theta^{-1}-\left(\mathrm{I}_{n}-\frac{1}{n+d}\mathbf{1}_{n}\mathbf{1}_{n}^{\top}\right)\right\|_{\mathrm{op}}+\frac{d}{n},$
$\displaystyle\leq\frac{\frac{C_{1}}{d}+C_{2}(\beta)\left(\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\right)}{1-\frac{C_{1}}{d}-C_{2}(\beta)\left(\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\right)}+\frac{d}{n},$
$\displaystyle\leq\frac{C^{\prime}_{1}}{d}+C^{\prime}_{2}\sqrt{\frac{n}{d^{2}}}+\frac{d}{n}.$

for large enough $d$ and small enough $n/d^{2}$ (depending only on $\beta$).
$\square$

###  2.3 Reducing to a net

We show some useful estimates in Section 3.5, summarized in the following
lemma.

######  Lemma 2.4 (Some high-probability events).

Let
$\omega_{1},\cdots,\omega_{n}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}[\mathcal{S}^{d-1}]$,
and $\Theta_{ij}\coloneqq\langle\omega_{i},\omega_{j}\rangle^{2}$. Denote
$U(a)_{i}\coloneqq\langle\omega_{i},a\rangle^{2}$ for $a\in\mathcal{S}^{d-1}$.
We let $(a_{j})_{j=1}^{N}$ be a $(1/2)$-net of $\mathcal{S}^{d-1}$. Let
$\beta\geq 1$. There exists $\alpha=\alpha(\beta)>0$ such that if $n\leq\alpha
d^{2}$, then we have:

  * $(i)$

$\mathbb{P}[E_{1}]\geq 1-2\exp(-C_{1}d)$, with
$E_{1}\coloneqq\\{\max_{j\in[N]}\|U(a_{j})\|_{2}\leq C_{2}\\}$ (for a
sufficiently large $C_{2}$).

  * $(ii)$

$\mathbb{P}[E_{2}]\geq 1-2n^{-\beta}$, with
$E_{2}\coloneqq\\{\|\Theta^{-1}\|_{\mathrm{op}}\leq 2\\}$.

In the following, we fix $(a_{j})_{j=1}^{N}$ a $(1/2)$-net of
$\mathcal{S}^{d-1}$, such that $N\leq 5^{d}$ [Ver18]. Let $\tilde{q}\coloneqq
D^{-1}\mathbf{1}_{n}-\mathbf{1}_{n}$. For any matrix $M\in\mathbb{R}^{d\times
d}$, we have [Ver18]:

$\displaystyle\max_{a\in\mathcal{S}^{d-1}}a^{\top}Ma\leq
2\max_{a\in\mathcal{N}}a^{\top}Ma.$

Therefore:

$\displaystyle\mathbb{P}[\min_{a\in\mathcal{S}^{d-1}}\sum_{i=1}^{n}(\Theta^{-1}\tilde{q})_{i}\langle
a,\omega_{i}\rangle^{2}\leq-1]\leq\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}\tilde{q})_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{2}\Bigg{]}.$ (7)

Defining
$g_{\Theta}(a)\coloneqq\sum_{i=1}^{n}\tilde{q}_{i}[\Theta^{-1}U(a)]_{i}$, our
goal reduced to show that $\max_{j\in[N]}|g_{\Theta}(a_{j})|\leq 1/2$ with
probability at least $1-Cn^{-\beta}$, for $n/d^{2}$ small enough. First, we
show that we can truncate and center the variables $\tilde{q}_{i}$:

######  Lemma 2.5 (Truncating and centering $\tilde{q}$).

Let $A_{i}\coloneqq\\{|\tilde{q}_{i}|\leq 1\\}$ and
$A\coloneqq\cap_{i=1}^{n}A_{i}$. We denote $r_{i}\coloneqq\tilde{q}_{i}|A$,
and $y_{i}\coloneqq r_{i}-\mathbb{E}r_{i}$. Then $\\{y_{i}\\}_{i=1}^{n}$ are
i.i.d. centered $K/\sqrt{d}$-sub-Gaussian random variables, for some universal
$K>0$. Moreover, for any $\beta\geq 1$ there exists $\alpha=\alpha(\beta)>0$
such that if $n\leq\alpha d^{2}$, then:

$\displaystyle\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}\tilde{q})_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{2}\Bigg{]}\leq\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}y)_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{4}\Bigg{]}+Cn^{-\beta}.$

This lemma is proven in Section 3.6.

###  2.4 Controlling points on the net

In what follows, we replace the variables $\tilde{q}_{i}$ by $y_{i}$, thanks
to Lemma 2.5 (assuming $n\leq\alpha d^{2}$ for $\alpha=\alpha(\beta)$ small
enough). We define, for $a\in\mathcal{S}^{d-1}$:

$\displaystyle
f_{\Theta}(a)\coloneqq\sum_{i=1}^{n}y_{i}[\Theta^{-1}U(a)]_{i}=\sum_{i=1}^{n}[\Theta^{-1}y]_{i}U(a)_{i},$
(8)

with $U(a)\coloneqq(\langle\omega_{i},a\rangle^{2})_{i=1}^{n}$. We prove in
Section 3.7 the following elementary lemma:

######  Lemma 2.6.

Let $\\{y_{i}\\}_{i=1}^{n}$ be i.i.d. centered sub-Gaussian random variables,
with $\|y_{1}\|_{\psi_{2}}\leq K/\sqrt{d}$, and $M\in\mathcal{S}_{n}$. Then:

$\displaystyle\mathbb{P}\left[\|My\|_{\infty}\geq
C\|M\|_{\mathrm{op}}d^{-3/8}\right]\leq 2n\exp\\{-d^{1/4}\\}.$

We let

$\displaystyle E_{3}\coloneqq\left\\{\|\Theta^{-1}y\|_{\infty}\leq
C\|\Theta^{-1}\|_{\mathrm{op}}d^{-3/8}\right\\},$

and $E\coloneqq\cap_{k=1}^{3}E_{k}$. We have from Lemmas 2.4 and 2.6 that
(recall that $y$ is independent of $\Theta$) there is $\alpha=\alpha(\beta)>0$
such that for $n\leq\alpha d^{2}$:

$\displaystyle\mathbb{P}[E]\geq 1-Cn^{-\beta}.$ (9)

Let us fix $a\in\mathcal{S}^{d-1}$. For $\eta\in(0,1)$ we define
$S(\eta)\coloneqq\\{i\in[n]\,:\,|\langle\omega_{i},a\rangle|>\eta\\}$. Since
$\omega_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}[\mathcal{S}^{d-1}]$,
$|\langle\omega_{i},a\rangle|$ are i.i.d. sub-Gaussian random variables, with
sub-Gaussian norm $C/\sqrt{d}$ [Ver18]. $|S(\eta)|$ is thus a binomial random
variable, with parameters $n$ and $p\leq 2\exp\\{-Cd\eta^{2}\\}$. By Theorem 1
of [KM10], $|S(\eta)|$ is stochastically dominated by a Poisson random
variable with parameter $-n\log(1-p)$. Assuming that $d\eta^{2}\to\infty$, we
have for $d$ large enough444Since $\log(1-x)\geq-2x$ for $0\leq x\leq 1/2$.,

$\displaystyle-n\log(1-p)\leq 2np\leq 4n\exp\\{-Cd\eta^{2}\\}.$

Letting $\lambda\coloneqq 4n\exp\\{-Cd\eta^{2}\\}$ and
$X\sim\mathrm{Pois}(\lambda)$, $|S(\eta)|$ is thus stochastically dominated by
$X$. We reach that for all $x>\lambda$ (see e.g. Theorem 5.4 of [MU17] for the
second inequality):

$\displaystyle\mathbb{P}[|S(\eta)|\geq x]\leq\mathbb{P}[X\geq
x]\leq\Bigg{(}\frac{e\lambda}{x}\Bigg{)}^{x}e^{-\lambda}.$ (10)

We get from eq. (10) that

$\displaystyle\mathbb{P}[|S(\eta)|\geq
d^{1/4}]\leq\exp\Big{\\{}d^{1/4}\log(4ne)-Cd^{5/4}\eta^{2}-\frac{d^{1/4}\log
d}{4}\Big{\\}}\leq\exp\Big{\\{}d^{1/4}\log n-Cd^{5/4}\eta^{2}\Big{\\}}.$ (11)

We decompose $f_{\Theta}(a)$ in two parts, which we control separately:

$\displaystyle f_{\Theta}(a)=\underbrace{\sum_{i\in
S(\eta)}[\Theta^{-1}y]_{i}U(a)_{i}}_{\eqqcolon
f_{1}(\eta,a)}+\underbrace{\sum_{i\notin
S(\eta)}[\Theta^{-1}y]_{i}U(a)_{i}}_{\eqqcolon f_{2}(\eta,a)}.$ (12)

First, we have that under the event $E$ of eq. (9), and by the Cauchy-Schwarz
inequality:

$\displaystyle|f_{1}(\eta,a)|$ $\displaystyle\leq Cd^{-3/8}\sum_{i\in
S(\eta)}\langle\omega_{i},a\rangle^{2}\leq Cd^{-3/8}|S(\eta)|.$

Let us pick $\eta=d^{-1/8}t$, for some $t\geq 1$ (so that
$d\eta^{2}\to\infty$). Using eq. (11) in the previous inequality, as well as
the law of total probability (and $\mathbb{P}[E]\geq 1/2$), we reach:

$\displaystyle\mathbb{P}\left[|f_{1}(d^{-1/8}t,a)|\geq
C_{1}d^{-1/8}\middle|E\right]$ $\displaystyle\leq 2\exp\\{d^{1/4}\log
n-C_{2}dt^{2}\\}.$ (13)

We now control $f_{2}(\eta,a)$. For a random variable
$X(\\{y_{i},\omega_{i}\\})$, we denote $\|X\|_{\psi_{2},y}$ the sub-Gaussian
norm of the random variable with respect to the randomness of $\\{y_{i}\\}$
only (i.e. conditioned on the value of $\\{\omega_{i}\\}$). Since $y_{i}$ are
independent of $\\{\omega_{i}\\}$ (and thus of the choice of the set $S(\eta)$
and of $\Theta$), we get by Hoeffding’s inequality (recall that $y_{i}$ are
i.i.d. $K/\sqrt{d}$-sub-Gaussian), that for all $\\{\omega_{i}\\}$:

$\displaystyle\|f_{2}(\eta,a)\|_{\psi_{2},y}^{2}$
$\displaystyle\leq\frac{C}{d}\|\Theta^{-1}\widetilde{U}(a)\|_{2}^{2}.$ (14)

Here we denoted
$\widetilde{U}(a)_{i}\coloneqq\langle\omega_{i},a\rangle^{2}\mathds{1}\\{|\langle\omega_{i},a\rangle|\leq\eta\\}$.
Therefore:

$\displaystyle\|f_{2}(\eta,a)\|_{\psi_{2},y}^{2}$
$\displaystyle\leq\frac{C\|\Theta^{-1}\|_{\mathrm{op}}^{2}}{d}\sum_{i\notin
S(\eta)}\langle\omega_{i},a\rangle^{4}.$ (15)

We can then prove (see Section 3.8):

######  Lemma 2.7.

For all $q\in[1/2,1]$, there is a constant $C=C(q)>0$ such that for all $v\geq
0$, and all $\eta\in(0,1)$:

$\displaystyle\mathbb{P}\left[\sum_{i\notin
S(\eta)}\langle\omega_{i},a\rangle^{4}\geq\frac{n}{d^{2}}(3+v)\right]\leq
2\exp\left\\{-C\min\left(\frac{nd^{2/q}\eta^{4/q}}{d^{4}\eta^{8}}v^{2},n^{q}d^{1-2q}\eta^{2-4q}v^{q}\right)\right\\}.$

###  2.5 Ending the proof

We detail now how the combination of eq. (13) and Lemma 2.7 allows to complete
the proof. By Lemma 2.5, our task reduced to show that for a $1/2$-net
$(a_{j})_{j=1}^{N}$ of $\mathcal{S}^{d-1}$, we have with probability at least
$1-Cn^{-\beta}$, and assuming $n\leq\alpha d^{2}$ for $\alpha=\alpha(\beta)$
small enough:

$\displaystyle\max_{j\in[N]}|f_{\Theta}(a_{j})|\leq 1/4.$ (16)

Recall the decomposition of eq. (12). We fix $\eta=d^{-1/8}t$, for $t\geq 1$
large enough (not depending on $n,d$) such that eq. (13) gives, for $n,d$
large enough:

$\displaystyle\mathbb{P}\left[|f_{1}(d^{-1/8}t,a)|\geq
Cd^{-1/8}\middle|E\right]$ $\displaystyle\leq 10^{-d}.$ (17)

By Lemma 2.7 and eq. (15) we have, chosing $v=1$ and $q=3/5$555This is an
arbitrary choice, the only requirement needed is actually that
$q\in(1/2,3/4)$., that for all $x>0$:

$\displaystyle\mathbb{P}\left[|f_{2}(d^{-1/8}t,a)|\geq
x\|\Theta^{-1}\|_{\mathrm{op}}\sqrt{\frac{n}{d^{2}}}\right]$
$\displaystyle\leq\mathbb{E}_{\omega}\left[\exp\left(-\frac{Cnx^{2}}{d\sum_{i\notin
S(\eta)}\langle\omega_{i},a\rangle^{4}}\right)\right],$
$\displaystyle\overset{\mathrm{(a)}}{\leq}2\exp\left\\{-C_{1}\min\left(\frac{n}{t^{4/3}\sqrt{d}},n^{3/5}d^{-3/20}t^{-2/5}\right)\right\\}+\exp(-C_{2}dx^{2}),$
$\displaystyle\overset{\mathrm{(b)}}{\leq}2\exp\left\\{-C_{1}n^{3/5}d^{-3/20}t^{-2/5}\right\\}+\exp(-C_{2}dx^{2}),$
$\displaystyle\overset{\mathrm{(c)}}{\leq}10^{-d}+\exp(-C_{2}dx^{2}).$

where we used Lemma 2.7 in $(\rm a)$ with $v=1$ and $q=3/5$ (and bounding
$e^{-z}\leq 1$), in $(\rm b)$ the fact that
$n/\sqrt{d}=\omega(n^{3/5}d^{-3/20})$ since $n=\omega(d)$, and finally in
$(\rm c)$ we used that $n=\omega(d^{23/12})$, so that we can bound the first
term by $10^{-d}$ for $n,d$ large enough. We fix $x>0$ large enough (not
depending on $n,d$) such that the second term also satisfies
$\exp(-C_{2}dx^{2})\leq 10^{-d}$. All in all, we get:

$\displaystyle\mathbb{P}\left[|f_{2}(d^{-1/8}t,a)|\geq
C\|\Theta^{-1}\|_{\mathrm{op}}\sqrt{\frac{n}{d^{2}}}\right]$
$\displaystyle\leq 2\times 10^{-d}.$

And thus:

$\displaystyle\mathbb{P}\left[|f_{2}(d^{-1/8}t,a)|\geq
C\sqrt{\frac{n}{d^{2}}}\middle|E\right]$
$\displaystyle\leq\frac{\mathbb{P}\left[|f_{2}(d^{-1/8}t,a)|\geq
C\|\Theta^{-1}\|_{\mathrm{op}}\sqrt{\frac{n}{d^{2}}}\right]}{\mathbb{P}[E]}\leq
3\times 10^{-d}.$ (18)

Notice that the event $E$ of eq. (9) is independent of the net. Thus, we have
for all $u>0$:

$\displaystyle\mathbb{P}\left[\max_{j\in[N]}|f_{\Theta}(a_{j})|\geq u\right]$
$\displaystyle\leq
Cn^{-\beta}+\mathbb{P}\left[\max_{j\in[N]}|f_{\Theta}(a_{j})|\geq
u\middle|E\right].$ (19)

Combining eqs. (17) and (18) with the union bound (recall $N\leq 5^{d}$) we
get:

$\displaystyle\mathbb{P}\left[\max_{j\in[N]}|f_{\Theta}(a_{j})|\geq
C_{1}\sqrt{\frac{n}{d^{2}}}+C_{2}d^{-1/8}\middle|E\right]\leq 4\cdot
5^{d}\cdot 10^{-d}\leq 4\cdot 2^{-d}.$ (20)

By combining eqs. (19) and eq. (20), taking $d$ large enough, and $n/d^{2}$
small enough, this ends the proof of eq. (16), and thus of Theorem 1.2.

## 3 Auxiliary proofs

###  3.1 Proof of Lemma 2.1

We use the matrix flattening function, for $M\in\mathcal{S}_{d}$:

$\displaystyle\operatorname*{vec}(M)$
$\displaystyle\coloneqq((\sqrt{2}M_{ab})_{1\leq a<b\leq
d},(M_{aa})_{a=1}^{d})\in\mathbb{R}^{d(d+1)/2},$ (21)
$\displaystyle=((2-\delta_{ab})^{1/2}M_{ab})_{a\leq b}.$

It is an isometry:
$\langle\operatorname*{vec}(M),\operatorname*{vec}(N)\rangle={\rm Tr}[MN]$.
Note that $\Theta$ is the Gram matrix of the i.i.d. vectors
$X_{i}\coloneqq\operatorname*{vec}(x_{i}x_{i}^{\top})\in\mathbb{R}^{p}$, with
$p\coloneqq d(d+1)/2$.

Centering – Note that $\|X_{i}\|_{2}=\|x_{i}\|_{2}^{2}=1$. Moreover, we
have666We identify the matrices and their flattened versions.
$\mathbb{E}[X_{i}]=\mathrm{I}_{d}/d$, and if $Y_{i}\coloneqq
X_{i}-\mathbb{E}[X_{i}]$, then $\langle Y_{i},Y_{j}\rangle=\langle
X_{i},X_{j}\rangle-1/d$. Therefore, we can write

$\displaystyle\Theta=H+\frac{1}{d}\mathbf{1}_{n}\mathbf{1}_{n}^{\top},$

with $H_{ij}\coloneqq\langle Y_{i},Y_{j}\rangle$ the Gram matrix of the
$(Y_{i})_{i=1}^{n}$. We also sometimes denote $H=Y^{\top}Y$, with $Y$ the
matrix whose columns are given by $Y_{1},\cdots,Y_{n}$. Note that
$\mathbb{E}[\Theta]=(1-1/d)\mathrm{I}_{n}+(1/d)\mathbf{1}_{n}\mathbf{1}_{n}^{\top}$.
Thus, to prove Lemma 2.1 it suffices to show that with the required
probability bound:

$\displaystyle\left\|H-\mathrm{I}_{n}\right\|_{\mathrm{op}}\leq\frac{C_{1}}{d}+C_{2}(\beta)\left(\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\right).$
(22)

Projecting – Note that $\langle
Y_{i},\operatorname*{vec}(\mathrm{I}_{d})\rangle=0$, so that
$Y_{i}\in\\{\operatorname*{vec}(\mathrm{I}_{d})\\}^{\perp}$. We denote $P$ the
orthogonal projector onto $\\{\operatorname*{vec}(\mathrm{I}_{d})\\}^{\perp}$,
i.e.

$\displaystyle P$
$\displaystyle\coloneqq\mathrm{I}_{p}-\frac{1}{d}\operatorname*{vec}(\mathrm{I}_{d})\operatorname*{vec}(\mathrm{I}_{d})^{\top}.$
(23)

We remark that $(PY_{i})_{i=1}^{n}$ are still i.i.d., centered, and we have
$\langle PY_{i},PY_{j}\rangle=\langle Y_{i},Y_{j}\rangle$.

Rescaling – Note that $\mathbb{E}[Y_{i}]=0$, and without loss of generality
(up to using the vectors $Y^{\prime}_{i}\coloneqq\varepsilon_{i}Y_{i}$ with
$\varepsilon_{i}\overset{\mathrm{i.i.d.}}{\sim}\mathrm{Unif}(\\{\pm 1\\})$,
for which the Gram matrix $H^{\prime}$ satisfies
$H^{\prime}=\mathrm{Diag}(\varepsilon)H\mathrm{Diag}(\varepsilon)$ and has
thus the same eigenvalues as $H$) we can assume the $Y_{i}$ to be symmetric.

Let us compute the covariance of $Y$. For $a\leq b$ and $c\leq d$, we have

$\displaystyle\mathbb{E}[Y_{ab}Y_{cd}]$
$\displaystyle=[(2-\delta_{ab})(2-\delta_{cd})]^{1/2}\Bigg{[}\mathbb{E}(x_{a}x_{b}x_{c}x_{d})-\frac{\delta_{ab}\delta_{cd}}{d^{2}}\Bigg{]},$
$\displaystyle\overset{\mathrm{(a)}}{=}\frac{[(2-\delta_{ab})(2-\delta_{cd})]^{1/2}}{d^{2}}\Bigg{[}\frac{d}{d+2}(\delta_{ab}\delta_{cd}+\delta_{ac}\delta_{bd}+\delta_{abcd})-\delta_{ab}\delta_{cd}\Bigg{]},$
$\displaystyle=\frac{1}{d^{2}}\left[\frac{d}{d+2}\left(\delta_{abcd}+[(2-\delta_{ab})(2-\delta_{cd})]^{1/2}\delta_{ac}\delta_{bd}\right)-\frac{2}{d+2}\delta_{ab}\delta_{cd}\right],$
$\displaystyle=\frac{2}{d^{2}}\left[\frac{d}{d+2}\delta_{ac}\delta_{bd}-\frac{1}{d+2}\delta_{ab}\delta_{cd}\right].$
(24)

In $(a)$ we used the marginals of uniformly sampled random vectors on
$\mathcal{S}^{d-1}$, which can easily be obtained e.g. by using hyperspherical
coordinates777 The two moments needed are
$d^{2}\mathbb{E}[x_{1}^{4}]=3d/(2+d)$ and
$d^{2}\mathbb{E}[x_{1}^{2}x_{2}^{2}]=d/(d+2)$. . In matrix notation, eq. (24)
can be rewritten as:

$\displaystyle\mathbb{E}[YY^{\top}]$
$\displaystyle=\frac{2}{d^{2}}\left[\frac{d}{d+2}\mathrm{I}_{p}-\frac{1}{d+2}\operatorname*{vec}(\mathrm{I}_{d})\operatorname*{vec}(\mathrm{I}_{d})^{\top}\right],$
$\displaystyle=\frac{2}{d(d+2)}P.$

Therefore, if we denote $V_{i}\coloneqq PY_{i}\in\mathbb{R}^{p-1}$ the
coordinates of $Y_{i}$ in $\\{\operatorname*{vec}(\mathrm{I}_{d})\\}^{\perp}$,
we have that $\langle V_{i},V_{j}\rangle=\langle Y_{i},Y_{j}\rangle$, and

$\displaystyle\mathbb{E}[VV^{\top}]=\frac{2}{d(d+2)}\mathrm{I}_{p-1}.$

Denote

$\displaystyle\Sigma$
$\displaystyle\coloneqq(p-1)\mathbb{E}[VV^{\top}]=\frac{2(p-1)}{d(d+2)}\mathrm{I}_{p-1}=\left(1-\frac{1}{d}\right)\mathrm{I}_{p-1}.$
(25)

In particular $\|\Sigma-\mathrm{I}_{p-1}\|_{\mathrm{op}}\leq(1/d)$. Letting
$Z\coloneqq\Sigma^{-1/2}V$, the vector $Z$ satisfies
$\mathbb{E}[ZZ^{\top}]=(p-1)^{-1}\mathrm{I}_{p-1}$, and the Gram matrix
$H_{Z}$ of $Z_{1},\cdots,Z_{n}$ satisfies
$H-H_{Z}=Z^{\top}(\Sigma-\mathrm{I}_{p-1})Z$, and thus for all
$w\in\mathbb{R}^{p-1}$:

$\displaystyle|w^{\top}H_{Z}w-w^{\top}Hw|$
$\displaystyle=|w^{\top}Z^{\top}(\Sigma-\mathrm{I}_{p-1})Zw|,$
$\displaystyle\leq(1/d)\|Zw\|_{2}^{2},$ $\displaystyle=(1/d)w^{\top}H_{Z}w.$

Therefore $\|H-H_{Z}\|_{\mathrm{op}}\leq(1/d)\|H_{Z}\|_{\mathrm{op}}$. By the
triangle inequality, this yields that

$\displaystyle\|H-\mathrm{I}_{n}\|_{\mathrm{op}}\leq\frac{1}{d}+\left(1+\frac{1}{d}\right)\|H_{Z}-\mathrm{I}_{n}\|_{\mathrm{op}}.$
(26)

Using eq. (22) and eq. (26), it is clear that we conclude to eq. (4), it is
enough to show that (with the required probability bound):

$\displaystyle\|H_{Z}-\mathrm{I}_{n}\|_{\mathrm{op}}\leq\frac{6}{d}+C(\beta)\Bigg{(}\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\Bigg{)}.$
(27)

Gram matrix estimation – We will use the results of [BM22]. We need to
introduce the definition of a well-behaved random vector:

######  Definition 3.1 (Well-behaved vector).

Let $q\geq 1$. A random vector $X\in\mathbb{R}^{q}$ is said to be well-behaved
for $n\geq 1$ with constants $L,R>0$, $\alpha\in(0,2]$, $\delta\in[0,1]$ and
$\gamma\in[0,1)$ if:

  * $(i)$

$X$ is symmetric and isotropic: $\mathbb{E}[XX^{\top}]=\mathrm{I}_{q}$.

  * $(ii)$

If one considers $n$ i.i.d. draws $X_{1},\cdots,X_{n}$, then with probability
at least $1-\gamma$:

$\displaystyle\max_{1\leq i\leq
n}\Bigg{|}\frac{\|X_{i}\|_{2}^{2}}{q}-1\Bigg{|}\leq\delta.$

  * $(iii)$

For all $2\leq k\leq R\log n$ and all $t\in\mathbb{R}^{q}$:

$\displaystyle\|\langle X,t\rangle\|_{L_{k}}\leq Lk^{1/\alpha}\|\langle
X,t\rangle\|_{L_{2}}=Lk^{1/\alpha}\|t\|_{2}.$

Condition $(iii)$ corresponds to some $\psi_{\alpha}$ behavior of the
projections, uniformly in $t$, and for some $\alpha\in(0,2]$, but only up to
moments $k=\mathcal{O}(\log n)$. We can now state an immediate corollary to
Theorem 1.5 of [BM22] (precisely the particular case corresponding to $T$
being the unit sphere):

######  Corollary 3.1 ([BM22]).

Let $n,q\geq 1$. Let $\beta\geq 1$. Assume that the random vector
$A\in\mathbb{R}^{q}$ is well-behaved with respect to $n$ according to
Definition 3.1, with constants $L,R=R(\beta),\alpha,\gamma,\delta$. Let
$M\in\mathbb{R}^{q\times n}$ be a matrix with i.i.d. columns $A_{1},\cdots
A_{q}$. Then, with probability at least $1-\gamma-2\exp(-c_{0}n)-n^{-\beta}$,
we have

$\displaystyle\Bigg{\|}\frac{1}{q}M^{\top}M-\mathrm{I}_{n}\Bigg{\|}_{\mathrm{op}}$
$\displaystyle\leq
2\delta+c(L,\alpha,\beta)\Bigg{(}\sqrt{\frac{n}{q}}+\frac{n}{q}\Bigg{)}.$

Corollary 3.1 is an application of Theorem 1.5 of [BM22], for the simplest
case in which $T=\mathcal{S}^{n-1}$, so that the Gaussian width is
$\ell_{\star}(T)\coloneqq\mathbb{E}\|g\|_{2}\simeq\sqrt{n}$ (for
$g\sim\mathcal{N}(0,\mathrm{I}_{n})$),
$d_{T}\coloneqq\sup_{t\in\mathcal{S}^{n-1}}\|t\|=1$, and
$k_{\star}(T)\coloneqq(\ell_{\star}(T)/d_{T})^{2}\simeq n$. More precisely, we
have $(1+\mathcal{O}(n^{-1}))n\leq n^{2}/(n+1)\leq k_{\star}(T)\leq n$. Note
as well that we added the factor $p^{-1}$ in front of the Gram matrix
$M^{\top}M$ (it is implicit in [BM22] because the columns of $M$ there are
$A_{i}/\sqrt{p}$).

An important remark – We emphasize a technical point, related to the final
probability bounds we obtain in Theorem 1.2. In what follows, we will apply
Corollary 3.1 with $R=\infty$, as the moment bound will be valid for all
orders. In this context, the analysis of [BM22] would naturally imply that
Corollary 3.1 holds with probability at least $1-\gamma-2\exp(-c_{0}n)$, and
with a constant $c(L,\alpha)$ not depending on $\beta$. In turn, a more
careful analysis would reveal that the probability bound of Theorem 1.2 can be
made exponentially small in $d$. However, as proving this would require a
possibly lengthy technical analysis of the arguments of [BM22], for reasons of
clarity we chose to restrict to the most direct application of Theorem 1.5 of
[BM22], which gives then a sub-optimal polynomial probability upper bound.

In order to deduce eq. (27) from Corollary 3.1, with the dimension $q=p-1$
(recall $p=d(d+1)/2$), we need to verify that the distribution of the columns
$Z_{i}$ is well-behaved for some $\alpha,L,R,\delta,\gamma$. We let
$A_{i}\coloneqq\sqrt{q}Z_{i}$, and we check that it satisfies Definition 3.1.

Condition ($i$) –  Because of the random sign that we can add wlog, we have
seen that the distribution of $A$ is symmetric. Moreover, by our analysis
above, $\mathbb{E}[AA^{\top}]=q\mathbb{E}[ZZ^{\top}]=\mathrm{I}_{q}$, so that
$A$ is isotropic.

Condition ($ii$) –  Notice that for all $i$,
$\|Y_{i}\|_{2}^{2}=\|V_{i}\|_{2}^{2}=1-1/d$. Thus, with the notations from
above:

$\displaystyle\Bigg{|}\frac{1}{q}\|A\|_{2}^{2}-1\Bigg{|}$
$\displaystyle=\Bigg{|}V^{\top}(\Sigma^{-1}-\mathrm{I}_{q})V+\frac{1}{d}\Bigg{|},$
$\displaystyle\leq\|V\|_{2}^{2}\|\Sigma^{-1}-\mathrm{I}_{q}\|_{\mathrm{op}}+\frac{1}{d},$
$\displaystyle\overset{\mathrm{(a)}}{\leq}\frac{3}{d}.$

In $(\rm a)$ we used that

$\displaystyle\|\Sigma-\mathrm{I}_{q}\|_{\mathrm{op}}\leq\frac{1}{d}\Rightarrow\|\Sigma^{-1}-\mathrm{I}_{q}\|_{\mathrm{op}}\leq\frac{\frac{1}{d}}{1-\frac{1}{d}}\leq\frac{2}{d}.$

Thus $A$ satisfies the condition $(ii)$ with $\gamma=0$ and $\delta=3/d$
(since the bound is deterministic, there is no need to consider $n$ i.i.d.
samples).

Condition ($iii$) –  We are going to see that it actually holds for all $k\geq
2$ with $\alpha=1$, i.e. the random vector $A$ is uniformly sub-exponential.
Let $t\in\mathbb{R}^{q}$. Then888Again, since
$\|\Sigma-\mathrm{I}_{q}\|_{\mathrm{op}}\leq
1/d\Rightarrow\|\Sigma^{-1/2}-\mathrm{I}_{q}\|_{\mathrm{op}}\leq 2/d$.:

$\displaystyle|\langle A,t\rangle-\sqrt{q}\langle V,t\rangle|$
$\displaystyle=|\sqrt{q}V^{\top}(\Sigma^{-1/2}-\mathrm{I}_{q})t|,$
$\displaystyle\leq\sqrt{q}\|V\|_{2}\times\frac{2}{d}\times\|t\|_{2},$
$\displaystyle\overset{\mathrm{(a)}}{\leq}C\|t\|_{2},$

using in $(\rm a)$ that $q+1=d(d+1)/2$ and that
$\|V\|_{2}^{2}=\|Y\|_{2}^{2}={\rm
Tr}[(xx^{\top}-\mathrm{I}_{d}/d)^{2}]=1-1/d\leq 1$. We have then for all
$k\geq 2$:

$\displaystyle\|\langle A,t\rangle\|_{k}$
$\displaystyle\overset{\mathrm{(a)}}{\leq}2\Bigg{[}q^{k/2}\|\langle
V,t\rangle\|_{k}^{k}+C^{k}\|t\|_{2}^{k}\Bigg{]}^{1/k},$
$\displaystyle\overset{\mathrm{(b)}}{\leq}2\Bigg{[}\sqrt{q}\|\langle
V,t\rangle\|_{k}+C\|t\|_{2}\Bigg{]},$

using in $(\rm a)$ that $(x+y)^{k}\leq 2^{k-1}(x^{k}+y^{k})$ for $x,y>0$, and
in $(b)$ Minkowski’s inequality $(x+y)^{1/k}\leq(x^{1/k}+y^{1/k})$. Therefore,
it is enough to check that for all $k\geq 2$:

$\displaystyle\|\langle V,t\rangle\|_{k}\leq\frac{L}{d}k^{1/\alpha}\|t\|_{2},$
(28)

for some $\alpha\in(0,2]$. We will use the Hanson-Wright inequality for random
vectors on the sphere:

######  Lemma 3.2 (Hanson-Wright).

Let $d\geq 1$ and $x\sim\mathrm{Unif}(\mathcal{S}^{d-1})$. For any
$M\in\mathcal{S}_{d}$ and any $u>0$:

$\displaystyle\mathbb{P}\Big{[}\Big{|}dx^{\top}Mx-{\rm Tr}[M]\Big{|}\geq
u\Big{]}\leq
2\exp\Bigg{\\{}-C\min\Bigg{(}\frac{u^{2}}{\|M\|_{F}^{2}},\frac{u}{\|M\|_{\mathrm{op}}}\Bigg{)}\Bigg{\\}}.$
(29)

Remark – We prove Lemma 3.2 as a consequence of a general Hanson-Wright
inequality for random vectors satisfying a convex Lipschitz concentration
property [Ada15], easily satisfied by the Haar measure on $\mathcal{S}^{d-1}$.
We give details in Section 3.2.

Recall that $V=PY\in\mathbb{R}^{q}$, with $P$ the orthogonal projector onto
$\operatorname*{vec}(\mathrm{I}_{d})^{\perp}$, and that $t\in\mathbb{R}^{q}$.
If we identify $t$ with the corresponding element of $\mathbb{R}^{p}$ (or the
corresponding $d\times d$ symmetric matrix), then ${\rm Tr}[t]=0$, and
$\langle V,t\rangle=\langle Y,t\rangle=x^{\top}tx-{\rm Tr}[t]/d=x^{\top}tx$
for $x\sim\mathrm{Unif}(\mathcal{S}^{d-1})$. Using Lemma 3.2 with $M=t$ gives:

$\displaystyle\mathbb{P}\Big{[}d|\langle V,t\rangle|\geq u\Big{]}\leq
2\exp\Bigg{\\{}-C\min\Bigg{(}\frac{u^{2}}{\|t\|_{2}^{2}},\frac{u}{\|t\|_{\mathrm{op}}}\Bigg{)}\Bigg{\\}}.$

It is now classical to deduce the moments from the tails:

$\displaystyle d^{k}\|\langle V,t\rangle\|_{k}^{k}$
$\displaystyle=\int_{0}^{\infty}ku^{k-1}\mathbb{P}[d|\langle V,t\rangle|\geq
u]\mathrm{d}u,$ $\displaystyle\leq
2k\int_{0}^{\infty}u^{k-1}\exp\Bigg{\\{}-C\min\Bigg{(}\frac{u^{2}}{\|t\|_{2}^{2}},\frac{u}{\|t\|_{\mathrm{op}}}\Bigg{)}\Bigg{\\}}\mathrm{d}u,$
$\displaystyle\leq
2k\int_{0}^{\|t\|_{2}^{2}/\|t\|_{\mathrm{op}}}u^{k-1}\exp\\{-Cu^{2}/\|t\|_{2}^{2}\\}\mathrm{d}u+2k\int_{\|t\|_{2}^{2}/\|t\|_{\mathrm{op}}}^{\infty}u^{k-1}\exp\\{-Cu/\|t\|_{\mathrm{op}}\\}\mathrm{d}u,$
$\displaystyle\leq
2k\int_{0}^{\infty}u^{k-1}\exp\\{-Cu^{2}/\|t\|_{2}^{2}\\}\mathrm{d}u+2k\int_{0}^{\infty}u^{k-1}\exp\\{-Cu/\|t\|_{\mathrm{op}}\\}\mathrm{d}u,$
$\displaystyle\leq
kC^{-k/2}\|t\|_{2}^{k}\Gamma\Big{[}\frac{k}{2}\Big{]}+2k\Big{(}\frac{\|t\|_{\mathrm{op}}}{C}\Big{)}^{k}\Gamma(k),$
$\displaystyle\leq
k\|t\|_{2}^{k}\Bigg{\\{}C^{-k/2}\Gamma\Big{[}\frac{k}{2}\Big{]}+2C^{-k}\Gamma(k)\Bigg{\\}},$

since $\|t\|_{\mathrm{op}}\leq\|t\|_{2}=\|t\|_{F}$. This is simply the sum of
the sub-Gaussian and sub-exponential part of the tail given by Hanson-Wright’s
inequality. Thus we have

$\displaystyle d\|\langle V,t\rangle\|_{k}$ $\displaystyle\leq Lk\|t\|_{2},$

which is exactly eq. (28) for $\alpha=1$.

Applying Corollary 3.1 to $A=\sqrt{q}Z$ with
$L,R=\infty,\alpha=1,\gamma=0,\delta=3/d$, we reach that for all $\beta\geq
1$:

$\displaystyle\|Z^{\top}Z-\mathrm{I}_{n}\|_{\mathrm{op}}\leq\frac{6}{d}+C_{1}(\beta)\Bigg{(}\sqrt{\frac{n}{d^{2}}}+\frac{n}{d^{2}}\Bigg{)},$
(30)

with probability at least $1-n^{-\beta}-2\exp(-c_{0}n)$. This implies eq. (27)
and concludes the proof. ∎

###  3.2 Proof of Lemma 3.2

We use a generalization of Hanson-Wright’s inequality (usually stated for
i.i.d. sub-Gaussian vectors) which is due to [Ada15].

######  Definition 3.2 (Convex concentration property).

Let $n\geq 1$ and $X$ be a random vector in $\mathbb{R}^{n}$. We say that $X$
has the convex concentration property with constant $K$ if, for all
$\varphi:\mathbb{R}^{n}\to\mathbb{R}$ convex and $1$-Lipschitz, we have
$\mathbb{E}|\varphi(X)|<\infty$, and for every $t>0$:

$\displaystyle\mathbb{P}[|\varphi(X)-\mathbb{E}[\varphi(X)]|\geq t]\leq
2\exp(-t^{2}/K^{2}).$ (31)

Note that if $X=\sqrt{d}x$, with $x\sim\mathrm{Unif}[\mathcal{S}^{d-1}]$, then
$X$ satisfies Definition 3.2 for some absolute constant $K>0$ (the function
$\varphi$ does not even need to be convex), it is one of the most classical
results of concentration of measure, cf. e.g. Theorem 5.1.4 of [Ver18]. The
main result of [Ada15] is the following:

######  Proposition 3.3 (Hanson-Wright [Ada15]).

Let $n\geq 1$ and $X$ be a zero-mean vector in $\mathbb{R}^{n}$ that has the
convex concentration property with constant $K$. Then for all symmetric
$M\in\mathbb{R}^{n\times n}$ and $t>0$:

$\displaystyle\mathbb{P}[|X^{\top}MX-\mathbb{E}(X^{\top}MX)|\geq t]\leq
2\exp\Bigg{(}-C\min\Bigg{(}\frac{t^{2}}{2K^{4}\|M\|_{F}^{2}},\frac{t}{K^{2}\|M\|_{\mathrm{op}}}\Bigg{)}\Bigg{)}.$
(32)

Applying Proposition 3.3 to the vector $X$ described above yields Lemma 3.2.

###  3.3 Tail bounds for $\chi^{2}$ random variables

The following is a useful tail bound on $\chi_{d}^{2}$ random variables, from
[LM00].

######  Lemma 3.4 (Tail bounds for $\chi_{d}^{2}$).

Let $d\geq 1$, and
$x_{1},\cdots,x_{d}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,1)$. Let
$z\coloneqq(1/d)\sum_{i=1}^{d}x_{i}^{2}$. Then for all $u\geq 0$:

$\displaystyle\begin{dcases}\mathbb{P}\Bigg{[}z-1\geq
2\sqrt{\frac{u}{d}}+2\frac{u}{d}\Bigg{]}&\leq\exp(-u),\\\
\mathbb{P}\Bigg{[}z-1\leq-2\sqrt{\frac{u}{d}}\Bigg{]}&\leq\exp(-u).\end{dcases}$

######  Corollary 3.5 (Tail bounds for $\tilde{q}$).

Let $d\geq 1$, and
$x_{1},\cdots,x_{d}\overset{\mathrm{i.i.d.}}{\sim}\mathcal{N}(0,1)$. Let
$z\coloneqq(1/d)\sum_{i=1}^{d}x_{i}^{2}$, and we denote $\tilde{q}\coloneqq
1/z-1$. Notice that $\tilde{q}\geq-1$. Then, for all $t\in(0,1)$:

$\displaystyle\mathbb{P}[|\tilde{q}|\geq t]$ $\displaystyle\leq
2\exp\Bigg{(}-\frac{dt^{2}}{16}\Bigg{)}.$

Proof of Corollary 3.5 – We start with the upper tail $\tilde{q}\geq t$.
Notice that $\tilde{q}\geq t\Leftrightarrow z\leq(1+t)^{-1}$. Using Lemma 3.4
with $4u=d[t/(1+t)]^{2}$, we have (using that $t<1$):

$\displaystyle\mathbb{P}[\tilde{q}\geq
t]\leq\exp\Bigg{\\{}-\frac{dt^{2}}{4(1+t)^{2}}\Bigg{\\}}\leq\exp\Bigg{\\{}-\frac{dt^{2}}{16}\Bigg{\\}}.$

Similarly, for the lower tail, $\tilde{q}\leq-t\Leftrightarrow
z\geq(1-t)^{-1}$. Using Lemma 3.4 with $2u=d[1/(1-t)-\sqrt{(1+t)/(1-t)}]$, we
have (again using that $t\in(0,1)$):

$\displaystyle\mathbb{P}[\tilde{q}\leq-t]\leq\exp\Bigg{\\{}-\frac{d}{2}\Bigg{[}\frac{1}{1-t}-\sqrt{\frac{1+t}{1-t}}\Bigg{]}\Bigg{\\}}\leq\exp\Bigg{\\{}-\frac{dt^{2}}{4}\Bigg{\\}}.$

This ends the proof. $\square$

###  3.4 Proof of Lemma 2.3

Note that
$\lambda_{\mathrm{min}}(A)\geq\lambda_{\mathrm{min}}(B)-\varepsilon$, so that
$A\succ 0$ and
$\|A^{-1}\|_{\mathrm{op}}\leq\|B^{-1}\|_{\mathrm{op}}/(1-\varepsilon\|B^{-1}\|_{\mathrm{op}})$.
We can use the standard estimate:

$\displaystyle\|A^{-1}-B^{-1}\|_{\mathrm{op}}=\|B^{-1}(B-A)A^{-1}\|_{\mathrm{op}}\leq\|B^{-1}\|_{\mathrm{op}}\|A-B\|_{\mathrm{op}}\|A^{-1}\|_{\mathrm{op}}.$

Using the remark above and the fact that
$\|A-B\|_{\mathrm{op}}\leq\varepsilon$ completes the proof. $\square$

###  3.5 Proof of Lemma 2.4

The probability bound for the event $E_{2}$ is the conclusion of Corollary
2.2, so we focus on the bound for $E_{1}$. To control $\|U(a)\|_{2}$, we make
use of the following tail bound [Tal94, HMSO97, ALPTJ11].

######  Lemma 3.6 (Tail of sum of i.i.d. sub-Weibull random variables
[ALPTJ11]).

Let $q\in[1/2,1]$, and $W_{1},\cdots,W_{n}$ be i.i.d. centered random
variables satisfying $\mathbb{P}[|W_{1}|\geq t]\leq C_{1}e^{-C_{2}t^{q}}$.
Then for all $t>0$:

$\displaystyle\mathbb{P}\Big{[}\Big{|}\frac{1}{n}\sum_{\mu=1}^{n}W_{\mu}\Big{|}\geq
t\Big{]}$ $\displaystyle\leq
2\exp\Big{\\{}-C(q)\min(nt^{2},(nt)^{q})\Big{\\}}.$

Lemma 3.6 is a generalization of Bernstein’s inequality for $\psi_{q}$ tails,
with $q\in[1/2,1]$. This lemma is stated in [ALPTJ11], see Lemma 3.7 and eq.
(3.7) there, and is a classical consequence of the same result for symmetric
Weibull random variables [HMSO97].

We fix $a\in\mathcal{S}^{d-1}$. Note that:

$\displaystyle\|U(a)\|_{2}^{2}=\sum_{i=1}^{n}\langle\omega_{i},a\rangle^{4}.$

Since $\langle\omega_{i},a\rangle\overset{\rm d}{=}(\omega_{i})_{1}$ by
rotation invariance of the Haar measure on $\mathcal{S}^{d-1}$, it is easy to
check that $\mathbb{E}[\langle\omega_{i},a\rangle^{4}]=(3/d^{2})\cdot
d/(2+d)\leq 3/d^{2}$. Moreover, we have for all $t\geq 0$ [Ver18]:

$\displaystyle\mathbb{P}[\langle\omega_{i},a\rangle^{4}\geq t]\leq
2\exp\\{-Cd\sqrt{t}\\}.$

Therefore, applying Lemma 3.6 and using the union bound (recall $N\leq
5^{d}$), we get:

$\displaystyle\mathbb{P}\left[\sup_{j\in[N]}\|U(a_{j})\|_{2}^{2}\geq\frac{3n}{d^{2}}+t\right]\leq
2\exp\left\\{d\log
5-C\min\left(\frac{d^{4}t^{2}}{n},d\sqrt{t}\right)\right\\}.$

Taking e.g. $t=(2\log 5/C)^{2}$, and since $d^{4}/n=\omega(d)$, we reach the
conclusion.

###  3.6 Proof of Lemma 2.5

Note that $\tilde{q}_{i}=1/d_{i}-1\overset{\rm d}{=}d/\chi_{d}^{2}-1$. We let
$r_{i}\coloneqq\tilde{q}_{i}|A_{i}$. The $A_{i}$ are independent, and by
Corollary 3.5, $\mathbb{P}[A_{i}]\geq 1-2\exp(-d/16)$. By the law of total
expectation and the union bound, we thus have:

$\displaystyle\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}\tilde{q})_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{2}\Bigg{]}\leq\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}r)_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{2}\Bigg{]}+2ne^{-d/16}.$ (33)

Since $\tilde{q}_{i}\geq-1$, for all $x\in\mathbb{R}$: $\mathbb{P}[r_{i}\leq
x]=\mathbb{P}[\tilde{q}_{i}\leq x\wedge 1]/\mathbb{P}[\tilde{q}_{i}\leq 1]$,
and thus for all $x\in(0,1)$, by Corollary 3.5:

$\displaystyle\begin{dcases}\mathbb{P}[r_{i}\geq
x]&\leq\mathbb{P}[\tilde{q}_{i}\geq x]\leq 2e^{-dx^{2}/16},\\\
\mathbb{P}[r_{i}\leq-x]&\leq\frac{\mathbb{P}[\tilde{q}_{i}\leq-x]}{1-2e^{-d/16}}\leq
4e^{-dx^{2}/16}.\end{dcases}$

Moreover, $\mathbb{P}[|r_{i}|>1]=0$. $r_{i}$ are thus i.i.d. sub-Gaussian
random variables, with sub-Gaussian norm smaller than $K/\sqrt{d}$. Moreover,
by the law of total expectation:

$\displaystyle\mathbb{E}[\tilde{q}_{i}]=\mathbb{E}[r_{i}]\mathbb{P}(A_{i})+\mathbb{E}[\tilde{q}_{i}\mathds{1}\\{|\tilde{q}_{i}|\geq
1\\}],$

so that since $\mathbb{P}[A_{i}]\geq 1-2e^{-d/16}$, and using Cauchy-Schwarz:

$\displaystyle|\mathbb{E}[\tilde{q}_{i}]-\mathbb{E}[r_{i}]|$
$\displaystyle\leq|\mathbb{E}[r_{i}]|\cdot
2e^{-d/16}+\sqrt{2}\mathbb{E}[\tilde{q}_{i}^{2}]^{1/2}e^{-d/32},$
$\displaystyle\overset{\mathrm{(a)}}{\leq}2e^{-d/16}+Ce^{-d/32}/\sqrt{d},$

using in $(\rm a)$ that $|r_{i}|\leq 1$ and that
$\mathbb{E}[\tilde{q}_{i}^{2}]^{1/2}\leq C/\sqrt{d}$. Since
$\mathbb{E}\tilde{q}_{i}=2/(d-2)$, we get

$\displaystyle|\mathbb{E}r_{i}|\leq\frac{3}{d}.$

Recall that $y_{i}=r_{i}-\mathbb{E}r_{i}$. Therefore we have, for all
$a\in\mathcal{S}^{d-1}$:

$\displaystyle\left|\sum_{i=1}^{n}[\Theta^{-1}(y-r)]_{i}\langle\omega_{i},a\rangle^{2}\right|$
$\displaystyle\leq\|\mathbb{E}r\|_{2}\|\Theta^{-1}\|_{\mathrm{op}}\|U(a)\|_{2},$
$\displaystyle\leq\frac{3\sqrt{n}}{d}\|\Theta^{-1}\|_{\mathrm{op}}\|U(a)\|_{2}.$

Using Lemma 2.4, it is clear that if $n\leq\alpha d^{2}$ for
$\alpha=\alpha(\beta)>0$ small enough, we have

$\displaystyle\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}r)_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{2}\Bigg{]}\leq\mathbb{P}\Bigg{[}\max_{j\in[N]}\Bigg{|}\sum_{i=1}^{n}(\Theta^{-1}y)_{i}\langle
a_{j},\omega_{i}\rangle^{2}\Bigg{|}\geq\frac{1}{4}\Bigg{]}+Cn^{-\beta}.$ (34)

Combining eqs. (33) and eq. (34) gives the sought result. Finally,
$(y_{i})_{i=1}^{n}$ are i.i.d. centered sub-Gaussian random variables with
sub-Gaussian norm $K/\sqrt{d}$. ∎

###  3.7 Proof of Lemma 2.6

Let $M\in\mathcal{S}_{n}$, and denote $z\coloneqq My$. By Hoeffding’s
inequality, for all $i\in[n]$:

$\displaystyle\mathbb{P}[|z_{i}|\geq t]\leq
2\exp\left\\{-\frac{Cdt^{2}}{\|M_{i}\|_{2}^{2}}\right\\}\leq
2\exp\left\\{-\frac{Cdt^{2}}{\|M\|_{\mathrm{op}}^{2}}\right\\},$

with $(M_{i})_{i=1}^{n}$ the rows of $M$, since
$\|M\|_{\mathrm{op}}\geq\max_{i\in[n]}\|M_{i}\|_{2}$. Thus by the union bound:

$\displaystyle\mathbb{P}[\|z\|_{\infty}\geq t]\leq
2n\exp\left\\{-\frac{Cdt^{2}}{\|M\|_{\mathrm{op}}^{2}}\right\\}.$

Letting $t=C\|M\|_{\mathrm{op}}d^{-3/8}$ ends the proof. ∎

###  3.8 Proof of Lemma 2.7

Let $q\in[1/2,1]$. Recall that

$\displaystyle\sum_{i\notin S(\eta)}\langle\omega_{i},a\rangle^{4}$
$\displaystyle=\sum_{i=1}^{n}\langle\omega_{i},a\rangle^{4}\mathds{1}\\{|\langle\omega_{i},a\rangle|\leq\eta\\}$

We let
$z_{i}\coloneqq\langle\omega_{i},a\rangle^{4}\mathds{1}\\{|\langle\omega_{i},a\rangle|\leq\eta\\}$.
They are i.i.d. random variables, with
$\mathbb{E}[z_{i}]\leq\mathbb{E}[\langle\omega_{i},a\rangle^{4}]\leq 3/d^{2}$,
and for all $t\geq 0$:

$\displaystyle\mathbb{P}[z_{i}\geq t]$
$\displaystyle\leq\min\left[2e^{-Cd\sqrt{t}},\mathds{1}\\{t^{1/4}\leq\eta\\}\right],$
$\displaystyle\leq 2\exp\left\\{-Cd\eta^{2-4q}t^{q}\right\\}.$

Consequently $z^{\prime}_{i}=z_{i}d^{1/q}\eta^{2/q-4}$ satisfy
$\mathbb{P}[z^{\prime}_{i}\geq t]\leq 2\exp\\{-Ct^{q}\\}$. We use again Lemma
3.6 to get:

$\displaystyle\mathbb{P}\left[\sum_{i=1}^{n}z_{i}\geq
n\mathbb{E}[z_{i}]+nd^{-1/q}\eta^{-2/q+4}t\right]\leq
2\exp\\{-C_{q}\min(nt^{2},(nt)^{q})\\}.$

This last inequality can be rewritten as, for all $v\geq 0$:

$\displaystyle\mathbb{P}\left[\sum_{i=1}^{n}z_{i}\geq\frac{n}{d^{2}}(3+v)\right]\leq
2\exp\left\\{-C_{q}\min\left(nd^{-4+2/q}\eta^{4/q-8}v^{2},n^{q}d^{1-2q}\eta^{2-4q}v^{q}\right)\right\\}.\qed$

Acknowledgements – The authors are grateful to Tim Kunisky, from whom they
learned about this problem, and to Joel Tropp for insightful discussions.

## References

  * [Ada15] Radosław Adamczak.  A note on the Hanson-Wright inequality for random vectors with dependencies.  Electronic Communications in Probability, 20:1 – 13, 2015.
  * [ALMT14] Dennis Amelunxen, Martin Lotz, Michael B McCoy, and Joel A Tropp.  Living on the edge: Phase transitions in convex programs with random data.  Information and Inference: A Journal of the IMA, 3(3):224–294, 2014\.
  * [ALPTJ11] Radoslaw Adamczak, Alexander E Litvak, Alain Pajor, and Nicole Tomczak-Jaegermann.  Restricted isometry property of matrices with independent columns and neighborly polytopes by random sampling.  Constructive Approximation, 34:61–88, 2011.
  * [BM22] Daniel Bartl and Shahar Mendelson.  Random embeddings with an almost Gaussian distortion.  Advances in Mathematics, 400:108261, 2022.
  * [GJJ+20] Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran.  Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes.  In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 954–965. IEEE, 2020.
  * [Gor88] Yehoram Gordon.  On Milman’s inequality and random subspaces which escape through a mesh in $\mathbb{R}^{n}$.  In Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986–87, pages 84–106. Springer, 1988.
  * [HKPX23] Jun-Ting Hsieh, Pravesh K Kothari, Aaron Potechin, and Jeff Xu.  Ellipsoid fitting up to a constant.  In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2023.
  * [HMSO97] Paweł Hitczenko, Stephen J Montgomery-Smith, and Krzysztof Oleszkiewicz.  Moment inequalities for sums of certain independent symmetric random variables.  Studia Math, 123(1):15–42, 1997.
  * [KD22] Daniel M Kane and Ilias Diakonikolas.  A nearly tight bound for fitting an ellipsoid to gaussian random points.  arXiv preprint arXiv:2212.11221, 2022.
  * [KM10] Achim Klenke and Lutz Mattner.  Stochastic ordering of classical discrete distributions.  Advances in Applied probability, 42(2):392–410, 2010.
  * [LM00] Beatrice Laurent and Pascal Massart.  Adaptive estimation of a quadratic functional by model selection.  Annals of Statistics, pages 1302–1338, 2000.
  * [MU17] Michael Mitzenmacher and Eli Upfal.  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge university press, 2017.
  * [PPW+19] Anastasia Podosinnikova, Amelia Perry, Alexander S Wein, Francis Bach, Alexandre d’Aspremont, and David Sontag.  Overcomplete independent component analysis via SDP.  In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2583–2592. PMLR, 2019.
  * [PTVW22] Aaron Potechin, Paxton Turner, Prayaag Venkat, and Alexander S Wein.  Near-optimal fitting of ellipsoids to random points.  arXiv preprint arXiv:2208.09493, 2022.
  * [Sau11] James James Francis Saunderson.  Subspace identification via convex optimization.  PhD thesis, Massachusetts Institute of Technology, 2011.
  * [SCPW12] James Saunderson, Venkat Chandrasekaran, Pablo A Parrilo, and Alan S Willsky.  Diagonal and low-rank matrix decompositions, correlation matrices, and ellipsoid fitting.  SIAM Journal on Matrix Analysis and Applications, 33(4):1395–1416, 2012.
  * [SPW13] James Saunderson, Pablo A Parrilo, and Alan S Willsky.  Diagonal and low-rank decompositions and fitting ellipsoids to random points.  In 52nd IEEE Conference on Decision and Control, pages 6031–6036. IEEE, 2013.
  * [Tal94] Michel Talagrand.  The supremum of some canonical processes.  American Journal of Mathematics, 116(2):283–325, 1994.
  * [Ver18] Roman Vershynin.  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press, 2018.