Compressed Sensing: Locally Competitive Algorithms for Sparse Encoding in the Brain.

If you recall there is an on-going concern, that one would want to map the current understanding in compressed sensing and biological processes of encoding information such as the primary visual cortex. I see Bruno Olshausen as being one of the first one to have influenced in some fashion our understanding that everything was sparse [1]. It is no surprise then that he and some of the Rice folks have gotten together and taken a stab at this issue on how sparse coding is happening in the brain. Christopher Rozell, Don Johnson, Rich Baraniuk and Bruno Olshausen have come out with a nice way to resolve that issue in Sparse Coding via Thresholding and Local Competition in Neural Circuits.

The abstract reads:

While evidence indicates that neural systems may be employing sparse approximations to represent sensed stimuli, the mechanisms underlying this ability are not understood. We describe a locally competitive algorithm (LCA) that solves a collection of sparse coding principles minimizing a weighted combination of mean-squared error (MSE) and a coefficient cost function. LCAs are designed to be implemented in a dynamical system composed of many neuron-like elements operating in parallel. These algorithms use thresholding functions to induce local (usually one-way) inhibitory competitions between nodes to produce sparse representations. LCAs produce coefficients with sparsity levels comparable to the most popular centralized sparse coding algorithms while being readily suited for neural implementation. Additionally, LCA coefficients for video sequences demonstrate inertial properties that are both qualitatively and quantitatively more regular (i.e., smoother and more predictable) than the coefficients produced by greedy algorithms.

This is a fascinating article. It ends with the equally intriguing :

The current limitations of neurophysiological recording mean that exploring the sparse coding hypothesis must rely on testing specific proposed mechanisms. Though the LCAs we have proposed appear to map well to known neural architectures, they still lack the biophysical detail necessary to be experimentally testable. We will continue to build on this work by mapping these LCAs to a detailed neurobiological population coding model that can produce verifiable predictions. Furthermore, the combination of sparsity and regularity induced in LCA coefficients may serve as a critical front-end stimulus representation that enables visual perceptual tasks, including pattern recognition, source separation and object tracking. By using simple computational primitives, LCAs also have the benefit of being implementable in analog hardware. An imaging system using VLSI to implement LCAs as a data collection front end has the potential to be extremely fast and energy efficient. Instead of digitizing all of the sensed data and using digital hardware to run a compression algorithm, analog processing would compress the data into sparse coefficients before digitization. In this system, time and energy resources would only be spent digitizing coefficients that are a critical component in the signal representation.

Eventually, I wonder how this greedy encoding algorithm would handle the hierarchical nature of the brain.

Reference:
[1] Emergence of Simple-Cell Receptive Field Properties by Learning a Sparse Code for Natural Images, Olshausen BA, Field DJ (1996). Nature, 381: 607-609.

Compressed Sensing: Updating the Big Picture on Compressed Sensing

I can easily see how newcomers could be impressed by the deluge of papers on the subject as we go along. Hence, I am trying to add every new papers/preprints on Compressed Sensing in this living document entitled Compressed Sensing: The Big Picture. Each step depicted in the figure shown above is followed by the paragraph title of the document covering that step. As one can see, the manifold part of the framework (red arrows), where one does operations only with compressed data has not yet been illustrated yet. I have added some links in the Hardware section even though those are mostly links to the blog. It will be expanded. The current paragraphs now are:

• 0. Understanding Compressed Sensing
• 1. Sparse Dictionnaries (how to make/find them)
• 2. CS Measurement Matrices
• 3. Reconstruction Techniques (codes)
• 4. Hardware Implementations
• 5. CS Search Engine
• 6. Calendar of events
  
• 7. References

Compressed Sensing: Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity

[Update: the codes for this algorithm are here ]

Here is another preprint from Arxiv.org: Subspace Pursuit for Compressive Sensing: Closing the Gap Between Performance and Complexity by Wei Dai and Olgica Milenkovic

