1. Optimal and algorithmic norm regularization of random matrices.
- Author
-
Jain, Vishesh, Sah, Ashwin, and Sawhney, Mehtaab
- Subjects
RANDOM matrices ,POLYNOMIAL time algorithms ,RANDOM graphs ,DETERMINISTIC algorithms - Abstract
Let A be an n\times n random matrix whose entries are i.i.d. with mean 0 and variance 1. We present a deterministic polynomial time algorithm which, with probability at least 1-2\exp (-\Omega (\epsilon n)) in the choice of A, finds an \epsilon n \times \epsilon n sub-matrix such that zeroing it out results in \widetilde {A} with \[ \lVert \widetilde {A}\rVert = O(\sqrt {n/\epsilon }). \] Our result is optimal up to a constant factor and improves previous results of Rebrova and Vershynin, and Rebrova. We also prove an analogous result for A a symmetric n\times n random matrix whose upper-diagonal entries are i.i.d. with mean 0 and variance 1. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF