On the Spectral Norms of Pseudo-Wigner and Related Matrices

Abstract

We investigate the spectral norms of symmetric $N\times N$ matrices from two pseudo-random ensembles. The first is the pseudo-Wigner ensemble introduced in "Pseudo-Wigner Matrices" by Soloveychik, Xiang and Tarokh and the second is its sample covariance-type analog defined in this work. Both ensembles are defined through the concept of $r$-independence by controlling the amount of randomness in the underlying matrices, and can be constructed from dual BCH codes. We show that when the measure of randomness $r$ grows as $N^{\rho }$, where $\rho \in (0,1]$ and $\epsilon >0$, the norm of the matrices is almost surely within $o\left(\frac{{\log }^{1+\epsilon }N}{N^{\min [\rho ,2/3]}}\right)$ distance from $1$. Numerical simulations verifying the obtained results are provided.