标题： 随机矩阵的最优和算法范数正则化 显示英文标题

标题： Optimal and algorithmic norm regularization of random matrices

摘要： 设$A$为一个$n\times n$随机矩阵，其元素为独立同分布的，均值为$0$，方差为$1$。 我们提出一个确定性多项式时间算法，在选择$A$时至少有$1-2\exp(-\Omega(\epsilon n))$的概率，找到一个$\epsilon n \times \epsilon n$子矩阵，使得将其置零后得到的$\widetilde{A}$具有\[\|\widetilde{A}\| = O\left(\sqrt{n/\epsilon}\right).\]。我们的结果在常数因子范围内是最优的，并改进了 Rebrova 和 Vershynin 以及 Rebrova 的先前结果。 我们还证明了一个类似的结果，针对$A$，即一个对称的$n\times n$随机矩阵，其上对角线元素是独立同分布的。 具有均值$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(-\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$.