# Exact threshold for approximate ellipsoid fitting of random points

Afonso S Bandeira, Antoine Maillard

<figure><img src="image_1.png" /></figure>

► To cite this version:

Afonso S Bandeira, Antoine Maillard. Exact threshold for approximate ellipsoid fitting of random points. Electronic Journal of Probability, 2025, 30 (none), 10.1214/25-EJP1378. hal-05495104

HAL Id: hal-05495104

https://inria.hal.science/hal-05495104v1

Submitted on 9 Feb 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_3.png" /></figure>

Electron. J. Probab. 30 (2025), article no. 126, 1–46.
ISSN: 1083-6489 https://doi.org/10.1214/25-EJP1378

# Exact threshold for approximate ellipsoid fitting of random points

Afonso S. Bandeira*

Antoine Maillard†

## Abstract

We consider the problem (P) of exactly fitting an ellipsoid (centered at 0) to n standard Gaussian random vectors in $R^d$, as $n, d \to \infty$ with $n/d^2 \to \alpha > 0$. This problem is conjectured to undergo a sharp transition: with high probability, (P) has a solution if $\alpha < 1/4$, while (P) has no solutions if $\alpha > 1/4$. So far, only a trivial bound $\alpha > 1/2$ is known to imply the absence of solutions, while the sharpest results on the positive side assume $\alpha \le \eta$ (for $\eta > 0$ a small constant) to prove that (P) is solvable. In this work we show a universality property for the minimal fitting error achievable by ellipsoids: we show that, to leading order, it coincides with the minimal error in a so-called "Gaussian equivalent" problem, for which the satisfiability transition can be rigorously analyzed. Our main results follow from this finding, and they are twofold. On the positive side, we prove that if $\alpha < 1/4$, there exists an ellipsoid fitting all the points up to a small error, and that the lengths of its principal axes are bounded above and below. On the other hand, for $\alpha > 1/4$, we show that achieving small fitting error is not possible if the length of the ellipsoid's shortest axis does not approach 0 as $d \to \infty$ (and in particular there does not exist any ellipsoid fit whose shortest axis length is bounded away from 0 as $d \to \infty$). To the best of our knowledge, our work is the first rigorous result characterizing the expected phase transition in ellipsoid fitting at $\alpha = 1/4$. In a companion non-rigorous work, the second author and D. Kunisky give a general analysis of ellipsoid fitting using the replica method of statistical physics, which inspired the present work.

**Keywords:** ellipsoid fitting; high-dimensional probability; statistical physics.

**MSC2020 subject classifications:** 60D05; 52A22; 90C22.

Submitted to EJP on September 5, 2024, final version accepted on June 25, 2025.

Supersedes arXiv:2310.05787.

<footnote>*Department of Mathematics, ETH Zürich (Switzerland). E-mail: bandeira@math.ethz.ch</footnote>

<footnote>†Department of Mathematics, ETH Zürich (Switzerland) and Inria Paris & DI ENS, PSL University, Paris (France). E-mail: antoine.maillard@inria.fr. To whom correspondence shall be sent.</footnote>
# 1 Introduction and main results

## 1.1 The ellipsoid fitting conjecture

We consider the random ellipsoid fitting problem: given $n$ random standard Gaussian vectors in dimension $d$, when do they all lie on the boundary of a (centered) ellipsoid? Formally, we define an ellipsoid fit using the set $S_d$ of $d \times d$ real symmetric matrices, as follows.

**Definition 1.1 (Ellipsoid fit).** Let $x_1, \dots, x_n \in \mathbb{R}^d$. We say that $S \in S_d$ is an ellipsoid fit for $(x_\mu)_{\mu=1}^n$ if it satisfies:

$$ (P) : \left\{ \begin{array}{l} x_\mu^\top S x_\mu = d \quad \text{for all } \mu \in \{1, \dots, n\}, \\ S \succeq 0. \end{array} \right. \qquad (1.1) $$

In Definition 1.1, the matrix $S \succeq 0$ defines the ellipsoid $\Sigma := \{x \in \mathbb{R}^d : x^\top S x = d\}$. Geometrically speaking, the eigenvectors of $S$ give the directions of the principal axes of the ellipsoid, while its eigenvalues $(\lambda_i)_{i=1}^d$ are related to the lengths $(r_i)_{i=1}^d$ of its principal (semi-)axes by $r_i = \sqrt{d}\lambda_i^{-1/2}$.

**Scaling** – In what follows, we will rather refer to the rescaled quantities $r'_i = r_i/\sqrt{d}$ as the lengths of the ellipsoid axes, effectively rescaling distances so that the sphere of radius $\sqrt{d}$ (with $S = I_d$) has all (semi-)axes of length 1. In particular, the lengths of the ellipsoid’s longest and shortest axis are then respectively $\lambda_{\min}(S)^{-1/2}$ and $\lambda_{\max}(S)^{-1/2}$.

We are interested in finding an ellipsoid fit to a set of random points $x_1, \dots, x_n$ i.i.d. $\sim N(0, I_d)$. The question of the existence of such an ellipsoid arose first in [31, 29, 30], which conjectured the following (see e.g. Conjecture 2 in [30] or Conjecture 1.1 in [28]).

**Conjecture 1.2 (The ellipsoid fitting conjecture).** Let $n, d \ge 1$, and $x_1, \dots, x_n$ be drawn i.i.d. from $N(0, I_d)$. Let $p(n, d) := P[\exists S \in S_d \text{ an ellipsoid fit for } (x_\mu)_{\mu=1}^n]$. For any $\varepsilon > 0$, the following holds:

$$ \limsup_{d \to \infty} \frac{n}{d^2} \le \frac{1-\varepsilon}{4} \Rightarrow \lim_{d \to \infty} p(n, d) = 1, \qquad (1.2) $$

$$ \liminf_{d \to \infty} \frac{n}{d^2} \ge \frac{1+\varepsilon}{4} \Rightarrow \lim_{d \to \infty} p(n, d) = 0. \qquad (1.3) $$

Informally, Conjecture 1.2 predicts a sharp transition for the existence of an ellipsoid fit in the regime $n/d^2 \to \alpha > 0$ exactly at $\alpha = 1/4$.

## 1.2 Related works

Conjecture 1.2 was first stated and studied in the series of works [31, 29, 30], where it arose as being connected to the decomposition of a (random) data matrix $M$ as $M = L + D$, with $L \succeq 0$ being low-rank, and $D$ a diagonal matrix. Connections to other problems throughout theoretical computer science have since then been unveiled, such as certifying a lower bound on the discrepancy of a random matrix using a canonical semidefinite relaxation [29, 28], overcomplete independent component analysis [27], or Sum-of-Squares lower bound for the Sherrington-Kirkpatrick Hamiltonian [12]. We refer the reader to the detailed expositions of [28, 21] on the connections of ellipsoid fitting to theoretical computer science and machine learning.

Interestingly, Conjecture 1.2 arose both from numerical evidence<fnref n="1" /> and the remark that $d^2/4$ is known to be the statistical dimension (or squared Gaussian width) of $S_d^+$, the

<footnote n="1">¹Given $(x_\mu)_{\mu=1}^n$, eq. (1.1) is a convex problem (it is an example of a semidefinite program, or SDP), which is efficiently solvable when solutions exist.</footnote>
## Exact threshold for approximate ellipsoid fitting of random points

<figure><img src="image_4.png" /><figcaption>Figure 1: A summary of the current state of the ellipsoid fitting conjecture. In red, we show regions for which ellipsoid fitting is rigorously known to be unsatisfiable (UNSAT), and in orange regions which are conjectured to be. Similarly, we show in green regions rigorously known to be satisfiable (SAT), and in yellow regions which are conjectured to be so. Figure is taken from [21].</figcaption></figure>

set of positive semidefinite matrices [7, 2]. As such, if one replaces eq. (1.1) by

$$ (P_{\text{Gauss.}}) : \left\{ \begin{array}{l} \text{Tr}[SG_{\mu}] = d \text{ for all } \mu \in \{1, \dots, n\}, \\ S \succeq 0, \end{array} \right. \qquad (1.4) $$

in which $(G_{\mu})_{\mu=1}^n$ are (independent) standard Gaussian matrices, Conjecture 1.2 provably holds for $(P_{\text{Gauss.}})$. The crucial property of $(P_{\text{Gauss.}})$ behind this result is that the affine subspace $\{S \in S_d : (\text{Tr}[SG_{\mu}] = d)_{\mu=1}^n\}$ is randomly oriented, uniformly in all directions. Although this motivation for the conjecture was known, our work is (to the best of our knowledge) the first mathematically rigorous approach to leverage the connection between $(P)$ and $(P_{\text{Gauss.}})$.

Indeed, previous progress on Conjecture 1.2 has mostly focused on proving the existence of a fitting ellipsoid using an ansatz solution: the first line of eq. (1.1) defines an affine subspace $V$ of symmetric matrices of codimension $n$, so one can study a well-chosen $S^* \in V$, and argue that for small enough $n$ it satisfies $S^* \succeq 0$ with high probability as $d \to \infty$. Various such constructions have been used, and we summarize in Fig. 1 the current rigorous progress on the ellipsoid fitting conjecture that arose from these approaches. Presently, the best rigorous results on Conjecture 1.2 are due to the recent works [5, 16, 36] and can be summarized as follows:

**Theorem 1.3 ([5, 16, 36]).** Let $n, d \ge 1$, and $x_1, \dots, x_n \stackrel{\text{i.i.d.}}{\sim} N(0, I_d)$. Let $p(n, d) := P[\exists S \in S_d \text{ an ellipsoid fit for } (x_{\mu})_{\mu=1}^n]$. There exists a (small) universal constant $\eta > 0$ such that:

$$ \limsup_{d \to \infty} \frac{n}{d^2} \le \eta \Rightarrow \lim_{d \to \infty} p(n, d) = 1, $$

Moreover, if $n > d(d+1)/2$, then $p(n, d) = 0$.

Note that the bound $n > d(d+1)/2$ in Theorem 1.3 arises from a simple dimension counting argument, as $d(d+1)/2$ is the dimension of the space of symmetric matrices: for such values of $n$, not only does there not exist a solution to eq. (1.1), there does not exist any solution even without the constraint $S \succeq 0$!

**Statistical physics approaches: heuristic and rigorous** – In this work, we tackle Conjecture 1.2 using techniques inspired by the statistical physics of disordered systems. While analytical methods developed in this field were originally designed to study models known as spin glasses [4, 22], they have seen in the past decades a great number of applications in high dimensional statistics, theoretical computer science, and machine learning. Moreover, despite these techniques often being non-rigorous, a growing line of mathematics literature has emerged establishing many of their predictions. Notably, ellipsoid fitting is an example of a semidefinite program (SDP)<fnref n="2" /> with random linear

<footnote n="2">²i.e. a combination of linear equations with a positivity constraint $S \succeq 0$.</footnote>
constraints, and some such SDPs have been previously analyzed with tools of statistical physics [24, 18], although the methods of these works fall short for analyzing the satisfiability transition in random ellipsoid fitting [21]. We refer the interested reader to the recent book [8] that compiles many (sometimes surprising) applications of the theory of disordered systems, as well as mathematically rigorous approaches to it.

Notably, in the companion work to our manuscript [21], non-rigorous methods of statistical physics are employed to provide a detailed picture of the satisfiability transition in random ellipsoid fitting. Besides predicting a threshold for $n \sim d^2/4$, this work gives analytical formulas for the typical shape of ellipsoid fits in the satisfiable phase (i.e. the spectral density of $S$), generalizes these predictions for non-Gaussian but rotationally-invariant vectors $\{x_\mu\}_{\mu=1}^n$, and also studies the performance of different explicit solutions, notably ones used in the previous literature (see Fig. 1). We emphasize that the present paper is, in contrast, mathematically rigorous.

**Inspiration of our approach** – Importantly, the non-rigorous analysis of [21] suggests that a quantity known as the free entropy (or free energy) in statistical physics, is universal: its value is (with high probability) the same for (P) and a variant of ($P_{Gauss.}$), as $d \to \infty$. Such a universality property would have major consequences, as the free entropy carries deep information about the structure of the space of solutions to the problem. Remarkably, similar phenomena have been studied numerically and theoretically in statistical learning models, in which one can effectively replace an arbitrary (and possibly complicated) data distribution by its “Gaussian equivalent”. Investigating this Gaussian equivalence phenomenon is the object of a recent and very active line of work, with consequences on the theory of empirical risk minimization and beyond [13, 17, 23, 11, 1, 9, 20, 10, 32]. Inspired by these works (in particular [23]) we provide a rigorous proof of the universality conjectured in [21], using an interpolation argument. We then leverage tools of the theory of random convex programs [7, 2], such as Gordon’s min-max inequality [14], to sharply characterize the space of solutions to ($P_{Gauss.}$). Using the aforementioned universality allows to transfer many of these conclusions to the original problem (P), yielding our main results.

## 1.3 Main results

We now state our main results, separating the conjecturally satisfiable ($\alpha = n/d^2 < 1/4$) and unsatisfiable ($\alpha > 1/4$) regimes.

**Notation** – $f = o_d(g)$ (respectively $f = O_d(g)$) means that $f/g \to 0$ as $d \to \infty$ (respectively $f/g$ is bounded as $d \to \infty$). We also use $g \gtrsim f$ to denote $f = O_d(g)$. We denote $S_d$ the set of $d \times d$ real symmetric matrices, while $S^{d-1}(r)$ refers to the Euclidean sphere of radius $r$ in $\mathbb{R}^d$. For $S \in S_d$, $\text{Sp}(S) = \{\lambda_i\}_{i=1}^d$ is the set of eigenvalues of $S$. For $\gamma \in [1, \infty]$, $\|S\|_{S_\gamma} := (\sum_i |\lambda_i|^{\gamma})^{1/\gamma}$ stands for the Schatten-$\gamma$ norm. $B_\gamma(S, \delta)$ is the Schatten-$\gamma$ ball of radius $\delta$ centered in $S$, and $B_\gamma(\delta)$ the ball centered at $S = 0$. We denote by $\|S\|_{\text{op}} := \|S\|_{S_\infty}$ the operator norm, and $\|S\|_F := \|S\|_{S_2}$ the Frobenius norm. For a function $\psi: \mathbb{R} \to \mathbb{R}$, we write $\|\psi\|_L$ to denote its Lipschitz constant. Finally, we use a generic nomenclature $C, c > 0$ to denote positive constants (not depending on the dimension), that may vary from line to line. If necessary, we will make explicit the dependency of these constants on parameters of the problems. Finally, we use in the text the abbreviation “w.h.p.”, short for “with high probability”, to refer to events that have probability $1 - o_d(1)$ as $d \to \infty$.

### 1.3.1 The satisfiable phase: $\alpha < 1/4$

Our main result on the “positive” side of the ellipsoid fitting conjecture can be stated as follows.
**Theorem 1.4 (Satisfiable regime).** Assume $\alpha := \limsup(n/d^2) < 1/4$ and let $r \in [1, 4/3)$. There exist $0 < \lambda_- \le \lambda_+$, depending only on $\alpha$, such that the following holds. Let

$$ \Gamma_r(\varepsilon) := \left\{ S \in S_d : \mathrm{Sp}(S) \subseteq [\lambda_-, \lambda_+] \text{ and } \frac{1}{n} \sum_{\mu=1}^n \left| \sqrt{d} \left[ \frac{x_\mu^\mathrm{T} S x_\mu}{d} - 1 \right] \right|^r \le \varepsilon \right\}. $$

Then for any $\varepsilon > 0$, if $x_1, \dots, x_n \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, I_d)$, $P[\Gamma_r(\varepsilon) \neq \emptyset] \to 1$ as $n, d \to \infty$.

Let us make a series of remarks on Theorem 1.4. First, one can alternatively formulate its conclusion as:

$$ \underset{d \to \infty}{\mathrm{p-lim}} \min_{\mathrm{Sp}(S) \subseteq [\lambda_-, \lambda_+]} \frac{1}{n} \sum_{\mu=1}^{n} \left| \sqrt{d} \left[ \frac{x_\mu^\mathrm{T} S x_\mu}{d} - 1 \right] \right|^r = 0, \quad (1.5) $$

where $\mathrm{p-lim}$ denotes limit in probability. Secondly, while our current proof limits the choice of $r \in [1, 4/3)$, it might be possible to refine our arguments to reach the same result for any $r \in [1, 2]$, see our discussion in Section 1.4. Moreover, note that by standard concentration arguments, we expect Gaussian points to be close to the sphere $S^{d-1}(\sqrt{d})$, i.e. the ellipsoid defined by $S = I_d$. A detailed analysis yields, for any $r \in [1, 2]$:

$$ \underset{d \to \infty}{\mathrm{p-lim}} \frac{1}{n} \sum_{\mu=1}^{n} \left| \sqrt{d} \left[ \frac{\|x_\mu\|^2}{d} - 1 \right] \right|^r = \mathbb{E}[|Z|^r] > 0, \quad (1.6) $$

where $Z \sim \mathcal{N}(0, 2)$. This follows from classical concentration arguments, see Appendix B for a detailed derivation. Theorem 1.4 therefore shows that there exists an ellipsoid whose “fitting error” improves by an arbitrary factor over the one achieved by the unit sphere, as long as $\alpha < 1/4$. On the other hand, we will see that this is not possible for $\alpha > 1/4$, strongly suggesting that our results capture the phenomenon responsible for the conjectured satisfiability transition of ellipsoid fitting. In Section 1.4 we will consider possible future directions that could allow to improve our results to the existence of fitting ellipsoids with exactly zero error, i.e. the conjecture of eq. (1.2).

Finally, we notice that Theorem 1.4 is coherent with the non-rigorous analysis of [21], which predicts that for any $\alpha < 1/4$ typical solutions to ellipsoid fitting have spectral density contained in an interval of the type $[\lambda_-, \lambda_+]$ depending only on $\alpha$.

### 1.3.2 The unsatisfiable phase: $\alpha > 1/4$

Our main result towards proving the non-existence of fitting ellipsoids for $\alpha > 1/4$ is the following.

**Theorem 1.5 (Unsatisfiable regime).** Assume $\alpha := \liminf(n/d^2) > 1/4$. Let $\phi : \mathbb{R}_+ \to \mathbb{R}_+$ be a non-decreasing differentiable function, with $\phi(0) = 0$, and such that $\phi$ has a unique global minimum in 0. For any $\varepsilon > 0$ and $M > 0$ we let:

$$ \Gamma(\varepsilon, M) := \left\{ S \in S_d : \mathrm{Sp}(S) \subseteq [0, M] \text{ and } \frac{1}{n} \sum_{\mu=1}^{n} \phi \left( \sqrt{d} \left| \frac{x_\mu^\mathrm{T} S x_\mu}{d} - 1 \right| \right) \le \varepsilon \right\}. $$

There exists $\varepsilon = \varepsilon(\alpha, \phi) > 0$ such that for all $M > 0$, if $x_1, \dots, x_n \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, I_d)$,

$$ \lim_{d \to \infty} P[\Gamma(\varepsilon, M) \neq \emptyset] = 0. $$

As stated below, a direct corollary of Theorem 1.5 is that, when $\alpha > 1/4$, ellipsoid fitting admits (w.h.p.) no solutions with spectrum bounded above as $d \to \infty$ (i.e. an ellipsoid whose smallest axis has length bounded away from zero).
**Corollary 1.6** (Non-existence of fitting ellipsoids with bounded spectrum). Let $\alpha > 1/4$. Let $n, d \to \infty$ with $n/d^2 \to \alpha > 0$, and $x_1, \dots, x_n \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, I_d)$. We denote $\Gamma$ the set of ellipsoid fits for $(x_\mu)_{\mu=1}^n$. Then, for all $c > 0$,

$$ \lim_{d \to \infty} \mathbb{P}[\exists S \in \Gamma : \|S\|_{\text{op}} \le c] = 0. $$

In particular, our results imply that the negative side of the ellipsoid fitting conjecture, i.e. eq. (1.3), would follow from either:

**H.1** a proof that (for $\alpha > 1/4$ and with high probability) the set of ellipsoid fits is bounded in spectral norm as $d \to \infty$,

or

**H.2** a proof that, if $S \in \Gamma$ is an ellipsoid fit, there exists a (possibly different) ellipsoid fit $\hat{S} \in \Gamma$ that has bounded spectral norm as $d \to \infty$.

As a consequence of Corollary 1.6, proving either H.1 or H.2 would yield the negative side of the ellipsoid fitting conjecture. Notice further that Theorem 1.5 implies the non-existence of bounded ellipsoid fits even allowing a small “fitting error”, so that it would be sufficient to prove H.2 considering an ellipsoid $\hat{S}$ that fits $(x_\mu)_{\mu=1}^n$ only up to a small enough error $\varepsilon > 0$ (in the sense of Theorem 1.5).

## 1.4 Discussion and consequences

The combination of our two main results (Theorem 1.4 and Theorem 1.5) provides strong evidence for the original ellipsoid fitting conjecture (Conjecture 1.2). Our conclusions are attained through the study of a “Gaussian equivalent” problem, which partly motivated Conjecture 1.2. Informally, we show that an approximate version of the ellipsoid fitting (i.e. by allowing infinitesimally small error) undergoes a sharp satisfiability transition at $\alpha = n/d^2 = 1/4$. Moreover, we also show in our proof that in the Gaussian equivalent problem, the satisfiability transition for this “approximate” version corresponds to the one of the exact fitting problem (i.e. not allowing for any non-zero error). This strongly suggests that our method is indeed capturing the phenomenon responsible for the ellipsoid fitting transition.

Our results are an example of a universality phenomenon in high-dimensional stochastic geometry: we show that the statistical dimension (or the square of the Gaussian width) of the set of positive semidefinite matrices determines the satisfiability of – a modified version of – random ellipsoid fitting, even though the affine subset $\{S \in S_d : (x_\mu^\top S x_\mu = d)_{\mu=1}^n\}$ is not randomly oriented uniformly in all directions. In general, understanding the conditions under which universality holds in such problems of high-dimensional random geometry is an important open question. We mention [26], which proves universality between a model in which the random subspace is given by the kernel of a random i.i.d. Gaussian matrix, and a second model where the subspace is the kernel of a matrix with independent elements (not necessarily Gaussian).

### 1.4.1 Towards Conjecture 1.2

Unfortunately, while our main theorems characterize a satisfiability transition for ellipsoid fitting at the expected threshold, they do not formally imply Conjecture 1.2. We discuss briefly some improvements of our results that could potentially allow to bridge this gap.

On the “positive” side of the conjecture (i.e. the regime $\alpha = n/d^2 < 1/4$), Theorem 1.4 shows the existence of bounded ellipsoids that can achieve arbitrarily small error $\varepsilon$
(where the error is taken to 0 after $d \to \infty$). On the other hand, a proof of eq. (1.2) would require to invert these limits, and take $\varepsilon \to 0$ before $d \to \infty$. In this regard, an important strengthening of Theorem 1.4 would be to obtain non-asymptotic bounds on $\mathbb{P}[\Gamma_r(\varepsilon) = \emptyset]$, that depend on $\varepsilon$.

Another potential for improvement stems from geometrical considerations: denoting $V := \{S \in S_d : x_\mu^\top S x_\mu = d$ for all $\mu \in [n]\}$, one may use Theorem 1.4 to bound the distance of the set $\Gamma_r(\varepsilon)$ to the affine subspace $V$. Since $\lambda_{\min}(S) \ge \lambda_-(\alpha)$ for any $S \in \Gamma_r(\varepsilon)$, it would suffice to show that $d_{op}(\Gamma_r(\varepsilon), V) \le \lambda_-(\alpha)$ to deduce eq. (1.2), the first part of Conjecture 1.2. We perform in Appendix C a naive analysis of necessary conditions for this conclusion to follow from Theorem 1.4. Unfortunately, we find that (among other considerations) these conditions would require a significantly stronger form of Theorem 1.4, by proving the conclusion for larger values of $r \in [1, 2]$ and/or a better scaling with $d$ of the minimal error achievable (i.e. proving the conclusion of Theorem 1.4 for $\Gamma_r(\varepsilon_d)$ with $\varepsilon_d \to 0$ as $d \to \infty$).

Moreover, let us emphasize that a critical difficulty in improving our proof techniques would be to quantitatively sharpen the universality arguments we carry out, and in particular to strengthen Proposition 2.2, which shows the universality of the minimal fitting error, or “ground state” energy, for ellipsoid fitting and a simpler “Gaussian equivalent” problem. While the present form of Proposition 2.2 shows universality of this error up to a $o_d(1)$ difference, this estimate would likely have to be improved in order to carry out the aforementioned approaches. This part of our proof is greatly inspired by a recent literature on similar universality phenomena [13, 17, 23, 11, 1, 9, 20, 10, 32], and we are not aware of the existence of such universality results at a finer scale (or even predictions/conjectures of conditions under which they should hold).

Finally, on the “negative” side of the conjecture (i.e. for $\alpha > 1/4$), as emphasized in Corollary 1.6 and the discussion thereafter, Theorem 1.5 reduces the second part of Conjecture 1.2 (eq. (1.3)) to proving either H.1 or H.2. If such a proof were to become available, our results would imply the regime $\alpha > 1/4$ of Conjecture 1.2.

