Let $\Pi$ be a $k\times n$ sparse random matrix. For a fixed $r$-dimensional subspace $V\subset{\mathbb R}^n$, let $U_V:{\mathbb R}^r\to{\mathbb R}^n$ denote an isometry from ${\mathbb R}^r$ onto $V$. The product $\Pi U_V$ is a central model in randomized dimension reduction and has been studied primarily through trace and Gaussian comparison inequalities. In this work, we develop an approach to the spectral norm of the matrix product $\Pi U_V$, based on entropy estimates for level sets of vectors $x\in V$. Combining the method with existing estimates, we show the following. Assume that \[ k\ge C\,r(\log\log r)^2,\qquad p\ge (\log k)/k. \] Let $\Pi$ be a $k\times n$ matrix with i.i.d. entries equidistributed with the product $b\,\xi$, where $b$ is a Bernoulli($p$) random variable and $\xi$ is mean-zero, independent of $b$, and satisfies $|\xi|\le1$ almost surely. Then with high probability \[ \|\Pi U_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.
A random $n\times k$ matrix $S$ is an \emph{$(r,\alpha)$-oblivious subspace injection} (OSI) if $\mathbb{E}\|S^\top x\|_2^2=\|x\|_2^2$ for every $x\in\mathbb{R}^n$, and for every fixed $r$-dimensional subspace $V\subset\mathbb{R}^n$, with probability close to one, one has $\alpha\|x\|_2^2\le\|S^\top x\|_2^2$ for all $x\in V$. In this work, we show that in the regime $r=\Omega(k)$ and $\alpha=\Omega(1)$, and under a mild additional structural assumption, no constant-row-sparsity matrix $S$ is OSI, thereby answering, in a strong form, a question raised by Cama\~no, Epperly, Meyer, and Tropp. We show that the failure of the OSI property for sparse random matrices stems from a general deterministic phenomenon, thereby reducing a probabilistic problem to a non-probabilistic one. This phenomenon is related to the restricted invertibility principle introduced in the seminal work of Bourgain--Tzafriri. Let $(n_k)_{k\in\mathbb{N}}$ be a sequence of integers satisfying $\frac{n_k}{k}\to\infty$. For each $k$, let $S^{(k)}$ be a $n_k\times k$ non-random matrix with $O(1)$ nonzero entries per row, whose nonzero entries have average magnitude $O(1)$, and such that the total number of pairs of rows with supports overlapping at two or more indices is $o({n_k}^2/k)$. We prove that for every constant $\varepsilon>0$, as $k\to\infty$, the overwhelming majority of $k\times \lfloor\varepsilon k\rfloor$ submatrices of $(S^{(k)})^\top$ have the smallest singular value $o(1)$. Thus, the well-invertible submatrices whose existence is guaranteed by the Bourgain--Tzafriri theorem are rare. The proof is itself based on probabilistic tools.
Han Huang, M. Rudelson, Konstantin E. Tikhomirov· 0 citations
The main thrust of the result is that it is actually obtained by an efficient \textit{online} algorithm that minimizes prefix discrepancy, and is also essentially optimal, since online prefix discrepancy is known to scale as $\omega(\sqrt{d})$ for $d =o(\log T)$.
Dylan J. Altschuler, Konstantin E. Tikhomirov· 1 citation