A Fast and Robust Paradigm for Fourier Compressed Sensing Based on Coded Sampling

Frank Ong, Reinhard Heckel, Kannan Ramchandran

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

8 Scopus citations

Abstract

First-order gradient methods are commonly used for compressed sensing reconstruction. However, for Fourier sampling systems, they require computing a large number of fast Fourier transforms (FFTs), which can be expensive in real-time applications. In this paper, instead of random sub-sampling, we use a sampling scheme inspired by coding theory from a recent sparse-FFT work of Pawar and Ramchandran [1]. In particular, we show that Iterative Soft Thresholding Algorithm (ISTA) applied on the Least Absolute Shrinkage and Selection Operator (LASSO) with the coded sampling provides an O(log n) per-iteration speedup over the standard iteration cost, where n is the signal length. Since the coded sampling operation deviates from the common randomized compressed sensing sampling, it is a priori unclear whether LASSO can recover sparse signals. We provide recovery guarantees for LASSO using the coded sampling guaranteed for an arbitrary signal-to-noise ratio. For a k-sparse signal and under a uniformly random sparsity model, we show that LASSO recovers the underlying signal from O(k log4 n) measurements through the coded sensing system, with a reconstruction error that is proportional to the sparsity level and noise energy. Moreover, we demonstrate numerically computational speedups for using this scheme as well as lower MRI acquisition times.

Original languageEnglish
Title of host publication2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages5117-5121
Number of pages5
ISBN (Electronic)9781479981311
DOIs
StatePublished - May 2019
Externally publishedYes
Event44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Brighton, United Kingdom
Duration: 12 May 201917 May 2019

Publication series

NameICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
Volume2019-May
ISSN (Print)1520-6149

Conference

Conference44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
Country/TerritoryUnited Kingdom
CityBrighton
Period12/05/1917/05/19

Keywords

  • Coded sampling
  • Compressed sensing
  • FFAST
  • LASSO
  • MRI

Fingerprint

Dive into the research topics of 'A Fast and Robust Paradigm for Fourier Compressed Sensing Based on Coded Sampling'. Together they form a unique fingerprint.

Cite this