Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation

Koujin Takeda, Yoshiyuki Kabashima

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 $\ell_1$-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.

Introduction

Compressed sensing (CS) is a paradigm for recovering a sparse signal $x \in \mathbb{R}^N$ from a small number of linear measurements $y = Fx \in \mathbb{R}^M$, where $M < N$. The standard approach for reconstruction is $\ell_1$-norm minimization, which is robust but computationally demanding. Standard solvers like interior-point methods scale at $O(N^3)$, making them impractical for high-dimensional data such as high-resolution images. While faster algorithms like Approximate Message Passing (AMP) exist, they often rely on specific assumptions about the measurement matrix $F$, such as i.i.d. Gaussian entries. This work introduces a systematic reconstruction method based on Maximum A Posteriori (MAP) estimation that achieves $O(N^2)$ complexity and is applicable to more general measurement matrices.

Methodology

The proposed algorithm is derived from a Bayesian framework. The authors define a posterior probability $P(x|y, F)$ and seek the MAP solution that maximizes this probability. To ensure the MAP solution is equivalent to the $\ell_1$-norm minimum, they employ a limit process where a temperature-like parameter $\beta \to \infty$.

Key components of the algorithm include:

  1. Quadratic Regularization: Introduced to handle singular constraints and stabilize the optimization process.
  2. Iterative Thresholding: Derived from the stationary conditions of the posterior, leading to an efficient update rule.
  3. Partition Ratio ($\gamma$): A critical parameter introduced to improve convergence near the reconstruction threshold. This "partial update" rule prevents the algorithm from oscillating and ensures it reaches the optimal solution.

In a significant theoretical finding, the authors demonstrate that the "Onsager reaction term" in AMP—which is crucial for its convergence—can be interpreted as a specific choice of the partition ratio within this MAP framework. This provides an optimization-based justification for a term originally derived from statistical physics.

Results and Discussion

The algorithm was evaluated using synthetic sparse signals with dimensions $N=1000$ and $N=2000$. Two types of measurement matrices were tested: standard i.i.d. Gaussian matrices and sparse random matrices (where 90% of entries are zero).

Phase Transition and Success Region

The performance is characterized by phase transition plots in the $(\rho, \alpha)$ plane, where $\alpha = M/N$ is the measurement rate and $\rho = K/M$ is the sparsity relative to the number of measurements.

Phase transition plot showing the success rate of the MAP-based algorithm compared to the theoretical l1-norm threshold.

As shown in Figure 1, the MAP algorithm with an optimized partition ratio achieves a success region that is nearly identical to the theoretical limit of $\ell_1$ minimization. This confirms that the proposed $O(N^2)$ algorithm does not sacrifice reconstruction quality for computational speed.

Generalization to Sparse Matrices

A key advantage of the MAP framework is its applicability to non-Gaussian matrices. The algorithm successfully reconstructed signals using matrices that were 90% sparse, demonstrating its robustness for hardware-constrained or structured measurement scenarios where standard AMP might struggle.

Success rate for sparse measurement matrices, demonstrating the algorithm's applicability to general matrices.

Conclusion

This work provides a computationally efficient $O(N^2)$ reconstruction algorithm for compressed sensing based on MAP estimation. By establishing a link between the partition ratio and the Onsager reaction term in AMP, it offers new theoretical insights into message-passing algorithms. While the algorithm shows excellent performance, future research is needed to automate the selection of the optimal partition ratio $\gamma$ and to refine the decay schedule of the regularization parameters to further close the convergence speed gap with AMP.

Summary updated

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.
BibTeX
@article{takeda2013reconstruction,
  author = {Koujin Takeda and Yoshiyuki Kabashima},
  title = {{Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation}},
  journal = {Journal of Physics Conference Series},
  year = {2013},
  doi = {10.1088/1742-6596/473/1/012003},
}
Figure