Pseudo-Wigner Matrices
Lists
Only you see this
Abstract
We consider the problem of generating pseudorandom matrices based on the similarity of their spectra to Wigner's semicircular law. We introduce the notion of an r-independent pseudo-Wigner matrix ensemble and prove the closeness of the spectra of its matrices to the semicircular density in the Kolmogorov distance. We give an explicit construction of a family of N × N pseudo-Wigner ensembles using dual BCH codes and show that the Kolmogorov complexity of the obtained matrices is of the order of log(N) bits for a fixed designed Kolmogorov distance precision. We compare our construction with the quasi-random graphs introduced by Chung et al. and demonstrate that the pseudo-Wigner matrices pass stronger randomness tests than the adjacency matrices of these graphs (lifted by the mapping 0 → 1 and 1 → -1) do. Finally, we provide numerical simulations verifying our theoretical results.
BibTeX
@article{soloveychik2018pseudo,
author = {Ilya Soloveychik and Yu Xiang and Vahid Tarokh},
title = {{Pseudo-Wigner Matrices}},
journal = {IEEE Trans. Information Theory},
year = {2018},
url = {https://openreview.net/forum?id=T1o5zcoqSe-},
}Loading related content...