### 1.4.2 Further directions

Our proof method that leverages universality of the minimal fitting error is quite versatile, and we end our discussion by mentioning a few further directions and generalized results that stem from our analysis.

**The dual program** – First, as a semidefinite program, ellipsoid fitting admits a dual formulation, as written e.g. in [5]. While the limitations of Theorems 1.4 and 1.5, discussed above, prevent us from directly drawing conclusions on the dual, it might be possible to directly apply to it a similar universality approach. Such an application might allow to overcome some current limitations of our results, and we leave this investigation for future work.

**Beyond Gaussian vectors** – Secondly, while we perform our analysis for $x_1, \dots, x_n \sim \mathcal{N}(0, I_d)$, it is clear from our proof that our results (both Theorems 1.4 and 1.5) hold for any i.i.d. $(x_\mu)_{\mu=1}^n$ such that the matrices $W_\mu := (x_\mu x_\mu^\top - I_d)/\sqrt{d}$ satisfy a uniform pointwise normality (or uniform one-dimensional CLT) assumption, as defined in Definition 4.5, and proven for the case of Gaussian vectors in Lemma 4.9. An interesting example of a non-Gaussian distribution is given by the case of rotationally-invariant vectors with fluctuating norm, of the form

$$x_\mu \stackrel{d}{=} \sqrt{r_\mu} \omega_\mu,$$

with $r_\mu$ and $\omega_\mu$ independent, and $\omega_\mu \sim \text{Unif}(\mathbb{S}^{d-1}(\sqrt{d}))$. Letting $\tau := \lim_{d \to \infty}[\sqrt{d}\text{Var}(r_1)]$, [21] conjectures that the ellipsoid fitting transition point for this model is located at
$n/d^2 = \alpha_c(\tau) \in (0, 1/2)$, and gives an exact expression of $\alpha_c(\tau)$ (see Fig. 5 of [21]), showing that ellipsoid fitting becomes harder as the fluctuations of the norm increase. While pointwise normality may not hold in this setting, it is conceivable that our proof techniques can be adapted to handle these distributions, by following the calculations of [21], to obtain results akin to Theorems 1.4 and 1.5. More generally, while it is clear that some distributions can not satisfy uniform pointwise normality (see the discussion below Lemma 4.9 for examples), a more thorough investigation of the class of distributions of $x_\mu$'s for which pointwise normality holds (and thus our proof applies) is, in our opinion, an interesting direction to explore.

**A minimal nuclear norm estimator** – Let us conclude by mentioning a different approach to a possible solution of the first part of Conjecture 1.2. It is conjectured in [21] (through non-rigorous methods) that the minimal nuclear norm solution, i.e.

$$ \hat{S}_{NN} := \arg\min_{\substack{S \in S_d \\ \{x_\mu^\top S x_\mu = d\}_{\mu=1}^n}} \|S\|_{S_1} = \arg\min_{\substack{S \in S_d \\ \{x_\mu^\top S x_\mu = d\}_{\mu=1}^n}} \sum_{i=1}^d |\lambda_i(S)|, $$

satisfies $\hat{S}_{NN} \ge 0$ with high probability for any $\alpha < 1/4$. Analyzing $\hat{S}_{NN}$, whether through the techniques of the present paper or with different methods, is another promising approach to prove eq. (1.2), the “positive” part of Conjecture 1.2.

## 1.5 Structure of the paper

In Section 2 we present the proof of our main results. The proof of some intermediate results is postponed to later sections: in Section 3 we study in detail the “Gaussian equivalent” problem to random ellipsoid fitting, and in Section 4 we prove a crucial universality property for the minimal fitting error between ellipsoid fitting and its “Gaussian equivalent”.

## 2 Proof of the main results

We prove here Theorems 1.4 and 1.5. The core idea of our proof can be sketched as follows:

(i) Using rigorous methods inspired by statistical physics, we prove that a quantity known as the asymptotic free entropy is universal for the ellipsoid fitting problem of eq. (1.1) and a variant of its Gaussian counterpart of eq. (1.4), for any value of $\alpha = n/d^2$. The main technique we use is an interpolation method. In a suitable limit (known as the low-temperature limit in statistical physics), this implies the universality of the minimal “fitting error”.

(ii) We study the Gaussian equivalent problem using methods of random convex geometry [7, 2], leveraging in particular Gordon's min-max inequality [14]. When $\alpha < 1/4$ we show that not only a zero error is achievable, but that one can achieve it by a matrix whose spectrum is contained in an interval of the type $[\lambda_-, \lambda_+]$, i.e. the axis of the corresponding ellipsoid have lengths bounded above and below. On the other hand, for $\alpha > 1/4$, we prove that not only is the Gaussian equivalent problem not satisfiable, but one can lower bound the minimal fitting error as long as the set of candidate matrices is contained in an operator norm ball $B_{op}(M)$ (for any constant $M > 0$).

(iii) We prove that the conclusions of (ii) transfer to the original ellipsoid fitting problem, using the universality shown in (i).
Our proof of (i) leverages an important line of work on free entropy universality [17, 23, 11], and a part of it closely follows the proof of [23], which we will point out in relevant places. Nevertheless, as our setting does not satisfy all the hypotheses of this work, and for completeness of our exposition, we chose to write the whole proof in a self-contained manner.

## 2.1 Reduction of the problem and Gaussian equivalent

For any $0 \le \lambda_{-} \le \lambda_{+}$, any function $\phi: \mathbb{R} \to \mathbb{R}$ and any $\varepsilon > 0$ we define the set

$$ \Gamma(\phi, \lambda_{-}, \lambda_{+}, \varepsilon) := \left\{ S \in \mathcal{S}_d : \mathrm{Sp}(S) \subseteq [\lambda_{-}, \lambda_{+}] \text{ and } \frac{1}{n} \sum_{\mu=1}^{n} \phi \left( \sqrt{d} \left[ \frac{x_{\mu}^{\top} S x_{\mu}}{d} - 1 \right] \right) \le \varepsilon \right\}. \quad (2.1) $$

If one thinks of $\phi$ as an error (or loss) function, then $\Gamma(\phi, \lambda_{-}, \lambda_{+}, \varepsilon)$ represents the set of matrices with spectrum in $[\lambda_{-}, \lambda_{+}]$ that solve (P) up to an approximation error $\varepsilon$. Notice that for any $S \in \mathcal{S}_d$:

$$ \sqrt{d} \left[ \frac{x_{\mu}^{\top} S x_{\mu}}{d} - 1 \right] = \mathrm{Tr}[W_{\mu} S] - \frac{d - \mathrm{Tr}[S]}{\sqrt{d}}, \quad (2.2) $$

with $W_{\mu} := (x_{\mu}x_{\mu}^{\top} - I_{d})/\sqrt{d}$. Moreover, $W_{\mu}$ has the same first two moments as a Gaussian matrix. Formally, we define:

**Definition 2.1 (Matrix ensembles).** Let $d \ge 1$. We say that a random symmetric $W \in \mathcal{S}_d$ is generated according to$^3$:

* $W \sim \mathrm{GOE}(d)$ if $W_{ij} \stackrel{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0, [1 + \delta_{ij}]/d)$ for $i \le j$.

* $W \sim \mathrm{Ellipse}(d)$ if $W \stackrel{\mathrm{d}}{=} (xx^{\top} - I_{d})/\sqrt{d}$ for $x \sim \mathcal{N}(0, I_{d})$.

One checks easily that $E_{\mathrm{Ellipse}(d)}[W_{ij}W_{kl}] = E_{\mathrm{GOE}(d)}[W_{ij}W_{kl}]$ for any $i \le j$ and $k \le l$. This remark and eq. (2.2) lead to consider the following modified problem, with $W_{\mu} := (x_{\mu}x_{\mu}^{\top} - I_{d})/\sqrt{d}$ and $b \in \mathbb{R}$:

$$ \Gamma_b(\phi, \lambda_{-}, \lambda_{+}, \varepsilon) := \left\{ S \in \mathcal{S}_d : \mathrm{Sp}(S) \subseteq [\lambda_{-}, \lambda_{+}] \text{ and } \frac{1}{n} \sum_{\mu=1}^{n} \phi (\mathrm{Tr}[W_{\mu}S] - b) \le \varepsilon \right\}. \quad (2.3) $$

In the rest of the proof we will focus on studying the set $\Gamma_b$ of eq. (2.3) with$^4 b \in \mathbb{R}$, for both $W_{\mu} \sim \mathrm{Ellipse}(d)$ and $W_{\mu} \sim \mathrm{GOE}(d)$ (which we call the “Gaussian equivalent” problem). At the end of our proof, we will transfer our conclusions on $\Gamma_b$ back to the original solution set $\Gamma$ of eq. (2.1).

## 2.2 Universality of the minimal error

We can now state the main result concerning on the universality of the minimal error (or “ground state energy” in statistical physics jargon). This result is inspired by a rich line of work on universality of empirical risk minimization [17, 23, 11, 9].

**Proposition 2.2 (Ground state universality).** Let $\phi: \mathbb{R} \to \mathbb{R}_{+}$ and $\psi: \mathbb{R} \to \mathbb{R}$ two bounded differentiable functions with bounded derivatives, and assume furthermore $\|\psi'\|_{L} < \infty$. Let $n, d \ge 1$ and $n, d \to \infty$ with $\alpha_{1}d^{2} \le n \le \alpha_{2}d^{2}$ for some $0 < \alpha_{1} \le \alpha_{2}$, and $B \subseteq S_{d}$ a closed set such that $B \subseteq B_{\mathrm{op}}(C_{0})$ for some $C_{0} > 0$ (not depending on $d$). For

<footnote>$^3$GOE(d) stands for Gaussian Orthogonal Ensemble.</footnote>

<footnote>$^4$Furthermore, by rescaling $S$ (and up to a change in $\lambda_{-}, \lambda_{+}, \phi$) we will reduce to the case $b \in \{-1, 0, 1\}$.</footnote>
Exact threshold for approximate ellipsoid fitting of random points

$X_1, \dots, X_n \in S_d$ we define the ground state energy:

$$ \mathrm{GS}_d(\{X_\mu\}) := \inf_{S \in \mathcal{B}} \frac{1}{d^2} \sum_{\mu=1}^{n} \phi(\mathrm{Tr}[X_\mu S]). \quad (2.4) $$

Then we have:

$$ \lim_{d \to \infty} \left| \mathbb{E}_{\{W_\mu\} \stackrel{\text{i.i.d.}}{\sim} \text{Ellipse}(d)} \psi[\mathrm{GS}_d(\{W_\mu\})] - \mathbb{E}_{\{G_\mu\} \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)} \psi[\mathrm{GS}_d(\{G_\mu\})] \right| = 0. \quad (2.5) $$

Therefore, for any $\rho \ge 0$ and $\delta > 0$:

$$ \left\{ \begin{array}{l} \lim_{d \to \infty} \mathbb{P}[\mathrm{GS}_d(\{W_\mu\}) \ge \rho + \delta] \le \lim_{d \to \infty} \mathbb{P}[\mathrm{GS}_d(\{G_\mu\}) \ge \rho], \\ \\ \lim_{d \to \infty} \mathbb{P}[\mathrm{GS}_d(\{W_\mu\}) \le \rho - \delta] \le \lim_{d \to \infty} \mathbb{P}[\mathrm{GS}_d(\{G_\mu\}) \le \rho]. \end{array} \right. \quad (2.6) $$

**A word on the proof** – The main proof technique we use is Gaussian interpolation: namely we define an interpolating $U_\mu(t)$ such that $U_\mu(0) = G_\mu$ and $U_\mu(1) = W_\mu$, and show that $\mathrm{GS}_d(\{U_\mu(t)\})$ is constant (up to negligible terms) along the interpolation path. Note that while Proposition 2.2 is very close to the results of [23], there is a technical difference with the setup of this work: for any fixed $S$, the random variable $\mathrm{Tr}[WS]$ for $W \sim \text{Ellipse}(d)$ is not sub-Gaussian but only sub-exponential. As a consequence, we can not achieve a good control of the Lipschitz constant of the error (or “energy” function) of eq. (2.4) with respect to the Frobenius norm of $S$, as is required in [23]. We bypass this difficulty by controlling instead the Lipschitz constant with respect to the operator norm (see Lemma 4.1), using important empirical process bounds over the operator norm ball (see Lemma 4.3): this leads to the limitation $B \subseteq B_{\mathrm{op}}(C_0)$. Interestingly, improving these bounds would also allow to relax the limitation $r \in [1, 4/3)$ in Theorem 1.4, as we discuss after. Having dealt with this difficulty, the rest of the interpolation argument is very similar to [23]. We show Proposition 2.2 in Section 4, deferring some arguments to Appendix D.

## 2.3 The Gaussian equivalent problem

We now study the Gaussian equivalent problem. We will later transfer our analysis to the original ellipsoid fitting case using Proposition 2.2. Our results are stated separately for the satisfiable and unsatisfiable regimes.

**Proposition 2.3 (Regular solutions in the satisfiable regime).** Let $n, d \to \infty$ with $n/d^2 \to \alpha < 1/4$, and let $\{G_\mu\}_{\mu=1}^n \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)$. Let

$$ V := \{S \in S_d : \forall \mu \in [n], \mathrm{Tr}[G_\mu S] = 1\}. $$

There exist $0 < \lambda_\_ \le \lambda_+$ (depending only on $\alpha$) such that:

$$ \lim_{d \to \infty} \mathbb{P}\{\exists S \in V \text{ s.t. } \mathrm{Sp}(S) \subseteq [\lambda_\_, \lambda_+]\} = 1. $$

Proposition 2.3 shows that for $\alpha < 1/4$, there exist with high probability ellipsoids satisfying the “Gaussian equivalent” to random ellipsoid fitting, and that such solutions might also be assumed to have their axes' lengths bounded above and below as $d \to \infty$. In the unsatisfiable regime $\alpha > 1/4$, we show on the other hand that with high probability there are no solutions to the Gaussian equivalent problem, even allowing for some error when fitting the random points.

**Proposition 2.4 (No approximate solution in the unsatisfiable regime).** Let $n, d \to \infty$ with $n/d^2 \to \alpha > 1/4$, and let $\{G_\mu\}_{\mu=1}^n \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)$. Let $b \in \mathbb{R}$ and denote $C_\mu^{(b)}(S) := |\mathrm{Tr}(G_\mu S) - b|$. Define the affine subspace:

$$ V_b := \{S \in S_d : \forall \mu \in [n], C_\mu^{(b)}(S) = 0\}. $$
Exact threshold for approximate ellipsoid fitting of random points

(i) Assume that $b \neq 0$. Then there exist $c = c(\alpha, b) > 0$ and $\eta = \eta(\alpha, b) \in (0, 1)$ such that

$$ \lim_{d \to \infty} \mathbb{P}\{\forall S \geq 0 : \#\{\mu \in [n] : C_{\mu}^{(b)}(S) > c\} \geq \eta n\} = 1. $$

(ii) Assume that $b = 0$. Then there exist $c = c(\alpha) > 0$ and $\eta = \eta(\alpha) \in (0, 1)$ such that, with probability $1 - o_d(1)$, the following holds for all $\tau \geq 0$:

$$ \sup_{S \geq 0} \|S\|_F \leq \tau \sqrt{d}. \\ \#\{\mu \in [n] : C_{\mu}^{(0)}(S) > c\tau\} < \eta n $$

Propositions 2.3 and 2.4 are proven in Section 3. Our proof follows a standard approach in random geometry problems involving Gaussian distributions, by leveraging Gordon's min-max inequality [14] and its sharpness in convex settings [35, 34]. It strengthens for our setting the results obtained for general random convex programs in [7, 2] (using either Gordon's inequality or tools of integral geometry).

## 2.4 The satisfiable regime: Proof of Theorem 1.4

Propositions 2.2 and 2.3 have the following consequence, taking $B := \{S : \lambda_-I_d \leq S \leq \lambda_+I_d\}$, with $(\lambda_-, \lambda_+)$ given by Proposition 2.3.

**Corollary 2.5.** Let $n, d \to \infty$ with $n/d^2 \to \alpha < 1/4$, and $W_1, \dots, W_n \stackrel{\text{i.i.d.}}{\sim} \text{Ellipse}(d)$. There exist $\lambda_-, \lambda_+ > 0$ depending only on $\alpha$ such that the following holds. If we have $\phi : \mathbb{R} \to \mathbb{R}_+$ with $\|\phi\|_{\infty}, \|\phi'\|_{\infty} < \infty$ and such that $\phi(0) = 0$, then

$$ \text{p-lim}_{d \to \infty} \text{Sp}(S) \subseteq [\lambda_-, \lambda_+] \frac{1}{n} \sum_{\mu=1}^{n} \phi(\text{Tr}[W_{\mu}S] - 1) = 0. $$

The proof of Corollary 2.5 is immediate by combining Propositions 2.2 and 2.3. We can furthermore relax some of the assumptions on $\phi$ in Corollary 2.5, as we now show.

**Lemma 2.6.** Corollary 2.5 holds for $\phi(x) = |x|^r$, for any $1 \leq r < 4/3$.

Note that the limitation $r < 4/3$ is a consequence of a limitation on the control of an empirical process that is done in Lemma 4.3 (see also the discussion in Section 4.1).

**Proof of Lemma 2.6.** Let us first assume that $r > 1$, so that $\phi(x) = |x|^r$ is continuously differentiable in $x = 0$. Let $\varepsilon > 0$ and $A > 0$, and let us denote $u_A : \mathbb{R}_+ \to [0, 1]$ a $C^\infty$ function such that $u_A(x) = 1$ if $x \leq A$ and $u_A(x) = 0$ if $x \geq A + 1$. We denote $\phi_A(z) := |z|^r u_A(|z|)$. Then $\phi_A$ is bounded, with bounded derivative. Moreover, we have for any $x \in \mathbb{R}$:

$$ |x|^r = \phi_A(x) + |x|^r (1 - u_A(|x|)) \leq \phi_A(x) + |x|^r \mathbf{1}\{|x| \geq A\}. $$

By Corollary 2.5, under an event of probability $1 - o_d(1)$ we can fix $S$ with $\text{Sp}(S) \in [\lambda_-, \lambda_+]$ and such that $\sum_{\mu=1}^n \phi_A(\text{Tr}[W_\mu S] - 1) \leq n\varepsilon/2$. We pick $\gamma > 1$ such that $\gamma r \leq 4/3$, and condition on the $1 - o_d(1)$ probability event, thanks to Lemma 4.3:

$$ \max_{\|R\|_{\text{op}}=1} \sum_{\mu=1}^{n} |\text{Tr}(W_{\mu}R)|^{\gamma r} \leq Cn \quad (2.7) $$
Exact threshold for approximate ellipsoid fitting of random points

We have, with probability $1 - o_d(1)$:

$$
\begin{align*}
\frac{1}{n} \sum_{\mu=1}^{n} |\operatorname{Tr}[W_{\mu}S] - 1|^r &\le \frac{\varepsilon}{2} + \frac{1}{n} \sum_{\mu=1}^{n} |\operatorname{Tr}[W_{\mu}S] - 1|^r \mathbf{1}\{|\operatorname{Tr}[W_{\mu}S] - 1| \ge A\}, \\
&\stackrel{(a)}{\le} \frac{\varepsilon}{2} + \frac{A^{r(1-\gamma)}}{n} \sum_{\mu=1}^{n} |\operatorname{Tr}[W_{\mu}S] - 1|^{\gamma r}, \\
&\stackrel{(b)}{\le} \frac{\varepsilon}{2} + \frac{A^{r(1-\gamma)} 2^{\gamma r-1}}{n} [n + C \lambda_{+}^{\gamma r} n], \\
&\le \frac{\varepsilon}{2} + C(\gamma, r, \alpha) A^{r(1-\gamma)}.
\end{align*}
$$

We used in (a) the following inequality, for a positive random variable $X$, $t \ge 0$, and any
$\gamma > 1$:

$$
\mathrm{E}[X \mathbf{1}\{X \ge t\}] = t \mathrm{E} \left[ \frac{X}{t} \mathbf{1}\left\{ \frac{X}{t} \ge 1 \right\} \right] \le t^{1-\gamma} \mathrm{E}[X^{\gamma}].
$$

In (b) we used eq. (2.7) and $|a+b|^r \le 2^{r-1}(|a|^r + |b|^r)$. We pick

$$
A = \left( \frac{\varepsilon}{2C(\gamma, r, \alpha)} \right)^{1/[r(1-\gamma)]} .
$$

We have then, with probability $1 - o_d(1)$:

$$
\min_{\mathrm{Sp}(S) \subseteq [\lambda_-, \lambda_+]} \frac{1}{n} \sum_{\mu=1}^{n} |\mathrm{Tr}[W_\mu S] - 1|^r \le \varepsilon,
$$

which ends the proof.

We now tackle the case $r = 1$. For $\eta > 0$, we let $v_\eta : \mathbb{R}_+ \to [0, 1]$ a $C^\infty$ function such that $v_\eta(x) = 1$ for $x \ge \eta$ and $v_\eta(x) = 0$ for $x \le \eta/2$. A transposition of the argument above shows that Corollary 2.5 applies to $\phi_\eta(x) := |x|v_\eta(|x|)$, which is continuously differentiable everywhere. Notice that for any $x \in \mathbb{R}$:

$$
|x| = \phi_{\eta}(x) + |x|(1 - v_{\eta}(|x|)) \le \phi_{\eta}(x) + |x|\mathbf{1}\{|x| \le \eta\} \le \phi_{\eta}(x) + \eta.
$$

So, for any $S \in \mathcal{S}_d$:

$$
\frac{1}{n} \sum_{\mu=1}^{n} |\operatorname{Tr}[W_{\mu}S] - 1| \le \frac{1}{n} \sum_{\mu=1}^{n} \phi_{\eta}(\operatorname{Tr}[W_{\mu}S] - 1) + \eta. \quad (2.8)
$$

Fixing now any $\varepsilon > 0$, and letting $\eta := \varepsilon/2$, we get from Corollary 2.5 applied to $\phi_\eta$ that
with probability $1 - o_d(1)$:

$$
\min_{\mathrm{Sp}(S) \subseteq [\lambda_-, \lambda_+]} \frac{1}{n} \sum_{\mu=1}^{n} \phi_{\eta}(\mathrm{Tr}[W_{\mu}S] - 1) \le \frac{\varepsilon}{2}.
$$

Combining this result with eq. (2.8), we get that with probability $1 - o_d(1)$:

$$
\min_{\mathrm{Sp}(S) \subseteq [\lambda_-, \lambda_+]} \frac{1}{n} \sum_{\mu=1}^{n} |\mathrm{Tr}[W_{\mu}S] - 1| \le \varepsilon,
$$

which ends the proof.

<figure><img src="image_5.png" /></figure>

**Proof of Theorem 1.4** – Notice that Lemma 2.6 precisely shows that, for $\phi(x) = |x|^r$
and $\varepsilon > 0$, the set $\Gamma_1$ of eq. (2.3) is non-empty with high probability. We now use the
following remark (recall the definition of $\Gamma$ in eq. (2.1)):
**Lemma 2.7.** For any $(x_\mu)_{\mu=1}^n$ and $\lambda_-, \lambda_+, \varepsilon > 0, r \ge 1$, if $S \in \Gamma_1(|\cdot|^r, \lambda_-, \lambda_+, \varepsilon)$, then $\hat{S} \in \Gamma(|\cdot|^r, \lambda'_-, \lambda'_+, \varepsilon')$, with

$$ \hat{S} = \frac{dS}{\sqrt{d + \mathrm{Tr}[S]}}, \quad \lambda'_- = \frac{\lambda_-}{\lambda_+ + d^{-1/2}}, \quad \lambda'_+ = \frac{\lambda_+}{\lambda_- + d^{-1/2}}, \quad \varepsilon' = \frac{\varepsilon}{(\lambda_- + d^{-1/2})^r}. $$

Since $\lambda'_+ \le \lambda_+ / \lambda_-$, $\varepsilon' \le \varepsilon / (\lambda_-)^r$, and $\lambda'_- \ge \lambda_- / (2\lambda_+)$ for $d$ large enough, combining Lemmas 2.6 and 2.7 imply that for any $r \in [1, 4/3)$ and $\varepsilon > 0$:

$$ \mathbb{P}[\Gamma(|\cdot|^r, a, b, \varepsilon) \neq \emptyset] \to_{d \to \infty} 1, $$

for some $0 < a \le b$ depending only on $\alpha$, which ends the proof of Theorem 1.4. $\square$

**Proof of Lemma 2.7.** Let $S \in \Gamma_1(|\cdot|^r, \lambda_-, \lambda_+, \varepsilon)$. Defining $\hat{S} = dS / (\sqrt{d} + \mathrm{Tr}[S])$, we have by eq. (2.2):

$$ \left| \sqrt{d} \left[ \frac{x_\mu^\top \hat{S} x_\mu}{d} - 1 \right] \right|^r = \left( \frac{d}{\sqrt{d} + \mathrm{Tr}[S]} \right)^r |\mathrm{Tr}[S W_\mu] - 1|^r, \\ \le \frac{1}{(\lambda_- + d^{-1/2})^r} |\mathrm{Tr}[S W_\mu] - 1|^r. \quad \square $$

## 2.5 The unsatisfiable regime: Proof of Theorem 1.5

Propositions 2.2 and 2.4 have the following corollary.

**Corollary 2.8.** Let $n, d \to \infty$ with $n/d^2 \to \alpha > 1/4$, and $W_1, \dots, W_n \stackrel{\text{i.i.d.}}{\sim} \text{Ellipse}(d)$. Let $\phi: \mathbb{R}_+ \to \mathbb{R}_+$ be a non-decreasing differentiable function, with $\phi(0) = 0$, and such that $\phi$ has a unique global minimum in 0. Then:

(i) Let $b \in \{-1, 1\}$. There exists $\varepsilon = \varepsilon(\alpha, \phi) > 0$ such that for all $M > 0$:

$$ \lim_{d \to \infty} \mathbb{P} \left[ \min_{\mathrm{Sp}(S) \subseteq [0, M]} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[W_\mu S] - b|) \ge \varepsilon \right] = 1. $$

