Deterministic Random Matrices

ABSTRACT: Random matrices have become a very active area of research in the recent years and have found enormous applications in modern mathematics, physics, engineering, biological modeling, and other fields. In this work, we focus on symmetric sign (+/-1) matrices (SSMs) that were originally utilized by Wigner to model the nuclei of heavy atoms in mid-50s. Assuming the entries of the upper triangular part to be independent +/-1 with equal probabilities, Wigner showed in his pioneering works that when the sizes of matrices grow, their empirical spectra converge to a non-random measure having a semicircular shape. Later, this fundamental result was improved and substantially extended to more general families of matrices and finer spectral properties. In many physical phenomena, however, the entries of matrices exhibit significant correlations. At the same time, almost all available analytical tools heavily rely on the independence condition making the study of matrices with structure (dependencies) very challenging. The few existing works in this direction consider very specific setups and are limited by particular techniques, lacking a unified framework and tight information-theoretic bounds that would quantify the exact amount of structure that matrices may possess without affecting the limiting semicircular form of their spectra.

Reliable deterministic construction of SSMs with random-looking spectra and low algorithmic and computational complexity is of particular interest due to the natural correspondence of SSMs and undirected graphs, since the latter are extensively used in combinatorial and CS applications e.g. for the purposes of derandomization. Unfortunately, most of the existing constructions of pseudo-random graphs focus on the extreme eigenvalues and do not provide guaranties on the whole spectrum. In this work, using binary Golomb sequences, we propose a simple completely deterministic construction of circulant SSMs with spectra converging to the semicircular law with the same rate as in the original Wigner ensemble. We show that this construction has close to lowest possible algorithmic complexity and is very explicit. Essentially, the algorithm requires at most 2log(n) bits implying that the real amount of randomness conveyed by the semicircular property is quite small.

BIO: Ilya Soloveychik received his BSc degree in Applied Mathematics and Physics from the Moscow Institute of Physics and Technology, Moscow, Russia in 2007, the MSc degree in Mathematics and the PhD degree in Electrical Engineering from the Hebrew University of Jerusalem, Israel in 2013 and 2016, respectively. He is currently a Fulbright postdoctoral fellow with the Harvard School of Engineering and Applied Sciences. His research interests include random matrix theory, high-dimensional statistics and signal processing, and graphical models. He received the Potanin Scholarship for excellence in studies in 2005, the Klein Prize and the Kaete Klausner Scholarship in 2011. In 2015 he was awarded the Feder Family Prize for outstanding research in the field of Communications Technology and in 2016 – the Wolf Foundation Prize for excellence in studies.

Hosted by: Paul Bogdan