A General Framework for the Design of Compressive Sensing using Density Evolution

This paper proposes a general framework to design a sparse sensing matrix A\in R^{m\times n}, in a linear measurement system y = \Ax^{\natural} + w, where y \in R^n, x^{\natural}\in R^n, and w denote the measurements, the signal with certain structures, and the measurement noise, respectively. By viewing the signal reconstruction from the measurements as a message passing algorithm over a graphical model, we leverage tools from coding theory in the design of low density parity check codes, namely the density evolution, and provide a framework for the design of matrix A. Particularly, compared to the previous methods, our proposed framework enjoys the following desirable properties: (i) Universality: the design supports both regular reconstruction and preferential reconstruction, and incorporates them in a single framework; (ii) Flexibility: the framework can easily adapt the design of A to a signal x^{\natural} with different underlying structures. As an illustration, we consider the L1 regularizer, which correspond to Lasso, for both the regular reconstruction and preferential reconstruction scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., m\geq c_0 k\log(n/k) (the regular reconstruction) with regular design after proper distribution approximation, where c_0 > 0 is some fixed constant. We also provide numerical experiments to confirm the analytical results and demonstrate the superiority of our framework whenever a preferential treatment of a sub-block of vector x^{\natural} is required.