论文标题
在低级扰动下对条件数的平滑分析
Smoothed analysis of the condition number under low-rank perturbations
论文作者
论文摘要
令$ m $为$ n $ n $ n $ n $ n-k $的任意$ n $。我们研究$ m $ plus a \ emph {low-rank}扰动$ uv^t $的状况数量，其中$ u，v $是$ n $ by $ k $ nocal taby by $ k $ random高斯矩阵。在一些必要的假设下，这表明$ m+uv^t $不太可能具有较大的状况编号。这种扰动的主要优势与研究良好的密集高斯扰动（每个条目都被独立扰动）是$ o（nk）$成本的$ o（nk）$成本，$ u，v $和$ o（nk）$（nk）$（nk）$提高了执行matrix-vector-vector-vector-vector-vector-vector-vector $（m+uv^t）x $。这改善了$ω（n^2）$空间和时间复杂性增加所需的摄动要求，如果$ m $最初稀疏，这尤其负担。我们的结果还扩展到了$ u $和$ v $的排名大于$ k $以及对称和复杂设置的情况。我们还为线性系统求解并执行一些数值实验提供了应用。最后，讨论了在平滑分析框架中研究的其他问题上应用低级别噪声的障碍。
Let $M$ be an arbitrary $n$ by $n$ matrix of rank $n-k$. We study the condition number of $M$ plus a \emph{low-rank} perturbation $UV^T$ where $U, V$ are $n$ by $k$ random Gaussian matrices. Under some necessary assumptions, it is shown that $M+UV^T$ is unlikely to have a large condition number. The main advantages of this kind of perturbation over the well-studied dense Gaussian perturbation, where every entry is independently perturbed, is the $O(nk)$ cost to store $U,V$ and the $O(nk)$ increase in time complexity for performing the matrix-vector multiplication $(M+UV^T)x$. This improves the $Ω(n^2)$ space and time complexity increase required by a dense perturbation, which is especially burdensome if $M$ is originally sparse. Our results also extend to the case where $U$ and $V$ have rank larger than $k$ and to symmetric and complex settings. We also give an application to linear systems solving and perform some numerical experiments. Lastly, barriers in applying low-rank noise to other problems studied in the smoothed analysis framework are discussed.
