Source-linked AI summary
Turbo Compressed Sensing with Partial DFT Sensing Matrix
Junjie Ma, Xiaojun Yuan, Li Ping
TL;DR
The paper addresses efficient compressed-sensing recovery with partial DFT matrices, where AMP's Gaussian-matrix setting does not directly apply. It proposes a turbo algorithm with redesigned extrinsic-message computation, whose state evolution agrees with replica-method results and whose simulations outperform AMP for partial DFT sensing.
Problem
Partial DFT sensing matrices require efficient recovery, but their dependent entries differ from the i.i.d. Gaussian setting underlying AMP's near-optimality analysis.
Method
The proposed turbo algorithm uses an LMMSE processor for partial DFT information, a sparsity processor, and a novel computation of extrinsic sparsity messages.
Results
The proposed algorithm's state evolution is consistent with replica-method predictions, and simulations show it outperforms AMP with partial DFT sensing.
Takeaways & Limitations
The algorithm provides a turbo recovery approach whose predicted behavior matches replica-method analysis for partial DFT sensing.
Takeaways & Limitations
The state-evolution analysis relies on three assumptions, and more rigorous justification remains future work.
Abstract
from arXiv · showhide
In this letter, we propose a turbo compressed sensing algorithm with partial discrete Fourier transform (DFT) sensing matrices. Interestingly, the state evolution of the proposed algorithm is shown to be consistent with that derived using the replica method. Numerical results demonstrate that the proposed algorithm outperforms the well-known approximate message passing (AMP) algorithm when a partial DFT sensing matrix is involved.
I. INTRODUCTION
Partial DFT sensing creates a compressed-sensing setting where AMP's Gaussian-matrix state-evolution guarantees do not directly apply. The paper proposes a turbo algorithm whose state evolution matches replica-method predictions.
- Partial DFT matrices are widely used, motivating efficient recovery algorithms for the associated compressed-sensing problems.
- AMP can be near-optimal with i.i.d. Gaussian sensing matrices, but partial DFT entries are not independently drawn.
- Replica-method analyses predict different optimal reconstruction performance for partial DFT and i.i.d. Gaussian sensing matrices.
- The proposed turbo algorithm uses an LMMSE processor for partial DFT information and a second processor for sparsity information.
- Its main contribution is a novel computation of extrinsic sparsity messages, with state evolution coinciding with replica-method predictions.
A. Standard Turbo Algorithm
The standard turbo detector alternates an LMMSE estimator and a sparsity combiner, passing extrinsic information between them. Its operations derive prior statistics and LMMSE estimates for the transformed signal.
- The standard turbo detector iteratively connects an LMMSE estimator with a sparsity combiner through extrinsic and a priori information.
- Module A is an LMMSE estimator that produces a coarse extrinsic estimate of x from the observation y.
- Module B refines the estimate by combining the LMMSE output with the sparse distribution.
- Under Assumption 1, the a priori information about x is modeled through its mean and variance, which determine statistics of z = F x.
- The LMMSE estimator and associated MSE matrix are computed from the transformed-signal prior statistics.
2) Module B:
The sparsity combiner performs component-wise MMSE estimation under an AWGN model and forms extrinsic information for iterative processing. The standard detector's module B is LMMSE-compatible but yields no useful extrinsic output.
- The sparsity combiner refines LMMSE estimates by incorporating the sparse prior information about x.
- Module B models its input as an AWGN observation of x and updates prior statistics from module A's extrinsic output.
- Its MMSE estimator operates component-wise and computes posterior means and conditional variances for the signal entries.
- The extrinsic estimate excludes each entry's prior contribution before being passed back to module A in the next iteration.
- The LMMSE operation is optimal in the LMMSE sense when sparsity is ignored and no iteration is involved, unlike AMP's distributive message passing.
- In the standard detector, module B's extrinsic estimate is zero, so iterative processing provides no further improvement.
B. Proposed Turbo Compressed Sensing Algorithm
The proposed turbo algorithm changes the exchange structure between the two processors. Module A computes extrinsic information about x, while module B computes it about z.
- The proposed algorithm uses two modules that exchange extrinsic information about different variables rather than both processing x.
- Module A computes extrinsic information about x using an LMMSE estimator of z and two IDFT operations.
2) Module B:
Module B computes an extrinsic estimate of z rather than x, using Gaussian posterior assumptions and component-wise sparsity processing. This estimate becomes module A’s prior input in subsequent iterations.
- Module B computes the extrinsic estimate of z instead of x, unlike the standard detector.
- The analysis assumes posterior distributions of z conditioned on the prior information are Gaussian.
- The posterior entries of x are conditionally independent because the prior entries are independent and the sparsity combiner operates component-wise.
- The extrinsic mean and variance produced by module B serve as module A’s prior mean and variance in the next iteration.
- The DFT/IDFT operations can use FFT, and reordering extrinsic operations can save one DFT/IDFT pair.
III. STATE EVOLUTION
The proposed algorithm’s large-system performance is analyzed using state evolution, following the approach used for AMP.
- The proposed turbo compressed sensing scheme is analyzed in the large-system limit using state evolution.
A. State Evolution
The state evolution characterizes the iterative algorithm through two state variables under explicit assumptions, including Gaussian posterior behavior and sparse-signal estimation from AWGN observations.
- The iterative algorithm’s performance is characterized by a recursion involving two state variables.
- The analysis defines the MMSE for sparse-signal estimation from an AWGN observation with signal-to-noise ratio η.
- The state-evolution proposition applies under Assumptions 1–3.
- The proposed algorithm’s state evolution is derived by combining the module update equations with the posterior and prior relations.
B. Fixed Point of State Evolution
At convergence, the state evolution reduces to a fixed-point equation whose valid solution is consistent with the replica-method result.
- The convergence value η⋆ is characterized by a fixed-point equation obtained by combining the two state recursions and eliminating v.
- The fixed-point equation has two solutions, but only one is a valid convergence point.
- The fixed-point result is consistent with the corresponding expression derived using the replica method.
IV. NUMERICAL EXAMPLES
The proposed algorithm converges faster and reaches lower MSE than AMP in the reported comparison, while its state evolution agrees well with simulation. At a lower measurement ratio, AMP with partial DFT performs much worse than the proposed algorithm.
- The proposed algorithm converges faster than AMP and achieves lower convergence MSE in the reported comparison.MSE is averaged over 2000 realizations, and AMP uses i.i.d. Gaussian entries normalized to variance 1/N.
- The state evolution analysis agrees well with simulation for the proposed algorithm.
- At M/N ≈ 0.55, AMP with a partial DFT matrix performs much worse than the proposed algorithm.The setup uses N = 32768, M = 18022, λ = 0.4, and SNR = 50 dB.
V. CONCLUSION AND DISCUSSIONS
The state evolution is based on three assumptions and is supported by accurate numerical results, while rigorous justification remains an open future research topic.
- The proposed state evolution is developed under three assumptions.
- Numerical results demonstrate that the state evolution developed from these assumptions is accurate.
- Establishing more rigorous justifications for the state evolution is identified as future research.