Skip to main content

Pseudo-Wigner Matrices

Publication ,  Journal Article
Soloveychik, I; Xiang, Y; Tarokh, V
Published in: IEEE Transactions on Information Theory
April 1, 2018

We consider the problem of generating pseudo-random 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.

Duke Scholars

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

April 1, 2018

Volume

64

Issue

4

Start / End Page

3170 / 3178

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Soloveychik, I., Xiang, Y., & Tarokh, V. (2018). Pseudo-Wigner Matrices. IEEE Transactions on Information Theory, 64(4), 3170–3178. https://doi.org/10.1109/TIT.2017.2777464
Soloveychik, I., Y. Xiang, and V. Tarokh. “Pseudo-Wigner Matrices.” IEEE Transactions on Information Theory 64, no. 4 (April 1, 2018): 3170–78. https://doi.org/10.1109/TIT.2017.2777464.
Soloveychik I, Xiang Y, Tarokh V. Pseudo-Wigner Matrices. IEEE Transactions on Information Theory. 2018 Apr 1;64(4):3170–8.
Soloveychik, I., et al. “Pseudo-Wigner Matrices.” IEEE Transactions on Information Theory, vol. 64, no. 4, Apr. 2018, pp. 3170–78. Scopus, doi:10.1109/TIT.2017.2777464.
Soloveychik I, Xiang Y, Tarokh V. Pseudo-Wigner Matrices. IEEE Transactions on Information Theory. 2018 Apr 1;64(4):3170–3178.

Published In

IEEE Transactions on Information Theory

DOI

ISSN

0018-9448

Publication Date

April 1, 2018

Volume

64

Issue

4

Start / End Page

3170 / 3178

Related Subject Headings

  • Networking & Telecommunications
  • 4613 Theory of computation
  • 4006 Communications engineering
  • 1005 Communications Technologies
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing