Norms of structured random matrices

Abstract

For $m,n\in \mathbb{N}$ let $X=(X_{ij}{)}_{i\le m,j\le n}$ be a random matrix, $A=(a_{ij}{)}_{i\le m,j\le n}$ a real deterministic matrix, and $X_A=(a_{ij}{X}_{ij}{)}_{i\le m,j\le n}$ the corresponding structured random matrix. We study the expected operator norm of $X_A$ considered as a random operator between ${\ell }_p^n$ and ${\ell }_q^m$ for $1\le p,q\le \infty$. We prove optimal bounds up to logarithmic terms when the underlying random matrix $X$ has i.i.d. Gaussian entries, independent mean-zero bounded entries, or independent mean-zero ${\psi }_r$ ($r\in (0,2]$) entries. In certain cases, we determine the precise order of the expected norm up to constants. Our results are expressed through a sum of operator norms of Hadamard products $A\circ A$ and $(A\circ A{)}^T$.

50 pages, 1 figure, 1 table; Remark 1.1 and Subsection 5.4 added, typos corrected

References in corpus (2)

• Random sections of ellipsoids and the power of random information
• Norms of Randomized Circulant Matrices