For any fixed n×n complex matrix of norm up to 2^{n^0.001}, the least singular value of the matrix plus i.i.d. centered unit-variance complex noise is smaller than η with probability at most C(ξ) α, for α as small as 2^{-n^0.001}.
Approximate Spielman-Teng theorems for the least singular value of random combinatorial matrices
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
An approximate Spielman-Teng theorem for the least singular value $s_n(M_n)$ of a random $n\times n$ square matrix $M_n$ is a statement of the following form: there exist constants $C,c >0$ such that for all $\eta \geq 0$, $\Pr(s_n(M_n) \leq \eta) \lesssim n^{C}\eta + \exp(-n^{c})$. The goal of this paper is to develop a simple and novel framework for proving such results for discrete random matrices. As an application, we prove an approximate Spielman-Teng theorem for $\{0,1\}$-valued matrices, each of whose rows is an independent vector with exactly $n/2$ zero components. This improves on previous work of Nguyen and Vu, and is the first such result in a `truly combinatorial' setting.
citation-role summary
background 1
citation-polarity summary
fields
math.PR 1years
2019 1verdicts
CONDITIONAL 1roles
background 1polarities
unclear 1representative citing papers
citing papers explorer
-
Quantitative invertibility of random matrices: a combinatorial perspective
For any fixed n×n complex matrix of norm up to 2^{n^0.001}, the least singular value of the matrix plus i.i.d. centered unit-variance complex noise is smaller than η with probability at most C(ξ) α, for α as small as 2^{-n^0.001}.