Compressed Counting Meets Compressed Sensing
This work addresses compressed sensing for nonnegative signals, offering a computationally efficient method that is incremental in nature.
The paper tackles nonnegative signal recovery in compressed sensing by proposing a new framework using Compressed Counting, achieving recovery within additive precision with M=O(C/eps^p log N) measurements and requiring only one linear scan of coordinates.
Compressed sensing (sparse signal recovery) has been a popular and important research topic in recent years. By observing that natural signals are often nonnegative, we propose a new framework for nonnegative signal recovery using Compressed Counting (CC). CC is a technique built on maximally-skewed p-stable random projections originally developed for data stream computations. Our recovery procedure is computationally very efficient in that it requires only one linear scan of the coordinates. Our analysis demonstrates that, when 0<p<=0.5, it suffices to use M= O(C/eps^p log N) measurements so that all coordinates will be recovered within eps additive precision, in one scan of the coordinates. The constant C=1 when p->0 and C=pi/2 when p=0.5. In particular, when p->0 the required number of measurements is essentially M=K\log N, where K is the number of nonzero coordinates of the signal.