TY - GEN

T1 - Ellipsoid Fitting up to a Constant

AU - Hsieh, Jun Ting

AU - Kothari, Pravesh K.

AU - Potechin, Aaron

AU - Xu, Jeff

N1 - Publisher Copyright:
© Jun-Ting Hsieh, Pravesh K. Kothari, Aaron Potechin, and Jeff Xu.

PY - 2023/7

Y1 - 2023/7

N2 - 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.

AB - 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.

KW - average-case complexity

KW - random matrices

KW - Semidefinite programming

UR - http://www.scopus.com/inward/record.url?scp=85165574501&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85165574501&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2023.78

DO - 10.4230/LIPIcs.ICALP.2023.78

M3 - Conference contribution

AN - SCOPUS:85165574501

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

A2 - Etessami, Kousha

A2 - Feige, Uriel

A2 - Puppis, Gabriele

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 50th International Colloquium on Automata, Languages, and Programming, ICALP 2023

Y2 - 10 July 2023 through 14 July 2023

ER -