(ii) Let $b = 0$. For all $\tau > 0$, there exists $\varepsilon = \varepsilon(\tau, \alpha, \phi) > 0$ such that for all $M > 0$:

$$ \lim_{d \to \infty} \mathbb{P} \left[ \min_{\substack{\mathrm{Sp}(S) \subseteq [0, M] \\ \|S\|_F \ge \tau \sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[W_\mu S]|) \ge \varepsilon \right] = 1. $$

**Proof of Corollary 2.8.** Note that we can assume that $\phi$ is bounded with bounded derivative and $\phi'(0) = 0$: if not it is always possible to lower bound $\phi$ by such a function. $x \mapsto \phi(|x|)$ is then a bounded function on $\mathbb{R}$ with bounded derivative. We start with (i). By Proposition 2.4, there exist $c_\alpha, \eta_\alpha > 0$ such that

$$ \lim_{d \to \infty} \mathbb{P}\{\forall S \succeq 0 : \#\{\mu \in [n] : |\mathrm{Tr}(G_\mu S) - b| \le c_\alpha\} \le (1 - \eta_\alpha)n\} = 1. $$

Conditioning on this event, we have

$$ \inf_{S \succeq 0} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[G_\mu S] - b|) \ge n\eta_\alpha\phi(c_\alpha). $$

Using Proposition 2.2 with $B = \{S : \mathrm{Sp}(S) \subseteq [0, M]\}$ we reach that, for all $M > 0$, with probability $1 - o_d(1)$:

$$ \inf_{\mathrm{Sp}(S) \subseteq [0, M]} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[W_\mu S] - b|) \ge \frac{1}{2} \eta_\alpha \phi(c_\alpha). $$
Exact threshold for approximate ellipsoid fitting of random points

We now turn to (ii). Again by Proposition 2.4, we fix $c_\alpha, \eta_\alpha > 0$ such that for all $\tau \ge 0$:

