Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation
arXiv:1311.0095 · doi:10.1088/1742-6596/473/1/012003
Abstract
We propose a systematic method for constructing a sparse data reconstruction algorithm in compressed sensing at a relatively low computational cost for general observation matrix. It is known that the cost of l1-norm minimization using a standard linear programming algorithm is O(N^3). We show that this cost can be reduced to O(N^2) by applying the approach of posterior maximization. Furthermore, in principle, the algorithm from our approach is expected to achieve the widest successful reconstruction region, which is evaluated from theoretical argument. We also discuss the relation between the belief propagation-based reconstruction algorithm introduced in preceding works and our approach.
arXiv comment11 pages, 5 figures, proceedings of ELC International Meeting on "Inference, Computation, and Spin Glasses" (ICSG2013), Sapporo, Japan
References in corpus (9)
- Message Passing Algorithms for Compressed Sensing
- The dynamics of message passing on dense graphs, with applications to compressed sensing
- Observed Universality of Phase Transitions in High-Dimensional Geometry, with Implications for Modern Data Analysis and Signal Processing
- Probabilistic Reconstruction in Compressed Sensing: Algorithms, Phase Diagrams, and Threshold Achieving Matrices
- Statistical physics-based reconstruction in compressed sensing
- A typical reconstruction limit of compressed sensing based on Lp-norm minimization
- Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction
- Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation
- A signal recovery algorithm for sparse matrix based compressed sensing