Level-set entropy and sparse randomized embeddings

Abstract

Let $Π$ 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 $Π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 $Π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 $Π$ be a $k\times 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 $|ξ|\le1$ almost surely. Then with high probability \[ \|ΠU_V\|\le C\sqrt{kp}. \] Matching results hold for other random models with negatively associated entries.

Disclosure

“s unequal row supports and different coordinate levels dyadically, but uses the same cancellation mechanism. Funding acknowledgement. K.T. was partially supported by NSF grant DMS 2452120. Acknowledgement of AI Assistance. The author used ChatGPT for language editing, litera- ture search, and assistance in developing and checking some proof arguments during the preparation of this manuscript. All mathematical statements, proofs, and final wording were independently re- viewed and v”

PDF page 10

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:05:49.584026Z

Structural counts