This work develops 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$, and shows that matching results hold for other random models with negatively associated entries.
Abstract
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.
Given a subset $A \subseteq \mathbb F_2^n$, we can consider the distribution of the intersection size of $A$ with a uniformly random $d$-flat $F$. Motivated by the edge statistics problem and the hypercube statistics problem, the affine subspace statistics problem concerns the maximum of $\mathbb{P}[|F\cap A|=s]$ among...
Ting-Wei Chao, Zixuan Xu, D. Zakharov· 0 citations
Let $M_t$ denote the normalized average over the lattice points in the Euclidean ball of radius $t$ in $\mathbb{Z}^d$. We prove that the full maximal operator $f\mapsto\sup_{t\geq0}\lvert M_t f\rvert$ is bounded on $\ell^p(\mathbb{Z}^d)$, for every $1<p\leq\infty$, with a constant independent of the dimension. In parti...
Let $V$ be an $n$-dimensional vector space over a finite field of order $q$. Let $r\geq 3$, $(r-1)n\geq rk$ and let $\mathcal F_1,\ldots,\mathcal F_r\subset \genfrac{[}{]}{0pt}{}{V}{k}$, where $\genfrac{[}{]}{0pt}{}{V}{k}$ denotes the set of $k$-dimensional subspaces of $V$. Suppose that $F_1\cap\cdots\cap F_r\neq\{0\}...
We prove an improved restricted isometry bound for Gaussian partial circulant matrices with arbitrary prescribed sampling sets. There is a universal constant $C>0$ such that the following holds. Let $1\leq K\leq m\leq N$ be positive integers, let $\Omega\subset\mathbb Z_N$ be any fixed set with $|\Omega|=m$, and let $g...
Let $X=(X_1,\ldots,X_n)$ have independent coordinates with mean zero, variance one, and $\|X_i\|_{\psi_2}\le K$, and let $H_d=(\mathbb R^n)^{\otimes_2 d}$. Let $L>0$ and let $f:H_d\to\mathbb R$ be convex and $L$-Lipschitz. We prove that, for $0\le t\le c_KLn^{d/2}$, \[ \textsf{P}\left\{ \left\lvert f(X^{\otimes d})-\te...
In this paper, we study the sample complexity of the empirical plug-in estimator for the $2$-Gromov-Wasserstein distance $D_2$ between compactly supported probability measures on Euclidean spaces. Let $\mu$ and $\nu$ be supported on compact subsets of $\mathbb{R}^{d_x}$ and $\mathbb{R}^{d_y}$, respectively, and let $\w...
Pui-Kuen Leung, Riku Okada, Samuel Lok-Hei Wong· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
