2026/07/25 by Konstantin Tikhomirov
#math.PR #cs.DM #cs.DS
Let Π be a k× n sparse random matrix. For a fixed r-dimensional subspace V⊂\mathbb Rn, let UV:\mathbb Rr→\mathbb Rn denote an isometry from \mathbb Rr onto V. The product ΠUV 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 ΠUV, based on entropy estimates for level sets of vectors x∈ V. Combining the method with existing estimates, we show the following. Assume that k≥ C r(loglog r)2, p≥ (log k)/k. Let Π be a k× n matrix with i.i.d. entries equidistributed with the product b ξ, where b is a Bernoulli(p) random variable and ξ is mean-zero, independent of b, and satisfies |ξ|≤1 almost surely. Then with high probability ‖ΠUV‖≤ C√(kp). Matching results hold for other random models with negatively associated entries.