Smooth analysis of the condition number and the least singular value

Terence Tao, Van Vu

Type: Article

Publication Date: 2010-06-04

Citations: 105

DOI: https://doi.org/10.1090/s0025-5718-2010-02396-8

View Publication

Locations

Mathematics of Computation - View
arXiv (Cornell University) - View - PDF
Mathematics of Computation - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Singular Matrix	2014
+	Singular Values	2017	Luís Barreira
+	Singular statistics	2001	E. Bogomolny Ulrich Gerland C. Schmit
+	Singular statistics	2001	E. Bogomolny Ulrich Gerland C. Schmit
+	Singular statistics	2001	E. Bogomolny Ulrich Gerland C. Schmit
+	Singular statistics	2001	E. Bogomolny Ulrich Gerland C. Schmit
+	Singular statistics	2001	E. Bogomolny Ulrich Gerland C. Schmit
+	Singular value inequalities	1991	Roger A. Horn Charles R. Johnson
+ PDF	The least singular value of a random square matrix is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" overflow="scroll"><mml:mi mathvariant="normal">O</mml:mi><mml:mo stretchy="false">(</mml:mo><mml:msup><mml:mi>n</mml:mi><mml:mrow><mml:mo>−</mml:mo><mml:mn>1</mml:mn><mml:mo stretchy="false">/</mml:mo><mml:mn>2</mml:mn></mml:mrow></mml:msup><mml:mo stretchy="false">)</mml:mo></mml:math>	2008	Mark Rudelson Roman Vershynin
+ PDF	On the probability that a random ±1-matrix is singular	1995	Jeff Kahn János Komlós Endre Szemerédi
+	On the singularity probability of random Bernoulli matrices	2007	Terence Tao Van Vu
+	Singular Values and Singular Value Inequalities	2013	Roy Mathias
+	Singular Values and Singular Value Inequalities	2006	Roy Mathias
+	Numerical Range	2006	Chi-Kwong Li
+	Singular values and analytic function theory	2006
+	Complex Analysis	2013	Dennis G. Zill Patrick D. Shanahan
+	Real Analysis	2000	N. L. Carothers
+ PDF	On the lower bound of the number of real roots of a random algebraic equation with infinite variance	1972	G. Samal Μ. N. Mishra
+	Singular value decomposition	2018	Giuseppe C. Calafiore Laurent El Ghaoui
+	Singular Values and the Method of Least Squares	2022

Works That Cite This (101)

Action	Title	Year	Authors
+ PDF Chat	On the singularity of adjacency matrices for random regular digraphs	2015	Nicholas A. Cook
+ PDF	Ill-Posed Algebraic Systems with Noise Data	2015	Vladimir V. Ternovski
+	Edge Universality for non-Hermitian Random Matrices	2019	Giorgio Cipolloni László Erdős Dominik Schröder
+	Lower bounds for the smallest singular value of structured random matrices	2016	Nicholas A. Cook
+	Random matrices: tail bounds for gaps between eigenvalues	2015	Hoi H. Nguyen Terence Tao Van Vu
+	Linear Statistics of Non-Hermitian Matrices Matching the Real or Complex Ginibre Ensemble to Four Moments	2015	Phil Kopel
+	Regularity Conditions for Convergence of Linear Statistics of GUE	2015	Phil Kopel
+ PDF	Circular law for random discrete matrices of given row sum	2013	Hoi H. Nguyen Van H. Vu
+	Universality of the least singular value for sparse random matrices	2019	Ziliang Che Patrick Lopatto
+ PDF Chat	On sparse random combinatorial matrices	2022	Elad Aigner‐Horev Yury Person

Works Cited by This (24)

Action	Title	Year	Authors
+	Smoothed Analysis of Renegar’s Condition Number for Linear Programming	2002	John Dunagan Daniel A. Spielman Shang‐Hua Teng
+ PDF	Spectral Analysis of Large Dimensional Random Matrices	2009	Zhidong Bai Jack W. Silverstein
+ PDF	Eigenvalues and Condition Numbers of Random Matrices	1988	Alan Edelman
+ PDF	Inverse Littlewood–Offord theorems and the condition number of random discrete matrices	2009	Terence Tao Van H. Vu
+	On the spectrum of random matrices	1972	L. А. Pastur
+	Smallest singular value of random matrices and geometry of random polytopes	2004	A.E. Litvak Alain Pajor Mark Rudelson Nicole Tomczak-Jaegermann
+ PDF Chat	The condition number of a randomly perturbed matrix	2007	Van H. Vu Terence Tao
+ PDF	The probability that a slightly perturbed numerical analysis problem is difficult	2008	Peter Bürgisser Felipe Cucker Martin Lötz
+ PDF	On a lemma of Littlewood and Offord	1945	P. Erdős
+	Some estimates of norms of random matrices	2004	Rafał Latała