Ellipsoid Fitting up to a Constant

Jun Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, Jeff Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


In [11, 13], Saunderson, Parrilo, and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in Rd that passes through v1, v2, . . ., vm with high probability when the vis are chosen independently from the standard Gaussian distribution N(0, Id)? The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix X such that viTXvi = 1 for every 1 ≤ i ≤ m – a natural example of a random semidefinite program. SPW conjectured that m = (1 − o(1))d2/4 with high probability. Very recently, Potechin, Turner, Venkat and Wein [10] and Kane and Diakonikolas [8] proved that m ≳ d2/logO(1)(d) via a certain natural, explicit construction. In this work, we give a substantially tighter analysis of their construction to prove that m ≳ d2/C for an absolute constant C > 0. This resolves one direction of the SPW conjecture up to a constant. Our analysis proceeds via the method of Graphical Matrix Decomposition that has recently been used to analyze correlated random matrices arising in various areas [3, 2]. Our key new technical tool is a refined method to prove singular value upper bounds on certain correlated random matrices that are tight up to absolute dimension-independent constants. In contrast, all previous methods that analyze such matrices lose logarithmic factors in the dimension.

Original languageEnglish (US)
Title of host publication50th International Colloquium on Automata, Languages, and Programming, ICALP 2023
EditorsKousha Etessami, Uriel Feige, Gabriele Puppis
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959772785
StatePublished - Jul 2023
Externally publishedYes
Event50th International Colloquium on Automata, Languages, and Programming, ICALP 2023 - Paderborn, Germany
Duration: Jul 10 2023Jul 14 2023

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969


Conference50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

All Science Journal Classification (ASJC) codes

  • Software


  • average-case complexity
  • random matrices
  • Semidefinite programming


Dive into the research topics of 'Ellipsoid Fitting up to a Constant'. Together they form a unique fingerprint.

Cite this