An efficient algorithm for compression-based compressed sensing

Understand

Modern image and video compression codes employ elaborate structures existing in such signals to encode them into few number of bits.

• Compressed sensing recovery algorithms on the other hand use such signals' structures to recover them from few linear observations.
• Despite the steady progress in the field of compressed sensing, 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 through answering the following question: Can one employ a given compression code to build an efficient (polynomial time) compressed sensing recovery algorithm? In response to this question, the compression-based gradient descent (C-GD) algorithm is proposed.