Universality and sharp thresholds for ellipsoid fitting
We establish a sharp phase transition for fitting random vectors by an ellipsoid. The random vectors have independent subgaussian coordinates with mean zero, variance one, and a common fourth moment, and the number of vectors is proportional to the square of the dimension. We identify an explicit satisfiability threshold such that, with high probability, a positive definite ellipsoid passes through every data point below the threshold, whereas no positive semidefinite fit exists above it. We also determine the optimal squared fitting error throughout the unsatisfiable regime. In particular, the threshold depends on the coordinate distributions only through their common fourth moment, revealing a fourth moment universality phenomenon. For standard Gaussian data the threshold is $1/4$, resolving the ellipsoid fitting conjecture.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Robust Ellipsoid-specific Fitting via Expectation Maximization
Ellipsoid fitting is of general interest in machine vision, such as object detection and shape approximation. Most existing approaches rely on the least-squares fitting of quadrics, minimizing the algebraic or geometric …
Density Estimationobject-detectionObject DetectionNear-optimal fitting of ellipsoids to random points
Given independent standard Gaussian points $v_1, \ldots, v_n$ in dimension $d$, for what values of $(n, d)$ does there exist with high probability an origin-symmetric ellipsoid that simultaneously passes through all of t…
Fitting an ellipsoid to a quadratic number of random points
We consider the problem $(\mathrm{P})$ of fitting $n$ standard Gaussian random vectors in $\mathbb{R}^d$ to the boundary of a centered ellipsoid, as $n, d \to \infty$. This problem is conjectured to have a sharp feasibil…
Ellipsoid fitting with the Cayley transform
We introduce Cayley transform ellipsoid fitting (CTEF), an algorithm that uses the Cayley transform to fit ellipsoids to noisy data in any dimension. Unlike many ellipsoid fitting methods, CTEF is ellipsoid specific, mea…
ClusteringData VisualizationDimensionality ReductionRhythmLeast square ellipsoid fitting using iterative orthogonal transformations
We describe a generalised method for ellipsoid fitting against a minimum set of data points. The proposed method is numerically stable and applies to a wide range of ellipsoidal shapes, including highly elongated and arb…
Retrieval