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.
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.
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.
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.
No comments:
Post a Comment