Can I read Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes on EtoBox?

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes by Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya is a scholarly article available to read on EtoBox.

What is Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes about?

We prove that a random linear code over F_q, with probability arbitrarily close to 1, is list decodable at radius (1-1/q-\epsilon) with list size L=O(1/\epsilon^2) and rate R=\Omega_q(\epsilon^2/(log^3(1/\epsilon))). Up to the polylogarithmic factor in (1/\epsilon) and constant factors depending on q, this matches the lower bound L=\Omega_q(1/\epsilon^2) for the list size and upper bound R=O_q(\epsilon^2) for the rate. Previously only existence (and not abundance) of such codes was known for the special case q=2 (Guruswami, H{\aa}stad, Sudan and Zuckerman, 2002). In order to obtain our result, we employ a relaxed version of the well known Johnson bound on list decoding that translates the average Hamming distance between codewords to list decoding guarantees. We furthermore prove that the desired average-distance guarantees hold for a code provided that a natural complex matrix encoding the codewords satisfies the Restricted Isometry Property with respect to the Euclidean norm (RIP-2). For the case of random binary linear codes, this matrix coincides with a random submatrix of the Hadamard-Walsh transform matrix that is well studied in the compressed sensing literature. Finally, we

Author

Cheraghchi, Mahdi; Guruswami, Venkatesan; Velingker, Ameya

Published

2012

Language

EN