The smallest singular value conjecture for Gaussian matrix perturbations

Let A~\widetilde{A} be an arbitrary square matrix in Rn×n\mathbb{R}^{n\times n}, and let AA be a Gaussian perturbation of A~\widetilde{A} with variance σ2\sigma^2. Smallest singular value conjecture. It should satisfy

Pr{A12x}nxσ.\Pr\left\{\|A^{-1}\|_2\geq x\right\}\leq\frac{\sqrt{n}}{x\sigma}.

This would extend Edelman's sharp Gaussian-matrix bound from perturbations of the zero matrix to arbitrary centers; the paper proves the same estimate with constant 2.352.35 instead of 11.

Sources & referencesView supporting material

Primary source

Arvind Sankar, Daniel A. Spielman and Shang-Hua Teng, “Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices”, arXiv:cs/0310022 (2005).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.