$$ \lim_{d \to \infty} \mathbb{P} \left\{ \sup_{ \#\{\mu \in [n] : |\mathrm{Tr}(G_\mu S)| > c_\alpha \tau \} < \eta_\alpha n } \|S\|_F \le \frac{\tau}{2} \sqrt{d} \right\} = 1. $$

Stated differently:

$$ \lim_{d \to \infty} \mathbb{P}\{\forall S \succeq 0 : \|S\|_F \le \frac{\tau}{2}\sqrt{d} \text{ or } \#\{\mu \in [n] : |\mathrm{Tr}(G_\mu S)| > c_\alpha \tau\} \ge \eta_\alpha n\} = 1. $$

Conditioning on this event and since $\phi$ is non-decreasing on $\mathbb{R}_+$:

$$ \inf_{\|S\|_F \ge \tau\sqrt{d}} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[G_\mu S]|) \ge n\eta_\alpha\phi(c_\alpha\tau). $$

Using Proposition 2.2 with $B = \{S : 0 \preceq S \preceq MI_d$ and $\|S\|_F \ge \tau\sqrt{d}\}$ we reach that, for all $\tau, M$, with probability $1 - o_d(1)$:

$$ \inf_{\substack{\mathrm{Sp}(S) \subseteq [0, M] \\ \|S\|_F \ge \tau\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\mathrm{Tr}[W_\mu S]|) \ge \frac{1}{2}\eta_\alpha\phi(c_\alpha\tau), $$

which ends the proof. $\square$

We now turn to the proof of Theorem 1.5.

*Proof of Theorem 1.5*. – Let $M > 0$. As in the proof of Corollary 2.8, we can assume without loss of generality that $\phi$ has bounded derivative: if it does not, it is always possible to lower bound $\phi$ by such a function.

Let $\delta \in (0, 1)$, and $S$ with $\mathrm{Sp}(S) \subseteq [0, M]$ and $|\mathrm{Tr}[S] - d| \ge \delta\sqrt{d}$. Notice that, defining $S' := \sqrt{d}S/|d - \mathrm{Tr}[S]| \succeq 0$, we have with $b := \mathrm{sign}(d - \mathrm{Tr}[S]) \in \{\pm 1\}$:

$$ \mathrm{Tr}[S'W_\mu] - b = \frac{x_\mu^\top S x_\mu - d}{|\mathrm{Tr}S - d|}, $$

and so since $\phi$ is non-decreasing:

$$ \phi\left(\sqrt{d}\left|\frac{x_\mu^\top S x_\mu}{d} - 1\right|\right) \ge \phi(\delta|\mathrm{Tr}(W_\mu S') - b|). $$

Moreover, $\mathrm{Sp}(S') \subseteq [0, M/\delta]$. Since this argument is valid for any $S$ with $\mathrm{Sp}(S) \subseteq [0, M]$ we get:

$$ \min_{\substack{\mathrm{Sp}(S) \subseteq [0, M] \\ |\mathrm{Tr}[S] - d| \ge \delta\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi\left(\sqrt{d}\left|\frac{x_\mu^\top S x_\mu}{d} - 1\right|\right) \ge \min_{b \in \{\pm 1\}} \min_{\substack{\mathrm{Sp}(S) \subseteq [0, M/\delta] \\ \|S\|_F \ge \tau\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(\delta|\mathrm{Tr}[W_\mu S] - b|). $$

Using Corollary 2.8 applied to $x \mapsto \phi(\delta x)$ there exists therefore $c = c(\alpha, \delta, \phi) > 0$ such that with probability $1 - o_d(1)$:

$$ \min_{\substack{\mathrm{Sp}(S) \subseteq [0, M] \\ |\mathrm{Tr}[S] - d| \ge \delta\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi\left(\sqrt{d}\left|\frac{x_\mu^\top S x_\mu}{d} - 1\right|\right) \ge c(\alpha, \delta, \phi). \quad (2.9) $$
Exact threshold for approximate ellipsoid fitting of random points

Let now $S \in S_d$ with $\text{Sp}(S) \subseteq [0, M]$ and $|\text{Tr}[S] - d| \le \delta\sqrt{d}$. Then:

$$ \text{Tr}[W_{\mu}S] = \sqrt{d} \left( \underbrace{\frac{x_{\mu}^{\top}Sx_{\mu}}{d} - 1}_{|\cdot| \le \delta} + \underbrace{\frac{d - \text{Tr}[S]}{\sqrt{d}},}_{|\cdot| \le \delta} \right), $$

so that

$$ \min_{\substack{\text{Sp}(S) \subseteq [0, M] \\ |\text{Tr}[S] - d| \le \delta\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi\left(\sqrt{d} \left|\frac{x_{\mu}^{\top}Sx_{\mu}}{d} - 1\right|\right) \ge \min_{\substack{\text{Sp}(S) \subseteq [0, M] \\ |\text{Tr}[S] - d| \le \delta\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\text{Tr}[W_{\mu}S]|) - \|\phi'\|_{\infty} \delta. \quad (2.10) $$

Notice that since $\delta < 1$, for large enough $d$ we have $|\text{Tr}[S] - d| \le \delta\sqrt{d} \Rightarrow \text{Tr}[S] \ge d/2$. If moreover $S \succeq 0$, by Cauchy-Schwarz we have $\|S\|_F \ge \text{Tr}[S]/\sqrt{d} \ge \sqrt{d}/2$. This implies:

$$ \min_{\substack{\text{Sp}(S) \subseteq [0, M] \\ |\text{Tr}[S] - d| \le \delta\sqrt{d}}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\text{Tr}[W_{\mu}S]|) \ge \min_{\substack{\text{Sp}(S) \subseteq [0, M] \\ \|S\|_F \ge \sqrt{d}/2}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\text{Tr}[W_{\mu}S]|). \quad (2.11) $$

Using Corollary 2.8 we can obtain $\varepsilon = \varepsilon(\alpha, \phi) > 0$ such that, with probability $1 - o_d(1)$, we have:

$$ \min_{\substack{\text{Sp}(S) \subseteq [0, M] \\ \|S\|_F \ge \sqrt{d}/2}} \frac{1}{n} \sum_{\mu=1}^{n} \phi(|\text{Tr}[W_{\mu}S]|) \ge \varepsilon. \quad (2.12) $$

Combining eq. (2.9) with all three equations (2.10), (2.11), (2.12), we get that for any $\delta > 0$, with probability $1 - o_d(1)$:

$$ \min_{\text{Sp}(S) \subseteq [0, M]} \frac{1}{n} \sum_{\mu=1}^{n} \phi \left( \sqrt{d} \left[ \frac{x_{\mu}^{\top} S x_{\mu}}{d} - 1 \right] \right) \ge \min[c(\alpha, \delta, \phi), \varepsilon(\alpha, \phi) - \delta \|\phi'\|_{\infty}]. $$

Taking $\delta := \min(1, \varepsilon(\alpha, \phi)/(2\|\phi'\|_{\infty})) > 0$ ends the proof. $\square$

# 3 The Gaussian equivalent problem

## 3.1 The satisfiable regime: Proof of Proposition 2.3

### 3.1.1 Gordon's min-max theorem

We will use the Gaussian min-max theorem of Gordon [14], as stated in [35, 34]:

**Proposition 3.1 (Gaussian min-max theorem [14, 35, 34]).** Let $n, p \ge 1$, $W \in \mathbb{R}^{n \times p}$ an i.i.d. standard normal matrix, and $g \in \mathbb{R}^n$, $h \in \mathbb{R}^p$ two independent vectors with i.i.d. $\mathcal{N}(0, 1)$ coordinates. Let $S_v, S_u$ be two compact subsets respectively of $\mathbb{R}^p$ and $\mathbb{R}^n$, and let $\psi: S_v \times S_u \to \mathbb{R}$ a continuous function. We define the two optimization problems:

$$ \left\{ \begin{array}{ll} C(W) & := \min_{v \in S_v} \max_{u \in S_u} \{u^\top W v + \psi(v, u)\}, \\ C(g, h) & := \min_{v \in S_v} \max_{u \in S_u} \{\|u\|_2 h^\top v + \|v\|_2 g^\top u + \psi(v, u)\}. \end{array} \right. $$

Then:

(i) For all $t \in \mathbb{R}$, one has
$$ \mathbb{P}[C(W) < t] \le 2\mathbb{P}[C(g, h) \le t]. $$

(ii) Assume that $S_v, S_u$ are convex and that $\psi$ is convex-concave on $S_v \times S_u$. Then for all $t \in \mathbb{R}$:
$$ \mathbb{P}[C(W) > t] \le 2\mathbb{P}[C(g, h) \ge t]. $$
### 3.1.2 Gordon's min-max inequality and random geometry

We first introduce the notion of Gaussian width of a convex cone.

**Definition 3.2 (Gaussian width).** For $p \ge 1$, and a closed convex cone $K \subseteq \mathbb{R}^p$, we define its Gaussian width as

$$ \omega(K) := \mathbb{E} \max_{x \in K \cap \mathbb{S}^{p-1}} \langle g, x \rangle, $$

for $g \sim \mathcal{N}(0, I_p)$.

We show now a general result leveraging Gordon's min-max inequality to prove the existence of a solution to a general type of random geometry problem. Such applications are classical, and we show here that one can assume furthermore that the solution is bounded.

**Lemma 3.3.** Let $n, p \ge 1$, and $(g_\mu)_{\mu=1}^n$ i.i.d. $\mathcal{N}(0, I_p)$. We define $V := \{x \in \mathbb{R}^p : \forall \mu \in [n], \langle g_\mu, x \rangle = 1\}$. Let $K \subseteq \mathbb{R}^p$ be a closed convex cone, with Gaussian width $\omega(K)$. Assume that there exists $\varepsilon \in (0, 1)$ such that $n \le (1 - \varepsilon) \omega(K)^2$ as $n \to \infty$. Then:

$$ \lim_{n \to \infty} \mathbb{P} \left\{ \exists x \in K \cap V \text{ s.t. } \|x\|_2 \le \frac{2}{\sqrt{\varepsilon}} \right\} = 1. \quad (3.1) $$

*Proof of Lemma 3.3.* Let us denote, for $A > 0$:

$$ P_n(A) := \mathbb{P} \{ \exists x \in K \cap V \text{ s.t. } \|x\|_2 \le A \}, $$

and define $G \in \mathbb{R}^{n \times p}$ as the Gaussian matrix with $g_\mu$ as its $\mu$-th row. By elementary compactness and duality arguments, we have:

$$ 1 - P_n(A) = \mathbb{P} \left[ \min_{\substack{x \in K \\ \|x\|_2 \le A}} \|Gx - \mathbf{1}_n\|_2 > 0 \right] = \mathbb{P} \left[ \min_{\substack{x \in K \\ \|x\|_2 \le A}} \max_{\substack{\|\lambda\|_2 \le 1 \\ \|\lambda\|_2 \ge 1}} \{-\lambda^\top \mathbf{1}_n + \lambda^\top Gx\} > 0 \right], $$

for $G \in \mathbb{R}^{n \times p}$ with i.i.d. $\mathcal{N}(0, 1)$ elements. By dominated convergence we have then

$$ 1 - P_n(A) = \lim_{\eta \to 0} \mathbb{P} \left[ \min_{\substack{x \in K \\ \|x\|_2 \le A}} \max_{\substack{\|\lambda\|_2 \le 1 \\ \|\lambda\|_2 \ge 1}} \{-\lambda^\top \mathbf{1}_n + \lambda^\top Gx\} > \eta \right]. \quad (3.2) $$

Note that in eq. (3.2), both $x$ and $\lambda$ belong to a convex and compact set (since $K$ is closed and convex), and $\psi(x, \lambda) = -\lambda^\top \mathbf{1}_n$ is clearly convex-concave. We can thus apply item (ii) of Proposition 3.1:

$$ 1 - P_n(A) \le 2 \lim_{\eta \to 0} \mathbb{P} \left[ \min_{\substack{x \in K \\ \|x\|_2 \le A}} \max_{\substack{\|\lambda\|_2 \le 1 \\ \|x\|_2 \ge A}} \{-\lambda^\top \mathbf{1}_n + \|\lambda\|_2 g^\top x + \|x\|_2 \lambda^\top h\} \ge \eta \right], \quad (3.3) $$

with $g \sim \mathcal{N}(0, I_p)$ and $h \sim \mathcal{N}(0, I_n)$. We then control the right-hand-side of the last equation, using that $K$ is a cone:

$$ \begin{aligned} \min_{\substack{x \in K \\ \|x\|_2 \le A}} \max_{\substack{\|\lambda\|_2 \le 1 \\ \|x\|_2 \ge A}} \{-\lambda^\top \mathbf{1}_n + \|\lambda\|_2 g^\top x + \|x\|_2 \lambda^\top h\} &= \min_{\substack{x \in K \\ \|x\|_2 \le A}} \max\{0, \|\|x\|_2 h - \mathbf{1}_n\|_2 + g^\top x\}, \\ &= \max\left\{0, \min_{\substack{x \in K \\ \|x\|_2 \le A}} \left[\|\|x\|_2 h - \mathbf{1}_n\|_2 + g^\top x\right]\right\}, \\ &= \max\left\{0, \min_{v \in [0, A]} \left[\|v h - \mathbf{1}_n\|_2 + v \min_{x \in K \cap \mathbb{S}^{p-1}} g^\top x\right]\right\}. \end{aligned} \quad (3.4) $$

Note that $g \to \max_{x \in K \cap \mathbb{S}^{p-1}} [g^\top x]$ is 1-Lipschitz, and in particular concentrates on its average, which by definition is the Gaussian width $\omega(K)$. We use the classical result (see e.g. Theorem 3.25 of [37]):
**Theorem 3.4.** Let $X_1, \cdots, X_n \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 1)$. Let $f: \mathbb{R}^n \to \mathbb{R}$ a Lipschitz function. Then for all $t \ge 0$:

$$ \mathbb{P}[f(X_1, \cdots, X_n) - \mathbb{E}f(X_1, \cdots, X_n) \ge t] \le \exp \left\{ -\frac{t^2}{2\|f\|_L^2} \right\}. $$

Therefore, for $\delta \in (0, \omega(K))$, we have<fnref n="5" />:

$$ \mathbb{P} \left\{ \min_{x \in K \cap S^{p-1}} [g^\top x] \geq -\omega(K) + \delta \right\} \leq e^{-\delta^2/2}. \quad (3.5) $$

From eqs. (3.3), (3.4) and (3.5) we have:

$$ 1 - P_n(A) \le 2 \lim_{\eta \to 0} \mathbb{P} \left[ \max \left\{ 0, \min_{v \in [0, A]} \left[ \|vh - \mathbf{1}_n\|_2 + v(-\omega(K) + \delta) \right] \right\} \ge \eta \right] + 2e^{-\delta^2/2}. \quad (3.6) $$

Recall that we assumed $n \le (1 - \varepsilon) \omega(K)^2$ and $n \to \infty$. Therefore, for $n \ge n_0(\varepsilon, \delta)$ large enough we can assume $n \le (1 - \varepsilon/2) [\omega(K) - \delta]^2$. Let $v^* = v^*(\varepsilon) = \sqrt{(4 - \varepsilon)/\varepsilon}$ such that:

$$ \left(1 - \frac{\varepsilon}{4}\right) \mathbb{E}_{X \sim \mathcal{N}(0,1)} \left[ (v^* X - 1)^2 \right] = (v^*)^2. $$

Thus, for $A = v^*(\varepsilon)$, we have from eq. (3.6):

$$ 1 - P_n(v^*) \le 2 \lim_{\eta \to 0} \mathbb{P} \left[ \max \left\{ 0, \left[ \|v^*h - \mathbf{1}_n\|_2 + v^*(-\omega(K) + \delta) \right] \right\} \ge \eta \right] + 2e^{-\delta^2/2}. \quad (3.7) $$

By the law of large numbers we have ($\xrightarrow{P}$ denotes convergence in probability):

$$ \frac{1}{\sqrt{n}} \|v^*h - \mathbf{1}_n\|_2 \xrightarrow{P} \sqrt{\mathbb{E}[(v^*X - 1)^2]} = \frac{v^*}{\sqrt{1 - \frac{\varepsilon}{4}}} < \frac{v^*}{\sqrt{1 - \frac{\varepsilon}{3}}}. $$

In particular, with probability $1 - o_n(1)$, we have

$$ \|v^*h - \mathbf{1}_n\|_2 + v^*(-\omega(K) + \delta) \le v^* \sqrt{n} \left[ \left(1 - \frac{\varepsilon}{3}\right)^{-1/2} - \left(1 - \frac{\varepsilon}{2}\right)^{-1/2} \right] < 0. $$

Therefore, we have by eq. (3.7):

$$ 1 - P_n(v^*) \le o_n(1) + 2e^{-\delta^2/2}. $$

Taking the limit $n \to \infty$ and then $\delta \to \infty$ finishes the proof<fnref n="6" /> (notice that $v^* \le 2/\sqrt{\varepsilon}$). $\square$

### 3.1.3 The cone of positive matrices with bounded condition number

We study here the Gaussian width of the convex cone of positive semidefinite matrices with bounded condition number. We start with a classical result on the Gaussian width of $S_d^+$ [7, 2], we refer the reader to Proposition 10.2 of [2] for a proof.

**Proposition 3.5 (Gaussian width of $S_d^+$).** The Gaussian width of $S_d^+$ satisfies:

$$ \sqrt{\frac{d(d+1)}{4} - 1} \le \omega(S_d^+) \le \sqrt{\frac{d(d+1)}{4}}. $$

In particular, notice that $\omega(S_d^+) \sim d/2$ as $d \to \infty$. We generalize this result by asking that the matrices have bounded condition number.

<footnote n="5">⁵Since $g \stackrel{d}{=} -g$, $\min_{x \in K \cap S^{p-1}} [g^\top x] \stackrel{d}{=} -\max_{x \in K \cap S^{p-1}} [g^\top x]$.</footnote>

<footnote n="6">⁶Recall that $\delta < \omega(K)$ but $\omega(K) \to \infty$ as $n \to \infty$ by hypothesis.</footnote>
**Lemma 3.6** (Gaussian width of PSD matrices with bounded condition number). For any $\kappa \ge 1$, define $K_\kappa := \{S \in S_d^+ : \lambda_{\max}(S) \le \kappa \lambda_{\min}(S)\}$. Then $K_\kappa$ is a closed convex cone, and its Gaussian width satisfies

$$ \liminf_{d \to \infty} \frac{2\omega(K_\kappa)}{d} = f(\kappa), $$

where $\kappa \to f(\kappa) \in [0, 1]$ is non-decreasing, with $\lim_{\kappa \to \infty} f(\kappa) = 1$.

**Proof of Lemma 3.6.** The fact that $K_\kappa$ is a closed convex cone is easy to verify. Moreover, for any $\kappa \le \kappa'$ we have $K_\kappa \subseteq K_{\kappa'} \subseteq S_d^+$, and $\omega(S_d^+) \sim d/2$ by Proposition 3.5, so $\kappa \mapsto f(\kappa) \in [0, 1]$, and $f$ is non-decreasing. To finish the proof, we show that $f(\kappa) \to 1$ as $\kappa \to \infty$. We let $\kappa > 1$. To identify $S_d$ with $\mathbb{R}^{d(d+1)/2}$, we use the matrix flattening function, for $M \in S_d$:

$$ \begin{aligned} \mathrm{vec}(M) &:= ((\sqrt{2}M_{ab})_{1 \le a < b \le d}, (M_{aa})_{a=1}^d) \in \mathbb{R}^{d(d+1)/2}, \quad (3.8) \\ &= ((2 - \delta_{ab})^{1/2} M_{ab})_{a \le b}. \end{aligned} $$

It is an isometry $(\langle \mathrm{vec}(M), \mathrm{vec}(N) \rangle = \mathrm{Tr}[MN])$, and if $Z \sim \mathrm{GOE}(d)$ then the entries of $\mathrm{vec}(Z)$ satisfy $\mathrm{vec}(Z)_k \stackrel{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0, 2/d)$. We thus reach:

$$ \omega(K_\kappa) := \mathrm{E} \max_{\substack{S \in K_\kappa \\ \|S\|_F^2 = 2d}} \left\{ \frac{1}{2} \mathrm{Tr}[ZS] \right\}, $$

in which $Z \sim \mathrm{GOE}(d)$, cf. Definition 2.1. Letting $z_1 \ge \dots \ge z_d$ be the eigenvalues of $Z$, by Wigner's theorem [3] $(1/d) \sum_i \delta_{zi}$ weakly converges as $d \to \infty$ (a.s.) to $\sigma_{\mathrm{s.c.}}(dx) = (2\pi)^{-1} \sqrt{4-x^2} \mathbf{1}\{|x| \le 2\}dx$. Moreover, we have (taking $S$ having same eigenvectors as $Z$)$^7$:

$$ \omega(K_\kappa) \ge \mathrm{E} \max_{\substack{\lambda_1 \ge \dots \ge \lambda_d \ge 0 \\ \sum_i \lambda_i^2 \le 2d \\ \lambda_1 \le \kappa \lambda_d}} \left\{ \frac{1}{2} \sum_{i=1}^d \lambda_i z_i \right\}. \quad (3.9) $$

Let us now sketch the end of the proof. We define

$$ \left\{ \begin{aligned} \gamma(\kappa) &:= \sqrt{\frac{2}{\int_{2\kappa^{-1}}^2 x^2 \sigma_{\mathrm{s.c.}}(dx) + \frac{4}{\kappa^2} \int_{-2}^{2\kappa^{-1}} x \sigma_{\mathrm{s.c.}}(dx)}}, \\ \lambda_i^* &:= \gamma(\kappa) \left[ z_i \mathbf{1}\{z_i \ge 2\kappa^{-1}\} + \frac{2}{\kappa} \mathbf{1}\{z_i < 2\kappa^{-1}\} \right]. \end{aligned} \right. \quad (3.10) $$

Let $\varepsilon > 0$. Since one can show that $z_1 \to 2$ a.s. as $d \to \infty$ [3], with high probability we have $\lambda_1^* \le \kappa(1+\varepsilon)\lambda_d^*$. Moreover, one checks easily that $d^{-1} \sum_{i=1}^d [\lambda_i^*]^2 \xrightarrow{P} 2$ as $d \to \infty$. Letting $\mu_i := \lambda_i^*/\sqrt{1+\varepsilon}$, we can therefore use $\{\mu_i\}$ to lower bound $\omega(K_\kappa)$ as $d \to \infty$, with $\kappa_\varepsilon := \kappa(1+\varepsilon)$. This yields that, for any $\varepsilon > 0$:

$$ f(\kappa_\varepsilon) = \liminf_{d \to \infty} \frac{2\omega(K_{\kappa_\varepsilon})}{d} \ge \frac{1}{\sqrt{1+\varepsilon}} \sqrt{\frac{2 \left[ \int_{2\kappa^{-1}}^2 x^2 \sigma_{\mathrm{s.c.}}(dx) + \frac{2}{\kappa} \int_{-2}^{2\kappa^{-1}} x \sigma_{\mathrm{s.c.}}(dx) \right]^2}{\int_{2\kappa^{-1}}^2 x^2 \sigma_{\mathrm{s.c.}}(dx) + \frac{4}{\kappa^2} \int_{-2}^{2\kappa^{-1}} x \sigma_{\mathrm{s.c.}}(dx)}}. \quad (3.11) $$

Taking the limits $\kappa \to \infty$ and $\varepsilon \to 0$ in eq. (3.11) yields $\lim_{\kappa \to \infty} f(\kappa) \ge 1$, which ends the proof. $\square$

<footnote>$^7$Notice that we replaced $\|S\|_F^2 = 2d$ by $\|S\|_F^2 \le 2d$ since w.h.p. one can always find $S \in K_\kappa$ such that $\mathrm{Tr}[SZ] > 0$.</footnote>
### 3.1.4 Proof of Proposition 2.3

We can now complete the proof of Proposition 2.3. Recall that

$$V = \{S \in S_d : \forall \mu \in [n], \mathrm{Tr}[G_{\mu}S] = 1\}.$$

Since $\alpha = n/d^2 < 1/4$, by Lemma 3.6, we can find $\kappa = \kappa(\alpha)$ and $\varepsilon = \varepsilon(\alpha)$ such that $n \le (1-\varepsilon)\omega(K_\kappa)^2$ for $n$ large enough. Therefore, by Lemma 3.3 there exists $A = A(\alpha) > 0$ such that:

$$\lim_{d \to \infty} \mathbb{P} \{ \exists S \in V \text{ s.t. } S \succeq 0 \text{ and } \mathrm{Tr}[S^2] \le Ad \text{ and } \lambda_{\max}(S) \le \kappa \lambda_{\min}(S) \} = 1. \quad (3.12)$$

Notice that $H := n^{-1/2} \sum_{\mu=1}^n G_\mu \sim \mathrm{GOE}(d)$, and thus $\mathbb{P}[\|H\|_{\mathrm{op}} \le 3] = 1 - o_d(1)$ [38]. Conditioning on this event, let $S \in V$. Then $\mathrm{Tr}[HS] = \sqrt{n} = \sqrt{\alpha}d$, and thus by duality of $\| \cdot \|_{\mathrm{op}}$ and $\| \cdot \|_{S_1}$:

$$\mathrm{Tr}|S| \ge \frac{1}{\|H\|_{\mathrm{op}}} |\mathrm{Tr}[HS]| \ge \frac{\sqrt{\alpha}}{3} d.$$

The proof of Proposition 2.3 is then ended by noticing that:

$$\mathrm{Sp}(S) \subseteq [\lambda_{-}, \lambda_{+}] \leftarrow \begin{cases} S \succeq 0, \\ \mathrm{Tr}[S^2] \le A(\alpha)d, \\ \lambda_{\max}(S) \le \kappa(\alpha)\lambda_{\min}(S), \\ \mathrm{Tr}[S] \ge B(\alpha)d, \end{cases}$$

for some $0 < \lambda_{-} \le \lambda_{+}$ depending only on $\alpha$. $\square$

## 3.2 The unsatisfiable regime: Proof of Proposition 2.4

We will show the following general result on the unsatisfiability of approximate versions of a general class of random geometry problems.

**Proposition 3.7.** Let $b \in \mathbb{R}$, $p, n \to \infty$, $K \subseteq \mathbb{R}^p$ a closed convex cone, with Gaussian width $\omega(K)$, $(a_\mu)_{\mu=1}^n \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, I_p)$, and denote $C_\mu^{(b)}(x) := |a_\mu^\top x - b|$ the $\mu$-th "constraint". We denote

$$V_b := \{x \in \mathbb{R}^p : \forall \mu \in [n], C_\mu^{(b)}(x) = 0\}$$

a randomly-oriented affine subspace. Then we have the following:

(i) Assume that $b \ne 0$. Then

(a) If there exists $\varepsilon > 0$ such that $n \le (1-\varepsilon)\omega(K)^2$ as $n \to \infty$, then $\mathbb{P}[V_b \cap K \ne \emptyset] \to_{n \to \infty} 1$.

(b) If there exists $\varepsilon > 0$ such that $n \ge (1+\varepsilon)\omega(K)^2$ as $n \to \infty$, then there exist $c = c(\varepsilon, b) > 0$ and $\eta = \eta(\varepsilon, b) \in (0, 1)$ such that

$$\lim_{n \to \infty} \mathbb{P}\{\forall x \in K : \#\{\mu \in [n] : C_\mu^{(b)}(x) > c\} \ge \eta n\} = 1.$$

(ii) Assume that $b = 0$. Note that $V_0$ is a linear subspace, and $V_0 \cap K$ is a closed convex cone.

(a) Assume that $n \le (1-\varepsilon)\omega(K)^2$ for some $\varepsilon > 0$. Then as $n \to \infty$, $\mathbb{P}[V_0 \cap K \cap S^{p-1} \ne \emptyset] \to 1$.

(b) Assume that $n \ge (1+\varepsilon)\omega(K)^2$ for some $\varepsilon > 0$. Then there exist $c = c(\varepsilon, b) > 0$ and $\eta = \eta(\varepsilon, b) \in (0, 1)$ such that, with probability $1 - o_n(1)$, the following holds for all $\tau \ge 0$:

$$\max_{x \in K} \|x\|_2 \le \tau. \\ \#\{\mu \in [n] : C_\mu^{(0)}(x) > c\} < \eta n$$
It is clear that Proposition 3.7 ends the proof of Proposition 2.4. Indeed, seen as an element of $\mathbb{R}^{d(d+1)/2}$, $\sqrt{d/2}G_{\mu}^{\text{i.i.d.}} \sim \mathcal{N}(0, I_{d(d+1)/2})$, see the canonical embedding in eq. (3.8). By Proposition 3.5, we have $\omega(S_d^+)^2 = d^2/4 + o(d^2)$, and thus we can apply Proposition 3.7 with $p = d(d+1)/2$. The difference $\sqrt{d}$ in normalization in point (ii) of Proposition 2.4 comes from the additional $\sqrt{d}$ factor that arises when relating $G_{\mu}$ to a standard Gaussian.

We now focus on proving Proposition 3.7.

### 3.2.1 Proof of Proposition 3.7

We first show (i), assuming $b \neq 0$. Results of [7, 2] show that $V_b \cap K \neq \emptyset$ with high probability if $n \le (1 - \epsilon)\omega(K)^2$ (see e.g. Theorem 8.1 of [2]), i.e. point (a). While the converse is also shown in these works for $n \ge (1 + \epsilon)\omega(K)^2$, here we wish to prove the stronger statement (b). Assume therefore that $n \ge (1 + \epsilon)\omega(K)^2$. By the union bound, for all $c \ge 0$ and $\eta \in (0, 1)$:

$$ 
\begin{align*}
& \mathbb{P}(\exists x \in K : \#\{\mu \in [n] : C_{\mu}^{(b)}(x) > c\} < \eta n) \\
&= \mathbb{P}(\exists x \in K, \exists S \subseteq [n] : |S| > (1 - \eta)n \text{ and } \forall \mu \in S, C_{\mu}^{(b)}(x) \le c) \\
&\le \sum_{\substack{S \subseteq [n] \\ |S| > (1-\eta)n}} \mathbb{P}(\exists x \in K : \forall \mu \in S, C_{\mu}^{(b)}(x) \le c), \\
&\stackrel{(a)}{\le} \left[ \sum_{k < \eta \cdot n} \binom{n}{k} \right] \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \le c), \\
&\stackrel{(b)}{\le} \exp\left\{\eta n \log \frac{e}{\eta}\right\} \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \le c). \tag{3.13}
\end{align*}
$$

We used that $a_{\mu}$ are i.i.d. in (a), and the bound $\sum_{i=0}^k \binom{n}{i} \le (en/k)^k$ in (b). We now make use of the following lemma (proven later on).

**Lemma 3.8.** Recall that $n \ge (1+\epsilon)\omega(K)^2$. There exist $c_1, c_2 > 0$ and $\eta_0 \in (0, 1)$ depending only on $\epsilon$ such that for any $\eta \in (0, \eta_0)$:

$$ \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \le c_1 \cdot b) \le 2 \exp\{-nc_2\}. $$

Applying Lemma 3.8 in eq. (3.13), we can consider $\eta = \eta(\epsilon, b) \in (0, 1/2)$ small enough, such that $\eta < \eta_0$ and $\eta \log(e/\eta) \le c_2/2$. This yields then that

$$ \mathbb{P}(\exists x \in K : \#\{\mu \in [n] : C_{\mu}^{(b)}(x) > c_1 \cdot b\} < \eta n) \le 2 \exp\{-nc_2/2\} \to 0, $$

and ends the proof. We now prove (ii) of Proposition 3.7, assuming $b = 0$. (a) is here a simple consequence of the usual Gordon’s “escape through a mesh” theorem [14], so we focus on (b), assuming $n \ge (1 + \epsilon)\omega(K)^2$. Note that since K is a cone, we have for all $c \ge 0$, $\eta \in (0, 1)$:

$$ 
\begin{align}
& \sup_{x \in K} \|x\|_2 \nonumber \\
& \quad \#\{\mu \in [n] : C_{\mu}^{(0)}(x) > c\} < \eta n \nonumber \\
& = \sup\{v \ge 0 : \exists x \in K \cap \mathbb{S}^{p-1} \text{ s.t. } \#\{\mu \in [n] : C_{\mu}^{(0)}(x) > c/v\} < \eta n\}. \tag{3.14}
\end{align}
$$

We now use the following counterpart to Lemma 3.8 in the case $b = 0$, also proven later:

**Lemma 3.9.** Recall that $n \ge (1+\epsilon)\omega(K)^2$. There exist $c_1, c_2 > 0$ and $\eta_0 \in (0, 1)$ depending only on $\epsilon$ such that for any $\eta \in (0, \eta_0)$:

$$ \mathbb{P}(\exists x \in K \cap \mathbb{S}^{p-1} : \|\{a_{\mu}^{\top}x\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \le c_1) \le 2 \exp\{-nc_2\}. $$
Exact threshold for approximate ellipsoid fitting of random points

Repeating the same reasoning as in the $b \neq 0$ case, we can then find $c = c(\varepsilon) > 0$ and $\eta = \eta(\varepsilon) \in (0, 1/2)$ such that with probability $1 - o_n(1)$:

$$ \forall x \in K \cap S^{p-1} : \#\{\mu \in [n] : C_{\mu}^{(0)}(x) > c\} \geq \eta n. $$

Plugging this in eq. (3.14) yields that with probability $1 - o_n(1)$, for all $\tau \geq 0$:

$$ \max_{x \in K} \|x\|_2 \leq \tau, \\ \#\{\mu \in [n] : C_{\mu}^{(0)}(x) > c\tau\} < \eta n $$

which ends the proof.

We now prove the two Lemmas 3.8 and 3.9.

<figure><img src="image_6.png" /></figure>

### 3.2.2 Proofs of Lemma 3.8 and 3.9

*Proof of Lemma 3.8.* Note that for all $t \geq 0$ and $\eta \in (0, 1)$:

$$ \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \leq t) = \mathbb{P}[\exists x \in K : \|Gx - b1_m\|_{\infty} \leq t], \quad (3.15) $$

with $m := n(1 - \eta)$, $G \in \mathbb{R}^{m \times p}$ an i.i.d. $\mathcal{N}(0, 1)$ matrix, and $1_m$ the all-ones vector. We thus have:

$$ \begin{align} & \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \leq t) \nonumber \\ & \stackrel{(a)}{=} \lim_{A \to \infty} \mathbb{P}[\exists x \in K : \|x\|_2 \leq A \text{ and } \|Gx - b1_m\|_{\infty} \leq t], \nonumber \\ & \stackrel{(b)}{=} \lim_{A \to \infty} \mathbb{P}\left[ \min_{x \in K} \|Gx - b1_m\|_{\infty} \leq t \right], \tag{3.16} \end{align} $$

where (a) follows from dominated convergence, and (b) uses that the minimum is now over a compact set since $K$ is closed. Since $\| \cdot \|_{\infty}$ and $\| \cdot \|_1$ are dual norms, we have for all $x \in K$:

$$ \|Gx - b1_m\|_{\infty} = \max_{\substack{\lambda \in \mathbb{R}^m \\ \|\lambda\|_1 \leq 1}} [-b\lambda^{\top}1_m + \lambda^{\top}Gx]. $$

We can now use the Gaussian min-max inequality (Proposition 3.1), which, together with eq. (3.16), implies:

$$ \mathbb{P}(\exists x \in K : \|\{a_{\mu}^{\top}x - b\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \leq t) \leq \lim_{A \to \infty} 2\mathbb{P}[\gamma_A(g, h) \leq t] \stackrel{(a)}{\leq} 2\mathbb{P}[\gamma(g, h) \leq t]. $$

Here we defined:

$$ \gamma(g, h) := \inf_{x \in K} \max_{\substack{\lambda \in \mathbb{R}^m \\ \|\lambda\|_1 \leq 1}} [-b\lambda^{\top}1_m + \|\lambda\|_2 g^{\top}x + \|x\|_2 h^{\top}\lambda], \quad (3.17) $$

and $\gamma_A$ is defined by restricting the infimum to $\|x\|_2 \leq A$. Moreover, $g \sim \mathcal{N}(0, I_p)$, $h \sim \mathcal{N}(0, I_m)$. The inequality (a) holds since $\gamma(g, h) \leq \gamma_A(g, h)$ for all $A > 0$. To conclude the proof, it therefore suffices to show:

$$ \mathbb{P}[\gamma(g, h) \leq c_1 b] \leq 2 \exp\{-nc_2\}, \quad (3.18) $$

for $c_1, c_2$ small enough (depending on $\varepsilon, b$). We use again that $g \to \max_{x \in K \cap S^{p-1}} [g^\top x]$ is 1-Lipschitz, and in particular concentrates on the Gaussian width by Theorem 3.4. Using that $g$ is distributed as $-g$, this implies that for any $u > 0$:

$$ \mathbb{P}\left\{\min_{x \in K \cap S^{p-1}} [g^\top x] \leq -\omega(K) - u\right\} \leq e^{-u^2/2}. $$
Exact threshold for approximate ellipsoid fitting of random points

Since $\omega(K) \le \sqrt{n/(1+\varepsilon)}$ by hypothesis, we can fix $\delta = \delta(\varepsilon) > 0$ and $\eta_0 = \eta_0(\varepsilon) > 0$ such that for $n$ large enough we have for $\eta < \eta_0$: $\omega(K) + \delta\sqrt{m} \le \sqrt{m/(1+\varepsilon/2)}$ (recall that $m = (1-\eta)n$). Thus, since $K$ is a cone, and using the max-min inequality, we have with probability at least $1 - e^{-n(1-\eta_0)\delta^2/2}$:

$$ \gamma(g, h) \ge \inf_{\substack{v \ge 0 \\ \lambda \in \mathbb{R}^m \\ \|\lambda\|_1 \le 1}} \max \left[ -b\lambda^\top \mathbf{1}_m + v \left( h^\top \lambda - \|\lambda\|_2 (\omega(K) + \delta\sqrt{m}) \right) \right]. \quad (3.19) $$

Let us now assume that $b > 0$, and let $X \sim N(0, 1)$, and $D := E[|X|] = \sqrt{2/\pi}$. We pick $\sigma = \sigma(\varepsilon) \in (0, 1)$ (its choice will be constrained later on), and define $A_\varepsilon$ by:

$$ E[X^2 \mathbf{1}\{X \le A_\varepsilon\}] = \sigma(\varepsilon). \quad (3.20) $$

Finally, we define $\lambda^* = \lambda^*(h) \in \mathbb{R}^m$ by

$$ \lambda_{\mu}^{*} := \frac{1}{Dm} h_{\mu} \mathbf{1}\{h_{\mu} \le A_{\varepsilon}\}. \quad (3.21) $$

It is a simple exercise based on Hoeffding's and Bernstein's inequalities [38] to check that for any $u > 0$ (recall that $m = (1-\eta)n \ge (1-\eta_0(\varepsilon))n$):

$$ \left\{
\begin{array}{ll}
\mathbb{P}[\|\lambda^*\|_1 \le 1] & \ge 1 - \exp\{-C_1 n\}, \\
\mathbb{P}\left[h^\top \lambda^* - \frac{\sigma(\varepsilon)^2}{D} \le -u\right] & \le \exp\{-C_2 n \min(u^2, u)\}, \\
\mathbb{P}\left[\|\lambda^*\|_2^2 - \frac{\sigma(\varepsilon)^2}{mD^2} \ge \frac{u}{n}\right] & \le \exp\{-C_3 n \min(u^2, u)\}, \\
\mathbb{P}[\mathbf{1}_m \lambda^* \ge -C_4] & \le \exp\{-C_5 n\},
\end{array}
\right.
\quad (3.22) $$

for some positive constants $(C_a)_{a=1}^5$, all depending on $\varepsilon$. In particular, the first three lines of eq. (3.22) imply that for all $u \in (0, 1)$, with probability at least $1 - 3 \exp\{-C(\varepsilon)nu^2\}$:

$$ \|\lambda^*\|_1 \le 1 \quad \text{and} \quad \frac{h^\top \lambda^*}{\|\lambda^*\|_2} \frac{1}{\omega(K) + \delta\sqrt{m}} \ge \frac{\sigma(\varepsilon)^2/D - u}{\sqrt{\sigma(\varepsilon)^2/D^2 + u}} \sqrt{1 + \frac{\varepsilon}{2}}, \quad (3.23) $$

in which we used that $\omega(K) + \delta\sqrt{m} \le \sqrt{m}(1+\varepsilon/2)^{-1/2}$, and $m/n \le 1$. We can choose $\sigma(\varepsilon) \in (0, 1)$ sufficiently close to 1, and $u(\varepsilon) \in (0, 1)$ sufficiently close to 0 such that the right-hand side of eq. (3.23) is greater than 1. Combining it with the last equation of eq. (3.22) and the lower bound of eq. (3.19), we get that (with new constants $c_1, c_2$ depending on $\varepsilon$), with probability at least $1 - 2 \exp\{-c_2(\varepsilon)n\}$:

$$ \gamma(g, h) \ge bc_1(\varepsilon), $$

which implies eq. (3.18) and ends the proof. The case $b < 0$ is treated similarly, constraining $h_\mu \ge -A_\varepsilon$ rather than $h_\mu \le A_\varepsilon$ in eq. (3.21). $\square$

**Proof of Lemma 3.9.** Let $t \ge 0$. Repeating the same arguments as in the proof of Lemma 3.8 one obtains that

$$ \mathbb{P}(\exists x \in K \cap S^{p-1} : \|\{a_{\mu}^{\top} x\}_{\mu=1}^{(1-\eta)n}\|_{\infty} \le t) \le 2\mathbb{P}\left[\underbrace{\min_{x \in K \cap S^{p-1}} \max_{\lambda \in \mathbb{R}^m \atop \|\lambda\|_1 \le 1} \{\|\lambda\|_2 g^{\top} x + h^{\top} \lambda\} \le t}_{=: \gamma(g, h)}\right]. $$

Again, we can fix $\eta_0(\varepsilon) > 0$ and $\delta(\varepsilon) > 0$ such that for $\eta < \eta_0$ and $n$ large enough we have $\omega(K) + \delta\sqrt{m} \le \sqrt{m}[1 + \varepsilon/2]^{-1/2}$. By the max-min inequality and the concentration of the Gaussian width, this implies that with probability at least $1 - e^{-n(1-\eta_0)\delta^2}$:

$$ \gamma(g, h) \ge \max_{\substack{\lambda \in \mathbb{R}^m \\ \|\lambda\|_1 \le 1}} \left[ h^\top \lambda - \|\lambda\|_2 (\omega(K) + \delta\sqrt{m}) \right]. \quad (3.24) $$
Defining again $D := \sqrt{2/\pi}$ so that $D = E[|X|]$ for $X \sim \mathcal{N}(0, 1)$, we now define $\lambda^*$ as:

$$ \lambda_{\mu}^{*} := \frac{1}{Dm} h_{\mu}. $$

We have the counterpart to eq. (3.22) for this case: for any $u > 0$ and $\tau > 0$,

$$ \left\{ \begin{array}{ll} \mathbb{P}[\|\lambda^*\|_1 \le 1 + \tau] & \ge 1 - \exp\{-C_1 n \tau^2\}, \\ \mathbb{P}\left[h^T \lambda^* - \frac{1}{D} \le -u\right] & \le \exp\{-C_2 n \min(u^2, u)\}, \\ \mathbb{P}\left[\|\lambda^*\|_2^2 - \frac{1}{mD^2} \ge \frac{u}{n}\right] & \le \exp\{-C_3 n \min(u^2, u)\}, \end{array} \right. \quad (3.25) $$

for some $(C_a)_{a=1}^3$ depending on $\varepsilon$. We can fix $u = u(\varepsilon) > 0$ such that

$$ D^{-1} - u - \sqrt{\frac{u + D^{-2}}{1 + \varepsilon/2}} =: 2c_1(\varepsilon) > 0, $$

since the limit as $u \to 0$ of the left-hand side is strictly positive. Letting $\tau = 1$, we finally get that with probability at least $1 - 3 \exp(-c_2(\varepsilon)n)$ we can lower bound (using $\lambda = \lambda^*/2$ such that $\|\lambda\|_1 \le 1$)

$$ \begin{aligned} \gamma(g, h) &\ge \frac{D^{-1} - u}{2} - \frac{1}{2} \sqrt{\frac{u}{n} + \frac{1}{mD^2}} (\omega(K) + \delta\sqrt{m}), \\ &\ge \frac{D^{-1} - u}{2} - \frac{1}{2} \sqrt{\frac{u + D^{-2}}{1 + \varepsilon/2}}, \\ &\ge c_1(\varepsilon). \end{aligned} $$

This ends the proof. $\square$

<figure><img src="image_7.png" /></figure>

# 4 Universality: Proof of Proposition 2.2

This section is devoted to the proof of Proposition 2.2. We first show in Section 4.1 a critical result on the Lipschitz constant of the “error” function appearing in eq. (2.4). This requires controlling a random process on the operator norm sphere, which is also useful in the proof of Theorem 1.4, see Section 2.4. We leverage this control to show in Section 4.2 a general result on the universality of a quantity known as the asymptotic free entropy of the model, both for matrices arising from ellipsoid fitting and its Gaussian equivalent. This result follows from an interpolation argument. Finally, we apply these results in the so-called “low-temperature” limit in Section 4.3 to deduce Proposition 2.2. As we mentioned, while we can not directly apply the results of [23], parts of Sections 4.2 and 4.3.2 closely follows their approach. We defer to Appendix D some technicalities, as well as some parts of the proof that more directly follow the arguments of [23].

## 4.1 Lipschitz constant of the energy function, and bounding random processes

We show here the following result on the behavior of the error (or “energy”) function, under both models $X_\mu \sim \text{Ellipse}(d)$ and $X_\mu \sim \text{GOE}(d)$.

**Lemma 4.1 (Lipschitz constant of the energy).** Let $n, d \ge 1$ and $n, d \to \infty$ with $\alpha_1 d^2 \le n \le \alpha_2 d^2$ for some $0 < \alpha_1 < \alpha_2$. Let $\phi: \mathbb{R} \to \mathbb{R}_+$ such that $\|\phi'\|_\infty < \infty$, and $X_1, \dots, X_n \in S_d$ be generated i.i.d. according to either $\text{GOE}(d)$ or $\text{Ellipse}(d)$. For $S \in S_d$, we define the energy:

$$ E_{\{X_\mu\}}(S) := \frac{1}{d^2} \sum_{\mu=1}^{n} \phi[\text{Tr}(X_\mu S)]. $$
Then the following holds for some $C > 0$ (depending only on $\alpha$):

$$ \mathbb{P} \left[ \sup_{S_1, S_2 \in \mathcal{S}_d} \frac{|E_{\{X_\mu\}}(S_1) - E_{\{X_\mu\}}(S_2)|}{\|S_1 - S_2\|_{\text{op}}} \le C \|\phi'\|_{\infty} \right] \ge 1 - 2e^{-n}. $$

In other words, the energy function has a bounded Lipschitz constant (as $d \to \infty$) with respect to the operator norm. Note that this is strictly stronger than what a naive use of the triangular inequality and of the duality $\| \cdot \|_{\text{op}} \leftrightarrow \| \cdot \|_{S_1}$ yields:

$$ \frac{|E_{\{X_\mu\}}(S_1) - E_{\{X_\mu\}}(S_2)|}{\|S_1 - S_2\|_{\text{op}}} \le \frac{\|\phi'\|_{\infty}}{d^2} \sum_{\mu=1}^{n} \text{Tr}|X_\mu|, $$

since $\text{Tr}|X_\mu| \gtrsim d$ for $X_\mu \sim \text{GOE}(d)$, and $\text{Tr}|X_\mu| \gtrsim \sqrt{d}$ for $X_\mu \sim \text{Ellipse}(d)$. Instead, the proof of Lemma 4.1 is based on the following bounds for random processes, for which we separate the $\text{GOE}(d)$ and $\text{Ellipse}(d)$ setting. Lemma 4.2 is a consequence of elementary concentration results, and is proven in Appendix D.1, while Lemma 4.3 is proven in the following.

**Lemma 4.2 (Bounding random processes, GOE(d) setting).** Let $(G_\mu)_{\mu=1}^n \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)$. Let $r \in [1, 2]$. We assume that $n \ge \alpha_1 d^2$, for some $\alpha_1 > 0$. There exists $C = C(\alpha_1) > 0$ such that for all $t > 0$:

$$ \mathbb{P} \left[ \max_{\|S\|_r^2=d} \left( \sum_{\mu=1}^n |\text{Tr}[G_\mu S]|^r \right)^{1/r} \ge (C+t)n^{1/r} \right] \le \exp(-nt^2/2). $$

**Lemma 4.3 (Bounding random processes, Ellipse(d) setting).** Let $W_1, \dots, W_n$ be drawn i.i.d. from $\text{Ellipse}(d)$. Let $r \in [1, 4/3]$. We assume that $\alpha_1 d^2 \le n \le \alpha_2 d^2$, for some $0 < \alpha_1 < \alpha_2$. There are constants $C_1, C_2 > 0$ (that might depend on $\alpha_1, \alpha_2$) such that for all $t > 0$:

$$ \mathbb{P} \left[ \max_{\|S\|_{\text{op}}=1} \sum_{\mu=1}^{n} |\text{Tr}(W_\mu S)|^r \ge n(C_1+t) \right] \le 2 \exp \left\{ -C_2 \min \left( n t^{\frac{2}{r}}, n^{\frac{1}{4}+\frac{1}{r}} t^{\frac{1}{r}} \right) \right\}. $$

*Proof of Lemma 4.1.* We finish here the proof, assuming Lemmas 4.2 and 4.3. By the mean value theorem and the duality $\| \cdot \|_{\text{op}} \leftrightarrow \| \cdot \|_{S_1}$:

$$ \begin{aligned} |E_{\{X_\mu\}}(S_1) - E_{\{X_\mu\}}(S_2)| &\le \left| \sup_{S \in \mathcal{S}_d} \langle \nabla_S E_{\{X_\mu\}}(S), S_1 - S_2 \rangle \right|, \\ &\le \|S_1 - S_2\|_{\text{op}} \sup_{S \in \mathcal{S}_d} \|\nabla_S E_{\{X_\mu\}}(S)\|_{S_1}. \end{aligned} $$

Again using the duality $\| \cdot \|_{\text{op}} \leftrightarrow \| \cdot \|_{S_1}$:

$$ \begin{aligned} \|\nabla_S E_{\{X_\mu\}}(S)\|_{S_1} &= \frac{1}{d^2} \left\| \sum_{\mu=1}^n X_\mu \phi'[\text{Tr}(X_\mu S)] \right\|_{S_1}, \\ &= \frac{1}{d^2} \sup_{\|R\|_{\text{op}}=1} \sum_{\mu=1}^n \text{Tr}[X_\mu R] \phi'[\text{Tr}(X_\mu S)], \\ &\le \frac{\|\phi'\|_{\infty}}{d^2} \sup_{\|R\|_{\text{op}}=1} \sum_{\mu=1}^n |\text{Tr}[X_\mu R]|. \end{aligned} $$

Using Lemmas 4.2 and 4.3 in the case $r = 1$, we reach the sought statement. $\square$

<figure><img src="image_8.png" /></figure>
**Remark I** – Note that a naive argument using that Tr[W_μS] is a sub-exponential random variable yields Lemma 4.3 for r = 1, which is already enough to deduce Lemma 4.1. However, Lemma 4.3 is also used later in the proof of Theorem 1.4, see Section 2.4. Since Tr[W_μS] is the sum of many independent random variables, we can leverage its two-tailed behavior (by Bernstein's inequality) to prove Lemma 4.3 for all r ≤ 4/3, yielding the limitation r < 4/3 in Theorem 1.4. It is possible that a finer analysis could lead to a proof of Lemma 4.3 for the case 4/3 ≤ r ≤ 2, which would in turn imply Theorem 1.4 for r < 2.

**Remark II** – We give an informal argument as to why we can not hope to extend Lemma 4.2 nor 4.3 for $r > 2$. Indeed, in the GOE(d) setting, the choice $S = \sqrt{d}G_{\mu}/\|G_{\mu}\|_F$ (for some $\mu \in [n]$) yields that the objective function is at least $\sqrt{d}\|G_{\mu}\|_F \gtrsim \sqrt{n}$. In the Ellipse(d) setting, assume that $r > 2$. If $1/q + 1/r = 1$, then by the dualities $\ell^p \leftrightarrow \ell^q$ and $\|\cdot\|_{op} \leftrightarrow \|\cdot\|_{S_1}$:

$$ \max_{\|S\|_{op}=1} \left( \sum_{\mu=1}^{n} |\operatorname{Tr}(W_{\mu}S)|^r \right)^{1/r} = \max_{\|\lambda\|_q=1} \left\| \sum_{\mu=1}^{n} \lambda_{\mu} W_{\mu} \right\|_{S_1} . \quad (4.1) $$

Let us lower bound the right-hand side of eq. (4.1). Let $\beta \in (0, 1)$, $p = \beta n$, and $\lambda_1 = \dots = \lambda_p = p^{-1/q} > \lambda_{p+1} = \dots = \lambda_n = 0$. Then $\|\lambda\|_q = 1$. Moreover,

$$ \left\| \sum_{\mu=1}^{n} \lambda_{\mu} W_{\mu} \right\|_{S_1} = p^{1-1/q} d^{-1/2} \left\| \frac{1}{p} \sum_{\mu=1}^{p} x_{\mu} x_{\mu}^{\top} - I_d \right\|_{S_1}. $$

By classical results of concentration of Wishart matrices [38], we know that since $p \lesssim d^2$ then

$$ \left\| \frac{1}{p} \sum_{\mu=1}^{p} x_{\mu} x_{\mu}^{\top} - I_d \right\|_{S_1} \gtrsim \frac{d^{3/2}}{\sqrt{p}} \gtrsim \sqrt{\frac{d}{\beta}}, $$

where $\gtrsim$ might hide constants that depend on $\alpha$. We then reach:

$$ \left\| \sum_{\mu=1}^{n} \lambda_{\mu} W_{\mu} \right\|_{S_1} \gtrsim \beta^{1/2-1/q} n^{1-1/q}. $$

Since $r > 2$, one has $1/2 - 1/q < 0$. Letting $\beta$ going to 0, this shows that any bound of the type

$$ \max_{\|\lambda\|_q=1} \left\| \sum_{\mu=1}^{n} \lambda_{\mu} W_{\mu} \right\|_{S_1} \le C(\alpha) n^{1-1/q} $$

can not hold.

**Proof of Lemma 4.3.** Throughout this proof, constants might depend on $\alpha_1, \alpha_2$. Let us define, for any $S \in S_d$:

$$ \left\{ \begin{aligned} Y(S) &:= \sum_{\mu=1}^{n} |\operatorname{Tr}(W_{\mu}S)|^r, \\ X(S) &:= Y(S) - \operatorname{EY}(S). \end{aligned} \right. \quad (4.2) $$

For a set $E \subseteq S_d$, a norm $\|\cdot\|$ on $S_d$, and a value $\varepsilon > 0$, an $\varepsilon$-net of $E$ is a set $A \subseteq E$ such that every point of $E$ is at distance at most $\varepsilon$ from $A$ (for the distance induced by $\|\cdot\|$). We define the covering number $\mathcal{N}(E, \|\cdot\|, \varepsilon)$ as the smallest possible cardinality of an $\varepsilon$-net of $E$. We fix $\varepsilon \in (0, 1)$. It follows from classical covering number bounds [37] that if $T := \{S \in S_d : \|S\|_{op} = 1\}$, then

$$ \log \mathcal{N}(T, \|\cdot\|_{op}, \varepsilon) \le \frac{d(d+1)}{2} \log \frac{3}{\varepsilon}. \quad (4.3) $$
## Exact threshold for approximate ellipsoid fitting of random points

Let us fix $N$ an $\varepsilon$-net of $T$ for $\| \cdot \|_{op}$, of minimal cardinality. If we let $S^* := \arg \max_{\|S\|_{op}=1} Y(S)$, and $S_0 \in N$ with $\|S^* - S_0\|_{op} \le \varepsilon$, then we have by Minkowski's inequality (recall $r \ge 1$):

$$ \begin{aligned} \|\{\mathrm{Tr}[W_\mu S^*]\}_{\mu=1}^n\|_r - \|\{\mathrm{Tr}[W_\mu S_0]\}_{\mu=1}^n\|_r &\le \|\{\mathrm{Tr}[W_\mu(S_0 - S^*)]\}_{\mu=1}^n\|_r \\ &\le \varepsilon \max_{\|S\|_{op}=1} \|\{\mathrm{Tr}[W_\mu S]\}_{\mu=1}^n\|_r. \end{aligned} $$

This implies

$$ \max_{\|S\|_{op}=1} \sum_{\mu=1}^{n} |\mathrm{Tr}(W_{\mu}S)|^r \le \frac{1}{(1-\varepsilon)^r} \max_{S \in N} \sum_{\mu=1}^{n} |\mathrm{Tr}(W_{\mu}S)|^r. \quad (4.4) $$

We combine the covering number upper bound of eq. (4.3) and the relation of eq. (4.4) with the following lemma, proven later on, which bounds the deviation probability of the process for a given $S$.

**Lemma 4.4 (Tail bound at a fixed point).** With the notations of eq. (4.2), we have, for any $S \in T$:

$$ (i) \quad \mathbb{E}[Y(S)] \le C_1 n. $$

$$ (ii) \quad \text{For all } t \ge 0: $$

$$ \mathbb{P}[X(S) \ge nt] \le 2 \exp \left\{ -C_2 \min(n t^2, n \frac{t^2}{r}, n \frac{1}{4} + \frac{1}{r} t \frac{1}{r}) \right\}. $$

Note that the above constants may depend on $r$.

Picking $\varepsilon = 1/2$ and performing a union bound over $N$, we reach using eqs. (4.3), (4.4) and Lemma 4.4:

$$ \mathbb{P}[\sup_{S \in T} Y(S) \ge n(C_1 + t)] \le 2 \exp \left\{ C_3 n - C_2 \min(n t^2, n \frac{t^2}{r}, n \frac{1}{4} + \frac{1}{r} t \frac{1}{r}) \right\}. $$

We thus have for any $t \ge 1$:

$$ \mathbb{P}[\sup_{S \in T} Y(S) \ge n(C_1 + t)] \le 2 \begin{cases} \exp \{C_3 n - C_2 n \frac{t^2}{r}\} & \text{if } t \le n^{1-\frac{3r}{4}}, \\ \exp \{C_3 n - C_2 n \frac{1}{4} + \frac{1}{r} t \frac{1}{r}\} & \text{if } t \ge n^{1-\frac{3r}{4}}. \end{cases} $$

Note that $n^{1/4+1/r} \ge n$ since $r \le 4/3$. Therefore, for (new) constants $C_1, C_2$ we have for all $t > 0$:

$$ \mathbb{P}[\sup_{S \in T} Y(S) \ge n(C_1 + t)] \le 2 \exp \left\{ -C_2 \min(n t^2, n \frac{1}{4} + \frac{1}{r} t \frac{1}{r}) \right\}, $$

which ends the proof. $\square$

We now tackle Lemma 4.4.

**Proof of Lemma 4.4.** We start with (i). One has $\mathbb{E}[Y(S)] = n\mathbb{E}[|\mathrm{Tr}(W_1S)|^r]$. Let $Z := \mathrm{Tr}(W_1S) \stackrel{d}{=} (x^\top S x - \mathrm{Tr}[S]) / \sqrt{d}$, with $x \sim \mathcal{N}(0, I_d)$. Since $\|S\|_{op} = 1$, we have by Hanson-Wright's inequality [38]:

$$ \begin{aligned} \mathbb{P}[|Z| \ge t] &\le 2 \exp \left\{ -C \min \left( \frac{dt^2}{\|S\|_F^2}, \sqrt{dt} \right) \right\}, \\ &\le 2 \exp \left\{ -C \min \left( t^2, \sqrt{dt} \right) \right\}, \end{aligned} \quad (4.5) $$
where $C > 0$ is an absolute constant, and we used that $\|S\|_F \le \sqrt{d}\|S\|_{op}$. Separating the sub-Gaussian and the sub-exponential parts of the tail we have, we have for all $p \ge 1$:

$$
\begin{align*}
\mathbb{E}[|Z|^p] &= p \int_0^\infty du \, u^{p-1} \mathbb{P}[|Z| \ge u], \\
&\le 2p \left[ \int_0^{\sqrt{d}} du \, u^{p-1} e^{-Cu^2} + \int_{\sqrt{d}}^\infty du \, u^{p-1} e^{-C\sqrt{d}u} \right], \\
&\le 2p \left[ \int_0^\infty du \, u^{p-1} e^{-Cu^2} + e^{-Cd} \int_0^\infty du \, (u + \sqrt{d})^{p-1} e^{-C\sqrt{d}u} \right], \\
&\stackrel{(a)}{\le} 2p \left[ \frac{1}{2C^{p/2}} \Gamma(p/2) + e^{-Cd} \max(1, 2^{p-2}) \int_0^\infty du \, [u^{p-1} + d^{(p-1)/2}] e^{-C\sqrt{d}u} \right], \\
&\le 2p \left[ \frac{\Gamma(p/2)}{2C^{p/2}} + e^{-Cd} \max(1, 2^{p-2}) \left( \frac{\Gamma(p)}{C^p d^{p/2}} + \frac{d^{(p-2)/2}}{C} \right) \right].
\end{align*}
$$

We used in (a) that $(a+b)^x \le \max(1, 2^{x-1})(ax + b^x)$ for all $a, b, x \ge 0$. Using Minkowski's inequality, we reach that for all $p \ge 1$:

$$
\mathbb{E}[|Z|^p]^{1/p} \le C_1 \sqrt{p} + C_2 e^{-\frac{C_3 d}{p}} \left( \frac{p}{\sqrt{d}} + d^{\frac{1}{2}-\frac{1}{p}} \right), \quad (4.6)
$$

for some positive constants ($C_a$)$_{a=1}^3$ independent of $p$ and $d$. Informally, the sub-Gaussian tail dominates the first moments of $Z$ since the sub-exponential tail only kicks in at the scale $O(\sqrt{d})$. Eq. (4.6) implies claim (i) of Lemma 4.4 by taking $p=r$ (since the second term goes to 0 as $d \to \infty$ for any fixed $p$).

We turn to (ii). We make use of classical tail bounds for sub-Weibull random variables, recalled in Lemma A.1. Denoting $Z_\mu := \text{Tr}(W_\mu S)$, we have $X(S) = \sum_{\mu=1}^n \{|Z_\mu|^r - \mathbb{E}[|Z_\mu|^r]\}$. We decompose $X(S)$ in two parts, i.e. $X(S) = X_1(S) + X_2(S)$, with

$$
\left\{
\begin{aligned}
X_1(S) &:= \sum_{\mu=1}^{n} \left[ \min(|Z_\mu|, \sqrt{d})^r - \mathbb{E}\{\min(|Z_\mu|, \sqrt{d})^r\} \right], \\
X_2(S) &:= \sum_{\mu=1}^{n} \left( [|Z_\mu|^r - d^{r/2}] \mathbb{1}\{|Z_\mu| > \sqrt{d}\} - \mathbb{E}\left\{ [|Z_\mu|^r - d^{r/2}] \mathbb{1}\{|Z_\mu| > \sqrt{d}\} \right\} \right).
\end{aligned}
\right.
\qquad (4.7)
$$

We will successively bound $X_1(S)$, $X_2(S)$. To lighten the notations, we do not write their dependency on $S$ in what follows. Observe that $(Z_\mu)^n_{\mu=1}$ are i.i.d. random variables, and that they satisfy the tail bound of eq. (4.5).

**Bounding** $X_1$ - Denoting $T_\mu := \min(|Z_\mu|, \sqrt{d})$, we have $P[T_\mu \ge t] \le 2 \exp\{-C_2 t^2\}$ by the tail bound of eq. (4.5). Moreover, $\mathbb{E}[T_\mu^r] \le \mathbb{E}[|Z_\mu|^r] \le C_1$ (depending only on $r$) by eq. (4.6). Therefore, for every $t > C_1$, we have

$$
\mathbb{P}[|T_{\mu}^{r} - \mathbb{E}[T_{\mu}^{r}]| \ge t] = \mathbb{P}[T_{\mu}^{r} \ge \mathbb{E}[T_{\mu}^{r}] + t] \le 2e^{-C_2(t+\mathbb{E}[T_{\mu}^{r}])^{2/r}} \le 2e^{-C_2 t^{2/r}}.
$$

This implies that $P[|T_\mu^r - \mathbb{E}[T_\mu^r]| \ge t] \le 2e^{-Ct^{2/r}}$ for all $t \ge 0$ and some (new) constant $C > 0$, depending only on $r$. We can thus apply (i) of Lemma A.1 for $q = 2/r \in [1, 2]$ and $a_i = 1/n$ (so $\|a\|_2^2 = \|a\|_q^q = n^{-1}$), which yields that for all $t \ge 0$

$$
\mathbb{P}[|X_1| \ge nt] = \mathbb{P}\left[\frac{1}{n}\left|\sum_{\mu=1}^{n}\{T_{\mu}^{r} - \mathbb{E}[T_{\mu}^{r}]\}\right| \ge t\right] \le 2 \exp\left\{-Cn \min(t^2, t^{2/r})\right\}. \quad (4.8)
$$
**Bounding $X_2$** – We proceed similarly, using (ii) of Lemma A.1. Letting

$$U_{\mu} := d^{r/2} [|Z_{\mu}|^r - d^{r/2}] \mathbf{1}\{|Z_{\mu}| > \sqrt{d}\},$$

then $U_{\mu} \ge 0$, and moreover, by the Cauchy-Schwarz inequality:

$$\begin{aligned} \mathbb{E}[U_{\mu}] &\le d^{r/2} \sqrt{\mathbb{E}|Z_{\mu}|^{2r}} \sqrt{\mathbb{P}(|Z_{\mu}| > \sqrt{d})}, \\ &\le C_1 e^{-C_2 d}, \end{aligned}$$

for some $C_1, C_2 > 0$ depending only on $r$, using the moments and tail bound of eqs. (4.5) and (4.6). Repeating the argument used on $T_{\mu}$ above (using this time the second part of the tail of eq. (4.5)), we then reach that for all $t \ge 0$:

$$\mathbb{P}[|U_{\mu} - \mathbb{E}[U_{\mu}|] \ge t] \le 2e^{-Ct^{1/r}}.$$

We can then apply (ii) of Lemma A.1 with $q = 1/r \in [1/2, 1]$ to reach:

$$\begin{aligned} \mathbb{P}[|X_2| \ge nt] &= \mathbb{P}\left[\frac{1}{n}\left|\sum_{\mu=1}^{n}\{U_{\mu} - \mathbb{E}[U_{\mu}]\}\right| \ge t d^{r/2}\right] \le 2 \exp\left\{-C \min(nd^r t^2, d^{1/2}(nt)^{1/r})\right\}, \\ &\le 2 \exp\left\{-C \min(n^{1+r/2}t^2, n^{1/4+1/r}t^{1/r})\right\}, \end{aligned} \quad (4.9)$$

using that $\alpha_1 d^2 \le n \le \alpha_2 d^2$.

We conclude the proof of Lemma 4.4 by combining eqs. (4.8) and eq. (4.9), along with the union bound $\mathbb{P}[|X| \ge nt] \le \mathbb{P}[|X_1| \ge nt/2] + \mathbb{P}[|X_2| \ge nt/2]$. $\square$

## 4.2 Free entropy universality for matrix models

In this section we state and prove a general universality theorem for the asymptotic free entropy in a large class of matrix models, under a “uniform one-dimensional central limit theorem” assumption (or pointwise normality). We first need to define such an assumption.

**Definition 4.5 (Uniform pointwise normality).** Let $d \ge 1$, and $\rho$ a probability distribution on $S_d$. We say that $\rho$ satisfies a one-dimensional CLT with respect to the set $A_d \subseteq S_d$ if:

(i) The mean and covariance of $\rho$ are matching the GOE(d) distribution, i.e. for $W \sim \rho$ and $G \sim \text{GOE}(d)$, we have $\mathbb{E}[W] = \mathbb{E}[G] = 0$ and for all $i \le j$ and $k \le l$: $\mathbb{E}[W_{ij}W_{kl}] = \mathbb{E}[G_{ij}G_{kl}] = \delta_{ik}\delta_{jl}(1 + \delta_{ijkl})/d$.

(ii) For any bounded Lipschitz function $\varphi$, we have:

$$\limsup_{d \to \infty} \sup_{S \in A_d} \left| \mathbb{E}_{W \sim \rho}[\varphi(\text{Tr}[WS])] - \mathbb{E}_{G \sim \text{GOE}(d)}[\varphi(\text{Tr}[GS])] \right| = 0. \quad (4.10)$$

We can now state the universality theorem for the free entropy. Its proof is in great part an adaptation of the proof arguments for Theorem 1 and Lemma 1 in [23] (see also [17, 11, 9]). We sketch the ideas of its proof in the following, deferring some technicalities and adaptations of the arguments of [23] to appendices.

**Theorem 4.6 (Free entropy universality for matrix models).** Let $n, d \ge 1$ and $n, d \to \infty$ with $\alpha_1 d^2 \le n \le \alpha_2 d^2$ for some $0 < \alpha_1 \le \alpha_2$. We are given:

(i) $P_0$ a probability distribution on $S_d$, such that $\text{supp}(P_0) \subseteq B_2(C_0\sqrt{d})$, for a constant $C_0 > 0$.

(ii) $\phi: \mathbb{R} \to \mathbb{R}_+$ a bounded differentiable function with bounded derivative.
Exact threshold for approximate ellipsoid fitting of random points

(iii) A series of symmetric convex sets $A_d$ such that $\text{supp}(P_0) \subseteq A_d$.

(iv) $\rho$ a probability distribution on $S_d$, which satisfies a one-dimensional CLT with respect to $A_d$ as per Definition 4.5.

For $W_1, \dots, W_n \in S_d$ we define the free entropy:

$$F_d(\{W_\mu\}) := \frac{1}{d^2} \log \int P_0(dS) \exp \left\{ - \sum_{\mu=1}^{n} \phi(\text{Tr}[W_\mu S]) \right\}. \quad (4.11)$$

Then for any bounded differentiable function $\psi$ with bounded Lipschitz derivative we have

$$\lim_{d \to \infty} \left| \mathbb{E}_{\{W_\mu\} \stackrel{\text{i.i.d.}}{\sim} \rho} \psi[F_d(\{W_\mu\})] - \mathbb{E}_{\{G_\mu\} \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)} \psi[F_d(\{G_\mu\})] \right| = 0. \quad (4.12)$$

**Remark I** – One could straightforwardly weaken the hypothesis $\text{supp}(P_0) \subseteq A$ in Theorem 4.6 to the weaker condition $d^{-2} \log P_0(A^c) \to -\infty$ as $d \to \infty$.

**Remark II** – Note that our setup differs slightly from the one of [23], as we consider distributions $P_0$ with possibly continuous support, and (more importantly) for a fixed $S \in S_d$, the projections $\{\text{Tr}[W_\mu S]\}_{\mu=1}^n$ are not sub-Gaussian when $W_\mu \sim \text{Ellipse}(d)$, but only sub-exponential. Nevertheless, we will see that the approach of [23] can in large part be adapted to prove Theorem 4.6, thanks to the results we showed in Section 4.1.

**Sketch of proof of Theorem 4.6** – Since $\text{supp}(P_0) \subseteq A_d$, the integral in eq. (4.11) can be restricted to $S \in A_d$. We make use of an interpolation argument to show the universality of the free entropy. We define, for $t \in [0, \pi/2]$ and $\mu \in [n]$:

$$\left\{ \begin{aligned} U_\mu(t) &:= \cos(t)W_\mu + \sin(t)G_\mu, \\ \tilde{U}_\mu(t) &:= \frac{\partial U_\mu(t)}{\partial t} = -\sin(t)W_\mu + \cos(t)G_\mu. \end{aligned} \right. \quad (4.13)$$

Note that $\{U_\mu\}_{\mu=1}^n$ are still i.i.d., and are smooth functions of $t$. Moreover, if $W_\mu$ was also a GOE(d) matrix, then $U_\mu(t)$, $\tilde{U}_\mu(t)$ would be independent GOE(d) matrices. By the fundamental theorem of calculus:

$$|\mathbb{E}\psi[F_d(W)] - \mathbb{E}\psi[F_d(G)]| = \left| \int_0^{\pi/2} \frac{\partial}{\partial t} \{\mathbb{E}\psi[F_d(U(t))]\} dt \right| \stackrel{(a)}{\le} \int_0^{\pi/2} \left| \mathbb{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} \right| dt, \quad (4.14)$$

where (a) follows by dominated convergence since $\psi[F_d(U(t))]$ is continuously differentiable on $[0, \pi/2]$, and the triangular inequality. We will deduce Theorem 4.6 if we can show the following two lemmas:

**Lemma 4.7 (Domination).** Under the hypotheses of Theorem 4.6:

$$\int_0^{\pi/2} \sup_{d \ge 1} \left| \mathbb{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} \right| dt < \infty.$$

**Lemma 4.8 (Pointwise limit).** Under the hypotheses of Theorem 4.6, for any $t \in (0, \pi/2)$:

$$\lim_{d \to \infty} \mathbb{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} = 0.$$

Indeed, plugging Lemmas 4.7 and 4.8 in eq. (4.14) and taking the $d \to \infty$ limit using dominated convergence ends the proof of Theorem 4.6. We therefore focus on proving these two lemmas in the following.
As it will be useful, we state the result of the elementary computation of the derivative:

$$ \frac{\partial \psi[F_d(U(t))]}{\partial t} = - \frac{\psi'[F_d(U(t))]}{d^2} \sum_{\mu=1}^{n} \frac{\int P_0(dS) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu(t)S])} (\mathrm{Tr}[S\tilde{U}_\mu(t)] \phi'(\mathrm{Tr}[U_\mu(t)S]))}{\int P_0(dS) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu(t)S])}}. \quad (4.15) $$

Because {$G_\mu, W_\mu$} are i.i.d. we get further:

$$ \mathrm{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} = - \frac{n}{d^2} \mathrm{E} \left[ \psi'[F_d(U(t))] \frac{\int P_0(dS) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu(t)S])} (\mathrm{Tr}[S\tilde{U}_1(t)] \phi'(\mathrm{Tr}[U_1(t)S]))}{\int P_0(dS) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu(t)S])}} \right]. \quad (4.16) $$

Note that if $W_\mu$ was also a GOE(d) matrix, for any $t$, $U_\mu(t)$ and $\tilde{U}_\mu(t)$ would be independent GOE(d) matrices. The main idea behind the interpolation is that the matrix $W_\mu$ will only appear through some one-dimensional projection with a matrix $S$. We will then use Definition 4.5 to argue that one can effectively replace $W_\mu$ by a GOE(d) matrix, which by the argument above would mean that we can consider the case of independent GOE(d) matrices $U_\mu(t)$ and $\tilde{U}_\mu(t)$. In this case, the RHS of eq. (4.16) would be 0, since there is only a single term involving $\tilde{U}_1(t)$, which has zero mean: this crucial idea is the intuition behind Lemma 4.8.

The details of the proofs of Lemmas 4.7 and 4.8 are fairly technical and substantially follow the ones of their counterparts in [23]. For this reason, we defer them to Appendix D.2.

## 4.3 Proof of Proposition 2.2

### 4.3.1 Consequences of universality for ellipsoid fitting

We investigate here the consequences of Theorem 4.6 for the ellipsoid fitting problem. It follows by the Berry-Esseen central limit theorem [25] that the distribution Ellipse(d) satisfies uniform pointwise normality on a large set of matrices (in the sense of Definition 4.5).

**Lemma 4.9 (One-dimensional CLT for the ellipse problem).** Let $d \ge 1$ and $W \sim \mathrm{Ellipse}(d)$. Fix any $\eta \in (0, 1/2)$ Let $A_d := \{S \in S_d : \mathrm{Tr}[|S|^3] \le d^{3/2-\eta}\}$. Then $A_d$ is convex and symmetric, and the law of $W$ satisfies a one-dimensional CLT with respect to $A_d$, in the sense of Definition 4.5.

**Remark** – This lemma makes crucial use of the Gaussian nature of the vectors, and more specifically it relies on their rotation invariance and the first moments of their norm, as is clear from the proof. On the other hand, for vectors sampled from other distributions, such as $x \sim \mathrm{Unif}(\{\pm 1\}^d)$ or $x \sim \mathrm{Unif}(S^{d-1})$, it is easy to see that Lemma 4.9 can not hold: indeed, $S = I_d$ is such that $\mathrm{Tr}[SW] = 0$ deterministically, while $\mathrm{Tr}[SG] = \mathrm{Tr}[G] \sim \mathcal{N}(0, 2)$ for $G \sim \mathrm{GOE}(d)$. This is consistent, as in the example of these two distributions there always exists an ellipsoid fit, which is the sphere itself, and therefore Theorem 1.4 can not possibly hold.

*Proof of Lemma 4.9.* Note that $A_d$ is a centered ball for the $S_3$-norm, and is therefore convex and symmetric. The proof of the first and second moments condition of Definition 4.5 is immediate via a simple calculation. We focus on proving condition (ii) of Definition 4.5.
Exact threshold for approximate ellipsoid fitting of random points

Fix $S \in A_d$, with eigenvalues $(\lambda_i)_{i=1}^d$. With $W \sim \text{Ellipse}(d)$ and $G \sim \text{GOE}(d)$, let

$$ \begin{cases} X := \text{Tr}[SW], \\ Y := \text{Tr}[SG]. \end{cases} $$

It is trivial to see that $Y \sim \mathcal{N}(0, 2\text{Tr}[S^2]/d)$, so that $Y \stackrel{d}{=} d^{-1/2} \sum_{i=1}^d \lambda_i z_i$ for $z_i \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 2)$. Moreover,

$$ X \stackrel{d}{=} \frac{1}{\sqrt{d}} \sum_{i=1}^{d} \lambda_i (x_i^2 - 1), $$

with $x_i \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 1)$. We use the Berry-Esseen central limit theorem, and in particular the formulation of Chapter 11 of [25] – itself a simple consequence of the Lindeberg exchange method.

**Lemma 4.10 (Corollary 11.59 of [25]).** There exists a universal constant $C > 0$ such that the following holds. Let $p \ge 1$ and $X_1, \dots, X_p$ and $Y_1, \dots, Y_p$ be independent random variables, such that $\mathbb{E}[X_i] = \mathbb{E}[Y_i]$ and $\mathbb{E}[X_i^2] = \mathbb{E}[Y_i^2]$ for all $i \in [p]$. Let $\varphi : \mathbb{R} \to \mathbb{R}$ a Lipschitz function with Lipschitz constant $\|\varphi\|_L$. Then

$$ \left| \mathbb{E} \varphi \left( \sum_{i=1}^{p} X_i \right) - \mathbb{E} \varphi \left( \sum_{i=1}^{p} Y_i \right) \right| \le C \|\varphi\|_L \left[ \sum_{i=1}^{p} \left( \mathbb{E} |X_i|^3 + \mathbb{E} |Y_i|^3 \right) \right]^{1/3}. $$

Lemma 4.10 yields:

$$ |\mathbb{E} \varphi(X) - \mathbb{E} \varphi(Y)| \le C \|\varphi\|_L \left[ B \frac{\text{Tr}[|S|^3]}{d^{3/2}} \right]^{1/3}, $$

with $B = \mathbb{E}[|z^2 - 1|^3] + 2^{3/2} \mathbb{E}|z|^3$ for $z \sim \mathcal{N}(0, 1)$. Using the definition of $A_d$, we reach:

$$ \sup_{S \in A_d} |\mathbb{E} \varphi(X) - \mathbb{E} \varphi(Y)| \le C \|\varphi\|_L \sup_{S \in A_d} \left[ \frac{1}{\sqrt{d}} \frac{\text{Tr}|S|^3}{d} \right]^{1/3} \le C \|\varphi\|_L d^{-\eta/3} \to 0. $$

This ends the proof.

□

We can now state the main result of this section, a corollary of Theorem 4.6 and Lemma 4.9.

**Corollary 4.11 (Universality for ellipsoid fitting).** Let $n, d \ge 1$ and $n, d \to \infty$ with $\alpha_1 d^2 \le n \le \alpha_2 d^2$ for some $0 < \alpha_1 \le \alpha_2$. Let $P_0$ be a probability distribution such that $\text{supp}(P_0) \subseteq B_{\text{op}}(C_0)$ for some constant $C_0 > 0$. Let $\phi : \mathbb{R} \to \mathbb{R}_+$ a bounded differentiable function with bounded derivative. For $X_1, \dots, X_n \in S_d$ we define the free entropy:

$$ F_d(\{X_\mu\}) := \frac{1}{d^2} \log \int P_0(dS) \exp \left\{ - \sum_{\mu=1}^{n} \phi(\text{Tr}[X_\mu S]) \right\}. $$

Then for any $\psi$ such that $\|\psi\|_\infty, \|\psi'\|_\infty, \|\psi'\|_L < \infty$ we have

$$ \lim_{d \to \infty} \left| \mathbb{E}_{\{W_\mu\} \stackrel{\text{i.i.d.}}{\sim} \text{Ellipse}(d)} \psi[F_d(\{W_\mu\})] - \mathbb{E}_{\{G_\mu\} \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)} \psi[F_d(\{G_\mu\})] \right| = 0. \quad (4.17) $$

We notice that the only requirement for Corollary 4.11 to hold is $\text{supp}(P_0) \subseteq B_F(C\sqrt{d}) \cap B_3(d^{3/2-\eta})$ for some $C > 0$ and $\eta > 0$, a weaker requirement than $\text{supp}(P_0) \subseteq B_{\text{op}}(C_0)$.

**Proof of Corollary 4.11.** Since $B_{\text{op}}(C_0) \subseteq B_2(C_0\sqrt{d})$, hypothesis (i) of Theorem 4.6 is satisfied. Condition (ii) is satisfied by hypothesis. Since $B_{\text{op}}(C_0) \subseteq B_3(C_0d^{1/3}) \subseteq B_3(d^{1/2-\eta})$ for any $\eta \in (0, 1/6)$, condition (iii) of Theorem 4.6 is satisfied with $A_d = B_3(d^{1/2-\eta})$. Finally, Lemma 4.9 verifies condition (iv) for this choice of $A_d$. All in all we can apply Theorem 4.6, from which the conclusion follows. □
### 4.3.2 Proof of Proposition 2.2

We are now ready to prove Proposition 2.2, taking a “small-temperature” limit. Such arguments are classical in rigorous statistical mechanics, see e.g. Appendix A of [23]. Notice that the restriction $B \subseteq B_{op}(C_0)$ will be critical because we proved an upper bound on the Lipschitz constant of the energy for the operator norm, cf. Lemma 4.1. Recall the definition of the energy function:

$$E_{\{X_{\mu}\}}(S) := \frac{1}{d^2} \sum_{\mu=1}^{n} \phi[\mathrm{Tr}(X_{\mu}S)].$$

We fix $\eta \in (0, 1)$, and $\mathcal{N}_{\eta} \subseteq B$ a minimal $\eta$-net of $B$ for $\|\cdot\|_{op}$. Since $B \subseteq B_{op}(C_0)$ and $\dim(S_d) = d(d+1)/2$, it follows by standard covering number upper bounds [38, 37] that

$$\log |\mathcal{N}_{\eta}| = \log \mathcal{N}(B, \|\cdot\|_{op}, \eta) \le \log \mathcal{N} \left( B_{op}(C_0), \|\cdot\|_{op}, \frac{\eta}{2} \right) \le d^2 \log \frac{K}{\eta}, \quad (4.18)$$

for some $K > 0$ depending on $C_0$. Recall the definition of $\mathrm{GS}_d(\{X_{\mu}\})$ in eq. (2.4). We define:

$$\mathrm{GS}_d(\eta, \{X_{\mu}\}) := \inf_{S \in \mathcal{N}_{\eta}} E_{\{X_{\mu}\}}(S).$$

We will show the two lemmas:

**Lemma 4.12.** For any $\eta > 0$ and any $\psi$ such that $\|\psi\|_{\infty}, \|\psi'\|_{\infty}, \|\psi'\|_{L} < \infty$:

$$\lim_{d \to \infty} \left| \mathrm{E}_{\{W_{\mu}\}^{i.i.d. \sim \mathrm{Ellipse}(d)}} \psi[\mathrm{GS}_d(\eta, \{W_{\mu}\})] - \mathrm{E}_{\{G_{\mu}\}^{i.i.d. \sim \mathrm{GOE}(d)}} \psi[\mathrm{GS}_d(\eta, \{G_{\mu}\})] \right| = 0.$$

**Lemma 4.13.** Let $X_1, \dots, X_n \stackrel{\mathrm{i.i.d.}}{\sim} \rho$, with $\rho \in \{\mathrm{GOE}(d), \mathrm{Ellipse}(d)\}$. Then, with probability at least $1 - 2e^{-n}$:

$$|\mathrm{GS}_d(\eta, \{X_{\mu}\}) - \mathrm{GS}_d(\{X_{\mu}\})| \le C \|\phi'\|_{\infty} \cdot \eta.$$

These results are proven in the following, let us first see how they end the proof of Proposition 2.2. We fix $\eta \in (0, 1)$. We have

$$\begin{aligned} |\mathrm{E}\psi[\mathrm{GS}_d(\{W_{\mu}\})] - \mathrm{E}\psi[\mathrm{GS}_d(\{G_{\mu}\})]| & \le |\mathrm{E}\psi[\mathrm{GS}_d(\eta, \{W_{\mu}\})] - \mathrm{E}\psi[\mathrm{GS}_d(\eta, \{G_{\mu}\})]| \\ & \quad + \|\psi\|_{L} \sum_{X \in \{W, G\}} \mathrm{E}|\mathrm{GS}_d(\eta, \{X_{\mu}\}) - \mathrm{GS}_d(\{X_{\mu}\})|. \end{aligned}$$

The first term goes to 0 as $d \to \infty$ by Lemma 4.12. Finally, using Lemma 4.13 and the Cauchy-Schwarz inequality, we have:

$$\begin{aligned} \mathrm{E}|\mathrm{GS}_d(\eta, \{X_{\mu}\}) - \mathrm{GS}_d(\{X_{\mu}\})| & \le e^{-n/2} \sqrt{2\mathrm{E}|\mathrm{GS}_d(\eta, \{X_{\mu}\}) - \mathrm{GS}_d(\{X_{\mu}\})|^2 + C\|\phi'\|_{\infty}\eta} \\ & \stackrel{(a)}{\le} 4\alpha\|\phi\|_{\infty}e^{-n/2} + C\|\phi'\|_{\infty}\eta, \end{aligned}$$

using in (a) that $|E(S)| \le \alpha \|\phi\|_{\infty}$. Letting $d \to \infty$, we get

$$\lim_{d \to \infty} |\mathrm{E}\psi[\mathrm{GS}_d(\{W_{\mu}\})] - \mathrm{E}\psi[\mathrm{GS}_d(\{G_{\mu}\})]| \le C \|\phi'\|_{\infty} \|\psi\|_{L} \cdot \eta.$$

Taking the limit $\eta \to 0$ ends the proof of eq. (2.5). The claim of eq. (2.6) can be obtained easily by picking $\psi$ approximating an indicator function, see e.g. Section A.1.3 of [23] for a detail of this argument. $\square$
Exact threshold for approximate ellipsoid fitting of random points

Proof of Lemma 4.12. We define, for $\beta > 0$:

$$F_d(\eta, \beta, \{X_\mu\}) := \frac{1}{d^2\beta} \log \frac{1}{|\mathcal{N}_\eta|} \sum_{S \in \mathcal{N}_\eta} \exp \left\{ -\beta \sum_{\mu=1}^n \phi(\mathrm{Tr}[X_\mu S]) \right\}.$$

Using Corollary 4.11 with $P_0$ being the uniform distribution over $\mathcal{N}_\eta$, we have, for any $\beta > 0$:

$$\lim_{d \to \infty} |\mathrm{E}\psi[F_d(\eta, \beta, \{W_\mu\})] - \mathrm{E}\psi[F_d(\eta, \beta, \{G_\mu\})]| = 0. \quad (4.19)$$

Moreover, for any fixed $d, \eta$, we have $\mathrm{GS}_d(\eta, \{X_\mu\}) = \lim_{\beta \to \infty} F_d(\eta, \beta, \{X_\mu\})$. Thus:

$$|\mathrm{GS}_d(\eta, \{X_\mu\}) - F_d(\eta, \beta, \{X_\mu\})| \le \int_{\beta}^{\infty} \left| \frac{\partial F_d(\eta, s, \{X_\mu\})}{\partial s} \right| ds. \quad (4.20)$$

Defining the “Gibbs” measure for $S \in \mathcal{N}_\eta$:

$$P_\beta(S) := \frac{\exp\left\{-\beta \sum_{\mu=1}^n \phi(\mathrm{Tr}[X_\mu S])\right\}}{\sum_{S' \in \mathcal{N}_\eta} \exp\left\{-\beta \sum_{\mu=1}^n \phi(\mathrm{Tr}[X_\mu S'])\right\}},$$

it is easy to check that

$$\left| \frac{\partial F_d(\eta, s, \{X_\mu\})}{\partial s} \right| = \frac{1}{s^2 d^2} \left| \sum_{S \in \mathcal{N}_\eta} P_s(S) \log P_s(S) + \log |\mathcal{N}_\eta| \right|, \\ \stackrel{(a)}{\le} \frac{1}{s^2 d^2} \log |\mathcal{N}_\eta|, \\ \stackrel{(b)}{\le} \frac{1}{s^2} \log \frac{K}{\eta},$$

where (a) follows from the fact that, the uniform distribution over $\mathcal{N}_\eta$ maximizes the entropy, and (b) is eq. (4.18). Plugging the result back in eq. (4.20) we get:

$$|\mathrm{GS}_d(\eta, \{X_\mu\}) - F_d(\eta, \beta, \{X_\mu\})| \le \log \left(\frac{K}{\eta}\right) \int_{\beta}^{\infty} \frac{ds}{s^2}, \\ \le \frac{1}{\beta} \log \left(\frac{K}{\eta}\right). \quad (4.21)$$

Combining eqs. (4.19) and (4.21) we get, for any $\beta > 0$:

$$\limsup_{d \to \infty} |\mathrm{E}\psi[\mathrm{GS}_d(\eta, \{W_\mu\})] - \mathrm{E}\psi[\mathrm{GS}_d(\eta, \{G_\mu\})]| \\ \le \|\psi\|_L \limsup_{d \to \infty} \sum_{X \in \{W, G\}} \mathrm{E}|\mathrm{GS}_d(\eta, \{X_\mu\}) - F_d(\eta, \beta, \{X_\mu\})|, \\ \le \frac{2\|\psi\|_L}{\beta} \log \left(\frac{K}{\eta}\right).$$

Taking the limit $\beta \to \infty$ ends the proof of Lemma 4.12. $\square$

<figure><img src="image_9.png" /></figure>

Proof of Lemma 4.13. Note that $\mathrm{GS}_d(\eta, \{X_\mu\}) \ge \mathrm{GS}_d(\{X_\mu\})$ since $\mathcal{N}_\eta \subseteq B$. The other side of this inequality is a direct consequence of Lemma 4.1. Indeed, assuming that $E(S)$ is $C\|\phi'\|_\infty$-Lipschitz with respect to the operator norm, let us fix $S^* \in B$ such
Exact threshold for approximate ellipsoid fitting of random points

that $E(S^*) = \text{GS}_d(\{X_\mu\})$ (since $B$ is closed and bounded it is compact, therefore this minimizer exists). Letting $S \in \mathcal{N}_\eta$ such that $\|S^* - S\|_{\text{op}} \le \eta$, we have

$$ \text{GS}_d(\{X_\mu\}) = E(S^*), \\ \ge E(S) - |E(S^*) - E(S)|, \\ \ge \text{GS}_d(\eta, \{X_\mu\}) - C\|\phi'\|_{\infty} \cdot \eta, $$

which ends the proof. □

## References

[1] 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 (2011), 61–88. MR2796091

[2] 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 (2014), no. 3, 224–294. MR3311453

[3] Greg W Anderson, Alice Guionnet, and Ofer Zeitouni, *An introduction to random matrices*, Cambridge university press, 2010. MR2760897

[4] Philip W Anderson, *Spin glass vi: Spin glass as cornucopia*, Physics Today 42 (1989), no. 9, 9–11.

[5] Afonso S Bandeira, Antoine Maillard, Shahar Mendelson, and Elliot Paquette, *Fitting an ellipsoid to a quadratic number of random points*, Latin American Journal of Probability and Mathematical Statistics 21 (2024), no. 2, 1835. MR4818874

[6] Patrick Billingsley, *Convergence of probability measures*, John Wiley & Sons, 2013. MR0233396

[7] Venkat Chandrasekaran, Benjamin Recht, Pablo A Parrilo, and Alan S Willsky, *The convex geometry of linear inverse problems*, Foundations of Computational mathematics 12 (2012), 805–849. MR2989474

[8] Patrick Charbonneau, Enzo Marinari, Giorgio Parisi, Federico Ricci-tersenghi, Gabriele Sicuro, Francesco Zamponi, and Marc Mezard, *Spin glass theory and far beyond: Replica symmetry breaking after 40 years*, World Scientific, 2023.

[9] Yatin Dandi, Ludovic Stephan, Florent Krzakala, Bruno Loureiro, and Lenka Zdeborova, *Universality laws for gaussian mixtures in generalized linear models*, Proceedings of the 37th International Conference on Neural Information Processing Systems, 2023, pp. 54754–54768. MR4832810

[10] Oussama Dhifallah and Yue M Lu, *A precise performance analysis of learning with random features*, arXiv preprint arXiv:2008.11904, 2020.

[11] Federica Gerace, Florent Krzakala, Bruno Loureiro, Ludovic Stephan, and Lenka Zdeborová, *Gaussian universality of perceptrons with random labels*, Physical Review E 109 (2024), no. 3, 034305. MR4736165

[12] Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, and Goutham Rajendran, *Sum-of-squares lower bounds for Sherrington-Kirkpatrick via planted affine planes*, 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2020, pp. 954–965. MR4232101

[13] Sebastian Goldt, Bruno Loureiro, Galen Reeves, Florent Krzakala, Marc Mézard, and Lenka Zdeborová, *The gaussian equivalence of generative models for learning with shallow neural networks*, Mathematical and Scientific Machine Learning, PMLR, 2022, pp. 426–471.

[14] Yehoram Gordon, *On Milman's inequality and random subspaces which escape through a mesh in $R^n$*, Geometric Aspects of Functional Analysis: Israel Seminar (GAFA) 1986–87, Springer, 1988, pp. 84–106. MR0950977

[15] Paweł Hitczenko, Stephen J Montgomery-Smith, and Krzysztof Oleszkiewicz, *Moment inequalities for sums of certain independent symmetric random variables*, Studia Math 123 (1997), no. 1, 15–42. MR1438303
[16] Jun-Ting Hsieh, Pravesh K Kothari, Aaron Potechin, and Jeff Xu, *Ellipsoid fitting up to a constant*, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023), vol. 261, 2023, p. 78. MR4612948

[17] Hong Hu and Yue M Lu, *Universality laws for high-dimensional learning with random features*, IEEE Transactions on Information Theory **69** (2022), no. 3, 1932–1964. MR4564688

[18] Adel Javanmard, Andrea Montanari, and Federico Ricci-Tersenghi, *Phase transitions in semidefinite relaxations*, Proceedings of the National Academy of Sciences **113** (2016), no. 16, E2218–E2223. MR3494080

[19] Daniel Kane and Ilias Diakonikolas, *A nearly tight bound for fitting an ellipsoid to gaussian random points*, The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 3014–3028.

[20] Bruno Loureiro, Cedric Gerbelot, Hugo Cui, Sebastian Goldt, Florent Krzakala, Marc Mezard, and Lenka Zdeborová, *Learning curves of generic features maps for realistic datasets with a teacher-student model*, Advances in Neural Information Processing Systems **34** (2021), 18137–18151. MR4535572

[21] Antoine Maillard and Dmitriy Kunisky, *Fitting an ellipsoid to random points: predictions using the replica method*, IEEE Transactions on Information Theory (2024), 1–1. MR4810400

[22] Marc Mézard, Giorgio Parisi, and Miguel Angel Virasoro, *Spin glass theory and beyond: An introduction to the replica method and its applications*, vol. 9, World Scientific Publishing Company, 1987. MR1026102

[23] Andrea Montanari and Basil N Saeed, *Universality of empirical risk minimization*, Conference on Learning Theory, PMLR, 2022, pp. 4310–4312.

[24] Andrea Montanari and Subhabrata Sen, *Semidefinite programs on sparse random graphs and their application to community detection*, Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 814–827. MR3536616

[25] Ryan O'Donnell, *Analysis of boolean functions*, Cambridge University Press, 2014. MR3443800

[26] Samet Oymak and Joel A Tropp, *Universality laws for randomized dimension reduction, with applications*, Information and Inference: A Journal of the IMA **7** (2018), no. 3, 337–446. MR3858331

[27] Anastasia Podsinnikova, Amelia Perry, Alexander S Wein, Francis Bach, Alexandre d'Aspremont, and David Sontag, *Overcomplete independent component analysis via SDP*, The 22nd International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 2583–2592.

[28] Aaron Potechin, Paxton M Turner, Prayaag Venkat, and Alexander S Wein, *Near-optimal fitting of ellipsoids to random points*, The Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 4235–4295.

[29] 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** (2012), no. 4, 1395–1416. MR3028972

[30] James Saunderson, Pablo A Parrilo, and Alan S Willsky, *Diagonal and low-rank decompositions and fitting ellipsoids to random points*, 52nd IEEE Conference on Decision and Control, IEEE, 2013, pp. 6031–6036.

[31] James Francis Saunderson, *Subspace identification via convex optimization*, Ph.D. thesis, Massachusetts Institute of Technology, 2011.

[32] Dominik Schröder, Hugo Cui, Daniil Dmitriev, and Bruno Loureiro, *Deterministic equivalent and error universality of deep random features learning*, International Conference on Machine Learning, PMLR, 2023, pp. 30285–30320. MR4832812

[33] Michel Talagrand, *The supremum of some canonical processes*, American Journal of Mathematics **116** (1994), no. 2, 283–325. MR1269606

[34] Christos Thrampoulidis, Ehsan Abbasi, and Babak Hassibi, *Precise error analysis of regularized *m*-estimators in high dimensions*, IEEE Transactions on Information Theory **64** (2018), no. 8, 5592–5628. MR3832326
[35] Christos Thrampoulidis, Samet Oymak, and Babak Hassibi, Regularized linear regression: A precise analysis of the estimation error, Conference on Learning Theory, PMLR, 2015, pp. 1683-1709.

[36] Madhur Tulsiani and June Wu, Ellipsoid fitting up to constant via empirical covariance estimation, 2025 Symposium on Simplicity in Algorithms (SOSA), SIAM, 2025, pp. 134-143. MR4862671

[37] Ramon Van Handel, Probability in high dimension, Lecture Notes (Princeton University), 2014.

[38] Roman Vershynin, High-dimensional probability: An introduction with applications in data science, vol. 47, Cambridge university press, 2018. MR3837109

**Acknowledgments.** The authors are grateful to March Boedihardjo, Tim Kunisky, Petar Nizić-Nikolac, and Joel Tropp for insightful discussions and suggestions.

## A A classical concentration inequality

We will make use of the following elementary concentration inequality, a generalization of Bernstein's inequality for $\psi_q$ tails [33, 15, 1].

**Lemma A.1** (Tail of sum of independent sub-Weibull random variables [1]–). Let $q \in (0, 2]$, and $W_1, \dots, W_n$ be i.i.d. centered random variables satisfying $P[|W_1| \ge t] \le 2e^{-Ct^q}$.

(i) If $q \in [1, 2]$, then for all $a \in \mathbb{R}^n$ and all $t \ge 0$:

$$ P\left[\left|\sum_{\mu=1}^{n} a_{\mu} W_{\mu}\right| \geq t\right] \leq 2 \exp \left\{-c \min \left(\frac{t^{2}}{\|a\|_{2}^{2}}, \frac{t^{q}}{\|a\|_{q}^{q}}\right)\right\}, $$

where $q^* \in [2, +\infty]$ with $1/q + 1/q^* = 1$.

(ii) If $q \in [1/2, 1]$, then for all $t > 0$

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

This lemma is stated in [1], see Lemmas 3.6 and 3.7 – and eq. (3.7) – and is a consequence of the same result for symmetric Weibull random variables [15].

## B Fitting error of the sphere

We show here eq. (1.6). By Bernstein's inequality [38], we have for all $\mu \in [n]$ and $u \ge 0$:

$$ P\left[\left|\frac{\|x_{\mu}\|^2}{d} - 1\right| \geq u\right] \leq 2 \exp \left(-Cd \min(u, u^2)\right). $$

As a consequence, if $X_\mu := \sqrt{d}(\|x_\mu\|^2/d - 1)$, then$^8 \|X_\mu\|_{\psi_1} \le C$. Let $Y_\mu := |X_\mu|^r - E[|X_\mu^r|]$.

By the central limit theorem, $X_\mu \xrightarrow{d} \mathcal{N}(0, 2)$ as $d \to \infty$. One shows easily that (e.g. for $\varepsilon = 2$):

$$ \sup_{d \ge 1} \mathrm{E}[|X_\mu|^{2+\varepsilon}] < \infty, $$

and thus (since $r \le 2) |X_\mu|^r$ is uniformly integrable as $d \to \infty$. This implies (cf. Theorem 3.5 of [6]) that $E|X_\mu|^r \to E|Z|^r$ with $Z \sim \mathcal{N}(0, 2)$. Notice that $E[|Z|^r] = 2^r \Gamma([r+1]/2)/\sqrt{\pi}$.

<footnote>$^8$Where for $q \in [1, \infty)$, we defined the Orlicz norm of a random variable $X$ as $\|X\|_{\psi_q} := \inf\{t > 0 : E\exp(|X|^q/t^q) \le 2\}$. In particular if $\|X\|_{\psi_1} < \infty$ then $X$ is said to be a sub-exponential random variable. We refer to [38] for more details on these classical definitions.</footnote>
Exact threshold for approximate ellipsoid fitting of random points

Let $q := 1/r \in [1/2, 1]$. Since $\|X_\mu\|_{\psi_1} \le C$, we have $\|\|X_\mu|^r\|_{\psi_q} \le C$, and thus $\|Y_\mu\|_{\psi_q} \le C'$. We can then use Lemma A.1, and we get:

$$ \mathbb{P}\left[\left|\frac{1}{n}\sum_{\mu=1}^{n} (|X_{\mu}|^r - \mathbb{E}[|X_{\mu}|^r])\right| \ge t\right] \le 2\exp\left\{-c_r \min(nt^2, (nt)^{1/r})\right\}. $$

Combining the above, we get that for any $\varepsilon > 0$, we have with probability $1 - o_d(1)$:

$$ \mathbb{E}[|Z|^r] - \varepsilon \le \frac{1}{n} \sum_{\mu=1}^{n} \left| \sqrt{d} \left[ \frac{\|x_\mu\|^2}{d} - 1 \right] \right|^r \le \mathbb{E}[|Z|^r] + \varepsilon. $$

C Towards exact ellipsoid fitting

We show here the following proposition.

**Proposition C.1** (From approximate to exact ellipsoid fitting). Let $n, d \to \infty$ with $n/d^2 \to \alpha \in (0, 1/2)$. Let $\{X_\mu\}_{\mu=1}^n$ be symmetric random matrices, and $H_{\mu\nu} := \text{Tr}[X_\mu X_\nu]$. Assume that:

(i) With probability $1 - o_d(1)$, $\|H^{-1}\|_{\text{op}} \le Cn^{-1/2}$ for some $C = C(\alpha) > 0$.

(ii) There exists $\lambda_-$ such that there exists $S \succeq 0$ such that $\text{Tr}[X_\mu S] = 1$ for all $\mu \in [n]$.

$$ \text{p-lim}_{n \to \infty} \min_{S \succeq \lambda_- I_d} \frac{1}{\sqrt{n}} \sum_{\mu=1}^{n} |\text{Tr}(X_\mu S) - 1|^2 = 0. \quad (C.1) $$

Then, with probability $1 - o_d(1)$ there exists $S \succeq 0$ such that $\text{Tr}[X_\mu S] = 1$ for all $\mu \in [n]$.

Let us emphasize that given our current proof of Theorem 1.4 (cf. Section 2.4), if the assumptions of Proposition C.1 hold for $X_\mu \sim \text{Ellipse}(d)$ and $\alpha < 1/4$, then the first part of Conjecture 1.2 will hold.

However, the proof of Proposition C.1 is rather naive, as it crudely bounds the operator norm distance of the minimizer of eq. (C.1) to a subspace $V$ (the affine subspace of solutions to the linear constraints $\text{Tr}[X_\mu S] = 1$) by its distance in Frobenius norm. For these reasons, the assumptions of Proposition C.1 may be far from being optimal.

**Remark I** – Note that the condition (i) is clearly satisfied if $X_\mu \stackrel{\text{i.i.d.}}{\sim} \text{GOE}(d)$ and $\alpha \in (0, 1/2)$, since $H$ is then distributed as a Wishart matrix. On the other hand, while we expect it to hold as well for $X_\mu \stackrel{\text{i.i.d.}}{\sim} \text{Ellipse}(d)$, this condition is (to the best of our knowledge) not known unless $\alpha$ is small enough: interestingly, this was one of the limitations in the recent works [5, 36, 16] that proved that ellipsoid fitting is feasible for $\alpha$ sufficiently small.

**Remark II** – Note that it is sufficient for eq. (C.1) to hold that there exists $r \in [1, 2]$ such that:

$$ \text{p-lim}_{n \to \infty} \min_{S \succeq \lambda_- I_d} \frac{1}{n^{r/4}} \sum_{\mu=1}^{n} |\text{Tr}(X_\mu S) - 1|^r = 0. $$

At the moment, our proof of Theorem 1.4 (cf. Lemma 2.6) only implies (for $r < 4/3$) a similar statement with a prefactor $1/n$ rather than the required $1/n^{r/4}$. It would thus need to be improved to show that eq. (C.1) holds for the ellipsoid fitting setting.

**Proof of Proposition C.1.** Let $V := \{S \in S_d : \text{Tr}[X_\mu S] = 1, \forall \mu \in [n]\}$ be the affine space of solutions to the constraints. Let $\varepsilon > 0$, and $\hat{S} \succeq \lambda_- I_d$ such that

$$ \frac{1}{\sqrt{n}} \sum_{\mu=1}^{n} |\text{Tr}(X_\mu \hat{S}) - 1|^2 \le \varepsilon. $$
Note that for all $M \in S_d$, if $\|M\|_{op} \le \lambda_-$, then $\hat{S} + M \succeq 0$. In particular, $\|M\|_F \le \lambda_- \Rightarrow \hat{S} + M \succeq 0$. In order to conclude it thus suffices to show that $d_F(\hat{S}, V) \le \lambda_-$. The following lemma is an elementary geometrical result:

**Lemma C.2 (Euclidean distance to an affine subspace -).** Let $d \ge 1$ and $1 \le r \le d$ two integers. Let $(a_k, b_k)_{k=1}^r \in (\mathbb{R}^d \times \mathbb{R})^r$, with $(a_k)_{k=1}^r$ linearly independent. We define $G := \{x \in \mathbb{R}^d : a_k^\top x + b_k = 0, \forall k \in [r]\}$. Then, for any $y \in \mathbb{R}^d$:

$$d_2(y, G)^2 = v^\top H^{-1} v,$$

in which $v_k := a_k^\top y + b_k$, and $H_{kk'} = \langle a_k, a_{k'} \rangle$ is the Gram matrix of the $\{a_k\}$.

We now condition on the event of condition (i). For any $\varepsilon > 0$, applying Lemma C.2 yields (with probability $1 - o_d(1)$):

$$d_F(\hat{S}, V)^2 \le C(\alpha)\varepsilon,$$

so that picking $\varepsilon \le \lambda_-^2/C(\alpha)$ implies the result. $\square$

<figure><img src="image_10.png" /></figure>

# D Additional proofs for Proposition 2.2

## D.1 Proof of Lemma 4.2

The lemma is a direct corollary of the following elementary result.

**Proposition D.1 (Bounding a Gaussian process on the sphere).** Let $n, p \ge 1$. Let $G \in \mathbb{R}^{n \times p}$ with $G_{ij} \stackrel{\text{i.i.d.}}{\sim} \mathcal{N}(0, 1)$. There is $A > 0$ such that for all $\delta > 0$ and $r \ge 1$:

$$P\left[ \max_{\|x\|=1} \|Gx\|_r \ge [A(\sqrt{n} + \sqrt{p}) + \delta\sqrt{n}] n^{\max(1/r-1/2,0)} \right] \le \exp\left\{-\frac{n\delta^2}{2}\right\}.$$

*Proof of Proposition D.1.* Notice that $G \to \max_{\|x\|=1} \|Gx\|_r$ is Lipschitz:

$$\left| \max_{\|x\|=1} \|G_1 x\|_r - \max_{\|x\|=1} \|G_2 x\|_r \right| \le \max_{\|x\|=1} \|(G_1 - G_2)x\|_r, \\ \stackrel{(a)}{\le} n^{\max(\frac{1}{r}-\frac{1}{2},0)} \max_{\|x\|=1} \|(G_1 - G_2)x\|_2, \\ \le n^{\max(\frac{1}{r}-\frac{1}{2},0)} \|G_1 - G_2\|_F,$$

where we used Hölder's inequality in the form $\|y\|_r \le n^{\frac{1}{r}-\frac{1}{2}} \|y\|_2$ for $r \le 2$, and for $r \ge 2$ the fact that $\|y\|_r \le \|y\|_2$, alongside with $\|G\|_{op} \le \|G\|_F$. By Theorem 3.4 we reach:

$$P\left[ \max_{\|x\|=1} \|Gx\|_r \ge \mathbb{E} \max_{\|x\|=1} \|Gx\|_r + \delta n^{\max(1/r, 1/2)} \right] \le \exp\left\{-\frac{n\delta^2}{2}\right\}.$$

The proof is complete if we can show that $\mathbb{E} \max_{\|x\|=1} \|Gx\|_r = \mathcal{O}(n^{\max(1/r-1/2,0)}) \cdot (\sqrt{n} + \sqrt{p})$. This follows by the same inequality as above:

$$\mathbb{E} \max_{\|x\|=1} \|Gx\|_r \le n^{\max(\frac{1}{r}-\frac{1}{2},0)} \mathbb{E} \max_{\|x\|=1} \|Gx\|_2.$$

The bound $\mathbb{E} \max_{\|x\|=1} \|Gx\|_2 = \mathcal{O}(\sqrt{n} + \sqrt{p})$ is well-known, see e.g. [38]. $\square$

<figure><img src="image_11.png" /></figure>

## D.2 Proof of Theorem 4.6

As we have seen, it suffices to prove Lemmas 4.7 and 4.8. We introduce some additional notations.
• For any $\mu \in [n]$, we denote

$$ \langle \cdot \rangle_{\mu} := \frac{\int P_0(dS) e^{-\sum_{\nu(\neq \mu)} \phi[\mathrm{Tr}(U_{\nu}(t)S)]} (\cdot)}{\int P_0(dS) e^{-\sum_{\nu(\neq \mu)} \phi[\mathrm{Tr}(U_{\nu}(t)S)]}}. \quad (D.1) $$

We do not write explicitly the $t$ dependency of this average as it will be clear from context.

• For any $\mu$, we denote $\mathbb{E}_{(\mu)}$ the expectation conditioned on $\{G_{\mu}, W_{\mu}\}$, i.e. the expectation over $\{G_{\nu}, W_{\nu}\}_{\nu(\neq \mu)}$. Note that this notation is different from [23], for which $\mathbb{E}_{(\mu)}$ was the expectation with respect to $(G_{\mu}, W_{\mu})$. On the other hand, we denote without parenthesis the expectation with respect to these variables: e.g. $\mathbb{E}_{(1)}$ is conditioned on $\{G_1, W_1\}$, but $\mathbb{E}_{G_1, W_1}$ is the expectation w.r.t. $G_1, W_1$.

### D.2.1 Proof of Lemma 4.7

We fix $t \in (0, \pi/2)$, and we start from eq. (4.16), which we can rewrite using eq. (D.1) as:

$$ \mathbb{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} = -\frac{n}{d^2} \mathbb{E} \left[ \psi'[F_d(U(t))] \frac{\left\langle e^{-\phi(\mathrm{Tr}[U_1(t)S])} (\mathrm{Tr}[S\tilde{U}_1(t)] \phi'(\mathrm{Tr}[U_1(t)S])) \right\rangle_1}{\left\langle e^{-\phi(\mathrm{Tr}[U_1(t)S])} \right\rangle_1} \right]. $$

Since $\|\psi'\|_{\infty} < \infty$ and $n/d^2 \le \alpha_2$, using the triangular inequality the proof of Lemma 4.7 is complete if one can show the following bound, which will also be useful afterwards:

**Lemma D.2.** There exists a universal constant $C > 0$ such that:

$$ \sup_{d \ge 1} \sup_{t \in (0, \pi/2)} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \mathbb{E}_{W_1, G_1} \frac{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} |\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S])| \right\rangle_1}{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \right\rangle_1} \le C. $$

**Proof of Lemma D.2.** Note that

$$ \begin{aligned} & \mathbb{E}_{W_1, G_1} \frac{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} |\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S])| \right\rangle_1}{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \right\rangle_1} \\ & \le \|\phi'\|_{\infty} \mathbb{E}_{W_1, G_1} \left[ \frac{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} |\mathrm{Tr}[S\tilde{U}_1(t)]| \right\rangle_1}{\left\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \right\rangle_1} \right], \\ & \le e^{\|\phi\|_{\infty}} \|\phi'\|_{\infty} \mathbb{E}_{W_1, G_1} \left[ \left\langle |\mathrm{Tr}[S\tilde{U}_1(t)]| \right\rangle_1 \right], \end{aligned} \quad (D.2) $$

in which we used the positivity and boundedness of $\phi$ in the last inequality. To control the last term in eq. (D.2) we write:

$$ \begin{aligned} \mathbb{E}_{G_1, W_1} \left[ \left\langle |\mathrm{Tr}[S\tilde{U}_1(t)]| \right\rangle_1 \right] & \stackrel{(a)}{=} \left\langle \mathbb{E}_{G_1, W_1} |\mathrm{Tr}[S\tilde{U}_1(t)]| \right\rangle_1, \\ & \stackrel{(b)}{\le} \left\langle \left\{ \mathbb{E}_{G_1, W_1} (\mathrm{Tr}[S\tilde{U}_1(t)]^2) \right\}^{1/2} \right\rangle_1, \\ & \stackrel{(c)}{\le} \sqrt{2} \left\langle \left\{ \frac{1}{d} \mathrm{Tr}[S^2] \right\}^{1/2} \right\rangle_1, \end{aligned} \quad (D.3) $$

$$ \stackrel{(d)}{\le} \sqrt{2} C_0, \quad (D.4) $$

where (a) uses that $\langle \cdot \rangle_1$ is independent of $\{W_1, G_1\}$, (b) is from the Cauchy-Schwarz inequality, in (c) we use the hypothesis on the first two moments of $\rho$ matching the ones of GOE(d), and in (d) that $\mathrm{supp}(P_0) \subseteq B_2(C\sqrt{d})$. $\square$
### D.2.2 Proof of Lemma 4.8

We fix $t \in (0, \pi/2)$ for the rest of the proof, and we write $U, \tilde{U}$ for $U(t), \tilde{U}(t)$. We follow the ideas of Appendix A.3 of [23], and start again from eq. (4.16):

$$ \left| \mathrm{E} \frac{\partial \psi[F_d(U(t))]}{\partial t} \right| \le \alpha_2(I_1 + I_2), \qquad (\mathrm{D.5}) $$

with:

$$ I_1 = \left| \mathrm{E} \left[ \left\{ \psi'[F_d(U)] - \psi'[F_d(U^{(1)})] \right\} \frac{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S]))}{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])}} \right] \right|, $$

