2020/11/30 by Jain, Vishesh, Sah, Ashwin, Sawhney, Mehtaab
#FOS: Mathematics #Probability (math.PR)
paper · doi:10.48550/arxiv.2012.00175
Let A be an n× 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-2exp(-Ω(εn)) in the choice of A, finds an εn × εn sub-matrix such that zeroing it out results in \widetildeA with ‖\widetildeA‖ = O(√(n/ε)). 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× n random matrix whose upper-diagonal entries are i.i.d. with mean 0 and variance 1.