Random matrices acting on sets: Independent columns

Yaniv Plan, Roman Vershynin · 2025

Read Random matrices acting on sets: Independent columns by Yaniv Plan, Roman Vershynin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-16827.txt.

Introduction

Yaniv Plan and Roman Vershynin study random matrices with independent columns in this 2025 math paper. Such matrices can act as near-isometries, maps that barely distort lengths, when restricted to a chosen set, and the question is what controls the distortion.

Assuming each column is subgaussian with fixed length, the authors show the worst distortion is proportional to the Gaussian complexity of the set, scaled by the subgaussian norm of the columns. That clean linear scaling is new: matrices with independent rows or entries behave worse. A practical payoff follows: normalizing the columns of sparse random matrices yields stronger embedding guarantees than previously known.

Catalog record

CREATORYaniv Plan, Roman Vershynin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-16827

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Random matrices acting on sets: Independent columns Yaniv Plan, Roman Vershynin Abstract We study random matrices with independent subgaussian columns. Assuming each column has a fixed Euclidean norm, we establish conditions under which such matrices act as near-isometries when restricted to a given subset of their domain. We show that, with high probability, the maximum distortion caused by such a matrix is proportional to the Gaussian complexity of the subset, scaled by the subgaussian norm of the matrix columns. This linear dependence on the subgaussian norm is a new phenomenon, as random matrices with independent rows or independent entries typically exhibit superlinear dependence. As a consequence, normalizing the columns of random sparse matrices leads to stronger embedding guarantees. keywords random matrix theory; restricted isometries; dimension reduction; random embeddings; sparse matrices AMS 15A42; 60D05 † † shorttitle: Random matrices with independent columns † † support: R.V. is partially supported by NSF Grant DMS 2451011 and NSF+Simons Research Collaborations on the Mathematical and Scientific Foundations of Deep Learning; Y.P. is partially supported by an NSERC Discovery Grant (GR009284), an NSERC Discovery Accelerator Supplement (GR007657), and a Tier II Canada Research Chair in Data Science (GR009243). † † email: [email protected] † † email: [email protected] † † submitted: February 23, 2025 † † volume: 0 † † year: 2023 † † papernumber: 0 † † doi: 10.1214/YY-TN 1 Introduction Let A\in\mathbb{R}^{m\times n} be a random matrix and T\subset\mathbb{R}^{n} a fixed set. We study the question: Under what circumstances is A well conditioned when restricted to T ? More technically, we study the quantity \delta\coloneqq\sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\left\lVert x\right\rVert_{2}\Big\rvert. Observe that the isometry constant \delta is the smallest constant such that \left\lVert x\right\rVert_{2}-\delta\leq\left\lVert Ax\right\rVert_{2}\leq\left\lVert x\right\rVert_{2}+\delta\qquad\mbox{for all }x\in T. If \delta is small, A embeds T into \mathbb{R}^{m} without significantly distorting Euclidean norms. If T is replaced by the Minkowski difference T-T , then the embedding approximately preserves Euclidean distances between points in T , so we can think of A as a near isometry on T . Random matrices that are near isometries are useful in a variety of applications, including compressed sensing [ 12 , 11 ] , dimension reduction as in the Johnson-Lindenstrauss lemma [ 14 ] , and randomized sketching [ 27 , 22 ] . The subset T of interest varies by application. When T belongs to the sphere and \delta<1 , the null space of A is a random subspace that must not intersect T , and thus the study of \delta also has interesting implications regarding the behaviour of random subspaces [ 13 , 19 ] . If A is a random Gaussian matrix, the size of \delta is well understood [ 23 ] . It is controlled by the Gaussian width or Gaussian complexity of T [ 26 ] . Definition 1 (The Gaussian width and Gaussian complexity of a set) . The Gaussian width w(T) and the Gaussian complexity \gamma(T) of a set T\subset\mathbb{R}^{n} are defined as follows: w(T)\coloneqq\E\sup_{x\in T}\langle g,x\rangle,\quad\gamma(T)\coloneqq\E\sup_{x\in T}\lvert\langle g,x\rangle\rvert where g is a standard normal random vector in \mathbb{R}^{n} , i.e. g\sim N(0,I_{n}) . These two quantities are identical for symmetric sets, and in general we have w(T)+\mathrm{rad}(T)\asymp\gamma(T) , where \mathrm{rad}(T):=\sup_{x\in T}\lVert x\rVert_{2} . For more properties of Gaussian width and complexity, see [ 26 ] . To extend our discussion to more general random matrix ensembles, recall that the subgaussian norm of a random variable Z is defined as \left\lVert Z\right\rVert_{\psi_{2}}:=\inf\left\{t>0:\E\exp(Z^{2}/t^{2})\leq 2\right\} and Z is called subgaussian if \left\lVert Z\right\rVert_{\psi_{2}}<\infty . Further, the subgaussian norm of a random vector V\in\mathbb{R}^{n} is defined as \lVert V\rVert_{\psi_{2}}:=\sup_{x\in S^{n-1}}\lVert\langle V,x\rangle\rVert_{\psi_{2}} (1) i.e. it is the largest subgaussian norm of one-dimensional marginals of V . For basic introduction to subgaussian distributions, see [ 26 ] . Matrices with subgaussian entries (or rows or columns) represent a notable generalization beyond the Gaussian case. In particular, this generalization includes discrete and/or sparse random matrices, which can be used to accelerate computations [ 16 ] and are essential in applications like group testing [ 8 ] and wireless network activity detection [ 18 ] . When A has independent, isotropic, 1 1 1 Recall that a random vector V\in\mathbb{R}^{n} is called isotropic if \E VV^{\mathsf{T}}=I_{n} where I_{n} is the identity matrix. and subgaussian rows, the quantity \delta has similar guarantees to the Gaussian case as shown in the following theorem. Theorem 2 (Corollary 1.2 in [ 13 ] ) . Let A be an m\times n matrix whose rows are independent, isotropic, subgaussian random vectors in \mathbb{R}^{n} with subgaussian norms bounded by K . Then, for any subset T\subset\mathbb{R}^{n} , we have \E\sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\sqrt{m}\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\sqrt{\log K}\,\gamma(T). Moreover, for any u\geq 0 , with probability at least 1-3e^{-u^{2}} , we have \sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\sqrt{m}\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\sqrt{\log K}\left[w(T)+u\cdot\mathrm{rad}(T)\right]. Here and throughout the paper, C>0 denotes an absolute constant. This theorem builds directly on the work in [ 19 ] , which presents the same result but with K\sqrt{\log K} replaced by K^{2} . In fact, the K\sqrt{\log K} dependence is known to be optimal in this setting [ 13 ] . Similar preceding results also appear in the papers [ 17 , 21 , 10 ] ; see [ 19 , Section 3] for a discussion of their relationship. In this paper, we develop an analogous theory for matrices with independent subgaussian columns. While there are several studies of random matrices with independent subgaussian columns restricted to specific subsets—such as the set of sparse vectors [ 2 ] , finite sets [ 9 ] , or the entire sphere [ 25 ] —we are only aware of one result that allows arbitrary sets T , due to D. Bartl and S. Mendelson [ 4 ] . We now state our main theorem and corollary, and then compare to the results in [ 4 ] in Remark 7 below. Theorem 3 . Let A be an m\times n matrix whose columns A_{i} are independent, mean zero, subgaussian random vectors in \mathbb{R}^{m} satisfying \left\lVert A_{i}\right\rVert_{2}=1 almost surely and \left\lVert A_{i}\right\rVert_{\psi_{2}}\leq K . Then, for any subset T\subset\mathbb{R}^{n} , we have \E\sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\gamma(T). Moreover, for any u\geq 0 , with probability at least 1-3e^{-u^{2}} , we have \sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\left[w(T)+u\cdot\mathrm{rad}(T)\right]. A trivial rescaling argument yields the following: Corollary 4 . Let A be an m\times n matrix whose columns A_{i} are independent, mean zero, subgaussian random vectors in \mathbb{R}^{n} satisfying \left\lVert A_{i}\right\rVert_{2}=\lambda almost surely and \left\lVert A_{i}\right\rVert_{\psi_{2}}\leq K . Then, for any subset T\subset\mathbb{R}^{n} , we have \E\sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\lambda\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\gamma(T). Moreover, for any u\geq 0 , with probability at least 1-3e^{-u^{2}} , we have \sup_{x\in T}\Big\lvert\left\lVert Ax\right\rVert_{2}-\lambda\left\lVert x\right\rVert_{2}\Big\rvert\leq CK\left[w(T)+u\cdot\mathrm{rad}(T)\right]. Remark 5 (Why is column normalization needed?) . In contrast to the previous result (Corollary 2 ), here we require a hard normalization of columns: \lVert A_{i}\rVert_{2}=\lambda\quad\text{a.s. for all }i. (2) One cannot remove this assumption even for n=1 , or replace it with a weaker assumption of isotropy as in Theorem 2 . This is because a mean-zero isotropic subgaussian random vector A_{1} might vanish with probability 1/2 . For example, if \delta\sim\mbox{Bern}(1/2) and X is (independently) chosen uniformly from \sqrt{m}S^{m-1} , then \delta X is a subgaussian vector with O(1) subgaussian norm. If the columns

Read the complete text