Mathematics > Probability
Title:The Spectral Distribution of Matrix Least Squares Solutions, and the Ellipsoid Fitting Problem
Abstract:We study the spectral distribution of the least squares solution to a random linear system whose unknown is a symmetric matrix. In the normalized and isotropic setting, we derive a closed-form description of the support of the spectral distribution. As an application, we consider the ellipsoid fitting problem: given $n$ standard Gaussian vectors in $\mathbb{R}^d$, does there exist a centered ellipsoid passing through all of them? It was recently shown that this problem has a sharp phase transition at $n \approx d^2/4$. On the satisfiability side, unlike earlier results, these sharp results do not rely on least squares candidates. We show that the least squares candidates considered in earlier works have a threshold of positive semi-definiteness at $n \approx d^2/10$, which was previously observed numerically and predicted non-rigorously using statistical physics methods. Moreover, we show that the corresponding least squares dual certificates have a threshold of positive definiteness at $n \approx 2d^2/5$. Our approach combines several matrix concentration tools. A key technical ingredient, which may be of independent interest, is showing that a certain kernel matrix is well-conditioned with high probability until $n \approx d^2/2$.
| Comments: | 40 pages |
|---|---|
| Subjects: | Probability (math.PR) ; Data Structures and Algorithms (cs.DS); Statistics Theory (math.ST); Machine Learning (stat.ML) |
| Cite as: | arXiv:2611.23431 [math.PR] |
| (or arXiv:2611.23431v1 [math.PR] for this version) | |
| https://doi.org/10.48550/arXiv.2611.23431 arXiv-issued DOI via DataCite (pending registration) |
Submission history
Access Paper:
- HTML (experimental)
Current browse context:
References & Citations
- Google Scholar
- Semantic Scholar
BibTeX formatted citation
Bookmark
Bibliographic and Citation Tools
Code, Data and Media Associated with this Article
Demos
Recommenders and Search Tools
arXivLabs: experimental projects with community collaborators
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.