论文标题
最佳平滑分析和随机矩阵最小奇异值的定量普遍性
Optimal Smoothed Analysis and Quantitative Universality for the Smallest Singular Value of Random Matrices
论文作者
论文摘要
最小的奇异值和条件数在数值线性代数和算法分析中起着重要作用。在随机性的数值分析中，许多以前的作品做出了高斯假设，这些假设不足以反映输入的任意性。为了克服这一缺点，我们证明了最小的奇异值和随机矩阵条件数的第一个定量普遍性。 此外，由于对随机扰动的平滑分析的研究的动机，使确定性矩阵具有良好的条件，我们考虑了一个随机矩阵的类似物。对于由独立高斯噪声扰动的随机矩阵，我们表明该矩阵很快变成了高斯。特别是，我们从尖锐的高斯近似方面得出了随机矩阵的最佳平滑分析。
The smallest singular value and condition number play important roles in numerical linear algebra and the analysis of algorithms. In numerical analysis with randomness, many previous works make Gaussian assumptions, which are not general enough to reflect the arbitrariness of the input. To overcome this drawback, we prove the first quantitative universality for the smallest singular value and condition number of random matrices. Moreover, motivated by the study of smoothed analysis that random perturbation makes deterministic matrices well-conditioned, we consider an analog for random matrices. For a random matrix perturbed by independent Gaussian noise, we show that this matrix quickly becomes approximately Gaussian. In particular, we derive an optimal smoothed analysis for random matrices in terms of a sharp Gaussian approximation.
