Symmetric Pseudo-Random Matrices

被引：8
作者：
Soloveychik, Ilya [1 ]
Xiang, Yu [1 ]
Tarokh, Vahid [2 ]
机构：
[1] Harvard Univ, John A Paulson Sch Engn & Appl Sci, Cambridge, MA 02138 USA
[2] Duke Univ, Dept Elect & Comp Engn, Durham, NC 27708 USA
来源：
IEEE TRANSACTIONS ON INFORMATION THEORY | 2018年 / 64卷 / 04期
关键词：
Pseudo-random matrices; semicircular law; Wigner ensemble; UNIVERSALITY;
D O I：
10.1109/TIT.2018.2800004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We consider the problem of generating symmetric pseudo-random sign (+/- 1) matrices based on the similarity of their spectra to Wigner's semicircular law. Using binary m-sequences (Golomb sequences) of lengths n = 2(m) - 1, we give a simple explicit construction of circulant n x n sign matrices and show that their spectra converge to the semicircular law when n grows. The Kolmogorov complexity of the proposed matrices equals to that of Golomb sequences and is at most 2log(2)(n) bits.
引用
收藏
页码：3179 / 3196
页数：18
相关论文
共 51 条
[21]   Wigner theorems for random matrices with dependent entries: Ensembles associated to symmetric spaces and sample covariance matrices [J].
Hofmann-Credner, Katrin ;
Stolz, Michael .
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2008, 13 :401-414
[22]   Expander graphs and their applications [J].
Hoory, Shlomo ;
Linial, Nathan ;
Wigderson, Avi .
BULLETIN OF THE AMERICAN MATHEMATICAL SOCIETY, 2006, 43 (04) :439-561
[23]  
Hopcroft J.E., 2006, Introduction to Automata Theory, Languages, and Computation, V3rd
[24]   THEORY OF 2-DIMENSIONAL CYCLIC CODES [J].
IMAI, H .
INFORMATION AND CONTROL, 1977, 34 (01) :1-21
[25]  
Kemp T., 2013, INTRO RANDOM MATRIX
[26]  
Knuth D. E., 1998, Sorting and Searching, V2
[27]   3 APPROACHES TO QUANTITATIVE DEFINITION OF INFORMATION [J].
KOLMOGOROV, AN .
INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1968, 2 (02) :157-+
[28]  
Krivelevich M, 2006, BOLYAI MATH STUD, P199
[29]  
Li M., 1993, An introduction to Kolmogorov complexity and its applications, DOI [DOI 10.1007/978-3-030-11298-1, 10.1007/978-3-030-11298-1]
[30]  
MacWilliams F. J., 1991, The Theory Error-Correcting Codes
123456