论文标题
随机矩阵的最佳和算法规范正规化
Optimal and algorithmic norm regularization of random matrices
论文作者
论文摘要
令$ a $为$ n \ times n $随机矩阵，其条目为i.i.d.平均$ 0 $和差异$ 1 $。我们提出了确定性的多项式时间算法，该算法至少$ 1-2 \ exp（-Ω（εn））$在选择$ a $时找到了一个$εn\ timesεn$ sub-matrix，因此将其零零以$ \ \\ wideTilde {a} $ with \ with \ \ wideteDeD \ wideTiLde \ | = o \ left（\ sqrt {n/ε} \ right）。\ \]我们的结果是最佳的最佳因素，并改善了Rebrova和vershynin的先前结果，以及Rebrova。我们还证明了$ a $ a对称的$ n \ times n $随机矩阵的类似结果，其上层条目为i.i.d.平均$ 0 $和差异$ 1 $。
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(-Ω(εn))$ in the choice of $A$, finds an $εn \times εn$ sub-matrix such that zeroing it out results in $\widetilde{A}$ with \[\|\widetilde{A}\| = O\left(\sqrt{n/ε}\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$.
