Invertibility via distance for noncentered random matrices with continuous distributions. Issue 2 (1st May 2020)

• Record Type: Journal Article
• Authors: Tikhomirov, Konstantin
• Is Part Of: Random structures & algorithms. Volume 57:Issue 2(2020)
• Page Start: 526
• Page End: 562
• Publication Date: 2020-05-01
• Subjects: condition number -- invertibility -- smoothed analysis; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20920
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Let A be an n × n random matrix with independent rows R 1 ( A ), …, R n ( A ), and assume that for any i ≤ n and any three‐dimensional linear subspace F ⊂ R n the orthogonal projection of R i ( A ) onto F has distribution density ρ ( x ) : F → R + satisfying ρ ( x ) ≤ C 1 / max ( 1, ‖ x ‖ 2 2000 ) ( x ∈ F ) for some constant C 1 >0. We show that for any fixed n × n real matrix M we have 1 P { s min ( A + M ) ≤ t n − 1 / 2 } ≤ C ′ t, t > 0, where C ′ >0 is a universal constant. In particular, the above result holds if the rows of A are independent centered log‐concave random vectors with identity covariance matrices. Our method is free from any use of covering arguments, and is principally different from a standard approach involving a decomposition of the unit sphere and coverings, as well as an approach of Sankar‐Spielman‐Teng for noncentered Gaussian matrices.