Smooth analysis of the condition number and the least singular value

DOI10.1090/S0025-5718-2010-02396-8zbMath1253.65067MaRDI QIDQ3160742

Van H. Vu, Terence C. Tao

Publication date: 8 October 2010

Published in: Mathematics of Computation (Search for Journal in Brave)

Mathematics Subject Classification ID

60B20: Random matrices (probabilistic aspects)

65F35: Numerical computation of matrix norms, conditioning, scaling

15A12: Conditioning of matrices

Related Items

The probabilistic estimates on the largest and smallest $q$-singular values of random matrices, Mixed and componentwise condition numbers for matrix decompositions, Erratum to: Outliers in the spectrum of iid matrices with bounded rank perturbations, On the singularity of adjacency matrices for random regular digraphs, Random matrices: tail bounds for gaps between eigenvalues, Optimal inverse Littlewood-Offord theorems, Spectrum of non-Hermitian heavy tailed random matrices, Random matrices: universality of local spectral statistics of non-Hermitian matrices, On the concentration of random multilinear forms and the universality of random block matrices, Random matrices: law of the determinant, Random doubly stochastic matrices: the circular law, Intrinsic volumes of symmetric cones and applications in convex programming, The smallest singular value of random rectangular matrices with no moment assumptions on entries, Smoothed analysis of symmetric random matrices with continuous distributions, On a condition number of general random polynomial systems, Smoothed Analysis of Local Search Algorithms, Provably Weak Instances of Ring-LWE

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Smoothed analysis of condition numbers and complexity implications for linear programming
• On the distribution of the roots of certain symmetric matrices
• Smoothed analysis of complex conic condition numbers
• Spectral analysis of large dimensional random matrices
• Complexity theory of numerical linear algebra
• The eigenvalues of random symmetric matrices
• Invertibility of random matrices: norm of the inverse
• Inverse Littlewood-Offord theorems and the condition number of random discrete matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Smallest singular value of random matrices and geometry of random polytopes
• General formulas for the smoothed analysis of condition numbers
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• RANDOM MATRICES: THE CIRCULAR LAW
• The probability that a slightly perturbed numerical analysis problem is difficult
• Smoothed analysis of algorithms
• On the efficiency of algorithms of analysis
• The Probability That a Numerical Analysis Problem is Difficult
• Eigenvalues and Condition Numbers of Random Matrices
• The Expected Norm of Random Matrices
• Some estimates of norms of random matrices
• On the Efficiency of Newton's Method in Approximating All Zeros of a System of Complex Polynomials
• Numerical inverting of matrices of high order
• On a lemma of Littlewood and Offord
• Spectral norm of random matrices