TY - GEN
T1 - A Fast and Robust Paradigm for Fourier Compressed Sensing Based on Coded Sampling
AU - Ong, Frank
AU - Heckel, Reinhard
AU - Ramchandran, Kannan
N1 - Publisher Copyright:
© 2019 IEEE.
PY - 2019/5
Y1 - 2019/5
N2 - 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.
AB - 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.
KW - Coded sampling
KW - Compressed sensing
KW - FFAST
KW - LASSO
KW - MRI
UR - http://www.scopus.com/inward/record.url?scp=85068985147&partnerID=8YFLogxK
U2 - 10.1109/ICASSP.2019.8682063
DO - 10.1109/ICASSP.2019.8682063
M3 - Conference contribution
AN - SCOPUS:85068985147
T3 - ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings
SP - 5117
EP - 5121
BT - 2019 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019 - Proceedings
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 44th IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP 2019
Y2 - 12 May 2019 through 17 May 2019
ER -