Optimal and algorithmic norm regularization of random matrices

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