This paper considers the problem of compressive sensing over a finite alphabet, where the finite alphabet may be inherent to the nature of the data or a result of quantization. There are multiple examples of finite alphabet based static as well as time-series data with inherent sparse structure; and quantizing real values is an essential step while handling real data in practice. We show that there are significant benefits to analyzing the problem while incorporating its finite alphabet nature, versus ignoring it and employing a conventional real alphabet based toolbox. Specifically, when the alphabet is finite, our techniques (a) have a lower sample complexity compared to real-valued compressive sensing for sparsity levels below a threshold; (b) facilitate constructive designs of sensing matrices based on coding-theoretic techniques; (c) enable one to solve the exact @math -minimization problem in polynomial time rather than a approach of convex relaxation followed by sufficient conditions for when the relaxation matches the original problem; and finally, (d) allow for smaller amount of data storage (in bits).
The fact that real-valued compressive sensing allows for recovery of sparse signals based on linear measurements is reminiscent of error correction in linear channel codes and compression by lossless source codes over finite alphabet or fields @cite_11 @cite_28 . Such similarities have been identified in existing literature to serve varied goals. For example, the use of bipartite expander graphs to design real-valued sensing matrices is investigated in @cite_12 . The connection between real-valued compressive sensing and linear channel codes is explored in @cite_20 , by viewing sparse signal compression as syndrome-based source coding over real numbers and making use of linear codes over finite fields of large sizes. The design of real-valued sensing matrices based on LDPC codes is examined in @cite_27 and @cite_4 . The connection between sparse learning problems and coding theory is studied in @cite_0 . For real-valued compressive sensing over finite alphabet, the sparse signal recovery approaches that have been examined include approximate message passing @cite_14 , sphere decoding and semi-definite relaxation @cite_1 . However, an algebraic understanding of compressive sensing, particularly over finite fields, is yet limited, which is the main contribution of this paper.
@cite_14 @cite_4 @cite_28 @cite_1 @cite_0 @cite_27 @cite_12 @cite_20 @cite_11
2097947585 2145403642 2088587246 2963664181 2033375925 2009101269 628021441
In this paper we consider Basis Pursuit De-Noising (BPDN) problems in which the sparse original signal is drawn from a finite alphabet. To solve this problem we propose an iterative message passing algorithm, which capitalises not only on the sparsity but by means of a prior distribution also on the discrete nature of the original signal. In our numerical experiments we test this algorithm in combination with a Rademacher measurement matrix and a measurement matrix derived from the random demodulator, which enables compressive sampling of analogue signals. Our results show in both cases significant performance gains over a linear programming based approach to the considered BPDN problem. We also compare the proposed algorithm to a similar message passing based algorithm without prior knowledge and observe an even larger performance improvement. This is a tale of two linear programming decoders, namely channel coding linear programming decoding (CC-LPD) and compressed sensing linear programming decoding (CS-LPD). So far, they have evolved quite independently. The aim of the present paper is to show that there is a tight connection between, on the one hand, CS-LPD based on a zero-one measurement matrix over the reals and, on the other hand, CC-LPD of the binary linear code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows one to translate performance guarantees from one setup to the other. For Slepian-Wolf source networks, the error exponents obtained by Korner,Marton, and the author are shown to be universally attainable by linear codes also. Improved exponents are derived for linear codes with "large rates." Specializing the results to simple discrete memoryless sources reveals their relationship to the random coding and expurgated bounds for channels with additive noise. One corollary is that there are universal linear codes for this class of channels which attain the random coding error exponent for each channel in the class. The combinatorial approach of Csiszar-Korner-Marton is used. In particular, all results are derived from a lemma specifying good encoders in terms of purely combinatorial properties. We review connections between coding-theoretic objects and sparse learning problems. In particular, we show how seemingly different combinatorial objects such as error-correcting codes, combinatorial designs, spherical codes, compressed sensing matrices and group testing designs can be obtained from one another. The reductions enable one to translate upper and lower bounds on the parameters attainable by one object to another. We survey some of the well-known reductions in a unified presentation, and bring some existing gaps to attention. New reductions are also introduced; in particular, we bring up the notion of minimum L-wise distance of codes and show that this notion closely captures the combinatorial structure of RIP-2 matrices. Moreover, we show how this weaker variation of the minimum distance is related to combinatorial list-decoding properties of codes. Compressive sensing is an emerging technology which can recover a sparse signal vector of dimension n via a much smaller number of measurements than n. However, the existing compressive sensing methods may still suffer from relatively high recovery complexity, such as O(n3), or can only work efficiently when the signal is super sparse, sometimes without deterministic performance guarantees. In this paper, we propose a compressive sensing scheme with deterministic performance guarantees using expander-graphs-based measurement matrices and show that the signal recovery can be achieved with complexity O(n) even if the number of nonzero elements k grows linearly with n. We also investigate compressive sensing for approximately sparse signals using this new method. Moreover, explicit constructions of the considered expander graphs exist. Simulation results are given to show the performance and complexity of the new method. Compressed sensing (CS) is a relatively new area of signal processing and statistics that focuses on signal reconstruction from a small number of linear (e.g., dot product) measurements. In this paper, we analyze CS using tools from coding theory because CS can also be viewed as syndrome-based source coding of sparse vectors using linear codes over real numbers. While coding theory does not typically deal with codes over real numbers, there is actually a very close relationship between CS and error-correcting codes over large discrete alphabets. This connection leads naturally to new reconstruction methods and analysis. In some cases, the resulting methods provably require many fewer measurements than previous approaches. Preface 1. Coding and capacity 2. Finite fields, vector spaces, finite geometries and graphs 3. Linear block codes 4. Convolutional codes 5. Low-density parity-check codes 6. Computer-based design of LDPC codes 7. Turbo codes 8. Ensemble enumerators for turbo and LDPC codes 9. Ensemble decoding thresholds for LDPC and turbo codes 10. Finite geometry LDPC codes 11. Constructions of LDPC codes 12. LDPC codes based on combinatorial designs, graphs, and superposition 13. LDPC codes for binary erasure channels 14. Non-binary LDPC codes 15. LDPC code applications and advanced topics Index.