An efficient algorithm for compression-based compressed sensing
Abstract
Modern image and video compression codes employ elaborate structures in an effort to encode them using a small number of bits. Compressed sensing (CS) recovery algorithms, on the other hand, use such structures to recover the signals from a few linear observations. Despite the steady progress in the field of CS, the structures that are often used for signal recovery are still much simpler than those employed by state-of-the-art compression codes. The main goal of this paper is to bridge this gap by answering the following question: can one employ a compression code to build an efficient (polynomial time) CS recovery algorithm? In response to this question, the compression-based gradient descent (C-GD) algorithm is proposed. C-GD, which is a low-complexity iterative algorithm, is able to employ a generic compression code for CS and therefore enlarges the set of structures used in CS to those used by compression codes. Three theoretical contributions are provided: a convergence analysis of C-GD, a characterization of the required number of samples as a function of the rate-distortion function of the compression code and a robustness analysis of C-GD to additive white Gaussian noise and other non-idealities in the measurement process. Finally, the presented simulation results show that, in image CS, using compression codes such as JPEG2000, C-GD outperforms state-of-the-art methods, on average, by about $2$–$3$ dB in peak signal-to-noise ratio.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 11, 2018
- Source ID
- 10.1093/imaiai/iay014
Entities
People
- Arian Maleki
- Sajjad Beygi
- Shirin Jalali
- Urbashi Mitra
Organizations
- Air Force Office of Scientific Research
- Bell Labs
- California Department of Transportation
- Columbia University
- National Science Foundation
- Office of Naval Research
- University of Southern California