Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices

Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng

Let $\orig{A}$ be any matrix and let $A$ be a slight random perturbation of $\orig{A}$. We prove that it is unlikely that $A$ has large condition number. Using this result, we prov…