Compressive Sensing Literature and More This Week

Much tweeting, blogging and literature this week. But first, Angshul Majumdar sent me the following:

Hi Igor

I have made some joint-sparse (MMV) reconstruction code available on Matlab Central. Here is the link

http://www.mathworks.com/matlabcentral/fileexchange/32020

It contains functions for constrained and unconstrained algorithms for analysis and synthesis prior. Currently, the functions are for convex problem, but can be easily extended to the non-convex case.

Hope you find it useful :)

Angshul Majumdar

Thanks Angshul.

Pierre Vandergheynst tweets from FOCM on CS related matters.

In the comment section of one recent entry, Bob let us know that he blogged during SPARS, here are the entries:

• SPARS 2011, day 4
• SPARS 2011, day 3
• SPARS 2011, day 2
• SPARS 2011

Looks like some good discussions took place there. Of interest, Bob is opening a new blog called Null Space Pursuits. The RSS feed is here.

Dirk Lorenz  wrote about Solving Basis Pursuit itself with ISAL1, while Rich Baraniuk points to some cool tee-shirts. Laurent Jacques pointed me to this paper:

On Variable Density Compressive Sampling by Gilles Puy, Pierre Vandergheynst, and Yves Wiaux. The abstract reads:

Incoherence between sparsity basis and sensing basis is an essential concept for compressive sampling. In this context, we advocate a coherence-driven optimization procedure for variable density sampling. The associated minimization problem is solved by use of convex optimization algorithms. We also propose a refinement of our technique when prior information is available on the signal support in the sparsity basis. The effectiveness of the method is confirmed by numerical experiments. Our results also provide a theoretical underpinning to state-of-the-art variable density Fourier sampling procedures used in magnetic resonance imaging.

While Tibault Reveyrand  tweeted about this ICASSP paper:

COMPRESSIVE TRACKING OF DOUBLY SELECTIVE CHANNELS IN MULTICARRIER SYSTEMS BASED ON SEQUENTIAL DELAY-DOPPLER SPARSITY  by Daniel Eiwen, Georg Taubock, Franz Hlawatsch, and Hans G. Feichtinger. The abstract reads:

We propose a compressive method for tracking doubly selective channels within multicarrier systems, including OFDMsystems. Using the recently introduced concept of modified compressed sensing (MOD-CS), the sequential delay-Doppler sparsity of the channel is exploited to improve estimation performance through a recursive estimation mode. The proposed compressive channel tracking algorithm uses a MOD-CS version of OMP with reduced complexity. Simulation results demonstrate substantial performance gains over

conventional compressive channel estimation.

I also found the following on the interweb:

Michael Elad's presentation at SPARS11: K-SVD Dictionary-Learning for Analysis Sparse Models (PPT version here). The abstract reads:

The synthesis-based sparse representation model for signals has drawn a considerable interest in the past decade. Such a model assumes that the signal of interest can be decomposed as a linear combination of a {\em few} atoms from a given dictionary. In this talk we concentrate on an alternative, analysis-based model, where an analysis operator -- hereafter referred to as the "Analysis Dictionary" - multiplies the signal, leading to a sparse outcome. Our goal is to learn the analysis dictionary from a set of signal examples, and the approach taken is parallel and similar to the one adopted by the K-SVD algorithm that serves the corresponding problem in the synthesis model. We present the development of the algorithm steps, which include a tailored pursuit algorithm termed "Backward Greedy" algorithm and a penalty function for the dictionary update stage. We demonstrate its effectiveness in several experiments, treating synthetic data and real images, showing a successful and meaningful recovery of the analysis dictionary.

It's a little old: Compressive multiple view projection incoherent holography by  Adi Stern,. The abstract reads:

This Letter presents a new approach for imaging using a linear (vector) sensor. It exploits the fact that visual information within common human intelligible images may be compressed within only a partial set of radial strips of its Fourier domain. We present two imaging schemes, one coherent and the other incoherent, that capture the partial set of radial strips of the object Fourier domain. Two main advantages of the new approach are that the image is captured directly in a compressed form and that the acquisition time is shorter compared with conventional scanning imaging systems.

From Arxiv:

Structured Compressed Sensing: From Theory to Applications by Marco Duarte, and Yonina Eldar. The abstract reads:

Compressed sensing (CS) is an emerging field that has attracted considerable research interest over the past few years. Previous review articles in CS limit their scope to standard discrete-to-discrete measurement architectures using matrices of randomized nature and signal models based on standard sparsity. In recent years, CS has worked its way into several new application areas. This, in turn, necessitates a fresh look on many of the basics of CS. The random matrix measurement operator must be replaced by more structured sensing architectures that correspond to the characteristics of feasible acquisition hardware. The standard sparsity prior has to be extended to include a much richer class of signals and to encode broader data models, including continuous-time signals. In our overview, the theme is exploiting signal and measurement structure in compressive sensing. The prime focus is bridging theory and practice; that is, to pinpoint the potential of structured CS strategies to emerge from the math to the hardware. Our summary highlights new directions as well as relations to more traditional CS, with the hope of serving both as a review to practitioners wanting to join this emerging field, and as a reference for researchers that attempts to put some of the existing ideas in perspective of practical applications.

Fast and Efficient Compressive Sensing using Structurally Random Matrices by Thong T. Do, Lu Gan, Nam H. Nguyen, Trac D. Tran. The abstract reads:

This paper introduces a new framework of fast and efficient sensing matrices for practical compressive sensing, called Structurally Random Matrix (SRM). In the proposed framework, we pre-randomize a sensing signal by scrambling its samples or flipping its sample signs and then fast-transform the randomized samples and finally, subsample the transform coefficients as the final sensing measurements. SRM is highly relevant for large-scale, real-time compressive sensing applications as it has fast computation and supports block-based processing. In addition, we can show that SRM has theoretical sensing performance comparable with that of completely random sensing matrices. Numerical simulation results verify the validity of the theory as well as illustrate the promising potentials of the proposed sensing framework