$$ I_2 = \left| \mathrm{E} \left[ \psi'[F_d(U^{(1)})] \frac{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S]))}{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])}} \right] \right|, $$

with $U^{(\mu)}$ obtained from $U$ by setting $U_\mu = 0$. We show successively $I_1 \to 0$ and $I_2 \to 0$. Since $\psi'$ is assumed to be Lipschitz, we have:

$$ \begin{aligned} |\psi'[F_d(U)] - \psi'[F_d(U^{(1)})]| &\le \frac{\|\psi'\|_{\mathrm{Lip}}}{d^2} \left| \log \frac{\int P_0(\mathrm{d}S) e^{-\sum_{\nu=1}^n \phi(\mathrm{Tr}[U_\nu S])}}{\int P_0(\mathrm{d}S) e^{-\sum_{\nu=2}^n \phi(\mathrm{Tr}[U_\nu S])}} \right|, \\ &\le \frac{\|\psi'\|_{\mathrm{Lip}}}{d^2} \left| \log \left\langle e^{-\phi(\mathrm{Tr}[U_1S])} \right\rangle_1 \right|, \\ &\le -\frac{\|\psi'\|_{\mathrm{Lip}}}{d^2} \log \left\langle e^{-\phi(\mathrm{Tr}[U_1S])} \right\rangle_1, \\ &\le \frac{\|\psi'\|_{\mathrm{Lip}} \|\phi\|_\infty}{d^2}. \end{aligned} $$

Therefore,

$$ I_1 \le O_d \left( \frac{1}{d^2} \right) \times \mathrm{E} \left| \frac{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S]))}{\int P_0(\mathrm{d}S) e^{-\sum_{\nu} \phi(\mathrm{Tr}[U_\nu S])}} \right|, \qquad (\mathrm{D.6}) $$

