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.
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.
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})-\textsf{E}f(X^{\otimes d})\right\rvert>t \right\} \le C\exp\left[-c_K\mathcal I_{n,d}\left( \frac{t}{L n^{(d-1)/2}} \right)\right], \] where \[ \mathcal I_{n,d}(s)= \min\left\{ \frac{s^2}{d^2}, \frac{s^2}{d\log(e+nd/s^2)} \right\},\qquad s>0, \qquad \mathcal I_{n,d}(0)=0. \] The first rate is forced by changes in $\|X\|$. The second comes from changes of $X$ when its norm is nearly fixed. The proof constructs one coupling that controls both the coordinatewise conditional displacement and the mean squared Euclidean distance, and combines these bounds with a second-order estimate for $x\mapsto x^{\otimes d}$. The rate is minimax sharp, scale by scale, even when the subgaussian norms are bounded by an absolute constant. For bounded coordinates the logarithm in the second rate disappears.
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 $A \subseteq \mathbb F_2^n$ for any fixed $s\in\{1,\dots,2^d\}$ over a uniformly random $d$-flat $F$. We use $\lambda^*(d,s)$ to denote the limit of the maximum when $n$ goes to infinity. In this note, we prove tight bounds for $\lambda^*(d,s)$ in two different regimes. For $s=j2^k$ where $j$ is a positive odd integer, the best known lower bound construction achieving $\lambda^*(d,s)\ge 1-2^{-k}$ is due to taking $A$ as the union of $j$ parallel $(n-d+k)$-flats in $\mathbb F_2^n$. Our main result is a matching upper bound with an additive error term of $O(2^{-3k/2})$. We also study the case $s=1$, where we determine $\lambda^*(d,1)$ exactly. We show that the random construction where each point is included with probability $2^{-d}$ is optimal.
Ting-Wei Chao, Zixuan Xu, D. Zakharov· 0 citations
Let $A=(\xi_{ij})$ be an $n\times n$ random matrix with independent, not necessarily identically distributed, real entries satisfying \[ \mathbb E\xi_{ij}=0,\qquad \mathbb E\xi_{ij}^{2}=1,\qquad \sup_{z\in\mathbb R}\mathbb P(|\xi_{ij}-z|0$ and $b\in(0,1)$. We prove that, for every $\delta\in(0,1)$, there are constants $c,C>0$, depending only on $a,b,\delta$, such that \[ \mathbb P\left( s_{n+1-l}(A)>Ct\frac l{\sqrt n} \right) \le \exp\!\left(-c\min\{tl,n\}\right) \] for every $t\ge1$ and every $1\le l\le(1-\delta)n$. Thus, with no moment assumption beyond variance, all but a fixed proportion of the largest singular values satisfy the optimal upper bound of order $l/\sqrt n$ with an exponential upper-tail estimate. Combined with the lower bound of the rectangular least singular value bound, this gives $s_{n+1-l}(A)\asymp l/\sqrt n$ with failure probability exponentially small in $l$. The same argument gives the rectangular scale $\sqrt{N+1}-\sqrt{n-l+1}$ for $N\times n$ matrices whenever $N-n+l\le(1-\delta)N$.
Manuel Fernández, Achintya Raya Polavarapu· 0 citations
A nonuniform version in which the failure probability depends on the individual parameters, and a lower bound showing that a universal constant prefix discrepancy is impossible when $d=o(\ln T)$, are proved.
Let $d\geq5$. For a strictly increasing sequence $(\mu_k)$ of positive integers, set $\lambda_k=\mu_k!$ and consider the lacunary discrete spherical maximal operator $A_\star f:=\sup_k |A_{\lambda_k}f|$ associated with the discrete spherical averages \[ A_\lambda f(x):=\frac1{s_\lambda}\sum_{\substack{n\in\mathbb Z^d,\ |n|^2=\lambda}} f(x-n), \] where $s_\lambda:=\#\{n\in\mathbb Z^d:|n|^2=\lambda\}$. Kesler, Lacey and Mena proved that $A_\star$ is bounded on $\ell^p(\mathbb Z^d)$ for every $p>1$ if $\log\mu_k/\log k\longrightarrow\infty$, and asked about its endpoint behavior at $\ell\log\ell$. We resolve this endpoint question by characterizing all factorial sequences for which the $\ell\log\ell$ estimate holds. Define \[ C_{\log}=\sup_{N\geq2}\frac{\#\left\{k\geq 1:\mu_k\leq N\right\}}{1+\log N}. \] We prove that the $\ell\log\ell$ endpoint estimate holds if and only if $C_{\log}<\infty$. More precisely, if $C_{\log}<\infty$, then for every $\alpha>0$ and every finitely supported $f:\mathbb Z^d\to\mathbb C$, \begin{align*} \#\{x\in\mathbb Z^d:A_\star f(x)>\alpha\} \leq C_d(1+C_{\log})\sum_x \frac{|f(x)|}{\alpha} \left(1+\log^+\frac{|f(x)|}{\alpha}\right), \end{align*} where $C_d$ depends only on $d$. Conversely, if the above inequality holds with a finite constant $C_0$ in place of $C_d(1+C_{\log})$, then $C_{\log}\leq C_d(1+C_0)$. Thus their growth condition alone is insufficient at this endpoint. In particular, the estimate holds for $\lambda_k=(2^k)!$ and fails for $\lambda_k=(k+\lceil\exp(\sqrt{k})\rceil)!$.
Sanghyuk Lee, Ji Li, Chong-Wei Liang et al.· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
