2026-07-22T16:11:57Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18130 2024-03-06T11:01:06Z ddc:004 open_access

Ellipsoid Fitting up to a Constant Hsieh, Jun-Ting Kothari, Pravesh K. Potechin, Aaron Xu, Jeff Semidefinite programming random matrices average-case complexity In [Saunderson, 2011; Saunderson et al., 2013], Saunderson, Parrilo, and Willsky asked the following elegant geometric question: what is the largest m = m(d) such that there is an ellipsoid in ℝ^d that passes through v_1, v_2, …, v_m with high probability when the v_is are chosen independently from the standard Gaussian distribution N(0,I_d)? The existence of such an ellipsoid is equivalent to the existence of a positive semidefinite matrix X such that v_i^⊤ X v_i = 1 for every 1 ⩽ i ⩽ m - a natural example of a random semidefinite program. SPW conjectured that m = (1-o(1)) d²/4 with high probability. Very recently, Potechin, Turner, Venkat and Wein [Potechin et al., 2022] and Kane and Diakonikolas [Kane and Diakonikolas, 2022] proved that m ≳ d²/log^O(1) d via a certain natural, explicit construction. In this work, we give a substantially tighter analysis of their construction to prove that m ≳ d²/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 [Barak et al., 2019; Bafna et al., 2022]. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jun-Ting Hsieh and Pravesh K. Kothari and Aaron Potechin and Jeff Xu 2023 Is Part Of LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2023.78 urn:nbn:de:0030-drops-181304 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.78 eng https://creativecommons.org/licenses/by/4.0/legalcode