Rank of Sparse Bernoulli Matrices

2020/09/29 by Han Huang, Huang, Han · 2 citations
Physics and Astronomy · Mathematics · Computer Science · #Advanced Mathematical Theories and Applications #Random Matrices and Applications #Matrix Theory and Algorithms

paper · pdf · doi:10.48550/arxiv.2009.13726

Abstract

Let A_n be an n × n random matrix with i.i.d Bernoulli(p) entries. For a fixed positive integer β, suppose p satisfies ( log(n) )/( n ) ≤ p ≤ c_β where c_β∈ ( 0, 1/2 ) is a β-dependentvalue. For t ≥ 0, ℙ \ s _{n - β+ 1}(A) ≤ t n^-2β+ \mathfrakn(1) (pn)^-7 \ = t + ( 1 + o_\mathfrakn(1) ) ℙ \ \mboxeither β rows or β columns of A_n equal 0 \.

Cited by

• Singularity of biased discrete random matrix
• Accelerating Randomized Algorithms for Low-Rank Matrix Approximation

Related

• Rank deficiency of random matrices
• Singularity of sparse Bernoulli matrices
• Rank deficiency of Bernoulli random matrices for growing corank
• The rank of sparse random matrices
• Sharp invertibility of random Bernoulli matrices