Back to Search
Start Over
Optimal and algorithmic norm regularization of random matrices
- Publication Year :
- 2020
-
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 \[\|\widetilde{A}\| = O\left(\sqrt{n/\epsilon}\right).\] 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$.<br />Comment: 13 pages; comments welcome!
- Subjects :
- Mathematics - Probability
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2012.00175
- Document Type :
- Working Paper