论文标题
在对最小奇异值和离散噪声的平滑分析中
On the smoothed analysis of the smallest singular value with discrete noise
论文作者
论文摘要
令$ a $为$ n \ times n $ real矩阵，让$ m $为$ n \ times n $随机矩阵，其条目为i.i.d sub-gaussian随机变量，其平均$ 0 $和差异$ 1 $。我们为$ s_n（A+M）$的研究做出了两项贡献，这是$ a+m $的最小单数值。 （1）我们证明所有$ε\ geq 0 $， $$ \ mathbb {p} [s_n（a + m）\leqε] = o（ε\ sqrt {n}） + 2e^{ - ω（n）}，$$ 只有$ a $具有$ω（n）$单数值，即$ o（\ sqrt {n}）$。这扩展了Rudelson和Vershynin的众所周知的结果，这需要$ a $的所有单数值为$ o（\ sqrt {n}）$。 （2）我们证明了形式的任何界限 $ \ sup _ {\ | {a} \ | \ | \ leq n^{c_1}}} \ Mathbb {p} [s_n（a+m）\ leq n^{ - c_3}] 必须具有$ C_3 =ω（C_1 \ SQRT {C_2}）$。这补充了Tao和Vu的结果，Tao和Vu证明了$ C_3 = O（C_1C_2 + C_1 + 1）$的界限，并反驳了他们对可能服用$ C_3 = O（C_1 + C_2）$的猜测。
Let $A$ be an $n\times n$ real matrix, and let $M$ be an $n\times n$ random matrix whose entries are i.i.d sub-Gaussian random variables with mean $0$ and variance $1$. We make two contributions to the study of $s_n(A+M)$, the smallest singular value of $A+M$. (1) We show that for all $ε\geq 0$, $$\mathbb{P}[s_n(A + M) \leq ε] = O(ε\sqrt{n}) + 2e^{-Ω(n)},$$ provided only that $A$ has $Ω(n)$ singular values which are $O(\sqrt{n})$. This extends a well-known result of Rudelson and Vershynin, which requires all singular values of $A$ to be $O(\sqrt{n})$. (2) We show that any bound of the form $$\sup_{\|{A}\|\leq n^{C_1}}\mathbb{P}[s_n(A+M)\leq n^{-C_3}] \leq n^{-C_2}$$ must have $C_3 = Ω(C_1 \sqrt{C_2})$. This complements a result of Tao and Vu, who proved such a bound with $C_3 = O(C_1C_2 + C_1 + 1)$, and counters their speculation of possibly taking $C_3 = O(C_1 + C_2)$.
