Compressive sensing and algebraic coding: connections and challenges (Q2417681)

Compressed sensing refers to reconstruction of sparse or compressible signals from a few measurements. The reconstruction can be done by the use of many basis pursuit like algorithms. In such approach the key role is played by the measurement matrix, which converts the sparse signal into few measurements. The construction of such a matrix is not easy since it has to fulfill the so called Restricted Isometry Property (RIP) in order to assure exact reconstruction. There are two approaches for generating matrices that satisfy the RIP: probabilistic and deterministic. Deterministic approach is more recent and more convenient. A recent trend in sensing matrix generation has been to use of the methods from algebraic coding theory, and in particular, expander graphs and low-density parity-check codes. In this chapter some new constructions of sparse binary sensing matrices based on low-density parity-check codes are presented. Additionally, some of the recent results that lead to the fastest available algorithms for compressive sensing in specific situations are given. The theoretical results are confirmed by the presented experiments. For the entire collection see [Zbl 1410.93006].