We propose a new algorithm, termed subspace pursuit, for signal reconstruction of sparse and compressible signals with and without noisy perturbations. The algorithm has two important characteristics: low computational complexity, comparable to that of orthogonal matching pursuit techniques, and reconstruction capability of the same order as that of $l_{1}$-norm optimization methods. The presented analysis shows that in the noiseless setting, the proposed algorithm is capable of exactly reconstructing an arbitrary sparse signals, provided that the linear measurements satisfy the restricted isometry property with a constant parameter which can be described in a closed form. In the noisy setting and the case where the signal is not exactly sparse, it can be shown that the mean squared error of the reconstruction is upper bounded by a constant multiple of the measurement and signal perturbation energy.

They give some bounds for recovery by the Subspace Pursuit Algorithm of zero-one sparse signals, sparse signals with power-law decaying entries, with exponentially decaying entries and or with noise. The conclusions are somewhat impressive.

We introduced a new algorithm, termed subspace pursuit, for low-complexity recovery of a large class of sparse signals and for sampling matrices satisfying the RIP with a constant parameter δ3K. Also presented were simulation results demonstrating that the recovery performance of the algorithm matches, and sometimes even exceeds, that of the LP programming technique; and, simulations showing that the number of iterations executed by the algorithm for 0−1 sparse signals and compressible signals is of the order O(log K).

Credit Photo: Christie L. Dyett - NASA Space Coast Launch Services, via the Darkroastedblend blog. Yes new engines are added to the Space shuttle at every launch!

Compressed Sensing: New insights into one-norm solvers from the pareto curve now available.

In a previous entry I mentioned that New insights into one-norm solvers from the pareto curve by Gilles Hennenfent, Ewout van den Berg, Michael Friedlander and Felix Herrmann was closed. It is now viewable here.

Gilles also mentions to me that

