Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
From MaRDI portal
Publication:3435007
DOI10.1137/S0895479803436202zbMATH Open1179.65033OpenAlexW2170078634MaRDI QIDQ3435007FDOQ3435007
Authors: Arvind Sankar, Daniel A. Spielman, Shang-Hua Teng 
Publication date: 3 May 2007
Published in: SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0895479803436202
Recommendations
Direct numerical methods for linear systems and matrix inversion (65F05) Numerical computation of matrix norms, conditioning, scaling (65F35) Conditioning of matrices (15A12)
Cited In (73)
- A probabilistic Weyl-law for perturbed Berezin-Toeplitz operators
- Complex random matrices have no real eigenvalues
- Smoothed analysis of condition numbers and complexity implications for linear programming
- Quantitative results for banded Toeplitz matrices subject to random and deterministic perturbations
- Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
- From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices
- Quantitative invertibility of random matrices: a combinatorial perspective
- Estimating the norms of random circulant and Toeplitz matrices and their inverses
- Smoothed Analysis on Connected Graphs
- Robust smoothed analysis of a condition number for linear programming
- Low-rank approximation of a matrix: novel insights, new progress, and extensions
- Randomized numerical linear algebra: Foundations and algorithms
- Sublinear Cost Low Rank Approximation via Subspace Sampling
- Randomized subspace iteration: analysis of canonical angles and unitarily invariant norms
- Universality: random matrices, random geometry and SPDEs. Abstracts from the workshop held May 29 -- June 4, 2022
- The smallest singular value of random rectangular matrices with no moment assumptions on entries
- Convergence of the spectral measure of non-normal matrices
- On a problem posed by Steve Smale
- Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean
- On the smoothed analysis of the smallest singular value with discrete noise
- Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
- The single ring theorem
- Numerically safe Gaussian elimination with no pivoting
- Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
- On the Condition Number of the Shifted Real Ginibre Ensemble
- Random matrices: overcrowding estimates for the spectrum
- Lower bounds for the smallest singular value of structured random matrices
- Computational complexity of kernel-based density-ratio estimation: a condition number analysis
- Smooth analysis of the condition number and the least singular value
- The smallest singular value of a shifted $d$-regular random square matrix
- New studies of randomized augmentation and additive preprocessing
- An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation
- Solving linear systems of equations with randomization, augmentation and aggregation
- On sparse random combinatorial matrices
- Mixed and componentwise condition numbers for matrix decompositions
- Almost sure Weyl law for quantized tori
- A numerical comparison of different qualitative algorithms for solving 2D inverse elastic scattering problems
- Smoothed analysis of \(\kappa(A)\)
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Optimal lower bound on the least singular value of the shifted Ginibre ensemble
- Additive preconditioning for matrix computations
- Randomized preprocessing of homogeneous linear systems of equations
- The asymptotic distribution of the condition number for random circulant matrices
- Smoothed analysis of the squared Euclidean maximum-cut problem
- Universality for Eigenvalue Algorithms on Sample Covariance Matrices
- Smoothed analysis of symmetric random matrices with continuous distributions
- Smoothed analysis for the conjugate gradient algorithm
- Random matrix products: universality and least singular values
- Matrix regularizing effects of Gaussian perturbations
- Circular law for random matrices with unconditional log-concave distribution
- The least singular value of the general deformed Ginibre ensemble
- Probabilistic analysis of complex Gaussian elimination without pivoting
- Halting time is predictable for large models: a universality property and average-case analysis
- Randomized preprocessing versus pivoting
- Smoothed analysis of local search algorithms
- The smallest singular value of a shifted random matrix
- User-friendly tail bounds for sums of random matrices
- Smoothed analysis of some condition numbers
- A friendly smoothed analysis of the simplex method
- Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time
- Wegner estimate and upper bound on the eigenvalue condition number of non-Hermitian random matrices
- Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices
- Growth factors of orthogonal matrices and local behavior of Gaussian elimination with partial and complete pivoting
- Local spectrum of truncations of Kronecker products of Haar distributed unitary matrices
- Title not available (Why is that?)
- Mesoscopic central limit theorem for non-Hermitian random matrices
- Smoothed analysis of componentwise condition numbers for sparse matrices
- Random matrices generating large growth in LU factorization with pivoting
- Overlaps, eigenvalue gaps, and pseudospectrum under real Ginibre and absolutely continuous perturbations
- Some new results on the maximum growth factor in Gaussian elimination
- Quantitative invertibility of non-Hermitian random matrices
- Average-case analysis of the Gaussian elimination with partial pivoting
- Speeding up random walk mixing by starting from a uniform vertex
Uses Software
This page was built for publication: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3435007)