The second term in eq. (D.6) is bounded by Lemma D.2, uniformly in $t$. Therefore, we reach that $I_1 \to 0$ as $d \to \infty$.

We now tackle $I_2$. Note that since $U^{(1)}$ is independent of $U_1$, we can rewrite it as:

$$ \begin{aligned} I_2 &= \left| \mathrm{E}_{(1)} \left[ \psi'[F_d(U^{(1)})] \mathrm{E}_{G_1, W_1} \left[ \frac{\left\langle e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S])) \right\rangle_1}{\left\langle e^{-\phi(\mathrm{Tr}[U_1S])} \right\rangle_1} \right] \right| \right|, \\ &\le \|\psi'\|_{\infty} \mathrm{E}_{(1)} \left| \left\langle \mathrm{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S]))}{\left\langle e^{-\phi(\mathrm{Tr}[U_1S])} \right\rangle_1} \right] \right\rangle_1 \right| \end{aligned} \qquad (\mathrm{D.7}) $$

We focus on bounding the right-hand side of eq. (D.7). We will show the following lemma:

**Lemma D.3.** Uniformly over all $t \in [0, \pi/2]$ and $\{W_\mu, G_\mu\}_{\mu=2}^n$, and under the hypotheses of Theorem 4.6:

$$ \lim_{d \to \infty} \left\langle \mathrm{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1]\phi'(\mathrm{Tr}[U_1S]))}{\left\langle e^{-\phi(\mathrm{Tr}[U_1S])} \right\rangle_1} \right] \right\rangle_1 = 0. \qquad (\mathrm{D.8}) $$
Exact threshold for approximate ellipsoid fitting of random points

