More Like this

1. Ellipsoid fitting up to a constant

   https://doi.org/10.4230/LIPIcs.ICALP.2023.78  

   Hsieh, Jun-Ting; Kothari, Pravesh K.; Potechin, Aaron; Xu, Jeff (July 2023, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023))

   Etessami, Kousha; Feige, Uriel; Puppis, Gabriele (Ed.)

   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²/polylog(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. 

   more » « less
2. Conditioning of random Fourier feature matrices: double descent and generalization error

   https://doi.org/10.1093/imaiai/iaad054  

   Chen, Zhijun; Schaeffer, Hayden (April 2024, Information and Inference: A Journal of the IMA)

   Abstract We provide high-probability bounds on the condition number of random feature matrices. In particular, we show that if the complexity ratio $N/m$, where $$N$$ is the number of neurons and $$m$$ is the number of data samples, scales like $$\log ^{-1}(N)$$ or $$\log (m)$$, then the random feature matrix is well-conditioned. This result holds without the need of regularization and relies on establishing various concentration bounds between dependent components of the random feature matrix. Additionally, we derive bounds on the restricted isometry constant of the random feature matrix. We also derive an upper bound for the risk associated with regression problems using a random feature matrix. This upper bound exhibits the double descent phenomenon and indicates that this is an effect of the double descent behaviour of the condition number. The risk bounds include the underparameterized setting using the least squares problem and the overparameterized setting where using either the minimum norm interpolation problem or a sparse regression problem. For the noiseless least squares or sparse regression cases, we show that the risk decreases as $$m$$ and $$N$$ increase. The risk bound matches the optimal scaling in the literature and the constants in our results are explicit and independent of the dimension of the data. 

   more » « less
3. Ellipsoid Fitting Up to A Constant

   Junting Hsieh, Pravesh K (July 2023, International Colloquium on Automata, Languages and Programming, ICALP)

   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. 

   more » « less
4. Global eigenvalue fluctuations of random biregular bipartite graphs

   https://doi.org/10.1142/S2010326323500041  

   Dumitriu, Ioana; Zhu, Yizhe (July 2023, Random Matrices: Theory and Applications)

   We compute the eigenvalue fluctuations of uniformly distributed random biregular bipartite graphs with fixed and growing degrees for a large class of analytic functions. As a key step in the proof, we obtain a total variation distance bound for the Poisson approximation of the number of cycles and cyclically non-backtracking walks in random biregular bipartite graphs, which might be of independent interest. We also prove a semicircle law for random [Formula: see text]-biregular bipartite graphs when [Formula: see text]. As an application, we translate the results to adjacency matrices of uniformly distributed random regular hypergraphs. 

   more » « less
5. Spectral Radii of Products of Random Rectangular Matrices

   https://doi.org/10.1007/s10959-019-00942-9  

   Qi, Yongcheng; Xie, Mengzi (September 2019, Journal of Theoretical Probability)

   We consider m independent random rectangular matrices whose entries are independent and identically distributed standard complex Gaussian random variables. Assume the product of the m rectangular matrices is an n-by-n square matrix. The maximum absolute value of the n eigenvalues of the product matrix is called spectral radius. In this paper, we study the limiting spectral radii of the product when m changes with n and can even diverge. We give a complete description for the limiting distribution of the spectral radius. Our results reduce to those in Jiang and Qi (J Theor Probab 30(1):326–364, 2017) when the rectangular matrices are square. 

   more » « less