Compressed Sensing: A negative result, cross validation in CS via JL, a new deterministic construction, GRIP, Exploiting channel sparsity, CISS 08

Here is a new batch from the Rice repository. I am listing only those that I have not covered before. First, a somewhat bad news for some deterministic constructions of measurement matrices such as the contruction of Radu Berinde and Piotr Indyk or this one. Venkat Chandar came up with A negative result concerning explicit matrices with the restricted isometry property. The abstract reads:

In this note, we prove that matrices whose entries are all 0 or 1 cannot achieve good performance with respect to the Restricted Isometry Property (RIP). Most currently known deterministic constructions of matrices satisfying the RIP fall into this category, and hence these constructions suffer inherent limitations. In particular, we show that DeVore’s construction of matrices satisfying the RIP is close to optimal once we add the constraint that all entries of the matrix are 0 or 1.

A paper by Rachel Ward on Cross validation in compressed sensing via the Johnson Lindenstrauss lemma takes aim at providing sharp bounds for iterative reconstruction algorithms.

Compressed Sensing decoding algorithms aim to reconstruct an unknown N dimensional vector x from m less than N given measurements y = x, with an assumed sparsity constraint on x. All algorithms presently are iterative in nature, producing a sequence of approximations (s1, s2, ...) until a certain algorithm-specific stopping criterion is reached at iteration j, at which point the estimate ˆx = sj is returned as an approximation to x. In many algorithms, the error ||x−ˆx||lN2 of the approximation is bounded above by a function of the error between x and the best k-term approximation to x. However, as x is unknown, such estimates provide no numerical bounds on the error. In this paper, we demonstrate that tight numerical upper and lower bounds on the error ||x − sj ||lN2 for j  p iterations of a compressed sensing decoding algorithm are attainable with little effort. More precisely, we assume a maximum iteration length of p is pre-imposed; we reserve 4 log p of the original m measurements and compute the sj from the m − 4 log(p) remaining measurements; the errors ||x − sj ||lN2 , for j = 1, ..., p can then be bounded with high probability. As a consequence, a numerical upper bound on the error between x and the best k-term approximation to x can be estimated with almost no cost. Our observation has applications outside of Compressed Sensing as well.

We also have another deterministic construction of a measurement matrix by Stephen Howard, Robert Calderbank, and Stephen Searle in A fast reconstruction algorithm for deterministic compressive sensing using second order Reed-Muller codes. The abstract reads:

This paper proposes a deterministic compressed sensing matrix that comes by design with a very fast reconstruction algorithm, in the sense that its complexity depends only on the number of measurements n and not on the signal dimension N. The matrix construction is based on the second order Reed- Muller codes and associated functions. This matrix does not have RIP uniformly with respect to all k-sparse vectors, but it acts as a near isometry on k-sparse vectors with very high probability.

There is a follow-on on GRIP by Jarvis Haupt, Robert Nowak . The technical report is entitled A generalized restricted isometry property. The abstract reads:

Compressive Sampling (CS) describes a method for reconstructing high-dimensional sparse signals from a small number of linear measurements. Fundamental to the success of CS is the existence of special measurement matrices which satisfy the so-called Restricted Isometry Property (RIP). In essence, a matrix satisfying RIP is such that the lengths of all sufficiently sparse vectors are approximately preserved under transformation by the matrix. In this paper we describe a natural consequence of this property – if a matrix satisfies RIP, then acute angles between sparse vectors are also approximately preserved. We formulate this property as a Generalized Restricted Isometry Property (GRIP) and describe one application in robust signal detection.

Finally, the paper by Georg Taubock and Franz Hlawatsch is out. It is entitled A compressed sensing technique for OFDM channel estimation in mobile environments: Exploiting channel sparsity for reducing pilots. The abstract reads:

We consider the estimation of doubly selective wireless channels within pulse-shaping multicarrier systems (which include OFDM systems as a special case). A new channel estimation technique using the recent methodology of compressed sensing (CS) is proposed. CS-based channel estimation exploits a channel’s delay-Doppler sparsity to reduce the number of pilots and, hence, increase spectral efficiency. Simulation results demonstrate a significant reduction of the number of pilots relative to least-squares channel estimation.

At Princeton, the Conference on Information Sciences and Systems will take place March 19 through 21. It has been added to the Calendar. We have already seen some preprints but there are new papers as well. From the abstract list, the talks relevant to Compressed Sensing are:

Wednesday, March 19, 8:30am- 11:45am Session (with a break 10:00am -10:15am)

(INVITED SESSION)
WA-01 - Sparse Representations and Frames I: Compressed Sensing

Iteratively Re-weighted Least Squares Minimization: Proof of Faster than Linear Rate for Sparse Recovery
Daubechies, Ingrid, Princeton University (687)
DeVore, Ronald, University of South Carolina (688)
Fornasier, Massimo, Courant Institute of Mathematical Sciences (689)
Gunturk, Sinan, Johann Randon Institute for Computational and Applied Mathematics (690)

1-Bit Compressive Sensing (287)
Boufounos, Petros T., Rice University (665)
Baraniuk, Richard G., Rice University (666)

The Dantzig Selector and Generalized Thresholding (290)
Romberg, Justin, Georgia Tech (684)

Compressed Channel Sensing (264)
Bajwa, Waheed U., University of Wisconsin-Madison (610)
Haupt, Jarvis D., University of Wisconsin-Madison (611)
Raz, Gil M., GMR Research and Technology (612)
Nowak, Robert D., University of Wisconsin-Madison (613)

Noisy Compressive Sampling Limits in Linear and Sublinear Regimes (233)
Akcakaya, Mehmet, Harvard University (541)
Tarokh, Vahid, Harvard University (542)

A fast reconstruction algorithm for deterministic compressed sensing using second order Reed Muller codes (270)
Howard, Stephen, Defence Science and Technology Organisation, Australia (629)
Calderbank, Robert, Princeton University (630)
Searle, Stephen, University of Melbourne (631)


Thursday, March 20
8:30am- 11:45am Session (with a break 10:00am -10:15am)
TA-01 - Compressed Sensing I

On the frequency resolution of empirical mode decomposition (20)
Roy, Arnab, Pennsylvania State University (41)
Doherty, John F., Pennsylvania State University (42)

Improved Bounds for a Deterministic Sublinear-Time Sparse Fourier Algorithm (72)
Iwen, Mark A., University of Michigan, Ann Arbor (156)
Spencer, Craig V., University of Michigan, Ann Arbor (157)

An adaptive implementation of reference levels in Level-Crossing Analog-to-Digital Converters (116)
Guan, Karen M., University of Illinois at Urbana and Champaign (261)
Singer, Andrew C., University of Illinois at Urbana and Champaign (262)

Sparse Weighted Euclidean Superimposed Coding for Integer Compressed Sensing (158)
Dai, Wei, University of Illinois at Urbana and Champaign (366)
Milenkovic, Olgica, University of Illinois at Urbana and Champaign (367)

Reconstruction of compressively sensed images via neurally plausible local competitive algorithms (159)
Ortman, Robert L., Rice University (368)
Rozell, Christopher J., University of California, Berkeley (369)
Johnson, Don H., Rice University (370)

Sparse Weighted Euclidean Superimposed Coding for Integer Compressed Sensing (253)
Dai, Wei, University of Illinois at Urbana and Cha (588)
Milenkovic, Olgica, University of Illinois at Urbana and Cha (589)


Friday, March 21
8:30am- 11:45am Session (with a break 10:00am -10:15am)

FA-02 - Compressed Sensing II

Unsupervised distributional anomaly detection for a self-diagnostic speech activity detector (77)
Borges, Nash M., Johns Hopkins University (169)
Meyer, Gerard G., Johns Hopkins University (170)

Compressive Sensing Detection of Stochastic Signals (97)
Vila-Forcen, Jose-Emilio, Universidad Carlos III de Madrid (217)
Artes-Rodriguez, Antonio, Universidad Carlos III de Madrid (218)
Garcia-Frias, Javier, University of Delaware (219)

A Measure of Interference in Sparse Atomic Estimations (105)
Sturm, Bob L., University of California (238)
Shynk, John J., University of California (239)
Laurent, Daudet, University Pierre and Marie Curie (286)

On empirical capacity, random coding bound, and probability of outage of an object recognition system under constraint of PCA-encoding (186)
Chen, Xiaohan, West Virginia University (432)
Schmid, Natalia A., West Virginia University (433)


Image Credit: NASA/JPL/Space Science Institute, Photo of Enceladus taken the day before yesterday by Cassini.