PaperlayerView exact revision on arXiv

Source-linked AI summary

A stochastic gradient approach on compressive sensing signal reconstruction based on adaptive filtering framework

Jian Jin, Yuantao Gu, Shunliang Mei

arXiv:1303.2257v1cs.IT

TL;DR

The paper addresses sparse-signal reconstruction from an ill-conditioned compressive sensing system, where selecting parameters and measurements theoretically remains unresolved. It applies stochastic-gradient adaptive filtering with zero-attraction methods, including l0-LMS, l0-EFWLMS, and l0-ZAP. The proposed l0-ZAP has lower computational complexity and stronger de-noising behavior, while the methods' convergence and reconstruction quality involve practical trade-offs.

  • Problem

    CS reconstruction requires finding a sparse solution to an ill-conditioned underdetermined system, while theoretical rules for selecting algorithm parameters and the measurement count remain unavailable.

  • Method

    The paper applies adaptive filtering with zero-attraction sparsity constraints and proposes l0-LMS, l0-EFWLMS, and solution-space projection algorithm l0-ZAP.

  • Results

    l0-ZAP has significantly lower computational complexity than l0-LMS and l0-EFWLMS, and its lower-dimensional projected representation supports de-noising performance.

  • Takeaways & Limitations

    The adaptive filtering framework provides a reconstruction approach that can trade convergence rate, reconstruction quality, memory, and computation across the proposed algorithms.

  • Takeaways & Limitations

    The paper leaves theoretical determination of the proposed algorithms' parameters and the required measurement count under RIP as open problems.

Abstract

from arXiv · show

Based on the methodological similarity between sparse signal reconstruction and system identification, a new approach for sparse signal reconstruction in compressive sensing (CS) is proposed in this paper. This approach employs a stochastic gradient-based adaptive filtering framework, which is commonly used in system identification, to solve the sparse signal reconstruction problem. Two typical algorithms for this problem: $l_0$-least mean square ($l_0$-LMS) algorithm and $l_0$-exponentially forgetting window LMS ($l_0$-EFWLMS) algorithm are hence introduced here. Both the algorithms utilize a zero attraction method, which has been implemented by minimizing a continuous approximation of $l_0$ norm of the studied signal. To improve the performances of these proposed algorithms, an $l_0$-zero attraction projection ($l_0$-ZAP) algorithm is also adopted, which has effectively accelerated their convergence rates, making them much faster than the other existing algorithms for this problem. Advantages of the proposed approach, such as its robustness against noise etc., are demonstrated by numerical experiments.

1 Introduction

Compressive sensing reconstructs sparse signals from few measurements, but finding the sparsest solution is difficult because the underlying problem is ill-conditioned and l0 optimization is computationally hard. This paper applies an adaptive filtering framework with l0-based sparsity constraints to develop faster reconstruction methods.

  • Compressive sensing problem: Compressive sensing aims to recover sparse signals from M measurements, where K ≤ M ≪ N, using a sensing matrix satisfying incoherence and RIP conditions.The paper notes that random Gaussian measurements can satisfy these conditions with high probability.
  • Compressive sensing problem: The reconstruction task is to find the sparsest solution of an underdetermined linear system, but l0 optimization is non-convex and NP-hard.Convex l1-based formulations and other approximations are therefore commonly used.
  • Related reconstruction methods: Existing approaches include convex optimization, non-convex lp methods, and greedy pursuits, each trading reconstruction quality, measurements, or computational cost.Greedy pursuits have complexity around O(KMN) but may require more measurements and fail to find the sparsest solution in some cases.
  • Proposed framework: The paper uses an adaptive filtering framework that processes each row of A per iteration and replaces the usual l1 constraint with a continuous approximation of the l0 norm.This is motivated by the similarity between sparse system identification and compressive sensing reconstruction.
  • Proposed framework: The proposed algorithms are l0-LMS and l0-EFWLMS, followed by l0-ZAP, which applies zero attraction in the solution space to accelerate convergence.The paper presents the adaptive filtering framework as a new approach for CS reconstruction and introduces l0-ZAP as an improved reconstruction algorithm.

2 Our Algorithms

The paper recasts CS reconstruction as sparse system identification and applies stochastic-gradient adaptive filtering with zero-attraction penalties. It introduces l0-LMS, l0-EFWLMS, and the projection-based l0-ZAP method, then compares their computational, denoising, implementation, and memory properties.

  • Adaptive filtering framework: CS reconstruction is formulated as an adaptive system-identification problem by matching adaptive-filter variables with the sensing matrix and measurements.Rows of A and corresponding elements of y are used recursively because the available data may not suffice for direct convergence.
  • l0-LMS: l0-LMS adds an l0-norm penalty to the LMS cost function, using a continuous approximation because direct l0 minimization is NP-hard.The resulting zero-attraction term pulls small coefficients toward zero and promotes sparse CS solutions.
  • l0-EFWLMS: l0-EFWLMS applies the same zero-attraction idea to exponentially forgetting window LMS to improve convergence performance for sparse unknown parameters.Its recursion combines the EFW-LMS update with the zero-attraction mechanism.
  • l0-ZAP: l0-ZAP initializes with the least-squares solution, iterates using zero attraction in the solution space, and projects the updated vector back onto that space.The method omits the gradient correction term during these iterations to accelerate convergence.
  • Discussion: l0-ZAP has lower per-period complexity and requires fewer periods than l0-LMS and l0-EFWLMS, yielding significantly lower overall computation complexity.The reported orderings are l0-ZAP < l0-LMS < l0-EFWLMS per period and l0-ZAP < l0-EFWLMS < l0-LMS in period count.
  • Discussion: l0-LMS and l0-EFWLMS have good denoising performance, while l0-ZAP also denoises effectively because the projected noise has lower power and smaller dimension.l0-ZAP is easier to control because it uses two parameters instead of the three required by the other methods, but it needs about twice their memory at large scale.
  • Discussion: The zero-attraction idea can also be adopted by other LMS variants, including normalized LMS, potentially combining sparsity promotion with NLMS robustness.The paper presents this as an extension beyond the two LMS-based algorithms developed here.

3 Convergence analysis

The convergence analysis derives the steady-state mean-square deviation of l0-LMS and a parameter condition intended to guarantee convergence. It also shows that κ trades reconstruction quality against convergence speed.

  • Theorem 1 derives the final steady-state mean-square deviation between the original and reconstructed signals for l0-LMS.
  • The convergence condition requires the step-size parameter to satisfy 0 < µ < 2M.
  • The steady-state deviation is proportional to κ and the measurement-noise power, so larger κ increases deviation.
  • Smaller κ weakens zero attraction and slows convergence, making κ a trade-off between convergence rate and reconstruction quality.
  • The derived upper bound is constant for a given signal and can serve as a rough criterion for parameter selection.

4 Experiment Results

Experiments compare the three proposed methods with established CS reconstruction algorithms across reconstruction quality, convergence, sparsity, measurement count, noise, and step-size. The proposed methods generally provide strong reconstruction performance, while l0-ZAP converges fastest and l0-EFWLMS achieves the smallest MSD under noise.

  • Experimental setup: The experiments compare l0-LMS, l0-EFWLMS, and l0-ZAP with BP, SpaRSA, GPSR-BB, FPC-AS, IRLS, and OMP.The sensing matrix uses independently generated Gaussian entries, and sparse-signal coefficients and supports are randomly generated.
  • Algorithm performance: All three proposed methods reconstruct the original signal; l0-EFWLMS has the smallest converged MSD, whereas l0-ZAP converges fastest with lower reconstruction quality.The comparison uses MSD as the convergence-performance measure.
  • Algorithm performance: The proposed three methods have the least MSD in the CPU-time comparison, and l0-ZAP is fastest among the listed algorithms.CPU time is used as a rough complexity index, based on ten runs in MATLAB 7.4.
  • Measurement number: With measurement numbers below 230, the other algorithms fail, whereas the proposed methods reconstruct exactly until M reaches 220.The measurement-number experiment uses M from 140 to 320 and 200 repetitions per value.
  • Robustness against noise: Across SNR values from 4dB to 32dB, the three proposed methods have smaller MSDs than traditional algorithms; l0-EFWLMS is best and l0-ZAP is worst among them.Each SNR condition is evaluated with 200 repetitions.
  • Effect of parameter µ: For l0-LMS, exact-reconstruction thresholds occur near µ = {0.4, 0.5, 0.6, 0.7, 0.8} for M = {200, 250, 300, 350, 400}, matching condition (51).The experiment uses α = 10, κ = 10^-6, 100 simulations per setting, and step-sizes from 0.3 to 1.1.

5 Conclusion

The conclusion presents adaptive filtering as a framework for compressive sensing reconstruction, introduces three zero-attraction algorithms, and reports favorable reconstruction and noise-robustness results. It also identifies missing theory for parameter selection and measurement requirements under RIP.

  • Contributions: The paper introduces an adaptive filtering framework for CS and proposes l0-LMS, l0-EFWLMS, and l0-ZAP.The first two use zero attraction, while l0-ZAP applies zero attraction in the solution space to accelerate convergence.
  • Conclusions: Compared with typical existing algorithms, the proposed methods reconstruct signals with more nonzero coefficients under a fixed measurement count.This is stated as a conclusion from the experimental comparisons.
  • Conclusions: Under fixed sparsity, the proposed methods require fewer measurements and are more robust against noise than the compared typical algorithms.The conclusion summarizes the measurement-number and noise experiments.
  • Limitations and future work: No theoretical result yet determines how to choose the proposed algorithms' parameters or how many measurements M are needed in the RIP context.The paper lists convergence analyses for l0-EFWLMS and l0-ZAP as future work.

Appendix A Proof of (41)

The appendix proof simplifies the steady-state analysis by using the Gaussian, independent structure of the sensing matrix and noise together with large-N approximations.

  • Assumptions: The proof assumes additive noise and a sensing matrix whose entries are independent Gaussian variables.The noise and measurement matrix are treated as independent, and the matrix entries follow a Gaussian distribution.
  • Approximation: For diagonal terms, the proof invokes the central limit theorem because N is very large in compressive sensing.This yields an approximate expression for the relevant quantity.
  • Simplification: The non-diagonal terms are handled similarly, allowing the preceding equation to be simplified.The proof separately addresses diagonal and non-diagonal components before combining them.

Appendix B Proof of Theorem 1

The appendix derives the l0-LMS steady-state mean-square result and a step-size condition for convergence using misalignment moments, input correlations, and trace-based expectations.

  • Moment analysis: The proof rewrites the analysis using a misalignment vector and its second-moment matrix.It then postmultiplies the recursion by its transpose and takes expectations under an independence assumption.
  • Statistical quantities: The input correlation matrix, minimum mean-squared estimation error, and trace operator define the quantities used in the mean-square derivation.The sensing matrix is modeled as i.i.d. Gaussian with mean zero and variance 1/M.
  • Convergence condition: The convergence analysis requires 0 < µ < 2M.This condition follows from the stated inequality used to guarantee convergence.
  • Steady-state result: The appendix obtains a final steady-state mean-square expression for the l0-LMS reconstruction error.The theorem statement identifies this quantity as the final mean-square derivation in steady state.
Loading 1303.2257v1…