Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation

ELC International Meeting on Inference, Computation, and Spin Glasses

Takeda, Koujin^1 ; Kabashima, Yoshiyuki^2

Department of Intelligent Systems Engineering, Ibaraki University, Ibaraki, Japan^1

Department of Computational Intelligence and Systems Science, Tokyo Institute of Technology, Tokyo, Japan^2

关键词: 1-norm minimizations;    Belief propagation;    Computational costs;    Linear programming algorithm;    Maximum a posteriori estimation;    Observation matrix;    Reconstruction algorithms;    Theoretical arguments;   

Others  :  https://iopscience.iop.org/article/10.1088/1742-6596/473/1/012003/pdf
DOI  :  10.1088/1742-6596/473/1/012003

来源: IOP

【 摘 要 】

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 1-norm minimization using a standard linear programming algorithm is O(N3). We show that this cost can be reduced to O(N2) 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.