The sharp SAT/UNSAT phase transition in random ellipsoid fitting

• URL: http://arxiv.org/abs/2608.10184v1
• Date: Mon, 10 Aug 2026 19:55:11 GMT
• Title: The sharp SAT/UNSAT phase transition in random ellipsoid fitting
• Abstract summary: An emphellipsoid fit is a matrix $S succeq 0$ such that $x_itop S x_i =d$ for every $i$.<n>We prove Saunderson, Parrilo and Willsky's conjecture that, as $n,d to infty$, this semidefinite feasibility problem undergoes a sharp transition at $n sim d2/4$.
• Score: 5.7652356955571085
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Let $x_1,\ldots,x_n$ be independent standard Gaussian vectors in $\mathbb{R}^d$. An \emph{ellipsoid fit} is a matrix $S \succeq 0$ such that $x_i^\top S x_i =d$ for every $i$, so that all the points lie on the boundary of the centered ellipsoid $\{ x : x^\top S x = d\}$. Saunderson, Parrilo and Willsky conjectured that, as $n,d \to \infty$, this semidefinite feasibility problem undergoes a sharp transition at $n \sim d^2/4$. We prove this conjecture. If $\lim \sup n/d^2 = α^* <1/4$, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose $S$ with all eigenvalues in a fixed interval $[λ_- , λ_+] \subset (0,\infty)$ depending only on $α^*$. Conversely, if $\lim \inf n/d^2 > 1/4$, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension $d(d+1)/4$ of the positive semidefinite cone.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Permanents of matrix ensembles: computation, distribution, and geometry [0.0]
  We use the GPU to greaatly accelerate the computation of permanents over $mathbbC,$ $mathbbR,$ $mathbbF_p$ and $mathbbQ.$<n>We study the permanent along geodesics on the unitary group.<n>For the geodesic from the identity to the $n$-cycle permutation matrix, we find a universal scaling function $f(t)=frac1nln|perm((t))|$ that is independent of$n$ in
  arXiv  Detail & Related papers  (2026-02-08T22:31:42Z)
• Beyond Worst-Case Dimensionality Reduction for Sparse Vectors [47.927989749887864]
  We study beyond worst-case dimensionality reduction for $s$-sparse vectors.<n>For any collection $X$ of $s$-sparse vectors in $mathbbRO(s2)$, there exists a linear map to $mathbbRO(s2)$ which emphexactly preserves the norm of $99%$ of the vectors in $X$ in any $ell_p$ norm.<n>We show that both the non-linearity of $f$ and the non-negativity of $
  arXiv  Detail & Related papers  (2025-02-27T08:17:47Z)
• Fitting an ellipsoid to a quadratic number of random points [10.208117253395342]
  We consider the problem $(mathrmP)$ of fitting $n$ standard Gaussian random vectors in $mathbbRd$ to the boundary of a centered ellipsoid, as $n, d to infty$. This problem is conjectured to have a sharp feasibility transition: for any $varepsilon > 0$, if $n leq (1 - varepsilon) d2 / 4$ then $(mathrmP)$ has a solution with high probability.
  arXiv  Detail & Related papers  (2023-07-03T17:46:23Z)
• Near-optimal fitting of ellipsoids to random points [68.12685213894112]
  A basic problem of fitting an ellipsoid to random points has connections to low-rank matrix decompositions, independent component analysis, and principal component analysis. We resolve this conjecture up to logarithmic factors by constructing a fitting ellipsoid for some $n = Omega(, d2/mathrmpolylog(d),)$. Our proof demonstrates feasibility of the least squares construction of Saunderson et al. using a convenient decomposition of a certain non-standard random matrix.
  arXiv  Detail & Related papers  (2022-08-19T18:00:34Z)
• Spectral properties of sample covariance matrices arising from random matrices with independent non identically distributed columns [50.053491972003656]
  It was previously shown that the functionals $texttr(AR(z))$, for $R(z) = (frac1nXXT- zI_p)-1$ and $Ain mathcal M_p$ deterministic, have a standard deviation of order $O(|A|_* / sqrt n)$. Here, we show that $|mathbb E[R(z)] - tilde R(z)|_F
  arXiv  Detail & Related papers  (2021-09-06T14:21:43Z)
• Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs [25.597646488273558]
  We study the statistical properties of Laplacian smoothing, a graph-based approach to nonparametric regression. We prove that Laplacian smoothing is manifold-adaptive.
  arXiv  Detail & Related papers  (2021-06-03T01:20:41Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)
• Extremal elements of a sublattice of the majorization lattice and approximate majorization [0.0]
  We show that the extremal probability vectors, in general, do not exist for the closed balls $mathcalBp_epsilon(x)$ with $1pinfty$. We also give an explicit characterization of those extremal elements in terms of the radius and the center of the ball.
  arXiv  Detail & Related papers  (2020-01-23T19:09:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.