Skip to main content
Sparse Signal Reconstruction via ECME Hard Thresholding
IEEE Transactions on Signal Processing
  • Kun Qiu, Iowa State University
  • Aleksandar Dogandžić, Iowa State University
Document Type
Publication Date

We propose a probabilistic model for sparse signal reconstruction and develop several novel algorithms for computing the maximum likelihood (ML) parameter estimates under this model. The measurements follow an underdetermined linear model where the regression-coefficient vector is the sum of an unknown deterministic sparse signal component and a zero-mean white Gaussian component with an unknown variance. Our reconstruction schemes are based on an expectation-conditional maximization either (ECME) iteration that aims at maximizing the likelihood function with respect to the unknown parameters for a given signal sparsity level. Compared with the existing iterative hard thresholding (IHT) method, the ECME algorithm contains an additional multiplicative term and guarantees monotonic convergence for a wide range of sensing (regression) matrices. We propose a double overrelaxation (DORE) thresholding scheme for accelerating the ECME iteration. We prove that, under certain mild conditions, the ECME and DORE iterations converge to local maxima of the likelihood function. The ECME and DORE iterations can be implemented exactly in small-scale applications and for the important class of large-scale sensing operators with orthonormal rows used e.g., partial fast Fourier transform (FFT). If the signal sparsity level is unknown, we introduce an unconstrained sparsity selection (USS) criterion and a tuning-free automatic double overrelaxation (ADORE) thresholding method that employs USS to estimate the sparsity level. We compare the proposed and existing sparse signal reconstruction methods via one-dimensional simulation and two-dimensional image reconstruction experiments using simulated and real X-ray CT data.


This is a post-print of an article from IEEE Transactions on Signal Processing 60 (2012): 4551–4569, doi:10.1109/TSP.2012.2203818. Posted with permission.

© 2012 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Copyright Owner
Date Available
File Format
Citation Information
Kun Qiu and Aleksandar Dogandžić. "Sparse Signal Reconstruction via ECME Hard Thresholding" IEEE Transactions on Signal Processing Vol. 60 Iss. 9 (2012) p. 4551 - 4569
Available at: