Spectral Distribution of Product of Pseudorandom Matrices Formed From Binary Block Codes
Lists
Only you see this
Abstract
Let A ∈ {-1,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sub> ×n and B ∈ {-1,1} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sub> ×n be two matrices whose rows are drawn i.i.d. from the codewords of the binary codes C <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sup> and C <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sup> of length n and dual distances d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'a</sup> and d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'b</sup> , respectively, under the mapping 0 → 1 and 1 → -1. It is proven that as n → ∞ with y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sub> :=n/N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sub> ∈ (0,∞) and y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sub> :=n/N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sub> ∈ (0, ∞) fixed, the empirical spectral distribution of the matrix A B*/√{N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sub> N <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sub> } resembles a universal distribution (closely related to the distribution function of the free multiplicative convolution of two members of the Marchenko-Pastur family of densities) in the sense of the Lévy distance, if the asymptotic dual distances of the underlying binary codes are large enough. Moreover, an explicit upper bound on the Lévy distance of the two distributions in terms of y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">a</sub> , y <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sub> , d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'a</sup> , and d <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">'b</sup> is given. Under mild conditions, the upper bound is strengthened to the Kolmogorov distance of the underlying distributions. Numerical studies on the empirical spectral distribution of the product of random matrices from BCH and Gold codes are provided, which verify the validity of this result.
BibTeX
@article{babadi2013spectral,
author = {Behtash Babadi and Vahid Tarokh},
title = {{Spectral Distribution of Product of Pseudorandom Matrices Formed From Binary Block Codes}},
journal = {IEEE Trans. Information Theory},
year = {2013},
url = {https://openreview.net/forum?id=RorF9jzqKf},
}Loading related content...