2020/09/03 by Vishesh Jain, Jain, Vishesh, Ashwin Sah +3 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Blind Source Separation Techniques #FOS: Mathematics #Numerical Analysis (math.NA) #Probability (math.PR) #Random Matrices and Applications
paper · pdf · doi:10.48550/arxiv.2009.01699
openalex publication_date 2020/09/03 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
Let A be an n× n real matrix, and let M be an n× n random matrix whose entries are i.i.d sub-Gaussian random variables with mean 0 and variance 1. We make two contributions to the study of sn(A+M), the smallest singular value of A+M. (1) We show that for all ε≥ 0, ℙ[sn(A + M) ≤ ε] = O(ε√(n)) + 2e-Ω(n), provided only that A has Ω(n) singular values which are O(√(n)). This extends a well-known result of Rudelson and Vershynin, which requires all singular values of A to be O(√(n)). (2) We show that any bound of the form sup_‖A‖≤ nC1ℙ[sn(A+M)≤ n-C3] ≤ n-C2 must have C3 = Ω(C1 √(C2)). This complements a result of Tao and Vu, who proved such a bound with C3 = O(C1C2 + C1 + 1), and counters their speculation of possibly taking C3 = O(C1 + C2).