Randomized iterative hard thresholding for sparse approximations

Robert Crandall, Bin Dong, Ali Bilgin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


Typical greedy algorithms for sparse reconstruction problems, such as orthogonal matching pursuit and iterative thresholding, seek strictly sparse solutions. Recent work in the literature suggests that given a priori knowledge of the distribution of the sparse signal coefficients, better results can be obtained by a weighted averaging of several sparse solutions. Such a combination of solutions, while not strictly sparse, approximates an MMSE estimator and can outperform strictly sparse solvers in terms of l-2 reconstruction error. We introduce a novel method for obtaining such an approximate MMSE estimator by replacing the deterministic thresholding operator of Iterative Hard Thresholding with a randomized version. We demonstrate the improvement in performance experimentally for both synthetic 1D signals and real images.

Original languageEnglish (US)
Title of host publicationProceedings - DCC 2014
Subtitle of host publication2014 Data Compression Conference
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages1
ISBN (Print)9781479938827
StatePublished - 2014
Event2014 Data Compression Conference, DCC 2014 - Snowbird, UT, United States
Duration: Mar 26 2014Mar 28 2014

Publication series

NameData Compression Conference Proceedings
ISSN (Print)1068-0314


Other2014 Data Compression Conference, DCC 2014
Country/TerritoryUnited States
CitySnowbird, UT

ASJC Scopus subject areas

  • Computer Networks and Communications

Cite this