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\sim\mathcal N(0,I_N)$. For every $\delta,\eta\in(0,1)$, the normalized partial circulant matrix generated by $g$ has the RIP of order $K$ with constant at most $\delta$, with probability at least $1-\eta$ over the draw of $g$, provided \[ m\geq C\delta^{-2}K \max\{\log^2(eK)\log(2N)\log(em),\log(2/\eta)\}. \] The proof refines the Maurey entropy step in the chaos-process argument by combining a noncommutative Khintchine inequality with a Schatten moment estimate controlled by $m$, replacing one factor $\log(2N)$ in the Krahmer--Mendelson--Rauhut bound by $\log(em)$.
We establish Berry-Esseen bounds for the number of real roots of Gaussian Weyl polynomials $P_n$, where $n$ denotes the degree and is assumed to be sufficiently large. For each fixed $B$ above an absolute threshold, let $I_n=[-\sqrt n+B\sqrt{\log n}, \sqrt n-B\sqrt{\log n}]$. Uniformly over deterministic compact interv...
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.
This paper presents the first sparse GCD algorithm over the integers that achieves linear complexity in all fundamental parameters simultaneously and is the first sparse GCD algorithm over the integers that achieves linear complexity in all these parameters simultaneously.
A finite set of unit vectors is $k$-irreducible if every signed sum of between two and $k$ distinct elements has norm greater than one. Let $\mathcal{R}_k$ be the maximal asymptotic rate of such sets, and let $\kappa(\alpha)$ be the maximal asymptotic rate of spherical codes with pairwise inner products at most $\alpha...
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 $P_n$ be the matrix of a random permutation of $n$ symbols and let $M_n=\log\max_{|z|=1}|\det(I-zP_n)|$. Cook and Zeitouni proved that $M_n/\log n$ converges in probability to a constant $x_0$ for a uniform permutation. We show that the $\sqrt{\log n}$ fluctuations of $M_n$ are carried entirely by the number of cyc...
Zhi-Peng Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
