Invertibility of sparse non-Hermitian matrices

DOI10.1016/J.AIM.2017.02.009zbMATH Open1406.60013arXiv1507.03525OpenAlexW2963541360MaRDI QIDQ520368FDOQ520368

Mark Rudelson, Anirban Basak

Publication date: 3 April 2017

Published in: Advances in Mathematics (Search for Journal in Brave)

Abstract: We consider a class of sparse random matrices of the form $A_n=(x{i}_{i,j}delt{a}_{i,j}{)}_{i,j=1}^n$, where $x{i}_{i,j}$ are i.i.d.~centered random variables, and $delt{a}_{i,j}$ are i.i.d.~Bernoulli random variables taking value $1$ with probability $p_n$, and prove a quantitative estimate on the smallest singular value for $p_n=Omega(fraclognn)$, under a suitable assumption on the spectral norm of the matrices. This establishes the invertibility of a large class of sparse matrices. For $p_n=Omega(n^{-alpha})$ with some $alphain(0,1)$, we deduce that the condition number of $A_n$ is of order $n$ with probability tending to one under the optimal moment assumption on $x{i}_{i,j}$. This in particular, extends a conjecture of von Neumann about the condition number to sparse random matrices with heavy-tailed entries. In the case that the random variables $x{i}_{i,j}$ are i.i.d.~sub-Gaussian, we further show that a sparse random matrix is singular with probability at most $exp(-cn{p}_n)$ whenever $p_n$ is above the critical threshold $p_n=Omega(fraclognn)$. The results also extend to the case when $x{i}_{i,j}$ have a non-zero mean. We further find quantitative estimates on the smallest singular value of the adjacency matrix of a directed ErdH{o}s-R'{e}yni graph whenever its edge connectivity probability is above the critical threshold $Omega(fraclognn)$.

Full work available at URL: https://arxiv.org/abs/1507.03525

Recommendations

• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• Smallest singular value of sparse random matrices
• Singularity of sparse Bernoulli matrices
• Universality of the least singular value for sparse random matrices
• Invertibility of symmetric random matrices

zbMATH Keywords

sparse matricesspectral normrandom matricessmall ball probabilitysmallest singular value

Mathematics Subject Classification ID

Random matrices (probabilistic aspects) (60B20) Probabilistic methods in Banach space theory (46B09)

Cites Work

• Spectral analysis of large dimensional random matrices
• Random matrices: universality of ESDs and the circular law
• Title not available (Why is that?)
• Local operator theory, random matrices and Banach spaces.
• The concentration of measure phenomenon
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Some estimates of norms of random matrices
• Eigenvalues and Condition Numbers of Random Matrices
• Invertibility of symmetric random matrices
• Numerical inverting of matrices of high order
• Spectral norm of products of random and deterministic matrices
• The Littlewood-Offord problem and invertibility of random matrices
• Smallest singular value of a random rectangular matrix
• Around the circular law
• Invertibility of random matrices: Unitary and orthogonal perturbations
• The single ring theorem
• Limiting spectral distribution of sum of unitary and orthogonal matrices
• Smallest singular value of random matrices and geometry of random polytopes
• Invertibility of random matrices: norm of the inverse
• The Expected Norm of Random Matrices
• Invertibility of sparse non-Hermitian matrices
• No-gaps delocalization for general random matrices
• The least singular value of a random square matrix is O\((n ^{- 1/2})\)
• RANDOM MATRICES: THE CIRCULAR LAW
• The circular law for random matrices
• Estimation of moments of sums of independent real random variables
• Circular law theorem for random Markov matrices
• On the efficiency of algorithms of analysis
• Title not available (Why is that?)
• Condition numbers of random matrices
• Universality and the circular law for sparse random matrices
• Random doubly stochastic matrices: the circular law
• Smallest singular value of sparse random matrices
• Recent developments in non-asymptotic theory of random matrices

Cited In (28)

• Structure of eigenvectors of random regular digraphs
• The circular law for sparse non-Hermitian matrices
• Singularity of sparse Bernoulli matrices
• Circular law for the sum of random permutation matrices
• Random integral matrices: universality of surjectivity and the cokernel
• Extreme singular values of inhomogeneous sparse random rectangular matrices
• An upper bound on the smallest singular value of a square random matrix
• The rank of random regular digraphs of constant degree
• Controllability of Network Opinion in Erdös--Rényi Graphs Using Sparse Control Inputs
• Sparse random matrices have simple spectrum
• Sharp transition of the invertibility of the adjacency matrices of sparse random graphs
• A note on the singularity probability of random directed \(d\)-regular graphs
• Upper bound for intermediate singular values of random matrices
• A large deviation inequality for the rank of a random matrix
• Invertibility of sparse non-Hermitian matrices
• Surjectivity of near-square random matrices
• Universality of the least singular value for the sum of random matrices
• On the mixing time of Kac's walk and other high-dimensional Gibbs samplers with constraints
• The smallest singular value of a shifted $d$-regular random square matrix
• Polynomial Threshold Functions, Hyperplane Arrangements, and Random Tensors
• Concentration inequalities for random tensors
• Eigenvectors and controllability of non-Hermitian random matrices and directed graphs
• Universality of the least singular value for sparse random matrices
• An inertia formula for Hermitian matrices with sparse inverses
• Invertibility of adjacency matrices for random \(d\)-regular graphs
• Tail bounds for gaps between eigenvalues of sparse random matrices
• The sparse circular law under minimal assumptions
• Quantitative invertibility of non-Hermitian random matrices

This page was built for publication: Invertibility of sparse non-Hermitian matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q520368)