For interest, the source codes used to generate the results presented in the paper are distributed as part of Madagascar (http://rsf.sourceforge.net) reproducible documents.

Great! Conveying research results through the reproducible research paradigm is a good way to accelerate acceptance of one's findings, and bring Fame and Fortune...

Thank you Gilles.

Compressed Sensing: Toeplitz Block Matrices in Compressed Sensing

Following up on previous results, here is this preprint by Florian Sebert, Leslie Ying, and Yi Ming Zou entitled Toeplitz Block Matrices in Compressed Sensing. The abstract reads:

Recent work in compressed sensing theory shows that nxN independent and identically distributed (IID) sensing matrices whose entries are drawn independently from certain probability distributions guarantee exact recovery of a sparse signal with high probability even if n is much less than N. Motivated by signal processing applications, random filtering with Toeplitz sensing matrices whose elements are drawn from the same distributions were considered and shown to also be sufficient to recover a sparse signal from reduced samples exactly with high probability. This paper considers Toeplitz block matrices as sensing matrices. They naturally arise in multichannel and multidimensional filtering applications and include Toeplitz matrices as special cases. It is shown that the probability of exact reconstruction is also high. Their performance is validated using simulations.

There is a good summary of the type of matrices that satisfy RIP and with what probability. These types of block Toeplitz construction seem to be doing as well as the average gaussian random matrix.

Compressed Sensing: There is no theory behind it right now, but does it work ? and Lena in 3D

This is the question Raghunandan Kainkaryam and Radu Berinde are debating in the comments section of Raghunandan's blog entry entitled: Shifted Transversal Designs and Expander Graphs. Is there anyone who wants to try it out on their signals ? (i.e. reconstructing signals using this measurement matrix). I put the measurement matrix function in this m.file.

Unrelated to the previous statement, here is Lena in 3D using Make3d that was tried before on out of this world photographs before. You can see the full view here as well as some tornado views (here and here).


What does this say about this picture, but more importantly what does it say about the technique developed by Ashutosh Saxena, Min Sun and Andrew Ng.

Compressed Sensing: Almost Euclidean subspaces of ell-1-N via expander codes and a Compressive Sensing course,

When was the last time, you could talk about hardware implementation and Euclidian subspaces via expander codes ? This is why I think this subject is so interesting, some of the most pointed mathematical bounds have the ability to enable some engineering hardware. If you are reading this, you have embarked in some pretty unique endeavor.

When reading the materials of Piotr Indyk's course entitled: Sketching, Streaming and Sub-linear Space Algorithms, I was reminded I had not mentioned this important paper by Venkatesan Guruswami, James Lee, and Alexander Razborov entitled Almost Euclidean subspaces of ell-1-N via expander codes. The abstract reads:

We give an explicit (in particular, deterministic polynomial time) construction of subspaces X included in of dimension such that for every x element of X,

if we are allowed to use random bits and for any fixed constant , the lower bound can be further improved to . Our construction makes use of unbalanced bipartite graphs to impose local linear constraints on vectors in the subspace, and our analysis relies on expansion properties of the graph. This is inspired by similar constructions of error-correcting codes.

Of interest is the note entitled relationship to compressed sensing before paragraph 2. A historical view making sense of this result (and that of Piotr Indyk's Uncertainty Principles, Extractors, and Explicit Embeddings of L2 into L1) was given in this guest lecture by Venkatesan Guruswami entitled Euclidean Subspaces and Compressed Sensing. To a dim witted person like me it certainly is enlighting. I have added the paper in the list of deterministic measurement matrix of the big picture on CS.
[Un resume des resultats de ce papier se trouve ici]

I also discovered the course entitled Compressive Sensing by Mark Davenport, Richard Baraniuk, and Ronald DeVore where I finally learned something about the Gelfand n-widths. Anyway, the course content reads as:

• Introduction

Encoding of Analog Signals

• The Shannon-Whitaker Sampling Theorem
• Optimal Encoding
• Kolmogorov Entropy
• Optimal Encoding of Bandlimited Signals
• Stable Signal Representations

Sparse Signals and Sparse Approximation

• Preliminaries
• New Signal Models
• Sparse Approximation and ℓp Spaces
• Thresholding and Greedy Bases
• Greedy Algorithms

Compressive Sensing

• Compressive Sensing
• Gelfand n-widths
• Instance Optimality
• The Restricted Isometry Property
• The Nullspace Property
• Optimality and the MRIP
• Summary

Compressed Sensing: Finding needles in noisy haystacks, faster Sparse Measurements Matrix code and Treelet as a way to build bases on datasets

Rui Castro, Waheed Bajwa, Jarvis Haupt,Robert Nowak, Gil Raz present Finding needles in noisy haystacks.
The abstract reads:

The theory of compressed sensing shows that samples in the form of random projections are optimal for recovering sparse signals in high-dimensional spaces (i.e., finding needles in haystacks), provided the measurements are noiseless. However, noise is almost always present in applications, and compressed sensing suffers from it. The signal to noise ratio per dimension using random projections is very poor, since sensing energy is equally distributed over all dimensions. Consequently, the ability of compressed sensing to locate sparse components degrades significantly as noise increases. It is possible, in principle, to improve performance by “shaping” the projections to focus sensing energy in proper dimensions. The main question addressed here is, can projections be adaptively shaped to achieve this focusing effect? The answer is yes, and we demonstrate a simple, computationally efficient procedure that does so.

I very much like their crystal clear/visual explanation:

Incoherence between the projection vectors and the signal basis vectors is essential to compressed sensing, and is required for successful recovery from a small number of non-adaptive samples. The incoherence condition guarantees that one “spreads” the sensing energy over all the dimensions of the coordinate system of the basis. In essence, each compressive sample deposits an equal fraction of sensing energy in every dimension, making it possible to locate the sparse components without sensing directly in each and every dimension, which would require a number of samples equal to the length of the signal.

I just added a link to the article in the adaptive sampling techniques section of the Compressed Sensing Big Picture.

Raghunandan Kainkaryam seems to have implemented a faster Sparse Measurements Matrix code (initially implemented as a Monday Morning Algorithm and later included in the CS Code section, the algorithm is due to Radu Berinde and Piotr Indyk) in his blog entry entitled Shifted Transversal Designs are Expander Graphs. I have not checked on it yet.

Two other articles grabbed my attention on the internets:
Rank related properties, for Basis Pursuit and total variation regularization by Francois Malgouyres. The abstract reads:

This paper focuses on optimization problems containing an $l^1$ kind of regularity criterion and a smooth data fidelity term. A general theorem is adapted to this context. It gives an estimate of the distribution law of the "rank" of the solution to the optimization problems, when the initial datum follows a uniform (in a convex compact set) distribution law. It says that asymptotically, solution with a large rank are more and more likely. The main goal of this paper is to understand the meaning of this notion of rank for some energies which are commonly used in image processing. We study in details the energy whose level sets are defined as the convex hull of finite subset of R^N (think Basis Pursuit) and the total variation. For these energies, the notion of rank respectively relates to sparse representation and staircasing.


It seems interesting but I am not sure how it directly or indirectly impacts Compressed Sensing. Some of his more recent submissions also seem to be relevant to CS as well with the same caveat.

• F. Malgouyres, M. Nikolova, Average performance of the sparsest approximation using a general dictionary.
  
  
• F. Malgouyres, T. Zeng, Applying the Proximal Point Algorithm to a Non Negative Basis Pursuit Denoising model, Software.
  
  
• F. Malgouyres, Projecting onto a polytope simplifies data distributions.

The second article that grabbed my interest is Treelets - An Adaptive Multi-Scale Basis for Sparse Unordered Data by Ann Lee, Boaz Nadler and Larry Wasserman. The abstract reads:

In many modern applications, including analysis of gene expression and text documents, the
data are noisy, high-dimensional, and unordered — with no particular meaning to the given order
of the variables. Yet, successful learning is often possible due to sparsity: the fact that the data are typically redundant with underlying structures that can be represented by only a few features. In this paper, we present treelets—a novel construction of multi-scale bases that extends wavelets to non-smooth signals. The method is fully adaptive, as it returns a hierarchical tree and an orthonormal basis which both reflect the internal structure of the data. Treelets are especially well-suited as a dimensionality reduction and feature selection tool prior to regression and classification, in situations where sample sizes are small and the data are sparse with unknown groupings of correlated or collinear variables. The method is also simple to implement and analyze theoretically. Here we describe a variety of situations where treelets perform better than principal component analysis as well as some common variable selection and cluster averaging schemes. We illustrate treelets on a blocked covariance model and on several data sets (hyperspectral image data, DNA microarray data, and internet advertisements) with highly complex dependencies between variables.

I can't wait to see the code that implements that algorithm. To understand better why this is relevant to previous entries, the figure above is Figure 6

Fig. 6 shows an example of how treelets can learn the covariance structure for colon cell nuclei (Tissuetype 3). The method learns both the tree structure and a basis through a series of Jacobi rotations (see top right panel). By construction, the basis vectors are localized and supported on nested clusters in the tree (see the bottom left and top left panels). As a comparison, we have also computed the PCA eigenvectors. The latter vectors are global and involve all the original variables (see bottom right panel).

In other words, this is another technique building an orthonormal basis for a specific dataset.

Finally, I am going to add the Talks on Compressed Sensing at Institut Poincare in Paris as pointed out by Gabriel Peyre. Some of them will be in English.

Compressed Sensing: Figuring out the Compressibility of a Signal or Dataset

As I am adding elements in the Big Picture section on Compressed Sensing, I have come to appreciate how some subjects eventually have a connection to CS. Case in point, in the description of the framework, while reconstruction is focusing most of our attention, a definite area of interest also includes recognizing that the signal of interest can be sparse in some basis. As we all know, Compressibility or sparsity of the signal/dataset is a prerequisite for CS.

While some of us are lucky to have a good idea of what those bases are, others are left with tensor products of wavelets in the hope of finding something relevant to their areas of expertise. So the question to them is to either keep finding bases through the eigenfunction expansion of the underlying physics operator of the phenomena at hand or ... use recent Machine Learning techniques to build those. The question we are trying to answer is: How do you find dictionaries of functions that will lead you to have signals that are compressible in them ? Here are the three categories I have been able to make up while surveying the subject. I am open to more enlightment on the subject.

1.1 Basis Functions for which signals are either sparse or compressible

This is the lucky case and the subject of much investigation in the literature.

• Fourier, Polynomials, etc...
  
• All kinds of wavelets and higher dimensional related functions (like Curvelets, Ridgelets, Countourlets,....) through nonseparable forms or through the use of tensor-products of these functions. Laurent Duval has a an encyclopedic listing of the most recent functions at Where is the Starlet.
  

1.2 Algorithms that find sparse dictionaries

These algorithms are pretty new and are likely to grow as some of them are being used in areas of robotics and hyperspectral imaging where historically no known bases are known in advance:

• Dictionary Learning Algorithms for Sparse Representation (Matlab implementation of FOCUSS / FOCUSS-CNDL is here)
• Multiscale sparse image representation with learned dictionaries [Matlab implementation of the K-SVD algorithm is here]
  
• Efficient sparse coding algorithms [ Matlab code is here ]
• Non-negative Sparse Modeling of Textures (NMF) [Matlab implementation of NMF (Non-negative Matrix Factorization) and NTF (Non-negative Tensor), a faster implementation of NMF can be found here]

Let us note the Matlab Toolbox Sparsity by Gabriel Peyre that has some of these techniques implemented (but no good readme file :-))

1.3 Data Driven Dictionaries

I am not sure there is a good separation between Algorithms that find Dictionaries in which data are sparse/compressible in (1.2) and Data Driven Dictionaries (1.3) where one constructs a set of eigenfunctions on a set of high dimensional data and hope that the decomposition at every point will yield few large coefficients. The idea here is to build some harmonic analysis on the manifold, in short functions on a manifold that have the property of bringing about dimensionality reduction. In this setting, one can list:

• Geometric harmonics (as demoed here)
• Diffusion Wavelets

There are not different approaches rather one is an extension of the other. Let us note that random projection of data that belong to a manifold are using, albeit without being stated as such, the fact that these geometric harmonics and random functions are incoherent with each other (not unlike the 1-d example featured here). Writing on Random Projections of a manifold in high dimension generally do not point this out because in this case, we either do not have the computational ability nor the interest to reconstruct the "original" dataset.

But why should we care about high dimensional signals in imagery for instance?

One should also note that sometimes, an image (2-D dataset) is not just a unrelated collection of (pixel) values which happen to be presented in a 2-d shape. Sometimes, one is interested in the fact that elements in that 2-D array have some underlying connection or statistics to each other. In the Machine Learning community interested in machine vision, one is generally trying to use that fact by projecting these 2-d information into an N-D space with N in the realm of 1000's. Akin to hyperspectral imaging, now every "pixels" contain thousands of information relating to their neighborhood. These superpixels are then projected back into low dimension using dimensionality reduction techniques such as geometric harmonics in order to bring about parameters like depth ( It is important to figure out the limitation of this type of exercise).

Why am I saying this ? Because it seems to me that while some would feel comfortable dealing with curvelets in two dimensional imaging application, it is also becoming more obvious that when performing random projections of these high dimensional datasets, one keeps the relevant data/statistics (see the hyperspectral imaging work of Coifman) and that it might become more interesting to project up these 2-D image first. At which point, either Geometrics Harmonics or Non-Negative Tensor Factorization might be the only way to go about finding the sparse dictionary of this high dimensional space.

A point I have not seen in the literature is the potentiality of dictionaries to be specific to the hardware gathering the data.

Let us finally note that in the case of random projections, these sparse dictionaries are really useful for the reconstruction of the signal, and in some cases we don't care as much even though it is the only way to figure out if we have kept that information through the random projection process.

Credit photo: NASA / JPL / U. Arizona, Active avalanche on Mars as caught by the Hirise Camera. Via the planetary society blog

Compressed Sensing: 1-Bit Compressive Sensing, Causal Compensation for Erasures in Frame Representations, Curvelet-based seismic data processing

Found on the internets, the mind altering 1-Bit Compressive Sensing by Petros Boufounos and Richard Baraniuk.The abstract reads:

Compressive sensing is a new signal acquisition technology with the potential to reduce the number of measurements required to acquire signals that are sparse or compressible in some basis. Rather than uniformly sampling the signal, compressive sensing computes inner products with a randomized dictionary of test functions. The signal is then recovered by a convex optimization that ensures the recovered signal is both consistent with the measurements and sparse. Compressive sensing reconstruction has been shown to be robust to multi-level quantization of the measurements, in which the reconstruction algorithm is modified to recover a sparse signal consistent to the quantization measurements. In this paper we consider the limiting case of 1-bit measurements, which preserve only the sign information of the random measurements. Although it is possible to reconstruct using the classical compressive sensing approach by treating the 1-bit measurements as ±1 measurement values, in this paper we reformulate the problem by treating the 1-bit measurements as sign constraints and further constraining the optimization to recover a signal on the unit sphere. Thus the sparse signal is recovered within a scaling factor. We demonstrate that this approach performs significantly better compared to the classical compressive sensing reconstruction methods, even as the signal becomes less sparse and as the number of measurements increases.

Notwithstanding the obvious simple hardware implementation, I am stunned by the potential of this result. I am impatient to see an actual implementation of this modified FPC solver originally developed by Elaine Hale, Wotao Yin and Yin Zhang.

While the link exists for Reconstructing Sparse Signals From their Zero Crossings by Petros Boufounos, Richard Baraniuk. Permissions have not been set on the server for people of the outside to see it yet.


Petros Boufounos, Alan Oppenheim and Vivek Goyal introduces us to the subject of Causal Compensation for Erasures in Frame Representations. The abstract reads:

In a variety of signal processing and communications contexts, erasures occur inadvertently or can be intentionally introduced as part of a data reduction strategy. This paper discusses causal compensation for erasures in frame representations of signals. The approach described assumes linear synthesis of the signal using a pre-specified frame but no specific generation mechanism for the coefficients. Under this assumption it is demonstrated that erasures can be compensated for using low-complexity causal systems. If the transmitter is aware of the occurrence of the erasure, an optimal compensation is to project the erasure error to the remaining coefficients. It is demonstrated that the same compensation can be executed using a transmitter/receiver combination in which the transmitter is not aware of the erasure occurrence. The transmitter precompensates using projections, as if assuming erasures will occur. The receiver undoes the compensation for the coefficients that have not been erased, thus maintaining the compensation only of the erased coefficients. The stability of the resulting systems is explored, and stability conditions are derived. It is shown that stability for any erasure pattern can be enforced by optimizing a constrained quadratic program at the system design stage. The paper concludes with examples and simulations that verify the theoretical results and illustrate key issues in the algorithms.

This somehow resembles a little bit what Jort is doing.


Gilles Hennenfent, Ewout van den Berg, Michael Friedlander and Felix Herrmann produced New insights into one-norm solvers from the pareto curve. The paper is for SINBAD sponsors only for the moment, we at least get to see the abstract:

Geophysical inverse problems typically involve a trade off between data misfit and some prior. Pareto curves trace the optimal trade off between these two competing aims. These curves are commonly used in problems with two-norm priors where they are plotted on a log-log scale and are known as L-curves. For other priors, such as the sparsity-promoting one norm, Pareto curves remain relatively unexplored. We show how these curves lead to new insights in one-norm regularization. First, we confirm the theoretical properties of smoothness and convexity of these curves from a stylized and a geophysical example. Second, we exploit these crucial properties to approximate the Pareto curve for a large-scale problem. Third, we show how Pareto curves provide an objective criterion to gauge how different one-norm solvers advance towards the solution.

In the world of seismic signal processing, people have access to interesting sets of basis functions such as curvelets. Felix Herrmann, D. Wang, Gilles Hennenfent, and Peyman Moghaddam wrote a summary of the current field in Curvelet-based seismic data processing: a multiscale and nonlinear approach.

In this letter, the solutions to three seismic processing problems are presented that exploit the multiscale and multi-angular properties of the curvelet transform. Data regularization, multiple removal, and restoration of migration amplitudes are all formulated in terms of a sparsity promoting program that employs the high degree of sparsity attained by curvelets on seismic data and images. For each problem the same nonlinear program is solved, simultaneously minimizing the data misfit and the one norm (l1) on the desired curvelet domain solution. Parsimony of curvelets on seismic wavefields and images of the sedimentary crust with wavefront-like features underlies the successful solution of these problems and is a clear indication of the broad applicability of this transform in exploration seismology.

The next step would be to devise sensors that can directly acquire data in a compressed sensing fashion. As far I recall the oil drilling industry did not care much about getting less data as they have plenty of infrastructure to take care of that for the time being. However in some instances, getting few data is the only thing people can get (recall the 30 bit/s pulse mud business).