Compressed Sensing: Links, ITA'08 at UCSD and EUSIPCO 2008 in Lausanne

I have been told by one reader how uneasy it was to find this blog on the subject of compressed sensing. I checked with Google and other sites and found that there is indeed a small issue. It looks as though there is much spam on subjects that are very new and specifically an inability for Google to reference the subject through the labeling provided by the Blogger/Google system. Some of the difficulties may have to do with the fact that people tend to link to a specific entry rather than the full list of entries. I think one of the ways to solve this problem is for whoever wants to link to this blog on the subject of Compressed Sensing, Compressive Sampling or Compressive Sensing should link to the address below:

http://nuit-blanche.blogspot.com/search/label/CS

I also use

http://nuit-blanche.blogspot.com/search/label/compressed%20sensing

so there is no need to change anything on the websites that already have that address. These addresses have the distinct appeal of removing all my other ramblings not related to the subject :-)

Jort mentions that the 2008 European Signal Processing Conference (EUSIPCO-2008) taking place in Lausanne, Switzerland, will feature a special session on Sparsity in Signal Processing organized by Holger Rauhut, Georg Tauboeck, and Franz Hlawatsch. The deadline for submission is February 8th. The conference is taking place August 25th-29th.

Another reader pointed out that several talks will be given at Information Theory and Applications '08 at UCSD that we have not seen yet on the Rice Repository, I am going to mention the abstracts, I'd be very interested in seeing preprints whenever they are available (there is also a post-workshop course with some of the leading people as teachers).
Compressed sensing and linear codes over real numbers by Fan Zhang and Henry Pfister (Henry, I understand now why the preprint won't be available before the end of the month :-)).

Compressed sensing (CS) is a new area of signal processing and statistics that focuses on signal reconstruction from a small number of linear (e.g., dot product) measurements. In this paper, we analyze CS using tools from coding theory because CS can also be viewed as a syndrome-based source coding of sparse vectors using linear codes over real numbers. While coding theory does not typically deal with codes over real numbers, many results can be modified to apply in this case. In particular, there is a very close relationship between CS and error-correcting codes over large discrete alphabets.

Exploiting recent advances in capacity-approaching codes, we propose new approaches for CS of exactly sparse vectors. These methods are based on irregular low-density parity-check codes and result in provable oversampling thresholds with reconstruction complexities that are linear in the signal dimension $n$. Reconstruction succeeds with high probability (as $n\rightarrow\infty$) using a random signal and measurement model. We also discuss extensions to deterministic signal models and "approximately sparse" signals.

Algorithms and Bounds for Sensing Capacity and Compressed Sensing by M. Zhao, S. Aeron, V. Saligrama

We consider the problem of recovering sparse phenomena from projections of noisy data, a topic of interest in compressed sensing. We consider a notion of Sensing Capacity which is defined as the supremum of the ratio of the number of signal dimensions that can be identified per projection. Sensing Capacity is a function of sensing diversity, SNR, sensed environment (sparsity) as well as desired distortion up to which the sensed phenomena must be reconstructed. In this paper we will focus on the importance of SNR on sensing capacity. First, we prove algorithm independent results, i.e. find necessary and sufficient conditions on the number of projections required for reconstruction to given fidelity using information theoretic inequalities. Next, we present linear programming (LP) methods for recovering sparse signals in the presence of noise. The proposed algorithm does not require tuning parameters in contrast to other algorithms such as Lasso, which use tuning as a means of incorporating prior knowledge of noise statistics. We show that $SNR=O(\log n)$ is a necessary and sufficient condition for perfect recovery of discrete signals and exact support of continuous signals.

Integer compressed sensing via superimposed coding by Wei Dai and Olgica Milenkovic.

We introduce a new family of codes, termed weighted Euclidean superimposed codes (WESCs). This family generalizes the class of Euclidean superimposed codes, used in multiuser identification systems. WESCs allow for deterministic discrimination of bounded, integer-valued linear combinations of real-valued codewords, and can therefore also be seen as a specialization of compressed sensing schemes. We first present lower and upper bounds on the largest size a WESC, and show how to use classical coding-theoretic and new compressed sensing analytical tools to devise low-complexity decoding algorithms for these codes. Then we study sparse WESCs, in which the number of nonzero coordinates of codewords are significantly smaller than their length. Our results include a lower bound on the largest rate of sparse WESCs and a deterministic construction based on DeVore's method.

Combining geometry and combinatorics: A unified approach to sparse signal recovery by A.C. Gilbert, P. Indyk, H. Karloff, M.J. Strauss

There are two main algorithmic approaches to sparse signal recovery: geometric and combinatorial. The geometric approach starts with a geometric constraint on the measurement matrix $\Phi$ and then uses linear programming to decode information about $x$ from $\Phi x$. The combinatorial approach constructs $\Phi$ and a combinatorial decoding algorithm to match. We present a unified approach to these two classes of sparse signal recovery algorithms.

The unifying elements are the adjacency matrices of high-quality {\em unbalanced expanders}. We generalize the notion of {\em restricted isometry property} (RIP), crucial to compressed sensing results for signal recovery, from the Euclidean norm to the $\ell_p$ norm for $p >
1$, and then show that unbalanced expanders are essentially equivalent to RIP-$p$ matrices. From known deterministic constructions for such matrices, we obtain new {\em deterministic} measurement matrix constructions and algorithms for signal recovery which, compared to previous deterministic algorithms, are superior in either the number of measurements or in noise tolerance.

Bayesian matching pursuit Phil Schniter and Lee C. Potter.

We propose a Bayesian approach to the compressive sensing problem. In our formulation, the measurements are modeled as a known linear combination of the sparse coefficients plus additive white Gaussian noise of known variance, and the sparse coefficients are modeled as independent Gaussian random variables whose unknown means and variances are drawn
independently from a finite set according to known priors. So that the coefficient vector is sparse, the most a priori probable {mean,variance} combination can be set to {0,0}. Leveraging the discrete nature of the Gaussian mixture parameters, we propose an efficient tree-search which finds the mixture vectors that account for the dominant posterior probabilities. The MMSE estimate of the sparse-coefficient vector then follows directly from an average over these dominant posteriors. A key feature of our tree-search is a fast metric update which operates on the "matched filter outputs" (i.e., the inner products between the measurement vector and the columns of the combining matrix), hence the name ``Fast Bayesian Matching Pursuit.''

Compressive learning and inference by Richard Baraniuk, Chinmay Hegde, Marco Duarte, Mark Davenport, and Michael Wakin

Compressive Sensing (CS) is a new approach to data acquisition in which analog signals are digitized for processing not via uniform sampling but via measurements using more general, even random, test functions. In contrast with conventional wisdom, the new theory asserts that one can combine "low-rate sampling" with an optimization-based reconstruction process for efficient and accurate signal acquisition. While the growing CS literature has focused on reconstructing signals, in many applications, we are ultimately interested only in making inferences about the data. Examples include detecting tumors in medical images, classifying the type of vehicle in airborne surveillance, or estimating the trajectory of an object in a video sequence. In this talk we will review our recent work on new algorithms for compressive learning and inference that enjoy the same general benefits as CS. Specific techniques include compressive versions of the matched filter (dubbed the "smashed filter"), intrinsic dimension estimation for point clouds, and manifold learning algorithms. In our techniques, the number of measurements required is linear in the complexity of the data (sparsity in the case of a basis representation or dimension in the case of a manifold model) and only logarithmic in the ambient dimension.

Compressed channel sensing by R. Nowak, W. Bajwa, and J. Haupt

Channel sensing and estimation is an important component of modern wireless communication systems, and it is a crucial element of emerging systems such as cognitive radio. Wireless channels are multidimensional; delay, Doppler, and spatial diversity provides rich signaling environments that can be exploited to enhance communication capabilities. The identification of such channels is usually carried out by fully exciting or illuminating all dimensions and then applying linear estimation techniques. For high-dimensional channels, this is prohibitive and often ineffective. Linear estimation methods are ineffective because they ignore a key feature of such channels. Because of their high-dimensionality and the physical causes underlying them, wireless channels are often quite sparse, with a small number of dominant modes characterizing their structure. Estimation methods that do not capitalize on this sparsity do not perform well. This paper addresses channel sensing and estimation from a new perspective that exploits the inherent sparsity in high-dimensional wireless communication channels. Adapting ideas from
the theory of compressed sensing, we make two key observations: 1) sparse channels can be identified from a small number of properly chosen excitations or illuminations, and exhaustive probing is unnecessary; 2) nonlinear, sparse estimation methods such as the Lasso yield superior channel estimates compared to linear techniques. One of the especially novel mathematical aspects of our work is that we show that Toeplitz-structured sensing matrices, which naturally arise when pseudorandom excitations are employed, are very well suited to the identification of sparse channels.

Iterative signal recovery from incomplete and inaccurate measurements by J. Tropp, D. Needell, and R. Vershynin

Compressive Sampling (CoSa) offers a new paradigm for acquiring signals that are compressible with respect to an orthobasis. The major algorithmic challenge in CoSa is to approximate a compressible signal from noisy samples. Until recently, all provably correct reconstruction
techniques have relied on large-scale optimization, which tends to be computationally burdensome.

This talk describes a new iterative, greedy recovery algorithm, called CoSaMP that delivers the same guarantees as the best optimization-based approaches. Moreover, this algorithm offers rigorous bounds on computational cost and storage. It is likely to be extremely efficient for practical problems because it requires only matrix--vector multiplies with the sampling matrix. For some cases of interest, the running time is just O(N*log^2(N)), where N is the length of the signal.

Credit: NASA/JPL, Mars Rover Spirit on Sol 1002 or about 417 sols ago (one sol a Martian day is about 25 Earth hours).

Make3D: Depth Information From A Single Shot. Stressing the Algorithm With Other World Views

In a previous installment, we saw how coded aperture could use specific bayesian priors to infer depth. Ashutosh Saxena went a little further to make a similar technology more accessible using normal images. He just made available to everybody the ability to produce 3-D models from single snapshots. This is an extension of his work with Min Sun and Andrew Ng. The site is at:

