K. Qiu and A. Dogandžić
in Proc. 44th Annu. Conf. Inform. Sci. Syst., Princeton, NJ, Mar. 2010.
Abstract:
We propose double overrelaxation (DORE) and automatic double overrelaxation (ADORE) thresholding methods for sparse signal reconstruction. The measurements follow an underdetermined linear model, where the regression-coefficient vector is a sum of an unknown deterministic sparse signal component and a zero-mean white Gaussian component with an unknown variance. We first introduce an expectation-conditional maximization either (ECME) algorithm for estimating the sparse signal and variance of the random signal component and then describe our DORE thresholding scheme. The DORE scheme interleaves two successive overrelaxation steps and ECME steps, with goal to accelerate the convergence of the ECME algorithm. Both ECME and DORE algorithms aim at finding the maximum likelihood (ML) estimates of the unknown parameters assuming that the signal sparsity level is known. If the signal sparsity level is unknown, we propose an unconstrained sparsity selection (USS) criterion and show that, under certain conditions, maximizing the USS objective function with respect to the signal sparsity level is equivalent to finding the sparsest solution of the underlying underdetermined linear system. Our ADORE scheme demands no prior knowledge about the signal sparsity level and estimates this level by applying a golden-section search to maximize the USS objective function. We employ the proposed methods to reconstruct images from sparse tomographic projections and compare them with existing approaches that are feasible for large-scale data. Our numerical examples show that DORE is significantly faster than the ECME and related iterative hard thresholding (IHT) algorithms.
Full paper download:
(148 KB)
Detailed report on ArXiv:
(ECME thresholding methods for sparse signal reconstruction)
Matlab code:
The Matlab codes for the double overrelaxation (DORE) and automatic double overrelaxation (ADORE) thresholding methods proposed in the paper. All the simulation results reported in the above paper can be reproduced from the package. Please read the enclosed readme file as well. If you use this code in your research and publications, please refer to this paper. The package is only tested on PCs running Windows and should be able to run on other platforms if the appropriate wavelet toolbox is downloaded from the Rice wavelet toolbox .
(Version 1.0, last updated Mar. 5, 2010)
Follow-up work:
T. Blumensath has recently proposed an IHT version of DORE.