Random frames from binary linear block codes
Let C be an [n, k, d] binary linear block code of length n, dimension k and minimum Hamming distance d over GF(2n). Let d⊥ denote the minimum Hamming distance of the dual code of Cover GF(2n). Let ε : GF(2n) → {-1, 1}n be the component-wise mapping ε(vi) := (-1)vi , for v = (vI, v2, v2, ⋯, vn) ∈ GF(2n). Finally, for p < n, let ΦC be a p x n random matrix whose rows are obtained by mapping a uniformly drawn set of size p of the codewords of C under ε. Recently, the authors have established that [3] for d ⊥ large enough and y := p/n ∈ (0,1) fixed, as n → ∞ the empirical eigen-distribution of the Gram matrix of 1/√n ΦC resembles that of a random i.i.d, Rademacher matrix (i.e., the Marchenko-Pastur distribution). In this paper, we overview this result and discuss its implications on the design of frames for compressed sensing applications. ©2010 IEEE.