http://Make3d.stanford.edu

If you register with the site, you can upload your own images and see the results either in some Quicktime format or in VRML which can be viewed using the Cortona plugin for Windows, and this extension for Linux.

In order to push a little bit the boundaries of the algorithm, I specifically used imagery that is a little "weird" where the background has very sharp discontinuities: Planetary exploration.

The landscape as seen from Huygens when it landed on Titan is here:


Not bad for a single view (the Huygens probe survived only 30 minutes on Titan as expected and did not move) that no human has ever seen.

I am less impressed by the 3-D view rendered from the Mars rover Opportunity taken a week ago.


(the VRML can be seen here)
or Spirit



Some of the very sharp contrast images from Cassini looking a Phoebe did not converge.


But the beautiful view from the (amateur) HALO flight 2 is very interesting.


When using the 3D viewer, it looks like you are flying over clouds.

You can try it here.
Indoor scenes seem to provide also some good estimate, starting with the original shot:

while the 3D scene produces this:

one can view it with the 3D viewer.

I am half surprised by some of these results, if one recalls how the technique works, for outdoor photography, haze is an important part of the process that allows the method to differentiate between different depths. And so I am only half surprised that it does not converge for Phoebe (no atmosphere) but somewhat well on Mars (low atmosphere) and well on Titan (with an atmosphere) and on Earth at 28 km altitude looking at clouds and indoors.

Credit: ESA/NASA/JPL/University of Arizona/Alexei Karpenko

Today came close to being when.

When I saw this picture this morning, I could not help but think about a previous post entitled tracking multiple targets at sea: not a question of if.

Compressed Sensing: A Lower Bound for the Number of Measurements in Sparse Measurement Matrices ?

[Update: see the comment section of this post, Radu Berinde mentions that the bound I am mentioning is satisfied with high probability. Thank you Radu]

