DORE j'ADORE: Sparse signal reconstruction via ECME hard thresholding - implementation -

Kun Qiu just sent me the following:

Hi, Igor,

Hope everything is going well. The paper "Sparse signal reconstruction via ECME hard thresholding” by Aleksandar and myself appeared recently in IEEE Trans. Signal Processing, vol. 60, pp. 4551-4569, Sep. 2012. 

The ECME algorithm and its double overrelaxation (DORE) acceleration proposed in the paper solve the standard sparse signal reconstruction problem. The ECME algorithm is in essence an iterative hard thresholding (IHT) algorithm derived based on a probabilistic model. Compared to the existing IHT method, the ECME algorithm contains an additional multiplicative term which guarantees monotonic convergence for a wide range of sensing matrices, such as those with correlated rows. The DORE scheme significantly accelerates the ECME algorithm and I believe it is among the fastest sparse reconstruction methods. We also proposed in the paper an automatic DORE algorithm that can automatically select the sparsity from the data without manual tuning. 

The paper and the Matlab software package are posted at

http://home.eng.iastate.edu/~ald/ECME.html 

Could you help post the link to Nuit Blanche? 

Thanks, 

Kun

Sure Kun, do you think I am going to pass up a paper, an implementation and the possibility to do a play on words with Dior J'adore ? I don't think so. Here it is: Sparse signal reconstruction via ECME hard thresholding by Kun Qiu and Aleksandar Dogandžić. The abstract reads:

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 isunknown, 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.

The code is here.


Thanks Kun !


Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.