Natural Thresholding Algorithms for Signal Recovery With Sparsity

You are here

Top Reasons to Join SPS Today!

1. IEEE Signal Processing Magazine
2. Signal Processing Digital Library*
3. Inside Signal Processing Newsletter
4. SPS Resource Center
5. Career advancement & recognition
6. Discounts on conferences and publications
7. Professional networking
8. Communities for students, young professionals, and women
9. Volunteer opportunities
10. Coming soon! PDH/CEU credits
Click here to learn more.

Natural Thresholding Algorithms for Signal Recovery With Sparsity

Yun-Bin Zhao; Zhi-Quan Luo

The algorithms based on the technique of optimal k -thresholding (OT) were recently proposed for signal recovery, and they are very different from the traditional family of hard thresholding methods. However, the computational cost for OT-based algorithms remains high at the current stage of their development. This stimulates the development of the so-called natural thresholding (NT) algorithm and its variants in this paper. The family of NT algorithms is developed through the first-order approximation of the so-called regularized optimal k -thresholding model, and thus the computational cost for this family of algorithms is significantly lower than that of the OT-based algorithms. The guaranteed performance of NT-type algorithms for signal recovery from noisy measurements is shown under the restricted isometry property and concavity of the objective function of regularized optimal k -thresholding model. Empirical results indicate that the NT-type algorithms are robust and very comparable to several mainstream algorithms for sparse signal recovery.

Under the sparsity assumption, the problem of signal recovery from nonadaptive linear measurements can be formulated as a sparse optimization problem which may take different forms, depending on such factors as recovery environment, signal structure, and the prior information available for the signal [1][2]. A fundamental mathematical model for sparsity-based signal recovery can be described as follows. Let  A  be an  m×n  sensing matrix with  mn,  and let  y:=Ax+νRm  be the measurements for the signal  xRn , where  νRm  are the measurement errors. When  x  is  k -sparse or  k -compressible, the recovery of  x  can be formulated as the following sparsity-constrained optimization (SCO) problem:

SPS on Twitter

  • New SPS Webinar: On Wednesday, 8 February, join Dr. Roula Nassif for "Decentralized learning over multitask graphs"…
  • CALL FOR PAPERS: IEEE Signal Processing Magazine welcomes submissions for a Special Issue on Hypercomplex Signal an…
  • New SPS Webinar: On 15 February, join Mr. Wei Liu, Dr. Li Chen and Dr. Wenyi Zhang presenting "Decentralized Federa…
  • New SPS Webinar: On Monday, 13 February, join Dr. Joe (Zhou) Ren when he presents "Human Centric Visual Analysis -…
  • Help us illustrate the SPS story! In honor of our 75th anniversary, we need your support to capture the people, mem…

SPS Videos

Signal Processing in Home Assistants


Multimedia Forensics

Careers in Signal Processing             


Under the Radar