While fascinating, the Sparse Measurement Matrices proposed by Radu Berinde and Piotr Indyk has a small drawback, I think. Irrespective to the dimension of the underlying manifold under study, the number of measurements must meet a higher bound in order for all columns of the measurement matrix to be linearly independent. Namely, if k is the number of ones per column, n the number of measurements and m the dimension of the space where the signal lives, the maximum size of the signal (or dimension of the ambient space) cannot be higher than the binomial coefficient:

Conversely, the number of measurements (n) must be enough for the inequality to stand.

m less than C(n,k)

If one considers using k = 2, and the number of measurements is 2 (n=2) then the absolute maximum size of the signal is 1. When the number of measurements is 10, then the absolute maximum size of the signal is 45. When looking at a 5 MB image, one needs to play with n (number of measurements) and k (number of ones per column) to find the closest m to 5 x 10^6.

Wolfram's site has a collection of references on binomial coefficients and the latest sharpest bound is:

Sondow (2005) [1] and Sondow and Zudilin (2006) [2] noted the inequality

for a positive integer and a real number.

If I did the variable change correctly, the lower bound of this inequality translates into:

m less than 1/4 n (n/k)^k 1/(1-k/n)^(n-k-1)

or roughly when k is small compared to n:

m less than 1/(4 k^k) n^(k+1)

For k=4 (4 zeros per column)

m less than 1/1024 n^ 5
in other words
the signal size must be less than the fifth power of the number of measurements up to a constant

So that for a 5 MB image of dimension, the number of measurements must roughly be superior to 88 (in fact the number must be superior to 107). For some cases, this number is clearly above the intrinsic dimension of the dataset and one wonders whether it is wise to oversample compared to a Gaussian Random Matrix approach (which would require 2K+1 measurements where K is the intrinsic dimension of the signal). On the other hand, these 88 sparse samples do not require the huge memory overhead needed to store the Gaussian Matrix. Clearly one needs to investigate a sweet spot for small sized signals. I have included this condition in the function Sparse Measurement Matrix implemented here.

Another item of caution is that the measurement matrix needs to be computed beforehand. The structure of the matrix requires that the matrix be built in full before using it. The other random measurement matrices do not have this feature.

Also, and it is relevant to people thinking about Hardware implementations, the measurements itself can be extremely sparse (all zeros) or extremely full (all ones). The sparsity of these matrices is driven through a number of non-zeros elements by columns not rows.

Finally, in regards to a previous question, the sparsity structure of this measurement matrices can used by most current solvers through the use of a function handle. A minor point remains as to whether the actual solvers could not be further designed with the sparsity structure in mind.


Reference:
[1] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.

[2] Sondow, J. and Zudilin, W. "Euler's Constant, -Logarithms, and Formulas of Ramanujan and Gosper." Ramanujan J. 12, 225-244, 2006.

Photo Credit: NASA/JPL/Space Science Institute, The Cassini spacecraft's close flyby of Epimetheus (116 kilometers, or 72 miles across) on December 3, 2007 returned detailed images of the moon's south polar region.

Compressed Sensing: Nonlinear Approximation Techniques Using L1 and a Workshop.

So the L1 revolution is picking up and it will eventually help us solve linear particle transport equations. In the meantime, it looks like it is getting traction in the Applied Mathematics area interested in the solving of all kinds of PDEs, in particular the Navier-Stokes Equation and its simplified versions (1-D,...). In Survey of Nonlinear Approximation of PDEs in L1, Jean-Luc Guermond and Bojan Popov detail why L1 is becoming interesting for PDE solvers with 1-D and 2-D examples. They first point out that other areas are using L1 minimization techniques. While Compressed Sensing is one of them, they also mention CAD systems where L1 splines do better than L2 splines: "L1 splines are less oscillatory than L2 splines and L1 splines can compress data better than L2 splines." They then describe why in the PDE world, Galerkin methods are short in providing solution techniques (we already knew that in Neutron Transport !)

They first describe the attendant conformism that makes most of the engineering world live in L2 world (FEM).
and then provide what will sell the idea





Sweet. As they say in the concluding remarks: "We should not be afraid to work in Banach spaces. It is doable." It mirrors what I say to others when mentioning compressed sensing, "Come work on the dark side of the Force":-). Further reference on these results can be found in the following two papers:

1. J.-.L. GUERMOND, A finite element technique for solving first order PDE's in Lp, SIAM J. Numer. Anal. 42 2 (2004) 714--737.
2. J.-.L. GUERMOND, B. POPOV, Linear advection with ill-posed boundary conditions via L1-minimization, International Journal of Numerical Analysis and Modeling, 4:1 (2007) 39-47.

On a related note, Jean-Luc Guermond Bojan Popov and Ron DeVore organize a workshop on Nonlinear Approximation Techniques Using L1 at Texas A&M University on May 16th to 18th, 2008. It'll take place in the Blocker building, Room 120.

L1-based techniques are emerging in different fields of applied sciences. The objective of the workshop is to gather leading experts that are possibly unaware of each other's activity so that they exchange ideas and get a more global view of this new set of methods. The purpose of this workshop is also stimulate cross fertilization.

Compressed Sensing: Learning Bases from Scratch, an Optical Heterodyning Camera and RandomTime Coded Imaging

[Somebody at Honeywell is downloading this entry every four seconds. If you are that person, Please stop this] In line with the previous statement that one has to first find a sparse basis to then contemplate some hardware capability to eventually perform Compressed Sensing, Jort Gemmeke mentions to me that the Matlab implementation of Efficient sparse coding algorithms by Honglak Lee, Alexis Battle, Rajat Raina, Andrew Ng is here. The abstract reads:

Sparse coding provides a class of algorithms for finding succinct representations of stimuli; given only unlabeled input data, it discovers basis functions that capture higher-level features in the data. However, finding sparse codes remains a very difficult computational problem. In this paper, we present efficient sparse coding algorithms that are based on iteratively solving two convex optimization problems: an L1-regularized least squares problem and an L2-constrained least squares problem. We propose novel algorithms to solve both of these optimization problems. Our algorithms result in a significant speedup for sparse coding, allowing us to learn larger sparse codes than possible with previously described algorithms. We apply these algorithms to natural images and demonstrate that the inferred sparse codes exhibit end-stopping and non-classical receptive field surround suppression and, therefore, may provide a partial explanation for these two phenomena in V1 neurons.

This algorithm has the advantage over previous algorithms that it is very fast.


They then used this technique to produce a new machine learning algorithm called "Self Taught Learning". The paper is written by Honglak Lee, Alexis Battle, Rajat Raina, Benjamin Packer and Andrew Ng and is entitled Self-taught Learning: Transfer Learning from Unlabeled Data. The abstract reads:

We present a new machine learning framework called "self-taught learning" for using unlabeled data in supervised classification tasks. We do not assume that the unlabeled data follows the same class labels or generative distribution as the labeled data. Thus, we would like to use a large number of unlabeled images (or audio samples, or text documents) randomly downloaded from the Internet to improve performance on a given image (or audio, or text) classification task. Such unlabeled data is significantly easier to obtain than in typical semi-supervised or transfer learning settings, making self-taught learning widely applicable to many practical learning problems. We describe an approach to self-taught learning that uses sparse coding to construct higher-level features using the unlabeled data. These features form a succinct input representation and significantly improve classification performance. When using an SVM for classification, we further show how a Fisher kernel can be learned for this representation.

The subject of coded aperture in compressed sensing was mentioned before here and here. I found an other series of intriguing papers on Coded Aperture for Cameras. They do not perform Compressed Sensing per se, but it gives a pretty good view on how Compressed Sensing could be implemented. The project page is here, the paper is entitled Dappled Photography: Mask Enhanced Cameras for Heterodyned Light Fields and Coded Aperture Refocusing by Ashok Veeraraghavan, Ramesh Raskar, Amit Agrawal, Ankit Mohan and Jack Tumblin

The abstract reads:

