The smallest singular value of heavy-tailed not necessarily i.i.d. random matrices via random rounding (Q2073032)

The author of this very well-written paper uses and generalizes results of \textit{M. Rudelson} and \textit{R. Vershynin} [Adv. Math. 218, No. 2, 600--633 (2008; Zbl 1139.15015); Commun. Pure Appl. Math. 62, No. 12, 1707--1739 (2009; Zbl 1183.15031)] on estimates for the singular values \(\sigma_1(A),\ldots,\sigma_n(A)\) of a rectangular random matrix \(A\). A random variable \(X\) is said to have \emph{bounded concentration function} if there exist \(a,b>0\) with \(b<1\) such that \[ \sup\big\{P(|X-z|<a:\ z\in\mathbb R\big\}<b. \] As an example of the estimates, the author obtains an \(n\times n\) random matrix \(A\) with independent entries that have bounded concentration function such that there exists \(k>0\) such that \[ \mathbb E\|A\|_{\mathrm{HS}}^2\leq kn^2. \] Then \[ P\Big(\sigma_n(a)<\tfrac\varepsilon{\sqrt n}\Big)\leq C\varepsilon+e^{-cn},\qquad\qquad \varepsilon>\tfrac c{\sqrt n}, \] where \(C,c\) depend polynomially on \(k\) and \(a,b\). When \(A\) has identically distributed rows, the inequality works for all \(\varepsilon>0\). The author proves the following. Let \(N(S,\varepsilon B_2^N)\) be the covering number of \(S\) by \(\varepsilon B_2^n\). Given \(n\in\mathbb N\) and \(S\subset\mathbb R^n\), \(\gamma\in(1,\sqrt n)\), \(\varepsilon\in(0,\frac1{20\gamma})\), \(\kappa>1\), \(p>0\), and \(s>0\), there exists a deterministic set \(\mathcal N\subset S+4\varepsilon\gamma B_2^n\) with \[ \#\mathcal N\leq\begin{cases} N(S,\varepsilon B_2^N)\,(C_1\gamma)^{\frac{C_2n}{\gamma^{0.08}}},&\ \log\kappa\leq\frac{\log2}{\gamma^{0.09}}\\ N(S,\varepsilon B_2^N)\,(C_0\kappa)^{n}(\log\kappa)^{n-1},&\ \log\kappa\geq\frac{\log2}{\gamma^{0.09}}\ \end{cases} \] such that for every \(N\in\mathbb N\) and every random \(N\times n\) matrix \(A\) with independent columns with probability at least \[ 1-\kappa^{-2pn}\Big(1+\frac1{s^p}\Big)^n, \] there exist constants \(C_0\), \(C_1\), \(C_2\), \(C_3\) such that for every \(x\in S\) there exists \(y\in\mathcal N\) such that \[ |A(x-y)|\leq C_3\frac{\varepsilon\gamma\sqrt s}{\sqrt n}\sqrt{\sum_{j=1}^n \big(\mathbb E|Ae_j|^{2p}\big)^{1/p}}. \] The author provides several situations where different choices of the parameters are crucial to treat different regimes. An interesting byproduct is the following. Given \(N,n\in\mathbb N\), \(A\) an \(N\times n\) random matrix with mean zero independent entries and identically distributed rows and bounded concentration function, such that there exists \(k>0\) such that for every \(\sigma\subset\{1,\ldots,n\}\) with \(\#\sigma=\min(N-n+1,n)\) one has \[ \mathbb E\frac1{\#\sigma}\sum_{j\in\sigma}|Ae_j|^2\leq kN, \] then for every \(\varepsilon>0\) \[ P\Big((\sigma_n(A)<\varepsilon\big(\sqrt{N+1}-\sqrt n\Big) \leq(-C\varepsilon\log\varepsilon)^{N-n+1}+e^{-cN}, \] where \(C,c\) are absolute constants that depend polynomially on \(k,a,b\).