Reconstruction algorithm in compressed sensing based on maximum a posteriori estimation

Koujin Takeda, Yoshiyuki Kabashima

This paper, published in 2013 by Koujin Takeda and Yoshiyuki Kabashima, explores a more efficient way to solve the fundamental problem of signal recovery in compressed sensing.

TL;DR

The authors propose a sparse data reconstruction algorithm based on Maximum A Posteriori (MAP) estimation that reduces computational complexity from $O(N^3)$ to $O(N^2)$ for general measurement matrices. Crucially, they demonstrate that the "Onsager reaction term" used in Approximate Message Passing (AMP) can be understood as a specific type of "partition ratio" within their MAP framework, providing a new theoretical bridge between these two approaches.

What Problem Does This Paper Address?

In compressed sensing (CS), we aim to recover a sparse signal $x$ from a relatively small number of linear measurements $y = Fx$. The standard way to do this is through $\ell_1$-norm minimization (often called Lasso or Basis Pursuit).

While mathematically elegant, $\ell_1$ minimization is computationally expensive. Standard solvers like interior-point methods scale at $O(N^3)$, where $N$ is the signal dimension. This makes them impractical for high-dimensional data like high-resolution images or large-scale sensor networks. While faster algorithms like Approximate Message Passing (AMP) exist, they often rely on the assumption that the measurement matrix $F$ consists of independent and identically distributed (i.i.d.) Gaussian entries. This paper seeks a systematic reconstruction method that is computationally efficient ($O(N^2)$) but applicable to more general types of measurement matrices.

Methods

The authors derive their algorithm using a Bayesian approach. They define a posterior probability $P(x|y, F)$ and look for the "MAP solution"—the signal $x$ that maximizes this probability.

Key technical steps include:

  1. Posterior Formulation: They use a limit process ($\beta \to \infty$) to ensure the MAP solution is equivalent to the $\ell_1$-norm minimum.
  2. Regularization: To handle the singular nature of the constraints, they introduce a quadratic regularization term and a parameter $k$ that represents the "relative significance" of the constraint versus the minimization.
  3. Iterative Thresholding: By differentiating the exponential term of the posterior, they derive a stationary condition that looks like a thresholding function.
  4. The Partition Ratio: To improve convergence near the reconstruction threshold, they introduce a "partial update" rule using a partition ratio ($\gamma$). Instead of fully updating the estimate in each step, they keep a portion of the previous estimate.

Datasets

The paper evaluates the algorithm using synthetic numerical experiments:

  • Signal ($x$): Sparse vectors with $N=10^3$ or $N=2000$ dimensions. The non-zero entries are drawn from a Gaussian distribution.
  • Measurement Matrices ($F$):
    • Standard i.i.d. Gaussian matrices.
  • Sparse random matrices (where 90% of the entries are set to zero) to test the algorithm's performance on non-dense, general matrices.

Key Insights and Ideas

  • The "Aha" Moment on AMP: The most significant theoretical contribution is the link to AMP. In the AMP algorithm, a specific "Onsager reaction term" is added to ensure convergence. Takeda and Kabashima show that this term is essentially a specific choice of their "partition ratio" applied to the residual error. This provides a fresh, optimization-based perspective on a term originally derived from message-passing physics.
  • Complexity Gains: By using a single summation in their iterative equations, they achieve $O(N^2)$ complexity. If the measurement matrix $F$ is itself sparse, this drops further to $O(N)$.
  • Universality: The MAP framework doesn't strictly require the i.i.d. Gaussian assumptions that original AMP proofs rely on, suggesting it could be more robust for real-world hardware where measurement matrices have specific structures.

Key Results

  • Reconstruction Thresholds: Through "phase transition" plots, the authors show that their MAP algorithm (with a properly tuned partition ratio) achieves a success region almost identical to the theoretical limit of $\ell_1$ minimization.
  • Success with Sparse Matrices: The algorithm successfully reconstructed signals using a matrix that was 90% sparse, confirming its applicability beyond the standard dense Gaussian case.
  • Convergence Speed: In head-to-head tests, AMP still converges faster than the basic MAP algorithm. However, the authors show that the MAP algorithm's performance improves significantly as the partition ratio is optimized.

Limitations and Future Work

  • Tuning the Partition Ratio: While the paper proves that a good partition ratio exists, it does not provide a universal, automated "recipe" for choosing the optimal $\gamma$ for any arbitrary matrix $F$.
  • Convergence Gap: There is still a gap in convergence speed between the proposed MAP method and AMP. The authors suggest that future work should focus on designing a step-dependent partition ratio for the residual error to close this gap.
  • Parameter Scheduling: The algorithm requires the parameter $k$ to decay to zero over time. Finding the "perfect" decay rate is currently more of an empirical art than a settled science.

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},
}

Loading related content...

Figure