We describe a theoretical framework for reversibly modulating 4D light fields using an attenuating mask in the optical path of a lens based camera. Based on this framework, we present a novel design to reconstruct the 4D light field from a 2D camera image without any additional refractive elements as required by previous light field cameras. The patterned mask attenuates light rays inside the camera instead of bending them, and the attenuation recoverably encodes the rays on the 2D sensor. Our mask-equipped camera focuses just as a traditional camera to capture conventional 2D photos at full sensor resolution, but the raw pixel values also hold a modulated 4D light field. The light field can be recovered by rearranging the tiles of the 2D Fourier transform of sensor values into 4D planes, and computing the inverse Fourier transform. In addition, one can also recover the full resolution image information for the in-focus parts of the scene. We also show how a broadband mask placed at the lens enables us to compute refocused images at full sensor resolution for layered Lambertian scenes. This partial encoding of 4D ray-space data enables editing of image contents by depth, yet does not require computational recovery of the complete 4D light field.

A Frequently Asked Questions section on the two cameras is helpful to a person who has never heard of these 4D light fields cameras. The 4D refers to the fact that we have 2D spatial information as for any image but thanks to the masking mechanism, one can also obtain information about where the light rays are coming from, i.e. the angle: the four dimensions therefore imply 2 spatial dimension (y,x) and 2 angles. Most interesting is the discussion on the Optical Heterodyning Camera. It points out (see figure above) that in normal cameras with lenses, one samples the restricted version of the full Fourier transform of the image field. In the heterodyning camera, the part of the Fourier transform that is normally cut off from the sensor is "heterodyned" back into the sensor. For more information, the derivation of the Fourier Transform of the Mask for Optical Heterodyning is here. One may foresee how a different type of sampling could provide a different Cramer-Rao bound on object range. One should notice that we already have a bayesian approach to range estimation from a single shot as featured by Ashutosh Saxena and Andrew Ng , while on the other hand in the Random Lens Imaging approach, one could already consider depth if some machine learning techniques were used.

Of related interest is the work of Ramesh Raskar and Amit Agrawal on Resolving Objects at Higher Resolution from a Single Motion-Blurred Image where now one uses random coded exposure i.e. random projection in time.



The abstract reads

Motion blur can degrade the quality of images and is considered a nuisance for computer vision problems. In this paper, we show that motion blur can in-fact be used for increasing the resolution of a moving object. Our approach utilizes the information in a single motion-blurred image without any image priors or training images. As the blur size increases, the resolution of the moving object can be enhanced by a larger factor, albeit with a corresponding increase in reconstruction noise.

Traditionally, motion deblurring and super-resolution have been ill-posed problems. Using a coded-exposure camera that preserves high spatial frequencies in the blurred image, we present a linear algorithm for the combined problem of deblurring and resolution enhancement and analyze the invertibility of the resulting linear system. We also show a method to selectively enhance the resolution of a narrow region of high-frequency features, when the resolution of the entire moving object cannot be increased due to small motion blur. Results on real images showing up to four times resolution enhancement are presented.

The project webpage is here. In traditional cameras, blurring occurs because the shutter remains open while the dynamic scene takes place.
In coded exposure, the shutter is open/closed while the dynamic scene occurs.

The research by Ramesh Raskar and Amit Agrawal shows that random coded exposure allows the retrieval of the static object.


I believe this is the first time where random time coded imaging is used.


Unrelated: Laurent Duval me fait savoir que deux presentations auront lieu a Paris sur des sujets recontres sur ce blog. Elles auront lieu dans la serie de seminaires organises par Albert Cohen et Patrick Louis Combettes:

Demain, Mardi 22 janvier 2008,
À 11h30 : Jalil Fadili (ENSI, Caen) "Une exploration des problèmes inverses en traitement d'images par les représentations parcimonieuses"

Mardi 19 février 2008
À 10h15 : Yves Meyer (ENS, Cachan) "Échantillonnage irrégulier et «compressed sensing»"

Compressed Sensing: Utilizing Sparsity in Compressed Sensing Reconstruction Algorithms

