English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We consider the problem $(\rm P)$ of exactly fitting an ellipsoid (centeredat $0$) to $n$ standard Gaussian random vectors in $\mathbb{R}^d$, as $n, d \to\infty$ with $n / d^2 \to \alpha > 0$. This problem is conjectured to undergo asharp transition: with high probability, $(\rm P)$ has a solution if $\alpha <1/4$, while $(\rm P)$ has no solutions if $\alpha > 1/4$. So far, only atrivial bound $\alpha > 1/2$ is known to imply the absence of solutions, whilethe sharpest results on the positive side assume $\alpha \leq \eta$ (for $\eta> 0$ a small constant) to prove that $(\rm P)$ is solvable. In this work westudy universality between this problem and a so-called "Gaussian equivalent",for which the same transition can be rigorously analyzed. Our main results aretwofold. On the positive side, we prove that if $\alpha < 1/4$, there exist anellipsoid fitting all the points up to a small error, and that the lengths ofits 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 thelength 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 axislength is bounded away from $0$ as $d \to \infty$). To the best of ourknowledge, our work is the first rigorous result characterizing the expectedphase transition in ellipsoid fitting at $\alpha = 1/4$. In a companionnon-rigorous work, the first author and D. Kunisky give a general analysis ofellipsoid fitting using the replica method of statistical physics, whichinspired the present work.

Exact threshold for approximate ellipsoid fitting of random points