Coherence-Pattern Guided Compressive Sensing with Unresolved Grids by Albert Fannjiang, Wenjing Liao. The abstract reads:

Highly coherent sensing matrices arise in discretization of continuum imaging problems such as radar and medical imaging when the grid spacing is below the Rayleigh threshold. Algorithms based on techniques of band exclusion (BE) and local optimization (LO) are proposed to deal with such coherent sensing matrices. These techniques are embedded in the existing compressed sensing algorithms such as Orthogonal Matching Pursuit (OMP), Subspace Pursuit (SP), Iterative Hard Thresholding (IHT), Basis Pursuit (BP) and Lasso, and result in the modified algorithms BLOOMP, BLOSP, BLOIHT, BP-BLOT and Lasso-BLOT, respectively.

Under appropriate conditions, it is proved that BLOOMP can reconstruct sparse, widely separated objects up to one Rayleigh length in the Bottleneck distance {\em independent} of the grid spacing. One of the most distinguishing attributes of BLOOMP is its capability of dealing with large dynamic ranges.

The BLO-based algorithms are systematically tested with respect to four performance metrics: dynamic range, noise stability, sparsity and resolution. With respect to dynamic range and noise stability, BLOOMP is the best performer. With respect to sparsity, BLOOMP is the best performer for high dynamic range while for dynamic range near unity BP-BLOT and Lasso-BLOT with the optimized regularization parameter have the best performance. In the noiseless case, BP-BLOT has the highest resolving power up to certain dynamic range.

The algorithms BLOSP and BLOIHT are good alternatives to

BLOOMP and BP/Lasso-BLOT: they are faster than both BLOOMP and BP/Lasso-BLOT and shares, to a lesser degree, BLOOMP's amazing attribute with respect to dynamic range.

Detailed comparisons with existing algorithms such as Spectral Iterative Hard Thresholding (SIHT) and the frame-adapted BP are given.

Accelerated Linearized Bregman Method by Bo Huang, Shiqian Ma, Donald Goldfarb. The abstract reads:

In this paper, we propose and analyze an accelerated linearized Bregman (ALB) method for solving the basis pursuit and related sparse optimization problems. This accelerated algorithm is based on the fact that the linearized Bregman (LB) algorithm is equivalent to a gradient descent method applied to a certain dual formulation. We show that the LB method requires $O(1/\epsilon)$ iterations to obtain an $\epsilon$-optimal solution and the ALB algorithm reduces this iteration complexity to $O(1/\sqrt{\epsilon})$ while requiring almost the same computational effort on each iteration. Numerical results on compressed sensing and matrix completion problems are presented that demonstrate that the ALB method can be significantly faster than the LB method.

Signal Compression in Wireless Sensor Networks by Marco F. Duarte, Godwin Shen, Antonio Ortega, and Richard Baraniuk. The abstract reads:

Signal compression is an important tool for reducing the communication costs and increasing the lifetime of wireless sensor network deployments. In this paper, we overview and classify an array of proposed compression methods, with an emphasis on illustrating the differences between the various approaches.

Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent by Feng Niu, Benjamin Recht, Christopher R e and Stephen J. Wright. The abstract reads:

Stochastic Gradient Descent (SGD) is a popular algorithm that can achieve state-of-the-art performance on a variety of machine learning tasks. Several researchers have recently proposed schemes to parallelize SGD, but all require performance-destroying memory locking and synchronization. This work aims to show using novel theoretical analysis, algorithms, and implementation that SGD can be implemented without any locking. We present an update scheme called Hogwild! which allows processors access to shared memory with the possibility of over- writing each other's work. We show that when the associated optimization problem is sparse, meaning most gradient updates only modify small parts of the decision variable, then Hogwild! achieves a nearly optimal rate of convergence. We demonstrate experimentally that Hogwild! outperforms alternative schemes that use locking by an order of magnitude.

Asynchronous Code-Division Random Access Using Convex Optimization by Lorne Applebaum, Waheed U. Bajwa, Marco F. Duarte, and Robert Calderbank. The abstract reads:

Many applications in cellular systems and sensor networks involve a random subset of a large number of users asynchronously reporting activity to a base station. This paper examines the problem of multiuser detection (MUD) in random access channels for such applications. Traditional orthogonal signaling ignores the random nature of user activity in this problem and limits the total number of users to be on the order of the number of signal space dimensions. Contention-based schemes, on the other hand, suffer from delays caused by colliding transmissions and the hidden node problem. In contrast, this paper presents a novel pairing of an asynchronous non-orthogonal code-division random access scheme with a convex optimization-based MUD algorithm that overcomes the issues associated with orthogonal signaling and contention-based methods. Two key distinguishing features of the proposed MUD algorithm are that it does not require knowledge of the delay or channel state information of every user and it has polynomial-time computational complexity. The main analytical contribution of this paper is the relationship between the performance of the proposed MUD algorithm in the presence of arbitrary or random delays and two simple metrics of the set of user codewords. The study of these metrics is then focused on two specific sets of codewords, random binary codewords and specially constructed algebraic codewords, for asynchronous random access. The ensuing analysis confirms that the proposed scheme together with either of these two codeword sets significantly outperforms the orthogonal signaling-based random access in terms of the total number of users in the system

Image Credit: NASA/JPL/Space Science Institute
N00173225.jpg was taken on June 26, 2011 and received on Earth June 27, 2011. The camera was pointing toward TITAN at approximately 2,873,752 kilometers away, and the image was taken using the CL1 and CB3 filters.