One directly concludes that $I_2 \to 0$ from using the dominated convergence theorem in eq. (D.7) (the pointwise limit is given by Lemma D.3 and the domination hypothesis by Lemma D.2). This ends the proof of Lemma 4.8.

We thus focus on the proof of Lemma D.3. Following [23], the sketch of the proof is the following:

(i) Show that the denominator appearing in eq. (D.8) can be moved to the numerator by using the expansion of $1/x$ in power series around 1. This transforms the quantity to control to a sum of terms of the type $\langle \mathbb{E}_{G_1, W_1}[f(S_1, \dots, S_k)] \rangle_1$, with $S_1, \dots, S_k$ independent samples under $\langle \cdot \rangle_1$.

(ii) Extend the one-dimensional CLT of Definition 4.5 to $k$-dimensional projections of $G$ and $W$ (with $k = O_d(1)$), and to square-integrable locally-Lipschitz functions. This allows to apply it to the terms appearing in (i), and write (uniformly in $S_1, \dots, S_k$) that $\mathbb{E}_{G_1, W_1}[f(S_1, \dots, S_k)] \simeq \mathbb{E}_{G_1, \tilde{G}_1}[f(S_1, \dots, S_k)]$, with $\tilde{G}_1$ an independent GOE(d) matrix.

(iii) For the case of Gaussian matrices, as explained above we have $\tilde{U}_1$ independent of $U_1$. Using the form of the function $f$ that appears in eq. (D.8) this implies that $\mathbb{E}_{G_1, \tilde{G}_1}[f(S_1, \dots, S_k)] = 0$ and concludes the proof.

Let us perform this strategy in detail. The following lemma is proven in Section D.3.

**Lemma D.4 (Polynomial approximation to the fraction -).** For all $\delta > 0$, there exists a real polynomial $Q$ (depending only on $\delta$) such that for all $d \ge 1$, all $t \in (0, \pi/2)$ and all $\{W_\mu, G_\mu\}_{\mu=2}^n$:

