Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
From MaRDI portal
Publication:3435007
DOI10.1137/S0895479803436202zbMath1179.65033OpenAlexW2170078634MaRDI QIDQ3435007
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
Numerical computation of matrix norms, conditioning, scaling (65F35) Direct numerical methods for linear systems and matrix inversion (65F05) Conditioning of matrices (15A12)
Related Items (65)
Numerically safe Gaussian elimination with no pivoting ⋮ Smooth analysis of the condition number and the least singular value ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Lower bounds for the smallest singular value of structured random matrices ⋮ Smoothed analysis of \(\kappa(A)\) ⋮ Some new results on the eigenvalues of complex non-central Wishart matrices with a rank-1 mean ⋮ Smoothed Analysis of Local Search Algorithms ⋮ The smallest singular value of random rectangular matrices with no moment assumptions on entries ⋮ Smoothed Analysis of the Squared Euclidean Maximum-Cut Problem ⋮ Additive preconditioning for matrix computations ⋮ New studies of randomized augmentation and additive preprocessing ⋮ Random matrices: overcrowding estimates for the spectrum ⋮ On sparse random combinatorial matrices ⋮ From the Littlewood-Offord problem to the Circular Law: Universality of the spectral distribution of random matrices ⋮ Optimal lower bound on the least singular value of the shifted Ginibre ensemble ⋮ Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design ⋮ Smoothed Analysis on Connected Graphs ⋮ On the Condition Number of the Shifted Real Ginibre Ensemble ⋮ Quantitative invertibility of random matrices: a combinatorial perspective ⋮ A probabilistic Weyl-law for perturbed Berezin-Toeplitz operators ⋮ The smallest singular value of a shifted random matrix ⋮ Universality for the Conjugate Gradient and MINRES Algorithms on Sample Covariance Matrices ⋮ Universality for Eigenvalue Algorithms on Sample Covariance Matrices ⋮ An Improved Analysis and Unified Perspective on Deterministic and Randomized Low-Rank Matrix Approximation ⋮ Smoothed analysis of condition numbers and complexity implications for linear programming ⋮ Almost sure Weyl law for quantized tori ⋮ Universality: random matrices, random geometry and SPDEs. Abstracts from the workshop held May 29 -- June 4, 2022 ⋮ Quantitative invertibility of non-Hermitian random matrices ⋮ Speeding up random walk mixing by starting from a uniform vertex ⋮ Randomized preprocessing versus pivoting ⋮ Pseudospectral shattering, the sign function, and diagonalization in nearly matrix multiplication time ⋮ On the smoothed analysis of the smallest singular value with discrete noise ⋮ Computational complexity of kernel-based density-ratio estimation: a condition number analysis ⋮ Mesoscopic central limit theorem for non-Hermitian random matrices ⋮ Complex random matrices have no real eigenvalues ⋮ Halting time is predictable for large models: a universality property and average-case analysis ⋮ The single ring theorem ⋮ Randomized Subspace Iteration: Analysis of Canonical Angles and Unitarily Invariant Norms ⋮ Solving linear systems of equations with randomization, augmentation and aggregation ⋮ A Friendly Smoothed Analysis of the Simplex Method ⋮ Matrix regularizing effects of Gaussian perturbations ⋮ On a problem posed by Steve Smale ⋮ Robust smoothed analysis of a condition number for linear programming ⋮ Convergence of the spectral measure of non-normal matrices ⋮ The smallest singular value of a shifted $d$-regular random square matrix ⋮ Improved smoothed analysis of multiobjective optimization ⋮ User-friendly tail bounds for sums of random matrices ⋮ Randomized preprocessing of homogeneous linear systems of equations ⋮ Low-Rank Approximation of a Matrix: Novel Insights, New Progress, and Extensions ⋮ Smoothed analysis of symmetric random matrices with continuous distributions ⋮ Sharp transition of the invertibility of the adjacency matrices of sparse random graphs ⋮ Estimating the norms of random circulant and Toeplitz matrices and their inverses ⋮ Unnamed Item ⋮ Smoothed analysis for the conjugate gradient algorithm ⋮ A numerical comparison of different qualitative algorithms for solving 2D inverse elastic scattering problems ⋮ Mixed and componentwise condition numbers for matrix decompositions ⋮ Probabilistic analysis of complex Gaussian elimination without pivoting ⋮ The least singular value of the general deformed Ginibre ensemble ⋮ Random matrix products: universality and least singular values ⋮ The asymptotic distribution of the condition number for random circulant matrices ⋮ Local spectrum of truncations of Kronecker products of Haar distributed unitary matrices ⋮ Quantitative results for banded Toeplitz matrices subject to random and deterministic perturbations ⋮ Sublinear Cost Low Rank Approximation via Subspace Sampling ⋮ Circular law for random matrices with unconditional log-concave distribution ⋮ Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
Uses Software
This page was built for publication: Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
