A General Compressive Sensing Construct using Density Evolution

Abstract

This paper proposes a general framework to design a sparse sensing matrix A R^m n, in a linear measurement system y = Ax^ + w, where y R^m, x^ ^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 sensing and preferential sensing, and incorporates them in a single framework; (ii) Flexibility: the framework can easily adapt the design of to a signal x^ with different underlying structures. As an illustration, we consider the _1 regularizer, which correspond to Lasso, for both the regular sensing and preferential sensing scheme. Noteworthy, our framework can reproduce the classical result of Lasso, i.e., m c_0 k(n/k) (the regular sensing) 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 ^ is required.

Tasks

Reproductions