$$ \left| \left\langle \mathbb{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1 S])} (\mathrm{Tr}[S \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S]))}{\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \rangle_1} \right] \right\rangle_1 \right| \\ \le \left| \mathbb{E}_{G_1, W_1} \left\{ \langle e^{-\phi(\mathrm{Tr}[U_1 S])} (\mathrm{Tr}[S \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S])) \rangle_1 Q(\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \rangle_1) \right\} \right| + \delta. $$

We fix $\delta > 0$, and denote $Q(X) = \sum_{k=0}^K a_k X^k$ the polynomial of Lemma D.4. Therefore, uniformly in $d, t$, and $\{W_\mu, G_\mu\}$:

$$ \left| \left\langle \mathbb{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1 S])} (\mathrm{Tr}[S \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S]))}{\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \rangle_1} \right] \right\rangle_1 \right| \\ \le \sum_{k=0}^K |a_k| \left| \left\langle \mathbb{E}_{G_1, W_1} \left\{ e^{-\sum_{a=0}^k \phi(\mathrm{Tr}[U_1 S_a])} (\mathrm{Tr}[S_0 \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S_0])) \right\} \right\rangle_1 \right| + \delta, \quad (D.9) $$

with $\{S_a\}_{a=0}^k$ i.i.d. samples from $\langle \cdot \rangle_1$. We then extend the one-dimensional CLT of Definition 4.5 to finite-dimensional projections, similarly to Lemmas 29 and 30 of [23]. The proof of this lemma is deferred to Section D.3.

**Lemma D.5 (Extension of the CLT to finite-dimensional projections -).** Let $R \ge 1$ an integer, and $\tilde{G} \sim \mathrm{GOE}(d)$, independent of everything else. Let $\phi : \mathbb{R}^{2R} \to \mathbb{R}$ a locally Lipschitz function such that for both $X \in \{W, \tilde{G}\}$:

$$ \sup_{d \ge 1} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \sup_{t \in (0, \pi/2)} \left\langle \mathbb{E}_{X, G} \left[ \varphi \left( \left\{ \mathrm{Tr}(XS_a) \right\}_{a=1}^R, \left\{ \mathrm{Tr}(GS_a) \right\}_{a=1}^R \right) \right]^2 \right\rangle_1 < \infty. \quad (D.10) $$
Exact threshold for approximate ellipsoid fitting of random points

It is understood there that {$S_a$}^{i.i.d.} $\sim \langle \cdot \rangle_1$. Then

$$
\lim_{d \to \infty} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \sup_{t \in (0, \pi/2)} \left\langle \left| \mathbb{E}_{W,G} \varphi(\{\mathrm{Tr}(WS_a)\}, \{\mathrm{Tr}(GS_a)\}) - \mathbb{E}_{\tilde{G},G} \varphi(\{\mathrm{Tr}(\tilde{G}S_a)\}, \{\mathrm{Tr}(GS_a)\}) \right| \right\rangle_1 = 0.
$$

We wish to apply Lemma D.5 to eq. (D.9), i.e. to

$$
\varphi(\{\mathrm{Tr}(W_1 S_a)\}, \{\mathrm{Tr}(G_1 S_a)\}) := e^{-\sum_{a=0}^{k} \phi(\mathrm{Tr}[U_1 S_a])} (\mathrm{Tr}[S_0 \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S_0]))
$$

$\varphi$ is locally Lipschitz by our hypotheses on $\phi$. Moreover, note that for $X \in \{W, \tilde{G}\}$, and $\{S^a\} \in \mathrm{supp}(P_0)$ (using that $W$ has the same two first moments as $\tilde{G}$):

$$
\mathbb{E}_{X,G} \left[ \varphi \left( \{\mathrm{Tr}(XS_a)\}, \{\mathrm{Tr}(GS_a)\} \right) \right]^2 \le 2 \|\phi'\|_{\infty}^2 \mathrm{Tr}[S_0^2]/d \le 2C_0^2 \|\phi'\|_{\infty}^2 < \infty.
$$

This allows to apply Lemma D.5 in eq. (D.9), and to reach that, uniformly in {$W_\mu, G_\mu$}$_{\mu=2}^n$
and $t \in (0, \pi/2)$ we have:

$$
\begin{align*}
& \limsup_{d \to \infty} \left| \left\langle \mathbb{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1 S])} (\mathrm{Tr}[S \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S]))}{\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \rangle_1} \right] \right\rangle_1 \right| \\
& \le \delta + \sum_{k=0}^{K} |a_k| \limsup_{d \to \infty} \left| \left\langle \mathbb{E}_{G_1, W_1} \varphi(\{\mathrm{Tr}(W_1 S_a)\}, \{\mathrm{Tr}(G_1 S_a)\}) \right\rangle_1 \right|, \\
& \le \delta + \sum_{k=0}^{K} |a_k| \limsup_{d \to \infty} \left| \left\langle \mathbb{E}_{G_1, \tilde{G}_1} \varphi(\{\mathrm{Tr}(\tilde{G}_1 S_a)\}, \{\mathrm{Tr}(G_1 S_a)\}) \right\rangle_1 \right| \\
& \qquad + \sum_{k=0}^{K} |a_k| \limsup_{d \to \infty} \left| \left\langle \mathbb{E}_{G_1, W_1} \varphi(\{\mathrm{Tr}(W_1 S_a)\}, \{\mathrm{Tr}(G_1 S_a)\}) \right\rangle_1 \right. \\
& \qquad \qquad \left. - \mathbb{E}_{G_1, \tilde{G}_1} \varphi(\{\mathrm{Tr}(\tilde{G}_1 S_a)\}, \{\mathrm{Tr}(G_1 S_a)\}) \right|_1, \\
& \stackrel{(a)}{\le} \delta + \sum_{k=0}^{K} |a_k| \limsup_{d \to \infty} \left| \left\langle \mathbb{E}_{G_1, \tilde{G}_1} \left\{ e^{-\sum_{a=0}^k \phi(\mathrm{Tr}[V_1 S_a])} (\mathrm{Tr}[S_0 \tilde{V}_1] \phi'(\mathrm{Tr}[V_1 S_0])) \right\} \right\rangle_1 \right|,
\end{align*}
$$

where we used Lemma D.5 in (a), and with $V_1 = \cos(t)\tilde{G}_1 + \sin(t)G_1$, and $\tilde{V}_1 = -\sin(t)\tilde{G}_1 + \cos(t)G_1$. Since $G_1, \tilde{G}_1$ are gaussians, so are $V_1$ and $\tilde{V}_1$, and one verifies easily that they are independent since their covariance is zero. Therefore, we have:

$$
\mathbb{E}_{G_1, \tilde{G}_1} \left\{ e^{-\sum_{a=0}^{k} \phi(\mathrm{Tr}[V_1 S_a])} \left( \mathrm{Tr}[S_0 \tilde{V}_1] \phi'(\mathrm{Tr}[V_1 S_0]) \right) \right\} \\
= \mathbb{E}_{V_1} \left\{ e^{-\sum_{a=0}^{k} \phi(\mathrm{Tr}[V_1 S_a])} \left( \underbrace{\left[ \mathbb{E}_{\tilde{V}_1} \mathrm{Tr}[S_0 \tilde{V}_1] \right]}_{=0} \phi'(\mathrm{Tr}[V_1 S_0]) \right) \right\} = 0.
$$

Thus, we reach, for any $\delta > 0$:

$$
\limsup_{d \to \infty} \sup_{t \in (0, \pi/2)} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \left| \left\langle \mathbb{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1 S])} (\mathrm{Tr}[S \tilde{U}_1] \phi'(\mathrm{Tr}[U_1 S]))}{\langle e^{-\phi(\mathrm{Tr}[U_1 S])} \rangle_1} \right] \right\rangle_1 \right| \le \delta.
$$

Letting $\delta \to 0$ finishes the proof of Lemma D.3.

<figure><img src="image_12.png" /></figure>
## D.3 Additional proofs

### D.3.1 Proof of Lemma D.4

We use the power expansion of $x \mapsto 1/x$ around $x = 1$, defining, for $M \ge 1$:

$$Q_M(x) := \sum_{k=0}^{M} (1-x)^k, \qquad R_M(x) := \frac{1}{x} - Q_M(x).$$

We make use of Lemma 27 of [23]:

**Lemma D.6 ([23]).** For any integer $M \ge 1$ we have

* For all $x \ne 0$, $R_M(x) = (1-x)^{M+1}/x$.

* $x \mapsto R_M(x)^2$ is convex on $(0, 1]$.

* For any $s \in (0, 1)$ and $\eta > 0$, there exists $M \ge 1$ such that $\sup_{t \in [s, 1]} |R_M(t)| \le \eta$.

Since $e^{-\|\phi\|_{\infty}} \le e^{-\phi} \le 1$, we have that for all $\eta > 0$ there exists $M_{\eta} \ge 1$ such that for all $M \ge M_{\eta}$, all matrices $\{W_{\mu}, G_{\mu}\}_{\mu=1}^n$, all $t \in (0, \pi/2)$:

$$\left| R_M \left( \langle e^{-\phi(\mathrm{Tr}[SU_1])} \rangle_1 \right) \right| \le \eta. \qquad (\mathrm{D.11})$$

Thus, since $1/x = Q_M(x) + R_M(x)$:

$$\begin{aligned}
& \left| \left\langle \mathrm{E}_{G_1, W_1} \left[ \frac{e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S]))}{\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1} \right] \right\rangle_1 \right| \\
& \le \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S])) Q_M (\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1)] \right\rangle_1 \right| \\
& \qquad + \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S])) R_M (\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1)] \right\rangle_1 \right|, \\
& \stackrel{(a)}{\le} \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S])) Q_M (\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1)] \right\rangle_1 \right| \\
& \qquad + \eta \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} |(\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S]))|] \right\rangle_1, \\
& \le \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S])) Q_M (\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1)] \right\rangle_1 \right| \\
& \qquad + \eta \|\phi'\|_{\infty} \langle \mathrm{E}_{G_1, W_1} |\mathrm{Tr}[S\tilde{U}_1]| \rangle_1, \\
& \stackrel{(b)}{\le} \left| \left\langle \mathrm{E}_{G_1, W_1} [e^{-\phi(\mathrm{Tr}[U_1S])} (\mathrm{Tr}[S\tilde{U}_1] \phi'(\mathrm{Tr}[U_1S])) Q_M (\langle e^{-\phi(\mathrm{Tr}[U_1S])} \rangle_1)] \right\rangle_1 \right| + C\eta \|\phi'\|_{\infty},
\end{aligned}$$

using eq. (D.11) in (a), and the Cauchy-Schwarz inequality (cf. the proof of Lemma D.2) in (b). We emphasize that this bound is uniform in $t$ and $\{W_{\mu}, G_{\mu}\}$. Choosing $\eta = \delta/(C\|\phi'\|_{\infty})$ ends the proof of Lemma D.4.

## D.4 Proof of Lemma D.5

We first prove that the conclusion of Lemma D.5 holds uniformly over all $S_1, \dots, S_R \in A_d$ when the function $\varphi$ is assumed to be continuous with compact support:

**Lemma D.7.** Let $R \in \mathbb{N}^*$, and $\tilde{G} \sim \text{GOE}(d)$, independent of everything else. Let $\varphi: \mathbb{R}^{2R} \to \mathbb{R}$ be Lipschitz and compactly supported. Recall that $W \sim \rho$, a measure who is assumed to satisfy a one-dimensional CLT with respect to a set $A_d \subseteq S_d$, see Definition 4.5. We assume that $A_d$ is convex and symmetric. Then:

$$\lim_{d \to \infty} \sup_{S_1, \dots, S_R \in A_d} \left| \mathrm{E}_{W,G} \varphi(\{\mathrm{Tr}(WS_a)\}, \{\mathrm{Tr}(GS_a)\}) - \mathrm{E}_{\tilde{G},G} \varphi(\{\mathrm{Tr}(\tilde{GS}_a)\}, \{\mathrm{Tr}(GS_a)\}) \right| = 0.$$
Exact threshold for approximate ellipsoid fitting of random points

Proof of Lemma D.7. Recall that we use the matrix flattening function of eq. (3.8). Let us denote:

$$
\left\{
\begin{array}{l}
H := \begin{pmatrix} \operatorname{vec}(S^1) & 0 & \operatorname{vec}(S_2) & 0 & \cdots & \operatorname{vec}(S^R) & 0 \\ 0 & \operatorname{vec}(S^1) & 0 & \operatorname{vec}(S_2) & \cdots & 0 & \operatorname{vec}(S^R) \end{pmatrix} \in \mathbb{R}^{d(d+1) \times 2R}, \\
v := (\operatorname{vec}(W)^\top, \operatorname{vec}(G)^\top)^\top \in \mathbb{R}^{d(d+1)}, \\
h := (\operatorname{vec}(\tilde{G})^\top, \operatorname{vec}(G)^\top)^\top \in \mathbb{R}^{d(d+1)}.
\end{array}
\right.
\tag{D.12}
$$

Using these notations, we have:

$$
\left\{
\begin{array}{l}
\left( \{\operatorname{Tr}(WS_a)\}_{a=1}^R, \{\operatorname{Tr}(GS_a)\}_{a=1}^R \right) = H^\top v \in \mathbb{R}^{2R}, \\
\\
\left( \{\operatorname{Tr}(\tilde{GS}_a)\}_{a=1}^R, \{\operatorname{Tr}(GS_a)\}_{a=1}^R \right) = H^\top h \in \mathbb{R}^{2R}.
\end{array}
\right.
\tag{D.13}
$$

We add a small Gaussian noise to help us deal with characteristic functions later on. Let
$\delta > 0$, and $Z \sim \mathcal{N}(0, \delta^2 I_{2R})$. For all $S_1, \dots, S_R$ we have:

$$
\begin{align*}
|\mathrm{E} \varphi(H^\top v) - \mathrm{E} \varphi(H^\top h)| &\le |\mathrm{E} \varphi(H^\top v) - \mathrm{E} \varphi(H^\top v + Z)| + |\mathrm{E} \varphi(H^\top h) - \mathrm{E} \varphi(H^\top h + Z)| \\
&\phantom{\le} + |\mathrm{E} \varphi(H^\top v + Z) - \mathrm{E} \varphi(H^\top h + Z)|, \\
&\le 2 \|\varphi\|_L \mathrm{E} \|Z\|_2 + |\mathrm{E} \varphi(H^\top v + Z) - \mathrm{E} \varphi(H^\top h + Z)|, \\
&\le CR^{1/2} \|\varphi\|_L \delta + |\mathrm{E} \varphi(H^\top v + Z) - \mathrm{E} \varphi(H^\top h + Z)|. \tag{D.14}
\end{align*}
$$

We now control the last term of eq. (D.14). For $X \in \mathbb{R}^{2R}$ a random variable, we define its characteristic function as $\phi_X(u) := \mathrm{E} e^{-iu^\top X}$. We have then

$$
\begin{align*}
\frac{1}{(2\pi)^{2R}} \int_{\mathbb{R}^{2R}} \varphi(t) \int_{\mathbb{R}^{2R}} e^{it^\top u - \frac{\delta^2}{2} \|u\|^2} \phi_X(u) du \, dt &= \frac{1}{(2\pi\delta^2)^R} \mathrm{E}_X \int_{\mathbb{R}^{2R}} \varphi(t) e^{-\frac{\|t-x\|^2}{2\delta^2}} \, dt, \\
&= \mathrm{E} \varphi(X+Z).
\end{align*}
$$

Coming back to eq. (D.14) we get:

$$
\begin{align*}
& |\mathrm{E} \varphi(H^\top v + Z) - \mathrm{E} \varphi(H^\top h + Z)| \\
&\le \frac{1}{(2\pi)^{2R}} \int_{\mathbb{R}^{2R}} |\varphi(t)| \left| \int_{\mathbb{R}^{2R}} e^{it^\top u - \frac{\delta^2}{2} \|u\|^2} [\phi_{H^\top v}(u) - \phi_{H^\top h}(u)] du \right| dt, \\
&\le \frac{\|\varphi\|_{L_1}}{(2\pi)^{2R}} \int_{\mathbb{R}^{2R}} e^{-\frac{\delta^2}{2} \|u\|^2} |\phi_{H^\top v}(u) - \phi_{H^\top h}(u)| du. \tag{D.15}
\end{align*}
$$

Here $\|\varphi\|_{L_1} := \int |\varphi(t)| dt$. We will show that for any $u \in \mathbb{R}^{2R}$:

$$
\lim_{d \to \infty} \sup_{S_1, \dots, S_R \in A_d} |\phi_{H^\top v}(u) - \phi_{H^\top h}(u)| = 0. \quad (D.16)
$$

Combining eq. (D.16) with the dominated convergence theorem applied in eq. (D.15),
we get:

$$
\lim_{d \to \infty} \sup_{S_1, \dots, S_R \in A_d} |\mathrm{E} \varphi(H^\top v + Z) - \mathrm{E} \varphi(H^\top h + Z)| = 0.
$$

Plugging this back into eq. (D.14), we get that for any $\delta > 0$:

$$
\limsup_{d \to \infty} \sup_{S_1, \dots, S_R \in A_d} |\mathrm{E} \varphi(H^\top v) - \mathrm{E} \varphi(H^\top h)| \leq C R^{1/2} \|\varphi\|_L \delta.
$$
Exact threshold for approximate ellipsoid fitting of random points

Letting $\delta \to 0$ ends the proof of Lemma D.7. There remains to prove eq. (D.16). Let $u = (u^{(1)}, u^{(2)}) \in \mathbb{R}^{2R}$, with $u^{(1)}, u^{(2)} \in \mathbb{R}^R$, and let us fix $S_1, \cdots, S_R \in A_d$. We have

$$ 
\begin{aligned}
& |\phi_{H^\tau v}(u) - \phi_{H^\tau h}(u)| \\
& = \left| \mathrm{E} e^{-i \sum_{a=1}^r u_a^{(1)} \mathrm{Tr}[WS_a]} - i \sum_{a=1}^r u_a^{(2)} \mathrm{Tr}[GS_a]} - \mathrm{E} e^{-i \sum_{a=1}^r u_a^{(1)} \mathrm{Tr}[\tilde{G}S_a]} - i \sum_{a=1}^r u_a^{(2)} \mathrm{Tr}[GS_a]} \right|, \\
& \stackrel{(a)}{=} \left| \mathrm{E} \exp \left\{ -i \mathrm{Tr} \left[ W \sum_{a=1}^r u_a^{(1)} S_a \right] \right\} - \mathrm{E} \exp \left\{ -i \mathrm{Tr} \left[ \tilde{G} \sum_{a=1}^r u_a^{(1)} S_a \right] \right\} \right|, \quad (\text{D.17})
\end{aligned}
$$

using in (a) that $G$ is independent of $W, \tilde{G}$. We can assume that $u^{(1)} \neq 0$, otherwise the result of eq. (D.16) is clear. Since $A_d$ is symmetric and convex we have

$$ \hat{S} := \frac{1}{\|u^{(1)}\|_1} \sum_{a=1}^{r} u_a^{(1)} S_a \in A_d. $$

Therefore, letting $\varphi_u(x) := e^{-i\|u\|_1 x}$, we have by eq. (D.17):

$$ |\phi_{H^\tau v}(u) - \phi_{H^\tau h}(u)| = |\mathrm{E} \varphi_u(\mathrm{Tr}[\hat{S}W]) - \mathrm{E} \varphi_u(\mathrm{Tr}[\hat{S}\tilde{G}])| \quad (\text{D.18}) $$

Moreover,

$$ |\varphi_u(x) - \varphi_u(y)| = \|u\|_1 \left| \int_0^{y-x} e^{i\|u\|_1 t} dt \right| \le \|u\|_1 |y-x|, $$

so that $\|\varphi_u\|_L \le \|u\|_1$. We can then therefore apply the one-dimensional CLT of Definition 4.5 in eq. (D.18), and we get that

$$ \sup_{S_1, \cdots, S_R \in A_d} |\phi_{H^\tau v}(u) - \phi_{H^\tau h}(u)| \le \sup_{S \in A_d} |\mathrm{E} \varphi_u(\mathrm{Tr}[SW]) - \mathrm{E} \varphi_u(\mathrm{Tr}[S\tilde{G}])| \to_{d \to \infty} 0. $$

This ends the proof of eq. (D.16).

□

We then deduce the full statement of Lemma D.5 by a truncation argument.

End of the proof of Lemma D.5. $\varphi$ is now only assumed to be locally Lipschitz and square integrable, in the sense of eq. (D.10). We take the same notations as in the proof of Lemma D.7, see in particular eq. (D.12), so that

$$ 
\begin{aligned}
& \mathrm{E}_{W,G} \varphi (\{\mathrm{Tr}(WS_a)\}, \{\mathrm{Tr}(GS_a)\}) - \mathrm{E}_{\tilde{G},G} \varphi (\{\mathrm{Tr}(\tilde{G}S_a)\}, \{\mathrm{Tr}(GS_a)\}) \\
& = \mathrm{E} \varphi(H^\tau v) - \mathrm{E} \varphi(H^\tau h).
\end{aligned}
$$

Let $B > 0$, and let us denote $u_B : \mathbb{R}_+ \to [0, 1]$ a $C^\infty$ function such that $u_B(x) = 1$ if $x \le B$ and $u_B(x) = 0$ if $x \ge B + 1$. We denote $\varphi_B(z) := \varphi(z)u_B(\|z\|)$. One can then check easily that $\varphi_B$ is Lipschitz (because $\varphi$ is locally-Lipschitz), and compactly supported. Moreover, we have:

$$ 
\begin{aligned}
& \langle |\mathrm{E} \varphi(H^\tau v) - \mathrm{E} \varphi(H^\tau h)| \rangle_1 \\
& \le \langle |\mathrm{E} \varphi_B(H^\tau v) - \mathrm{E} \varphi_B(H^\tau h)| \rangle_1 + \sum_{z \in \{h, v\}} \langle \mathrm{E} |\varphi(H^\tau z)| (1 - u_B(\|H^\tau z\|)) \rangle_1. \quad (\text{D.19})
\end{aligned}
$$

We now control the different terms in eq. (D.19) successively. Notice that

$$ \langle |\mathrm{E} \varphi_B(H^\tau v) - \mathrm{E} \varphi_B(H^\tau h)| \rangle_1 \le \sup_{S_1, \cdots, S_R \in A_d} |\mathrm{E} \varphi_B(H^\tau v) - \mathrm{E} \varphi_B(H^\tau h)|, $$
Exact threshold for approximate ellipsoid fitting of random points

so that by Lemma D.7:

$$ \lim_{d \to \infty} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \sup_{t \in (0, \pi/2)} \langle |\mathbb{E} \varphi_B(H^\top v) - \mathbb{E} \varphi_B(H^\top h)| \rangle_1 = 0. \quad (D.20) $$

We now tackle the remaining terms in eq. (D.19). Let $z \in \{h, v\}$. Using the Cauchy-Schwarz inequality twice we get:

$$ \begin{aligned} \langle \mathbb{E} |\varphi(H^\top z)|(1 - u_B(\|H^\top z\|)) \rangle_1 &\le \langle \mathbb{E} |\varphi(H^\top z)|1\{\|H^\top z\|_2 \ge B\} \rangle_1, \\ &\le \langle (\mathbb{E}_z[\varphi(H^\top z)^2])^{1/2} \mathbb{P}_z\{\|H^\top z\|_2 \ge B\}^{1/2} \rangle_1, \\ &\le \langle (\mathbb{E}_z[\varphi(H^\top z)^2])^{1/2} \cdot \langle \mathbb{P}_z\{\|H^\top z\|_2 \ge B\} \rangle_1^{1/2} \rangle_1. \end{aligned} \quad (D.21) $$

The first term in eq. (D.21) is bounded by the square integrability assumption, cf. eq. (D.10). To bound the second term, we use Markov's inequality:

$$ \langle \mathbb{P}_z\{\|H^\top z\|_2 \ge B\} \rangle_1 \le \frac{1}{B^2} \langle \mathbb{E}_z \|H^\top z\|_2^2 \rangle_1. $$

From eq. (D.13) and the matching of the first two moments of $\rho$ with GOE(d), we have:

$$ \mathbb{E}_z \|H^\top z\|_2^2 = \frac{4}{d} \sum_{a=1}^{R} \mathrm{Tr}[S_a^2]. $$

Thus, we get:

$$ \langle \mathbb{P}_z \{ \|H^\top z\|_2 \ge B \} \rangle_1 \le \frac{4R}{B^2} \left\langle \frac{\mathrm{Tr} S^2}{d} \right\rangle_1 \le \frac{4RC_0}{B^2}. $$

All in all, we get:

$$ \sup_{d \ge 1} \sup_{\{W_\mu, G_\mu\}_{\mu=2}^n} \sup_{t \in (0, \pi/2)} \langle \mathbb{E} |\varphi(H^\top z)|(1 - u_B(\|H^\top z\|)) \rangle_1 \le \frac{C(R, \varphi)}{B}. \quad (D.22) $$

Combining eqs. (D.20) and eq. (D.22) into eq. (D.19), and taking $B \to \infty$ after $d \to \infty$, we conclude the proof of Lemma D.5. □