Hello, and welcome to Paper of the Day (Po’D): Sparse signal detection from incoherent projections Edition. Today’s paper provides an interesting view on whether one needs to reconstruct a compressively sensed (CS) signal before one can say anything about it: M. F. Duarte, M. A. Davenport, M. B. Waking and R. G. Baraniuk, “Sparse signal detection from incoherent projections,” Proc. ICASSP, 2006.

One thing I really like about this paper is that of its 14 references, 8 are “preprints”, and another one is presented at the same conference. That shows timely work!

My one line summary of this paper is:

Non-adaptive sensing by random projection onto a low dimensional subspace might kill the recovery of the underlying signal, but it need not keep us from saying something useful about its composition.

Consider that we have compressively sensed a signal which may or may not contain a particular code from our alphabet, embedded in interference and noise.

Given we have a dictionary containing our alphabet, and a dictionary that can sparsely describe the interference, and considering that the two are incoherent,

and considering that the noise is not sparsely described by either of them,

then we can detect the presence of a code from the alphabet from far fewer measurements than required to guarantee perfect recovery.

What is more, the detection can be accomplished by a low complexity algorithm like the plain pure greedy algorithm matching pursuit.

In this paper, the authors experimentally show excellent performance for a signal alphabet of chirps, a Fourier subdictionary sparsely describing the narrowband interference,

and varying amounts of AWGN. (An analysis of this approach is given in M. A. Davenport, M. B. Waking and R. G. Baraniuk, “Detection and estimation with compressive measurements”, Tech. Rep., Rice University, 2006.)

Of course, there is no reason to believe that we can improve detection performance by projecting a signal onto a low-dimensional space.

We are losing information, which is most dramatic when the signal cannot be recovered by, e.g., \(\ell_1\) minimization.

When we use MP with CS, we are attempting to solve in a serial fashion

$$

\min \|\vx\|_0 \; \textrm{subject to} \; \vy = \MPhi [\MPsi | \MF ]\vx

$$

where \(\MPhi\) is the sensing matrix,

\(\MPsi\) is our alphabet,

and \(\MF\) is the Fourier basis describing the interference.

Instead of flirting with disaster, we might as well just perform MP in the original signal space using the dictionary \([\MPsi | \MF ]\).

But where this approach comes in handy is when acquisition is expensive.

The authors mention in the conclusion the possibility of estimating the parameters of a sparse signal decomposition from the compressive measurements.

However, as the paper in this Po’D shows (which I hear is now accepted for publication), parameter estimation by CS, no matter the sensing matrix, performs no better than just picking off the first \(M\) samples of the original signal.