I have tried the Sparse Measurement Matrices of Radu Berinde and Piotr Indyk on a restricted set of examples. It seems to work as well as random Gaussian matrices. I have implemented a function that implements these matrices here. I used both l1-Magic and the re-weighted Lp reconstruction techniques and both yield similar results. However, currently none of the solvers take advantage of the fact that these matrices are sparse. For the re-weighted Lp technique, one can speed up the reconstruction fairly easily using the sparse function of Matlab since the full algorithm implementation takes about 10 lines. But we also know that the re-reweighted Lp scheme is also slow, so the generic question is, besides L1-Magic (for which Radu Berinde and Piotr Indyk have done an implementation)

How can any of the current reconstruction solvers listed below utilize the sparsity of the measurement matrices ?

• SparseLab
• GPSR
• ell-1 LS: Simple Matlab Solver for ell-1-Regularized Least Squares Problems
• sparsify
• SPGL1: A solver for large scale sparse reconstruction
• Regularized OMP
• TwIST

[Update: Duh, the answer is simple, instead of defining the matrix, one has to define a way to compute Ax and A'x through a function handle. Most of these softwares handle this. It goes to say I should not be posting late at night]

Source: Rice Compressed Sensing repository

Compressed Sensing: The slow realization that most events are sparse in EEGs and in Astronomy

The first step toward the hardware implementation of Compressed Sensing or Compressive Sampling is the realization that the phenomena to be studied is sparse in some basis. There are many engineering problems that still do not take advantage of this fact either because current methods have been somewhat successful or because the idea of using L1 regularization is still an odd beast for most. Two fields seem to waking up to this fact.

* EEGs are notoriously known for ill-posed problems. Andrew Bolstad, Barry Van Veen and Robert Nowak take a stab at Space-Time Sparse Reconstruction for Magneto-/Electroencephalography. The abstract reads:

This article presents a new spatio-temporal method for M/EEG source reconstruction based on the assumption that only a small number of events, localized in space and/or time, are responsible for the measured signal. Each space-time event is represented using a basis function expansion which re°ects the most relevant (or measurable) features of the signal. The basis function expansion effectively models sources which span local regions of cortex and occupy specific frequency bands and/or time windows. This model of neural activity leads naturally to a Bayesian likelihood function which balances the model fit to the data with the complexity of the model, where the complexity is related to the number of included events. A novel Expectation-Maximization algorithm which maximizes the likelihood function is presented. The new method is shown to be effective on several MEG simulations of neurological activity as well as data from a self-paced finger tapping experiment.

One wonders if a compressed sensing implementation could then be simply implemented using Open Source EEG and the addition rule presented in Sensor Networks.


* In Astronomy, the CLEAN and the CLEANEST algorithms are known to not be optimal but are the best tools available so far. Sebastien Bourguignon, Hervé Carfantan and Torsten Böhm tried to improve on this current algorithms by using sparsity in SparSpec : a new method for fitting multiple sinusoids with irregularly sampled data, the abstract reads:

Context. The location of pure frequencies in the spectrum of an irregularly sampled time series is an important topic in astrophysical data analysis. Especially in the domain of asteroseismology, a highly precise and unambiguous study of frequencies in photometric light or radial velocity curves is required.
Aims. Due to sampling irregularities and large observational gaps, the classic methods for frequency estimation (prewhitening techniques, clean, cleanest, etc.) sometimes suffer false detections. We propose a new framework for this problem that allows a more
precise and unambiguous frequency location.
Methods. Multisine fitting is addressed as the sparse representation of the data in an overcomplete dictionary of frequencies, hence the name SparSpec for the method. We model the data as the sum of an arbitrarily large number of pure frequencies, discretised on a fixed grid. Among all the many representations fitting the data, we seek the one with the fewest non-zero amplitudes. This solution can be computed by minimising a convex criterion with no local minima. A computationally efficient and convergent optimisation strategy is derived and a user-friendly software implementing SparSpec is provided online at http://www.ast.obs-mip.fr/Softwares.
Results. The method is first illustrated on a simple test example where SparSpec correctly locates the frequencies while classic methods fail. Then, simulations on more realistic artificial time series reveal the interest of this new methodology in terms of robustness toward sampling aliases. An application to the radial velocity curve of the pre-main sequence Herbig Ae star HD104237 is finally presented, where the method is able to determine oscillation frequencies even in the presence of strong low-frequency perturbations such as orbital movements. While SparSpec mainly confirms previously published studies for the four more important frequencies, it suggests some ambiguity about the position of a fifth frequency. Additional simulations show that the SparSpec results are more plausible.

What are the signs that you could be scatter brained ? you are drowning in a collision of acronyms: This time it is STS - space-time sparse, Space Transportation System, Superior Temporal Sulcus.

Monday Morning Algorithm 9: Implementation of Sparse Measurement Matrices for Compressive Sampling

Ok, so it's not Monday, at least I thought about the algorithm on Monday Morning so there. Last week I mentioned the work of Radu Berinde and Piotr Indyk on Sparse Recovery Using Sparse Random Matrices ( an older version of this paper is here). Since this is a potentially ground breaking work with regards to the hardware implementation of Compressive Sampling, I decided to implement a non-optimized version of the measurement matrix construction of the paper. As usual if you find a mistake please let me know. Also all the codes produced in the Monday Morning Algorithm Series can be found here.

clear
% Algorithm implementing the Sparse Measurement Matrix
% construction of Radu Berinde and Piotr Indyk in
% "Sparse Recovery Using Sparse Random Matrices"
% d is the number of ones per column
% m is the number of rows
% n is the number of columns
% generally m should be much less than n
% n is limited by (m,d) or
% factorial(m)/(factorial(d)*factorial(m-d))
% Written by Igor Carron
d=3
% m rows
m=5;
% n columns
n=10;
% with these parameters it works with n=10
% but it does not work with n greater than 10
A=zeros(m,n);
jj = 0;
for i=1:n
while sum(A(:,i),1)~=d | jj==47
jj=0;
A(:,i)=zeros(m,1);
for j=1:d
A(round((m-1)*rand(1,1))+1,i)=1;
end
v1 = diag(A(:,i))'*ones(m,n);
w = A - v1;
for j=1:i-1
if w(:,j)== zeros(m,1)
jj = 47;
end
end
end
end
% Measurement Matrix is A

Some people might think there is an error in j = 47, they think it is j =42. They are wrong. Also while this is a binary matrix, it can be used with non-binary objects. [ Update: I have made it a function and it is available here. It is working as nicely as the normal measurement matrices on the example set I used it on].

Credit Photo: NASA/JPL/ Space Science Institute, Saturn and Titan on June 9, 2006.

Compressed Sensing: Can we do Source Separation with Compressed Measurements ?

While Blind Source Separation can use sparsity in order to decompose signals in high dimensions, one wonders how this relates to Compressed Sensing /Compressive Sampling. Compressed Sensing is enabled by Sparsity and one then wonders how sampling could take advantage of that and provide the ability to solve the blind source separation problem.

A first step in that direction is taken by Thomas Blumensath and Mike Davies in Compressed Sensing and Source Separation

Separation of underdetermined mixtures is an important problem in signal processing that has attracted a great deal of attention over the years. Prior knowledge is required to solve such problems and one of the most common forms of structure exploited is sparsity. Another central problem in signal processing is sampling. Recently, it has been shown that it is possible to sample well below the Nyquist limit whenever the signal has additional structure. This theory is known as compressed sensing or compressive sampling and a wealth of theoretical insight has been gained for signals that permit a sparse representation. In this paper we point out several similarities between compressed sensing and source separation. We here mainly assume that the mixing system is known, i.e. we do not study blind source separation. With a particular view towards source separation, we extend some of the results in compressed sensing to more general overcomplete sparse representations and study the sensitivity of the solution to errors in the mixing system.

Credit photo: NASA/JPL , Titan's South Pole on December 20th, 2007.