More Web Proxy on the site http://driver.im/

research-article

Restricted isometry of fourier matrices and list decodability of random linear codes

Authors:

Mahdi Cheraghchi,

Venkatesan Guruswami,

Ameya VelingkerAuthors Info & Claims

SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

Pages 432 - 442

Published: 06 January 2013 Publication History

Abstract

We prove that a random linear code over @@@@_q, with probability arbitrarily close to 1, is list decodable at radius 1--1/q -- ε with list size L = O(1/ε²) and rate R = Ω_q(ε²/(log³(1/ε))). Up to the polylogarithmic factor in 1/ε and constant factors depending on q, this matches the lower bound L = Ω_q(1/ε²) for the list size and upper bound R = O_q(ε²) for the rate. Previously only existence (and not abundance) of such codes was known for the special case q = 2 (Guruswami, Hå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 improve the analysis of Rudelson and Vershynin (2008) on the number of random frequency samples required for exact reconstruction of k-sparse signals of length N. Specifically we improve the number of samples from O(k log (N) log² (k)(log k+log log N)) to O(k log(N) log³(k)). The proof involves bounding the expected supremum of a related Gaussian process by using an improved analysis of the metric defined by the process. This improvement is crucial for our application in list decoding.

References

[1]

{AL11} N. Ailon, E. Liberty. An almost optimal unrestricted fast Johnson-Lindenstrauss transform. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pages 185--191, 2011.

Digital Library

[2]

{BDDW08} R. G. Baraniuk, M. A. Davenport, R. A. DeVore, and M. B. Wakin. A simple proof of the restricted isometry property for random matrices. Constructive Approximation, 28(3):253--263, Dec. 2008.

[3]

{Bli86} V. M. Blinovsky. Bounds for codes in the case of list decoding of finite volume. Problems of Information Transmission, 22(1):7--19, 1986.

[4]

{Bli05} V. M. Blinovsky. Code bounds for multiple packings over a nonbinary finite alphabet. Problems of Information Transmission, 41(1):23--32, 2005.

Digital Library

[5]

{Bli08} V. M. Blinovsky. On the convexity of one coding-theory function. Problems of Information Transmission, 44(1):34--39, 2008.

Digital Library

[6]

{Can08} E. Candès. The restricted isometry property and its implications for compresses sensing. C. R. Math. Acad. Sci. Paris, 346:589--592, 2008.

[7]

{Car85} B. Carl. Inequalities of Bernstein-Jackson-type and the degree of compactness of operators in Banach spaces. Annales de l'institut Fourier, 35(3):79--118, 1985.

[8]

{CGV12} M. Cheraghchi, V. Guruswami, and A. Velingker. Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Electronic Colloquium on Computational Complexity (ECCC), 19:82, 2012.

[9]

{Che10} M. Cheraghchi. Applications of Derandomization Theory in Coding. PhD thesis, Swiss Federal Institute of Technology (EPFL), Lausanne, Switzerland, 2010. (available online at http://eccc.hpi-web.de/static/books/Applications_of_Derandomization_Theory_in_Coding/).

[10]

{Che11} M. Cheraghchi. Coding-theoretic methods for sparse recovery. In Proceedings of the Annual Allerton Conference on Communication, Control, and Computing, 2011.

[11]

{CRT06a} E. Candès, J. Romberg, and T. Tao. Robust uncertainty principle: Exact signal reconstruction from highly incomplete frequency information. IEEE Trans. on Inf. Th., 52:489--509, 2006.

Digital Library

[12]

{CRT06b} E. Candès, J. Romberg, and T. Tao. Stable signal recovery from incomplete and inaccurate measurements. Comm. Pure Appl. Math., 59:1208--1223, 2006.

[13]

{CT06} E. Candès and T. Tao. Near-optimal signal recovery from random projections: Universal encoding strategies? IEEE Transactions on Information Theory, 52:5406--5425, 2006.

Digital Library

[14]

{Don06} D. Donoho. Compressed sensing. IEEE Transactions on Information Theory, 52:1289--1306, 2006.

Digital Library

[15]

{Eli91} P. Elias. Error-correcting codes for list decoding. IEEE Transactions on Information Theory, 37:5--12, 1991.

Digital Library

[16]

{GGR11} P. Gopalan, V. Guruswami, and P. Raghavendra. List decoding tensor products and interleaved codes. SIAM J. Comput., 40(5):1432--1462, 2011.

Digital Library

[17]

{GHK11} V. Guruswami, J. Håstad, and S. Kopparty. On the list-decodability of random linear codes. IEEE Transactions on Information Theory, 57(2):718--725, 2011. Special issue dedicated to the scientific legacy of Ralf Koetter.

Digital Library

[18]

{GHSZ02} V. Guruswami, J. Håstad, M. Sudan, and D. Zuckerman. Combinatorial bounds for list decoding. IEEE Transactions on Information Theory, 48(5):1021--1035, 2002.

Digital Library

[19]

{GKZ08} P. Gopalan, A. R. Klivans, and D. Zuckerman. List-decoding reed-muller codes over small fields. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, pages 265--274, 2008.

Digital Library

[20]

{GL89} O. Goldreich and L. Levin. A hard-core predicate for all one-way functions. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 25--32, 1989.

Digital Library

[21]

{GN12} V. Guruswami and S. Narayanan. Combinatorial limitations of a strong form of list decoding. Electronic Colloquium on Computational Complexity (ECCC), 19:17, 2012.

[22]

{GS01} V. Guruswami and M. Sudan. Extensions to the Johnson bound. Unpublished manuscript, 2001. Available at http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.145.9405.

[23]

{GS10} V. Guruswami and A. Smith. Codes for computationally simple channels: Explicit constructions with optimal rate. In Proceedings of IEEE Symposium on the Foundations of Computer Science, 2010.

Digital Library

[24]

{GV10} V. Guruswami and S. Vadhan. A lower bound on list size for list decoding. IEEE Transactions on Information Theory, 56(11):5681--5688, 2010.

Digital Library

[25]

{KS99} S. R. Kumar and D. Sivakumar. Proofs, codes, and polynomial-time reducibilities. In Proceedings of the 14th Annual IEEE Conference on Computation Complexity, 1999.

Digital Library

[26]

{KW11} F. Krahmer and R. Ward. New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property. SIAM Journal on Mathematical Analysis, 43(3):1269--1281, 2011.

[27]

{LT91} M. Ledoux and M. Talagrand. Probability in Banach spaces. Springer Verlag, 1991.

[28]

{MU01} E. Mossel and C. Umans. On the complexity of approximating the VC dimension. Journal of Computer and System Sciences, 65(4):660--671, 2001.

Digital Library

[29]

{Rud11} A. Rudra. Limits to list decoding of random codes. IEEE Transactions on Information Theory, 57(3):1398--1408, 2011.

Digital Library

[30]

{RV08} M. Rudelson and R. Vershynin. On sparse reconstruction from Fourier and Gaussian measurements. Communications on Pure and Applied Mathematics, 61:1025--1045, 2008.

[31]

{STV01} M. Sudan, L. Trevisan, and S. Vadhan. Pseudorandom generators without the XOR lemma. Journal of Computer and Systems Sciences, 62(2):236--266, 2001.

Digital Library

[32]

{Tre01} L. Trevisan. Extractors and pseudorandom generators. Journal of the ACM, 48(4):860--879, 2001.

Digital Library

[33]

{Ver12} R. Vershynin. Introduction to the non-asymptotic analysis of random matrices. In Compressed Sensing, Theory and Applications, ed. Y. Eldar and G. Kutyniok (Chapter 5), Cambridge University Press, pages 210--268, 2012.

[34]

{ZP82} V. V. Zyablov and M. S. Pinsker. List cascade decoding. Problems of Information Transmission, 17(4):29--34, 1981 (in Russian); pp. 236--240 (in English), 1982.

Cited By

Kapralov MVelingker AZandieh AChan T(2019)Dimension-independent sparse fourier transformProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310603(2709-2728)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310603
Rudra AWootters MCzumaj A(2018)Average-radius list-recoverability of random linear codesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175312(644-662)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175312
Soltani MHegde C(2017)Fast Algorithms for Demixing Sparse Signals From Nonlinear ObservationsIEEE Transactions on Signal Processing10.1109/TSP.2017.270618165:16(4209-4222)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1109/TSP.2017.2706181
Show More Cited By

Index Terms

Restricted isometry of fourier matrices and list decodability of random linear codes
1. Mathematics of computing
2. Security and privacy
  1. Cryptography
    1. Mathematical foundations of cryptography

Recommendations

Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes

We prove that a random linear code over $\mathbb{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 ...
Limits to list decodability of linear codes
STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

We consider the problem of the best possible relation between the list decodability of a binary linear code and its minimum distance. We prove, under a widely-believed number-theoretic conjecture, that the classical "Johnson bound" gives, in general, ...
Improved List-Decodability of Random Linear Binary Codes
There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate <inline-formula> <tex-math notation="LaTeX">$1 - {H}(\text {p}) - \epsilon $ </...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

SODA '13: Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms

January 2013

1935 pages

ISBN:9781611972511

Program Chair:
Sanjeev Khanna
University of Pennsylvania

In-Cooperation

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 06 January 2013

Check for updates

Qualifiers

Research-article

Conference

SODA '13

SODA '13: ACM-SIAM Symposium on Discrete Algorithms

January 6 - 8, 2013

Louisiana, New Orleans

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
53
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 31 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kapralov MVelingker AZandieh AChan T(2019)Dimension-independent sparse fourier transformProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310603(2709-2728)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310603
Rudra AWootters MCzumaj A(2018)Average-radius list-recoverability of random linear codesProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175312(644-662)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175312
Soltani MHegde C(2017)Fast Algorithms for Demixing Sparse Signals From Nonlinear ObservationsIEEE Transactions on Signal Processing10.1109/TSP.2017.270618165:16(4209-4222)Online publication date: 15-Aug-2017
https://dl.acm.org/doi/10.1109/TSP.2017.2706181
Haviv IRegev O(2016)The restricted isometry property of subsampled fourier matricesProceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms10.5555/2884435.2884457(288-297)Online publication date: 10-Jan-2016
https://dl.acm.org/doi/10.5555/2884435.2884457
Haviv IRegev OZuckerman D(2015)The list-decoding size of fourier-sparse boolean functionsProceedings of the 30th Conference on Computational Complexity10.5555/2833227.2833230(58-71)Online publication date: 17-Jun-2015
https://dl.acm.org/doi/10.5555/2833227.2833230
Bourgain JDirksen SNelson JServedio RRubinfeld R(2015)Toward a Unified Theory of Sparse Dimensionality Reduction in Euclidean SpaceProceedings of the forty-seventh annual ACM symposium on Theory of Computing10.1145/2746539.2746541(499-508)Online publication date: 14-Jun-2015
https://dl.acm.org/doi/10.1145/2746539.2746541
Rudra AWootters MRoughgarden T(2015)It'll Probably Work OutProceedings of the 2015 Conference on Innovations in Theoretical Computer Science10.1145/2688073.2688092(287-296)Online publication date: 11-Jan-2015
https://dl.acm.org/doi/10.1145/2688073.2688092
Nelson JPrice EWootters MChekuri C(2014)New constructions of RIP matrices with fast multiplication and fewer rowsProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634185(1515-1528)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634185
Indyk PKapralov MPrice EChekuri C(2014)(Nearly) sample-optimal sparse Fourier transformProceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms10.5555/2634074.2634110(480-499)Online publication date: 5-Jan-2014
https://dl.acm.org/doi/10.5555/2634074.2634110
Rudra AWootters MShmoys D(2014)Every list-decodable code for high noise has abundant near-optimal rate puncturingsProceedings of the forty-sixth annual ACM symposium on Theory of computing10.1145/2591796.2591797(764-773)Online publication date: 31-May-2014
https://dl.acm.org/doi/10.1145/2591796.2591797

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten