Thursday, January 24, 2008

Compressed Sensing: SSP 2007, Some papers and posters and the ICASSP 2008 Abstracts

I found the following papers and posters on the Compressed Sensing subject at the 2007 IEEE Statistical Signal Processing Workshop. I know it is a little late but I have not seen some of them on the Rice Repository yet. It took place at the end of August 2007.

Sparse MRI Reconstruction via Multiscale L0-Continuation by Joshua Trzasko, Armando Manduca, Eric Borisch. The abstract reads:
Compressed Sensing” and related L1-minimization methods for reconstructing sparse magnetic resonance images (MRI) acquired at sub-Nyquist rates have shown great potential for dramatically reducing exam duration. Nonetheless, the nontriviality of numerical implementation and computational intensity of these reconstruction algorithms has thus far precluded their widespread use in clinical practice. In this work, we propose a novel MRI reconstruction framework based on homotopy continuation of the L0 semi-norm using redescending M-estimator functions. Following analysis of the continuation scheme, the sparsity measure is extended to multiscale form and a simple numerical solver that can achieve accurate reconstructions in a matter of seconds on a standard desktop computer is presented.
Differences between Observation and Sampling Error in Sparse Signal Reconstruction by Galen Reeves, Michael Gastpar. The abstract reads:
The field of Compressed Sensing has shown that a relatively small number of random projections provide sufficient information to accurately reconstruct sparse signals. Inspired by applications in sensor networks in which each sensor is likely to observe a noisy version of a sparse signal and subsequently add sampling error through computation and communication, we investigate how the distortion differs depending on whether noise is introduced before sampling (observation error) or after sampling (sampling error). We analyze the optimal linear estimator (for known support) and an $\ell_1$ constrained linear inverse (for unknown support). In both cases, observation noise is shown to be less detrimental than sampling noise and low sampling rates. We also provide sampling bounds for a non-stochastic $\ell_\infty$ bounded noise model.
Previously it was mentioned that EEG signals were interesting for CS because of their sparsity. Selin Aviyente made a similar finding (Sparse Representation for Signal Classification Ke Huang and Selin Aviyente) and continued her investigation by looking at an implementation of Compressed Sensing for EEG signals in
Compressed Sensing Framework for EEG Compression by Selin Aviyente. The abstract reads:
Many applications in signal processing require the efficient representation and processing of data. The traditional approach to efficient signal representation is compression. In recent years, there has been a new approach to compression at the sensing level. Compressed sensing (CS) is an emerging field which is based on the revelation that a small collection of linear projections of a sparse signal contains enough information for reconstruction. In this paper, we propose an application of compressed sensing in the field of biomedical signal processing, particularly electro-encophelogram (EEG) collection and storage. A compressed sensing framework is introduced for efficient representation of multichannel, multiple trial EEG data. The proposed framework is based on the revelation that EEG signals are sparse in a Gabor frame. The sparsity of EEG signals in a Gabor frame is utilized for compressed sensing of these signals. A simultaneous orthogonal matching pursuit algorithm is shown to be effective in the joint recovery of the original multiple trail EEG signals from a small number of projections.

DNA Array Decoding from Nonlinear Measurements by Belief Propagation by Mona Sheikh, Shriram Sarvotham, Olgica Milenkovic, Richard Baraniuk. The abstract reads:
We propose a signal recovery method using Belief Propagation (BP) for nonlinear Compressed Sensing (CS) and demonstrate its utility in DNA array decoding. In a CS DNA microarray, the array spots identify DNA sequences that are shared between multiple organisms, thereby reducing the number of spots required in a traditional DNA array. The sparsity in DNA sequence commonality between different organisms translates to conditions that render Belief Propagation (BP) ideal for signal decoding. However a high concentration of target molecules has a nonlinear effect on the measurements - it causes saturation in the spot intensities. We propose a tailored BP technique to estimate the target signal in spite of the nonlinearity and show that the original signal coefficients can be recovered from saturated values of their linear combinations.
Related report/papers from the Rice repository are: Compressed Sensing DNA Microarrays and DNA array decoding from nonlinear measurements by belief propagation


Rate-Distortion Bounds for Sparse Approximation by Alyson Fletcher, Sundeep Rangan, Vivek Goyal. The abstract reads:
Sparse signal models arise commonly in audio and image processing. Recent work in the area of compressed sensing has provided estimates of the performance of certain widely-used sparse signal processing techniques such as basis pursuit and matching pursuit. However, the optimal achievable performance with sparse signal approximation remains unknown. This paper provides bounds on the ability to estimate a sparse signal in noise. Specifically, we show that there is a critical minimum signal-to-noise ratio (SNR) that is required for reliable detection of the sparsity pattern of the signal. We furthermore relate this critical SNR to the asymptotic mean squared error of the maximum likelihood estimate of a sparse signal in additive Gaussian noise. The critical SNR is a simple function of the problem dimensions.


Differences between Observation and Sampling Error in Sparse Signal Reconstruction by G. Reeves and M. Gastpar. The abstract reads:
The field of Compressed Sensing has shown that a relatively small number of random projections provide sufficient information to accurately reconstruct sparse signals. Inspired by applications in sensor networks in which each sensor is likely to observe a noisy version of a sparse signal and subsequently add sampling error through computation and communication, we investigate how the distortion differs depending on whether noise is introduced before sampling (observation error) or after sampling (sampling error). We analyze the optimal linear estimator (for known support) and an $\ell_1$ constrained linear inverse (for unknown support). In both cases, observation noise is shown to be less detrimental than sampling noise and low sampling rates. We also provide sampling bounds for a non-stochastic $\ell_\infty$ bounded noise model.

Variable Projection and Unfolding in Compressed Sensing by Joel Goodman, Benjamin Miller, Gil Raz, Andrew Bolstad. The abstract reads:
The performance of linear programming techniques that are applied in the signal identification and reconstruction process in compressed sensing (CS) is governed by both the number of measurements taken and the number of non-zero coefficients in the discrete orthormal basis used to represent the signal. To enhance the capabilities of CS, we have developed a technique called Variable Projection and Unfolding (VPU) to extend the identification and reconstruction capability of linear programming techniques to signals with a much greater number of non-zero coefficients in the orthonormal basis in which the signals are best compressible.
Some details of this study can be found in this report entitled Analog-to-Information Study Phase
with the following abstract:
Many communications and Radar receivers must process data over a very wide band, which requires either high-rate analog-to-digital converters (ADCs) or multichannel receivers. The information content of that wideband data, however, is often sparse in some basis. Analog-to-Information (A2I) receivers exploit this sparseness in both the digital and analog domains by non-adaptively spreading the signal energy (analog) and using digital signal processing to recover the signal from an ADC sampling at a sub-Nyquist rate. A subsampled ADC implies the use of fewer receiver channels or less expensive, lower- rate devices. This report documents the signal processing techniques for such receivers developed by the MIT Lincoln Laboratory/GMR Research and Technology team in the study phase of the A2I program. We have developed two new A2I signal processing methods, both significantly outperforming compressed sensing (CS) techniques currently in the literature, which typically fail when signals occupy more than 15-20% of the downsampled band. One of our methods, Nonlinear Affine processing (NoLaff), uses a nonlinear front-end to spread signal energy before the sub-Nyquist ADC, and uses hypothesis testing to reconstruct the signal. In simulations, this technique has shown that it can reconstruct wideband signals occupying up to 72% of the downsampled basis, It is also much less sensitive to the difficulties CS has detecting signals with large magnitude variation in the compressible basis. Our other method, called Variable Projection and Unfolding (VPU), spreads the signal energy using random linear projections similar to those used in compressed sensing, but is able to reconstruct signals occupying nearly 100% of the downsampled basis. VPU achieves this using a technique similar to matching pursuit; the key difference being that VPU searches over blocks of consecutive columns rather than one column at a time.
So in short the VPU is a greedy algorithm.


Colored Random Projections for Compressed Sensing by Zhongmin Wang; Arce, G.R.; Paredes, J.L. The abstract reads:
The emerging theory of compressed sensing (CS) has led to the remarkable result that signals having a sparse representation in some known basis can be represented (with high probability) by a small sample set, taken from random projections of the signal. Notably, this sample set can be smaller than that required by the ubiquitous Nyquist sampling theorem. Much like the generalized Nyquist sampling theorem dictates that the sampling rate can be further reduced for the representation of bandlimited signals, this paper points to similar results for the sampling density in CS. In particular, it is shown that if additional spectral information of the underlying sparse signals is known, colored random projections can be used in CS in order to further reduce the number of measurements needed. Such a priori information is often available in signal processing applications and communications. Algorithms to design colored random projection vectors are developed. Further, an adaptive CS sampling method is developed for applications where non-uniform spectral characteristics of the signal are expected but are not known a priori.

Compressed Sensing for Wideband Cognitive Radios by Zhi Tian and Giannakis, G.B. The Abstract reads:
In the emerging paradigm of open spectrum access, cognitive radios dynamically sense the radio-spectrum environment and must rapidly tune their transmitter parameters to efficiently utilize the available spectrum. The unprecedented radio agility envisioned, calls for fast and accurate spectrum sensing over a wide bandwidth, which challenges traditional spectral estimation methods typically operating at or above Nyquist rates. Capitalizing on the sparseness of the signal spectrum in open-access networks, this paper develops compressed sensing techniques tailored for the coarse sensing task of spectrum hole identification. Sub-Nyquist rate samples are utilized to detect and classify frequency bands via a wavelet-based edge detector. Because spectrum location estimation takes priority over fine-scale signal reconstruction, the proposed novel sensing algorithms are robust to noise and can afford reduced sampling rates.

Laurent Duval mentioned to me that ICASSP 2008 will take place in Las Vegas and will feature three sessions on Compressed Sensing. Hopefully what will happen in Vegas will not stay in Vegas :-). I note the first Show and Tell Presentation session that is supposed to draw a large crowd. The deadline for proposing one of these show and tell presentation is February 1st, I am sure that a good presentation on dramatic improvement related to Compressed Sensing would go a long way toward making people think how it could be used in their own field. An enterprising student might even make a name for her/himself doing that. Here is the list of abstracts from the three sessions.

SS-1: Compressed Sensing I


Session Type: Special Lecture
Time: Tuesday, April 1, 10:30 - 12:30
Location: Lecture Room 1

SS-1.1: COMPRESSIVE SENSING ON A CMOS SEPARABLE TRANSFORM IMAGE SENSOR
;
Ryan Robucci; Georgia Institue of Technology
Leung Kin Chiu; Georgia Institue of Technology
Jordan Gray; Georgia Institue of Technology
Justin Romberg; Georgia Institue of Technology
Paul Hasler; Georgia Institue of Technology
David Anderson; Georgia Institue of Technology

SS-1.2: COMPUTING PERFORMANCE GUARANTEES FOR COMPRESSED SENSING
Kiryung Lee; University of Illinois at Urbana-Champaign
Yoram Bresler; University of Illinois at Urbana-Champaign

SS-1.3: FINDING NEEDLES IN NOISY HAYSTACKS
Rui Castro; University of Wisconsin - Madison
Jarvis Haupt; University of Wisconsin - Madison
Robert Nowak; University of Wisconsin - Madison
Gil Raz; University of Wisconsin - Madison

SS-1.4: WAVELET-DOMAIN COMPRESSIVE SIGNAL RECONSTRUCTION USING A HIDDEN MARKOV TREE MODEL
Marco Duarte; Rice University
Michael Wakin; University of Michigan
Richard Baraniuk; Rice University

SS-1.5: DISTRIBUTED COMPRESSED SENSING: SPARSITY MODELS AND RECONSTRUCTION ALGORITHMS USING ANNIHILATING FILTER
Ali Hormati; Ecole Polytechnique Federale de Lausanne
Martin Vetterli; Ecole Polytechnique Federale de Lausanne

SS-1.6: ON THE UNIQUENESS OF NON-NEGATIVE SPARSE AND REDUNDANT REPRESENTATIONS
Alfred M. Bruckstein; The Computer-Science Department
Michael Elad; The Computer-Science Department
Michael Zibulevsky; The Computer-Science Department

SPTM-L5: Compressed Sensing II

Session Type: Lecture
Time: Friday, April 4, 09:30 - 11:30
Location: Lecture Room 4

SPTM-L5.1: COMPRESSED SENSING WITH SEQUENTIAL OBSERVATIONS
Dmitry Malioutov; MIT
Sujay Sanghavi; MIT
Alan Willsky; MIT

SPTM-L5.2: RECONSTRUCTING SPARSE SIGNALS FROM THEIR ZERO CROSSINGS
Petros Boufounos; Rice
Richard Baraniuk; Rice

SPTM-L5.3: SPECTRUM-BLIND RECONSTRUCTION OF MULTI-BAND SIGNALS
Moshe Mishali; Technion
Yonina Eldar; Technion

SPTM-L5.4: FAST COMPRESSIVE SAMPLING WITH STRUCTURALLY RANDOM MATRICES
Thong Do; The Johns Hopkins University
Trac Tran; The Johns Hopkins University
Gan Lu; University of Liverpool

SPTM-L5.5: SPARSE RECONSTRUCTION BY SEPARABLE APPROXIMATION
Stephen Wright; University of Wisconsin
Robert Nowak; University of Wisconsin
Mário Figueiredo; Instituto Superior Técnico

SPTM-L5.6: COMPRESSED SENSING - PROBABILISTIC ANALYSIS OF A NULL-SPACE CHARACTERIZATION
Mihailo Stojnic; California Institute of Technology
Weiyu Xu; California Institute of Technology
Babak Hassibi; California Institute of Technology

SPTM-P11: Compressed Sensing III

Session Type: Poster
Time: Friday, April 4, 13:00 - 15:00
Location: Poster Area 5

SPTM-P11.1: FUNDAMENTAL PERFORMANCE BOUNDS FOR A COMPRESSIVE SAMPLING SYSTEM
Anna Gilbert; University of Michigan
Martin Strauss; University of Michigan

SPTM-P11.2: COMPRESSED SIGNAL RECONSTRUCTION USING THE CORRENTROPY INDUCED METRIC
Sohan Seth; University of Florida
Jose C. Principe; University of Florida

SPTM-P11.3: APPROXIMATE LOWER BOUNDS FOR RATE-DISTORTION IN COMPRESSIVE SENSING SYSTEMS
Bernard Mulgrew; The University of Edinburgh
Michael Davies; The University of Edinburgh

SPTM-P11.4: EXPLICIT MEASUREMENTS WITH ALMOST OPTIMAL THRESHOLDS FOR COMPRESSED SENSING
Farzad Parvaresh; California Institute of Technology
Babak Hassibi; California Institute of Technology

SPTM-P11.5: COMPRESSED SENSING – A LOOK BEYOND LINEAR PROGRAMMING
Christian R. Berger; University of Connecticut
Javier Areta; University of Connecticut
Krishna Pattipati; University of Connecticut
Peter Willett; University of Connecticut

SPTM-P11.6: MIXED-SIGNAL PARALLEL COMPRESSED SENSING AND RECEPTION FOR COGNITIVE RADIO
Zhuizhuan Yu; Texas A&M University
Sebastian Hoyos; Texas A&M University
Brian M. Sadler; Army Research Laboratory

SPTM-P11.7: COMPRESSIVE SENSING AND WAVEFORM DESIGN FOR THE IDENTIFICATION OF LINEAR TIME-VARYING SYSTEMS
Jun Zhang; Arizona State University
Antonia Papandreou-Suppappola; Arizona State University

SPTM-P11.8: ITERATIVELY REWEIGHTED ALGORITHMS FOR COMPRESSIVE SENSING
Rick Chartrand; Los Alamos National Laboratory
Wotao Yin; Rice University

SPTM-P11.9: SUBSPACE COMPRESSIVE DETECTION FOR SPARSE SIGNALS
Zhongmin Wang; Uinversity of Delaware
Gonzalo R. Arce; Uinversity of Delaware
Brian M. Sadler; Army Research Laboratory

SPTM-P11.10: AVERAGE CASE ANALYSIS OF SPARSE RECOVERY WITH THRESHOLDING: NEW BOUNDS BASED ON AVERAGE DICTIONARY COHERENCE
Mohammad Golbabaee; Ecole Polytechnique Federale de Lausanne
Pierre Vandergheynst; Ecole Polytechnique Federale de Lausanne

SPTM-P11.11: COMPLEX-VALUED SPARSE REPRESENTATION BASED ON SMOOTHED L0 NORM
G. Hosein Mohimani; Electrical Engineering Department, Sharif University of Technology
Massoud Babaie-Zadeh; Electrical Engineering Department, Sharif University of Technology
Christian Jutten; Labratoire des Images et de Signaux (LIS), Institut National Polytechnique de Grenoble (INPG)

SPTM-P11.12: STABLE SPARSE APPROXIMATIONS VIA NONCONVEX OPTIMIZATION
Rayan Saab; The University of British Columbia
Rick Chartrand; Los Alamos National Laboratory
Ozgur Yilmaz; The University of British Columbia


Finally there is another talk but not in the Compressed Sensing
Session: SPCOM-P2: Channel Modeling and Estimation
Location: Poster Area 2
Time: Tuesday, April 1, 10:30 - 12:30
Presentation: Poster
Topic: Signal Processing for Communications and Networking: Signal Transmission and Reception
Title: A COMPRESSED SENSING TECHNIQUE FOR OFDM CHANNEL ESTIMATION IN MOBILE ENVIRONMENTS: EXPLOITING CHANNEL SPARSITY FOR REDUCING PILOTS

Authors: Georg Tauboeck, Franz Hlawatsch
Abstract: 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.


and two panels might be of relevance:
Tuesday, April 1

PANEL-1: Compressed Sensing, Sparse Signal Processing, Rate of Innovation, Real Field Coding, and Irregular Sampling
Organized by Farokh Marvasti

and

Wednesday, April 2

PANEL-2: Convex Optimization Theory and Practice in Signal Processing
Organized by Yonina Eldar

No comments:

Printfriendly