Compressed Sensing: Reconstructing sparse signals from their zero crossings

In looking at the updates on the Rice site, I nearly missed this one from Petros Boufounos, Richard Baraniuk, Reconstructing sparse signals from their zero crossings. The abstract reads:

Classical sampling records the signal level at pre-determined time instances, usually uniformly spaced. An alternative implicit sampling model is to record the timing of pre-determined level crossings. Thus the signal dictates the sampling times but not the sampling levels. Logan’s theorem provides sufficient conditions for a signal to be recoverable, within a scaling factor, from only the timing of its zero crossings. Unfortunately, recovery from noisy observations of the timings is not robust and usually fails to reproduce the original signal. To make the reconstruction robust this paper introduces the additional assumption that the signal is sparse in some basis. We reformulate the reconstruction problem as a minimization of a sparsity inducing cost function on the unit sphere and provide an algorithm to compute the solution. While the problem is not convex, simulation studies indicate that the algorithm converges in typical cases and produces the correct solution with very high probability.

In the conclusion they mention:

In summary, formulating the problem of sparse signal reconstruction from zero crossings as a sparsity inducing optimization on the unit sphere stabilizes the reconstruction. This formulation can be extended beyond Fourier sparsity to accommodate other sparsity bases by appropriately modifying the sampling operator but the performance of such a modification needs to be evaluated. Furthermore, although the algorithm described provides the solution with high empirical probability, further research on reconstruction algorithms and their performance is necessary.

This is not unlike the result of Yves Meyer and Basarab Matei where using an additional constraint on the optimization (in the case of Meyer and Basarab, it's really a theorem), one seems to be able to retrieve full signal (in the case of Meyer and Basarab, it is proven).