CS: Brain TF, Sampling subspaces, MRFM, Wideband Signal Acquisition Receivers, Fine Grained Processor Performance Monitoring.

Have you ever wondered how the transfer function between the brain electrical circuitry and the rest of the sensorimotor system of the body was evaluated ? You can have a sense of how this calibration is done in the following video on a surgery performed on a Parkinson's patient and how simple movements can be seen in the EEG like readings in the brain. It looks as though, only specific parts of the brain are responsible for specific movements. Hmmm, it looks like this technique could be improved by some blind sparse deconvolution and this is also a clear (at least to me) sign that a compressive EEG system should not be difficult to build for a Brain-Computer Interface.

Oh well, let us go back to the new findings on the interwebs. I found the following potentially important paper on arxiv: Sampling and reconstructing signals from a union of linear subspaces by Thomas Blumensath. The abstract reads:

In this note we study the problem of sampling and reconstructing signals which are assumed to lie on or close to one of several subspaces of a Hilbert space. Importantly, we here consider a very general setting in which we allow infinitely many subspaces in infinite dimensional Hilbert spaces. This general approach allows us to unify many results derived recently in areas such as compressed sensing, affine rank minimisation and analog compressed sensing. Our main contribution is to show that a conceptually simple iterative projection algorithms is able to recover signals from a union of subspaces whenever the sampling operator satisfies a bi-Lipschitz embedding condition. Importantly, this result holds for all Hilbert spaces and unions of subspaces, as long as the sampling procedure satisfies the condition for the set of subspaces considered. In addition to recent results for finite unions of finite dimensional subspaces and infinite unions of subspaces in finite dimensional spaces, we also show that this bi-Lipschitz property can hold in an analog compressed sensing setting in which we have an infinite union of infinite dimensional subspaces living in infinite dimensional space.

While I was looking at the most recent entries on the Rice Compressive Sensing site, I noticed that I probably left out some recent entries. Here they are:

On the incoherence of noiselet and Haar bases by Tomas Tuma, Paul Hurley. The abstract reads:

Noiselets are a family of functions completely uncompressible using Haar wavelet analysis. The resultant perfect incoherence to the Haar transform, coupled with the existence of a fast transform has resulted in their interest and use as a sampling basis in compressive sampling. We derive a recursive construction of noiselet matrices and give a short matrix-based proof of the incoherence.

On the Applicability of Compressive Sampling in Fine Grained Processor Performance Monitoring by Tomas Tuma, Sean Rooney, Paul Hurley. The abstract reads:

Real-time performance analysis of processor behaviourr equires the efficient gathering of micro-architecturalinformation from processor cores. Such information can beexpected to be highly structured allowing it to be compressed, but the computational burden of conventional compression techniques exclude their use in this environment. We consider the use of new mathematical techniques that allow a signal to be compressed and recovered from a relatively small number of samples. These techniques, collectively termed Compressive Sampling, are asymmetric in that compression is simple, but recovery is complex. This makes them appropriate for applications in which the simplicity of the sensor can be offset against complexity at the ultimate recipient of the sensed information. We evaluate the practicality of using such techniques in the transfer of signals representing one or more micro-architectural counters from a processor core. We show that compressive sampling is usable to recover such performance signals, evaluating the trade-off between efficiency, accuracy and practicability within its various variants.

Bayesian orthogonal component analysis for sparse representation by Nicolas Dobigeon, Jean-Yves Tourneret. The abstract reads:

This paper addresses the problem of identifying a lower dimensional space where observed data can be sparsely represented. This under-complete dictionary learning task can be formulated as a blind separation problem of sparse sources linearly mixed with an unknown orthogonal mixing matrix. This issue is formulated in a Bayesian framework. First, the unknown sparse sources are modeled as Bernoulli-Gaussian processes. To promote sparsity, a weighted mixture of an atom at zero and a Gaussian distribution is proposed as prior distribution for the unobserved sources. A non-informative prior distribution defined on an appropriate Stiefel manifold is elected for the mixing matrix. The Bayesian inference on the unknown parameters is conducted using a Markov chain Monte Carlo (MCMC) method. A partially collapsed Gibbs sampler is designed to generate samples asymptotically distributed according to the joint posterior distribution of the unknown model parameters and hyperparameters. These samples are then used to approximate the joint maximum a posteriori estimator of the sources and mixing matrix. Simulations conducted on synthetic data are reported to illustrate the performance of the method for recovering sparse representations. An application to sparse coding on under-complete dictionary is finally investigated.

Hierarchical Bayesian Sparse Image Reconstruction With Application to MRFM by Nicolas Dobigeon, Alfred O. Hero, and Jean-Yves Tourneret. The abstract reads:

This paper presents a hierarchical Bayesian model to reconstruct sparse images when the observations are obtained from linear transformations and corrupted by an additive white Gaussian noise. Our hierarchical Bayes model is well suited to such naturally sparse image applications as it seamlessly accounts for properties such as sparsity and positivity of the image via appropriate Bayes priors. We propose a prior that is based on a weighted mixture of a positive exponential distribution and a mass at zero. The prior has hyperparameters that are tuned automatically by marginalization over the hierarchical Bayesian model. To overcome the complexity of the posterior distribution, a Gibbs sampling strategy is proposed. The Gibbs samples can be used to estimate the image to be recovered, e.g., by maximizing the estimated posterior distribution. In our fully Bayesian approach, the posteriors of all the parameters are available. Thus, our algorithm provides more information than other previously proposed sparse reconstruction methods that only give a point estimate. The performance of the proposed hierarchical Bayesian sparse reconstruction method is illustrated on synthetic data and real data collected from a tobacco virus sample using a prototype MRFM instrument.

Application of Compressive Sensing to the Design of Wideband Signal Acquisition Receivers by John Treichler, Mark Davenport, Richard Baraniuk. The abstract reads:

Compressive sensing (CS) exploits the sparsity present in many signals to reduce the number of measurements needed for digital acquisition. With this reduction would come, in theory, commensurate reductions in the size, weight, power consumption, and/or monetary cost of both signal sensors and any associated communication links. This paper examines the use of CS in environments where the input signal takes the
form of a sparse combination of narrowband signals of unknown frequencies that appear anywhere in a broad spectral band. We formulate the problem statement for such a receiver and establish a reasonable set of requirements that a receiver should meet to be practically useful. The performance of a CS receiver for this application is then evaluated in two ways: using the applicable (and still evolving) CS theory and using a set of computer simulations carefully constructed to compare the CS receiver against the performance expected from a conventional implementation. This sets the stage for work in a sequel that will use these results to produce comparisons of the size, weight, and power consumption of a CS receiver against an exemplar of a conventional design.

On Support Sizes of Restricted Isometry Constants by Jeffrey D. Blanchard, Andrew Thompson. The abstract reads:

A generic tool for analyzing sparse approximation algorithms is the restricted isometry property (RIP) introduced by Candes and Tao. For qualitative comparison of sufficient conditions derived from an RIP analysis, the support size of the RIP constants is generally reduced as much as possible with the goal of achieving a support size of twice the sparsity of the target signal. Using a quantitative comparison via phase transitions for Gaussian measurement matrices, three examples from the literature of such support size reduction are investigated. In each case, utilizing a larger support size for the RIP constants results in a sufficient condition for exact sparse recovery satised, with high probability, by a significantly larger subset of Gaussian matrices.

There following paper is available behind a paywall. The application of compressed sensing for photo-acoustic tomography by Provost J, Lesage F. The abstract reads:

Photo-acoustic (PA) imaging has been developed for different purposes, but recently, the modality has gained interest with applications to small animal imaging. As a technique it is sensitive to endogenous optical contrast present in tissues and, contrary to diffuse optical imaging, it promises to bring high resolution imaging for in vivo studies at midrange depths (3-10 mm). Because of the limited amount of radiation tissues can be exposed to, existing reconstruction algorithms for circular tomography require a great number of measurements and averaging, implying long acquisition times. Time-resolved PA imaging is therefore possible only at the cost of complex and expensive electronics. This paper suggests a new reconstruction strategy using the compressed sensing formalism which states that a small number of linear projections of a compressible image contain enough information for reconstruction. By directly sampling the image to recover in a sparse representation, it is possible to dramatically reduce the number of measurements needed for a given quality of reconstruction.

CS: Why Gabor Frames? , Compressive Inverse Scattering II, Compressed Counting, OBIC measurements

I just found the following interesting paper on arxiv: Why Gabor Frames? Two Fundamental Measures of Coherence and their Geometric Significance by Waheed Bajwa, Robert Calderbank, and Sina Jafarpour. The abstract reads:

In the standard compressed sensing paradigm, the N ×C measurement matrix is required to act as a near isometry on all k-sparse signals. This is the Restricted Isometry Property or k-RIP. It is known that certain probabilistic processes generate measurement or sensing matrices that satisfy k-RIP with high probability. However, no polynomial-time algorithm is known for verifying that a sensing matrix with the worst-case coherence μ satisfies k-RIP with k greater than μ^(−1). In contrast, this paper provides simple conditions that, when satisfied, guarantee that a deterministic sensing matrix acts as a near isometry on all but an exponentially small fraction of k-sparse signals. These conditions are defined in terms of the worst-case coherence μ and the expected coherence \nu among the columns of the measurement matrix. Under the assumption that C \ge N^2 and \nu \le N^(−1), the sparsity level k is determined by μ^(−2), while the fraction of “bad” k-sparse signals is determined by \nu^(−2) and μ^(−2). In contrast to the k-RIP condition, these conditions are also extremely easy to check. Applying these conditions to Gabor frames shows that it is possible to successfully recover k-sparse signals for k = O(μ^(−2)). In particular, this implies that Gabor frames generated from the Alltop sequence can successfully recover all but an exponentially small fraction of k-sparse signals for k = O(N).

These might be a little old ( a month or two old)

Compressive Inverse Scattering II. SISO Measurements with Born scatterers by Albert Fannjiang. The abstract reads:

Inverse scattering methods capable of compressive imaging are proposed and analyzed. The methods employ randomly and repeatedly (multiple-shot) the single-input-single-output (SISO) measurements in which the frequency, the chosen incidence and the sampling angle are related in a precise way and are capable of recovering exactly (point of extended) scatterers of sufficiently low sparsity.
For point targets, various sampling techniques are proposed to transform the scattering matrix into the random Fourier matrix. Two schemes are particularly interesting: The first one employs multiple frequencies with the sampling angle always in the back-scattering direction resembling the synthetic aperture (SA) imaging; the second employs only single frequency with the sampling angle in the (nearly) forward scattering direction in the high frequency limit, resembling that of the X-ray tomography. For extended targets, the Littlewood-Paley basis is used in analysis. A specially designed sampling scheme then transforms the scattering matrix into a block-diagonal matrix with each block being the random Fourier matrix corresponding to one of the multiple dyadic scales of the extended target. In other words by the Littlewood-Paley basis and the proposed sampling scheme the different dyadic scales of the target are decoupled and therefore can be reconstructed scale-by-scale by the proposed method.

Estimating Entropy of Data Streams Using Compressed Counting by Ping Li. The abstract reads:

The1 Shannon entropy is a widely used summary statistic, for example, network traffic measurement, anomaly detection, neural computations, spike trains, etc. This study focuses on estimating Shannon entropy of data streams. It is known that Shannon entropy can be approximated by R´enyi entropy or Tsallis entropy, which are both functions of the th frequency moments and approach Shannon entropy as  ! 1. Compressed Counting (CC)[24] is a new method for approximating the th frequency moments of data streams. Our contributions include:
• We prove that R´enyi entropy is (much) better than Tsallis entropy for approximating Shannon entropy.
• We propose the optimal quantile estimator for CC, which considerably improves
the estimators in [24].
• Our experiments demonstrate that CC is indeed highly effective in approximating
the moments and entropies. We also demonstrate the crucial importance of utilizing the variance-bias trade-off.

and On the Sample Complexity of Compressed Counting by the same author.

I also found the following on the interwebs (no link to the main paper):

OBIC measurements without lasers or raster-scanning based on compressive sensing by T. Sun, G. L. Woods, Marco Duarte, Kevin Kelly, C. Li, and Yin Zhang. The abstract reads:

Laser-based failure-analysis techniques such as optical beam- induced current (OBIC) or optical beam-induced resistance change (OBIRCH) involve scanning a focused laser beam across a sample by means of a laser scanning microscope (LSM). In this paper, we demonstrate a new method of obtaining OBIC data without requiring a laser or an LSM. Instead, we employ new techniques from the field of compressive sensing (CS). We use an incoherent light source and a spatial light modulator in an image plane of the device under test, supplying a series of pseudo-random on/off illumination patterns (structured illumination) and recording the resulting electrical (photocurrent) signals from the device. Advanced algorithms allow us to reconstruct the signal for the entire die. We present results from OBIC measurements on a discrete transistor and discuss extensions of CS techniques to OBIRCH. We also demonstrate static emission images obtained using CS techniques in which the incoherent light source is replaced with a single-element infrared photon detector so that no detector array is required.

CS: Democracy in Action, Compressed Sensing for MIMO radar, TV Theorem for Compressed Sensing Based Interior Tomography

Today we have three papers:

Compressed Sensing for MIMO radar - Algorithms and Performance by Thomas Strohmer and Benjamin Friedlander. The abstract reads:

Compressed sensing techniques make it possible to exploit the sparseness of radar scenes to potentially improve system performance. In this paper compressed sensing tools are applied to MIMO radar to reconstruct the scene in the azimuth-range-Doppler domain. Conditions are derived for the radar waveforms and the transmit and receive arrays so that the radar sensing matrix has small coherence and sparse recovery becomes possible. Theoretical performance bounds are presented and validated by numerical simulations.

A General Total Variation Minimization Theorem for Compressed Sensing Based Interior Tomography by Weimin Han, Hengyong Yu, and Ge Wang. The abstract reads:

Recently, in the compressed sensing framework we found that a two-dimensional interior region-of-interest (ROI) can be exactly reconstructed via the total variation minimization if the ROI is piecewise constant (Yu and Wang, 2009). Here we present a general theorem charactering a minimization property for a piecewise constant function defined on a domain in any dimension. Our major mathematical tool to prove this result is functional analysis without involving the Dirac delta function, which was heuristically used by Yu and Wang (2009).

and finally from the Rice Compressive Sensing repository we have:

Democracy in Action: Quantization, Saturation, and Compressive Sensing by Jason Laska, Petros Boufounos, Mark Davenport, and Richard Baraniuk. The abstract reads:

Recent theoretical developments in the area of compressive sensing (CS) have the potential to significantly extend the capabilities of digital data acquisition systems such as analog to digital converters and digital imagers in certain applications. A key hallmark of CS is that it enables sub-Nyquist sampling for signals, images, and other data. In this paper, we explore and exploit another heretofore relatively unexplored hallmark, the fact that certain CS measurement systems are democratic, which means that each measurement carries roughly the same amount of information about the signal being acquired. Using the democracy property, we re-think how to quantize the compressive measurements in practical CS systems. If we were to apply the conventional wisdom gained from conventional Shannon-Nyquist uniform sampling, then we would scale down the analog signal amplitude (and therefore increase the quantization error) to avoid the gross saturation errors that occur when the signal amplitude exceeds the quantizer’s dynamic range. In stark contrast, we demonstrate that a CS system achieves the best performance when it operates at a significantly nonzero saturation rate. We develop two methods to recover signals from saturated CS measurements. The first directly exploits the democracy property by simply discarding the saturated measurements. The second integrates saturated measurements as constraints into standard linear programming and greedy recovery techniques. Finally, we develop a simple automatic gain control system that uses the saturation rate to optimize the input gain.

Image Credit: NASA/JPL/Space Science Institut, Saturn's photo was taken on November 15, 2009 and received on Earth November 16, 2009.

CS: Inline hologram reconstruction with sparsity constraints, Reading the Book of Memory:

Responding to a request I made yesterday, one of the reader of this blog kindly sent me an invitation for Google Wave. However it looks like Google has a waiting list even for that so I have not received anything. Google, when a party sends an invitation, what is really important is not the sending, it is the receiving of that invitation by the second party that makes it an invitation. The process reminds me of the rental reservation process as experienced by Seinfeld.

In a recent entry, I mentioned the following paper A simple proof that random matrices are democratic but forgot to mention Mark Davenport from the list of authors. This has been fixed.

If you want to be added to the Compressive Sensing list of Twitter, please let me know.

Thanks to Andy for suggesting a replacement to Google Wave called ShowDocument and thanks to Laurent Jacques for mentioning different elements of response to Danny Bickson's question on Seeking CS data where the signal prior is not sparse or noise is non-gaussian. If you have answers to his question you are welcome to contribute.


In his blog, David Brady mentions this paper on compressive holography entitled: Inline hologram reconstruction with sparsity constraints by Loic Denis, Dirk Lorenz, Eric Thiebaut, Corinne Fournier, and Dennis Trede. The abstract reads:

Inline digital holograms are classically reconstructed using linear operators to model diraction. It has long been recognized that such reconstruction operators do not invert the hologram formation operator. Classical linear reconstructions yield images with artifacts such as distortions near the field-of-view boundaries or twin-images. When objects located at dierent depths are reconstructed from a hologram, in-focus and out-of-focus images of all objects superimpose upon each other. Additional processing, such as maximum-of-focus detection, is thus unavoidable for any successful use of the reconstructed volume. In this letter, we consider inverting the hologram formation model in Bayesian framework. We suggest the use of a sparsity-promoting prior, verified in many inline holography applications, and present a simple iterative algorithm for 3D object reconstruction under sparsity and positivity constraints. Preliminary results with both simulated and experimental holograms are highly promising.

Finally, on Twitter, Suresh Venkatasubramanian mentions two items of interest:

• a Junior Professorship (W1) „Bioinformatics for High Throughput Technologies“ and
• The Human Connectome Project

The first item related to the work in group testing and its relationship to compressive sensing while the second items connects to a paper I was reading at about the time I saw the tweet, namely Reading the Book of Memory: Sparse Sampling versus Dense Mapping of Connectomes by H. Sebastian Seung. It is an interesting paper as it brings to light the necessary methods to do a better job of understanding the brain connectivity. The abstract reads:

Many theories of neural networks assume rules of connection between pairs of neurons that are based on their cell types or functional properties. It is finally becoming feasible to test such pairwise models of connectivity, due to emerging advances in neuroanatomical techniques. One method will be to measure the functional properties of connected pairs of neurons, sparsely sampling pairs from many specimens. Another method will be to find a ‘‘connectome,’’ a dense map of all connections in a single specimen, and infer functional properties of neurons through computational analysis. For the latter method, the most exciting prospect would be to decode the memories that are hypothesized to be stored in connectomes.

CS: Several Initiatives

In random order here are a list of items that have been started or are in my mind:

I want to start a series of post entitled "These Technologies Do Not Exist" which will feature technologies that do not exist yet and which could be enabled by compressive sensing if they were investigated in-depth. The idea is that most funding agencies do fund mostly incremental technologies and that sometimes there is a need for researchers to go beyond being part of the 10% improvement business. If you have one of those ideas and feel it is OK to give it to the world, then by all means contact me for inclusion in the series.

Twitter has created a list feature recently. I put together a list of people that have declared an interest in Compressive Sensing, have read the blog or even published in the field, it is at:

http://twitter.com/#/list/igorcarron/compressed-sensing

Please realize this is not a list of people talking about compressive sensing all the time, rather a community of like minded spirits.

I want to expand a little bit the Big Picture page as they are clearly some areas that are more vigorous than others, I am thinking about including a blurb about:

• Matrix completion
• Non-Gaussian related issues as asked by Danny Bickson
• Positive signals
• RIP/NSP issues
• others ?
  

If anybody wants to help, you'll be duly credited in the page on your effort as usual.

I am considering starting a project dedicated to producing a compressive sensing EEG system for the purpose of doing very cheap BCI (Brain-Computer Interface). For that I think I need a Google wave account and have the ability to invite people (have Google Wave invites as well) since otherwise the concept is pretty moot. For the Googlers reading this blog and who have the means to make this happen, it's a hint.

Finally, because of different circumstances I am thinking aloud about starting a company dealing with incoherent systems which you might guess rightly has something to do with the subject area covered here.

Credit: ESA, View of the Earth by the Rosetta Spacecraft on its third Earth gravity assist maneuver.

CS: Seeking CS data where the signal prior is not sparse or noise is non-gaussian

Danny Bickson, a reader of this blog, asks the following interesting question:

Does anyone have/know of measurement data which captures signals with either non-gaussian noise, skewed noise, skewed signal prior, or non-unimodal signal (signal has several peeks not just at zero). Most of the works until now, assume sparse signal, so a Laplacian prior captures sparsity very well.

I initially replied that an answer could include most datasets that depends on power-laws (not strictly sparse) such as natural images but this is obviously not what Danny is after. There are also datasets coming out of hyperspectral work photon counting follows Poisson distribution (see for instance: Performance bounds on compressed sensing with Poisson noise by Rebecca Willett and Maxim Raginsky). This happens not just in hyperspectral work as other types of radiation (i.e. radioactive decay for instance,...) would also fall in that category, but I know of no CS radiation sensing system other than those for photons so far. In a different direction , there are different kinds of noises as well as shown in General Deviants: An Analysis of Perturbations in Compressed Sensing by Matthew A. Herman and Thomas Strohmer, the authors talk about a multiplicative noise and how it relates to the physics studied in different areas:

....It is important to consider this kind of noise since it can account for precision errors when applications call for physically implementing the measurement matrix A in a sensor. In other CS scenarios, such as when A represents a system model, E can absorb errors in assumptions made about the transmission channel. This can be realized in radar [7], remote sensing [8], telecommunications, source separation [5], [6], and countless other problems....

as Matt later explained here:

It is important to consider perturbations to the measurement matrix A since the physical implementation of sensors is never perfect in the real world (thus the matrix E can represent precision errors or other non-ideal phenomena). Viewed in a different way, the matrix A can also model a channel that a signal passes through such as in radar, telecommunications, or in source separation problems. The models of these types of channels always involve assumptions and/or approximations of their physical characteristics. In that way, the matrix E can absorb errors in these assumptions. Factors such as these must be accounted for in real-world devices.

Finally, the only bimodal priors I have ever seen were in sensorimotor studies [2] and they were used to see how humans could learn them and how sleep was essential in that learning process:

It could be that subjects need a consolidation period to adequately learn the distribution. Such improvements in learning contingent upon sleep have also been observed in visual learning [7].

But I am not sure this really fit what Danny was asking for and beyond these examples, I am a little bit at loss. Can any expert help ?




While we are on the subject, Aaron Clauset mentioned that his paper on power laws [1] has finally been accepted in SIAM review. I note from his blog entry the following:

Here's a brief summary of the 24 data sets we looked at, and our conclusions as to how much statistical support there is in the data for them to follow a power-law distribution:

Good:
frequency of words (Zipf's law)

Moderate:
frequency of bird sightings
size of blackouts
book sales
population of US cities
size of religions
severity of inter-state wars
number of citations
papers authored
protein-interaction degree distribution
severity of terrorist attacks

With an exponential cut-off:
size of forest fires
intensity of solar flares
intensity of earthquakes (Gutenberg-Richter law)
popularity of surnames
number of web hits
number of web links, with cut-off
Internet (AS) degree distribution
number of phone calls
size of email address book
number of species per genus

None:
HTTP session sizes
wealth
metabolite degree distribution

One should note that while power-laws are interesting for the purpose of spotting phenomena with potentially sparse sets (larger probability elements dominating the counting process and lower probability elements being compared to noise with the same counting process), those phenomena who do not follow power laws can evidently produce population of sparse sets as well. In the end, we are left with whether a CS counting process would be more appropriate than a more conventional counting process.


[1] Power-law distributions in empirical data by Aaron Clauset, Cosma Rohilla Shalizi, M. E. J. Newman
[2] Körding, KP. and Wolpert, D. (2003) Bayesian Integration with Multimodal priors.

CS: An Iteratively Reweighted Algorithm for Sparse Reconstruction of Subsurface Flow Properties from Nonlinear Dynamic Data, wow.

Unless I am mistaken (and this happens often), this is the second paper (the first one was Gradient Pursuit for Non-Linear Sparse Signal Modelling by Thomas Blumensath and Mike Davies, I mentioned it here) that looks at developing a solver for the resolution of a nonlinear inverse problem using sparsity as a constraint: An Iteratively Reweighted Algorithm for Sparse Reconstruction of Subsurface Flow Properties from Nonlinear Dynamic Data by Lianlin Li and Benham Jafarpour. The abstract reads:

In this paper, we present a practical algorithm based on sparsity regularization to effectively solve nonlinear dynamic inverse problems that are encountered in subsurface model calibration. We use an iteratively reweighted algorithm that is widely used to solve linear inverse problems with sparsity constraint known as compressed sensing to estimate permeability fields from nonlinear dynamic flow data.

From the beginning of the paper:

A challenging problem in predicting fluid flow displacement patterns in subsurface environment is the identification of spatially variable flow-related rock properties such as permeability and porosity. Characterization of subsurface properties usually involves solving a highly underdetermined nonlinear inverse problem where a limited number of measurements are used to reconstruct a large number of unknown parameters. To alleviate the non-uniqueness of the solution, prior information is integrated into the solution. Regularization of ill-posed inverse problems is commonly performed by imparting structural prior assumptions, such as smoothness, on the solution. Since many geologic formations exhibit natural continuity/correlation at various scales, decorrelating their spatial description can lead to a more compact or sparse representation in an appropriate compression transform domain such as wavelets or Fourier domain. The sparsity of flow-related subsurface properties in such incoherent bases has inspired the development of regularization techniques that attempt to solve a better-posed inverse problem in these domains. In this paper, we present a practical algorithm based on sparsity regularization to effectively solve nonlinear dynamic inverse problems that are encountered in subsurface model calibration. We use an iteratively reweighted algorithm that is widely used to solve linear inverse problems with sparsity constraint (known as compressed sensing) to estimate permeability fields from nonlinear dynamic flow data. To this end, we minimize a data misfit cost function that is augmented with an additive regularization term promoting sparse solutions in a Fourier-related discrete cosine transform domain. This regularization approach introduces a new weighting parameter that is in general unknown a priori, but controls the effectiveness of the resulting solutions. Determination of the regularization parameter can only be achieved through considerable numerical experimentation and/or a priori knowledge of the reconstruction solution. To circumvent this problem, we include the sparsity promoting constraint as a multiplicative regularization term which eliminates the need for a regularization parameter. We evaluate the performance of the iteratively reweighted approach with multiplicative sparsity regularization using a set of water flooding experiments in an oil reservoir where we use nonlinear dynamic flow data to infer the spatial distribution of rock permeabilities, While, the examples of this paper are derived from the subsurface flow and transport application, the proposed methodology also can be used in solving nonlinear inverse problems with sparsity constraints in other imaging applications such as geophysical, medical imaging, electromagnetic and acoustic inverse problems.

The replacement of the generic regularization parameter with something that is part of the physical phenomena being modeling is truly innovative. Lianlin also tells me that the genesis of the meeting with Benham Jafarpour started with him reading Nuit Blanche. Wow.

CS: New Bounds for RICs, Stable Recovery of Sparse Signals, Shifting Inequality and Recovery of Sparse Signals, Super-Resolution, OPTSPACE, PARNES

Recently, the NESTA reconstruction solver was updated to version 1.0. Today, we are presented with a reconstruction solver that aims at merging the good parts of both SPGL1 and NESTA in a potentially more rapid and robust solver called PARNES and introduced in PARNES: A rapidly convergent algorithm for accurate recovery of sparse and approximately sparse signals by Ming Gu, Lek-Heng Lim, Cinna Julie Wu. The abstract reads:

In this article we propose an algorithm, PARNES, for the basis pursuit denoise problem which approximately finds a minimum one-norm solution to an underdetermined least squares problem. PARNES, (1) combines what we think are the best features of currently available methods SPGL1 and NESTA, and (2) incorporates a new improvement that exhibits linear convergence under the assumption of the restricted isometry property (RIP). As with SPGL1, our approach 'probes the Pareto frontier' and determines a solution to the BPDN problem by exploiting its relation between the LASSO problem as given by their Pareto curve. As with NESTA we rely on the accelerated proximal gradient method proposed by Yu. Nesterov that takes a remarkable O((L/e)^1/2) iterations to come within e > 0 of the optimal value, where L is the Lipschitz constant of the gradient of the objective function. Furthermore we introduce an 'outer loop' that regularly updates the prox center. Nesterov's accelerated proximal gradient method then becomes the 'inner loop'. The restricted isometry property together with the Lipschitz differentiability of our objective function permits us to derive a condition for switching between the inner and outer loop in a provably optimal manner. A by-product of our approach is a new algorithm for the LASSO problem that also exhibits linear convergence under RIP.

The paper shows a comparison with some of the fastest code available (all of them, except for FISTA can be found on the reconstruction section of the Big Picture in Compressive Sensing). Lek-Heng tells me that an implementation of the code will be released as soon as the code is cleaned up and some improvements are made.

Also found on the internets: New Bounds for Restricted Isometry Constants by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

In this paper we show that if the restricted isometry constant \delta k of the compressed sensing matrix satisfies \delta_k < deltak ="(">

and Stable Recovery of Sparse Signals and an Oracle Inequality by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

This article considers sparse signal recovery in the presence of noise. A mutual incoherence condition which was previously used for exact recovery in the noiseless case is shown to be sufficient for stable recovery in the noisy case. Both bounded noise and Gaussian noise settings are considered. Furthermore, the condition is shown to be sharp. In addition, an oracle inequality is given under the mutual incoherence condition.

and finally the same authors have found a weaker condition than the traditional RIP in Shifting Inequality and Recovery of Sparse Signals by T. Tony Cai, Lie Wang, Guangwu Xu. The abstract reads:

In this paper we present a concise and coherent analysis of the constrained l1 minimization method for stable recovering of high-dimensional sparse signals both in the noiseless case and noisy case. The analysis is surprisingly simple and elementary, while leads to strong results. In particular, it is shown that the sparse recovery problem can be solved via l1 minimization under weaker conditions than what is known in the literature. A key technical tool is an elementary inequality, called Shifting Inequality, which, for a given nonnegative decreasing sequence, bounds the l2 norm of a subsequence in terms of the l1 norm of another subsequence by shifting the elements to the upper end.

In a different direction, we have: Super-Resolution and Reconstruction of Sparse Sub-Wavelength Images by Snir Gazit, Alexander Szameit, Yonina Eldar, Mordechai Segev. The abstract reads:

We use compressed sensing to demonstrate theoretically the reconstruction of sub-wavelength features from measured far-field, and provide experimental proof-of-concept. The methods can be applied to non-optical microscopes, provided the information is sparse.

and in the matrix completion area: OPTSPACE: A Gradient Descent Algorithm on the Grassman Manifold for Matrix Completion by by Raghunandan Keshavan, Andrea Montanari and Sewoong Oh. The abstract reads:

We consider the problem of reconstructing a low-rank matrix from a small subset of its entries. In this paper, we describe the implementation of an efficient algorithm called OptSpace, based on singular value decomposition followed by local manifold optimization, for solving the low-rank matrix completion problem. It has been shown that if the number of revealed entries is large enough, the output of singular value decomposition gives a good estimate for the original matrix, so that local optimization reconstructs the correct matrix with high probability. We present numerical results which show that this algorithm can reconstruct the low rank matrix exactly from a very small subset of its entries. We further study the robustness of the algorithm with respect to noise, and its performance on actual collaborative filtering datasets.

As mentioned earlier, the OPTSPACE code can be found here.

CS: Separable imagers, Compressed Imaging with a Separable Sensing Operator, Calibration issues of CS systems, Expander-based Compressed Sensing

As you probably recall (see here), one of the main issue with the Random Lens Imager, a system I consider to be a truly innovative Compressive Sensing system, is the amount of time spent in the calibration process. For what it's worth, I note that it's been nearly three years now since the report has been out but has, to my limited knowledge, not been published. Which makes me wonder sometimes about how truly innovative approaches have real difficulty making it into the literature.

In a presentation by Yair Rivenson and Adrian Stern on An Efficient Method for Multi-Dimensional Compressive Imaging, one can see the problem being expressed in plain words:

and how their approach (using separable sensing systems) can reduce that burden. The price to pay for not spending years in the calibration process seems to be more than a fair one:

The authors also want to use that type of approaches for r-dimensional signals where r is above 2.

A more in-depth explanation of the presentation's results can be found in Compressed Imaging with a Separable Sensing Operator by Yair Rivenson and Adrian Stern. The abstract reads:

Compressive imaging (CI) is a natural branch of compressed sensing (CS). Although a number of CI implementations have started to appear, the design of efficient CI system still remains a challenging problem. One of the main difficulties in implementing CI is that it involves huge amounts of data, which has far-reaching implications for the complexity of the optical design, calibration, data storage and computational burden. In this paper, we solve these problems by using a twodimensional separable sensing operator. By so doing, we reduce the complexity by factor of 10^6 for megapixel images. We show that applying this method requires only a reasonable amount of additional samples.

Let us recall that we have already seen this approach before ( see the work of Yin Zhang and others like Thong Do and John Sidles (see comments)) but it certainly is a good thing to now see the minimal price to be paid in exchange of this Kronecker product approach to imaging and other systems.

There are really two other ways to reduce that calibration burden of finding what the point spread function (or transfer function for higher dimensional problems) is: One could make the assumption that the measurement matrix is sparse and evaluate this issue as a compressed sensing problem called Blind Deconvolution or use a physical system that implements a sparse measurement system (RIP-1 matrices) such as in the new paper: Expander-based Compressed Sensing in the presence of Poisson Noise by Sina Jafarpour, Rebecca Willett, Maxim Raginsky, Robert Calderbank. The abstract reads:

This paper provides performance bounds for compressed sensing in the presence of Poisson noise using expander graphs. The Poisson noise model is appropriate for a variety of applications, including low-light imaging and digital streaming, where the signal-independent and/or bounded noise models used in the compressed sensing literature are no longer applicable. In this paper, we develop a novel sensing paradigm based on expander graphs and propose a MAP algorithm for recovering sparse or compressible signals from Poisson observations. The geometry of the expander graphs and the positivity of the corresponding sensing matrices play a crucial role in establishing the bounds on the signal reconstruction error of the proposed algorithm. The geometry of the expander graphs makes them provably superior to random dense sensing matrices, such as Gaussian or partial Fourier ensembles, for the Poisson noise model. We support our results with experimental demonstrations.

CS: Xampling, Compressive Wide-Band Spectrum Sensing, An unconstrained lq minimization, Random matrices are democratic

From the folks who brought us the Modulated Wideband Converter hardware, here is the design methodology underneath it called Xampling which in effect deals with Compressive Sensing for Analog signals: Xampling -- Part I: Practice by Moshe Mishali, Yonina Eldar and Asaf Elron . The abstract reads:

We introduce Xampling, a design methodology for sub-Nyquist sampling of continuous-time analog signals. The main principles underlying this framework are the ability to capture a broad signal model, low sampling rate, efficient analog and digital implementation and lowrate baseband processing. The main hypothesis of Xampling is that in order to break through the Nyquist barrier, one has to combine classic methods and results from sampling theory together with recent developments from the literature of compressed sensing. In this paper, we present the Xampling framework and examine several sub-Nyquist approaches in light of the four Xampling principles. It is shown that previous methods suffer from analog implementation issues, large computational loads in the digital domain, and have no baseband processing capabilities. An exception is the recently proposed modulated wideband converter (MWC) which satisfies the model, rate and implementation criteria, though lacking the baseband processing capability. Here, we extend the MWC by proposing a digital algorithm which extracts each band of the signal from the compressed measurements, thus enabling lowrate (baseband) processing. The converter with the proposed algorithm conforms with the Xampling desiderata. In addition, we describe two configurations of the converter for efficient spectrum sensing in wideband cognitive radio receivers. In the second part of this work we study theoretical aspects of rate and stability of sub-Nyquist systems, following the pragmatic theme of the Xampling methodology.

At the end of the paper, the author uses the example of the cognitive Radio which eventually led me to the following two papers and thesis: Distributed Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

—We consider a compressive wide-band spectrum sensing scheme for cognitive radio networks. Each cognitive radio (CR) sensing receiver transforms the received analog signal from the licensed system in to a digital signal using an analog-to-information converter. The autocorrelation of the compressed signal is then collected from each CR at a fusion center. A compressive sampling recovery algorithm that exploits joint sparsity is then employed to reconstruct an estimate of the signal spectrum and used to make a decision on signal occupancy. We compare the performance of this distributed compressive spectrum sensing scheme with a compressive spectrum sensing scheme at a single CR and show the performance gains obtained from spatial diversity.

and Compressive Wide-Band Spectrum Sensing by Ying Wang, Ashish Pandharipande, Yvan Lamelas Polo and Geert Leusy. The abstract reads:

We present a compressive wide-band spectrum sensing scheme for cognitive radios. The received analog signal at the cognitive radio sensing receiver is transformed in to a digital signal using an analog-to-information converter. The autocorrelation of this compressed signal is then used to reconstruct an estimate of the signal spectrum. We evaluate the performance of this scheme in terms of the mean squared error of the power spectrum density estimate and the probability of detecting signal occupancy.

And finally, to Yvan Lamelas Polo's thesis entitled: Compressive Wideband Spectrum Sensing for Cognitive Radio Applications with the following abstract:

It has been widely recognized that utilization of radio spectrum by licensed wireless systems, e.g., TV broadcasting, aeronautical telemetry, is quite low. In particular, at any given time and spatial region, there are frequency bands where there is no signal occupancy. There has been recent interest in improving spectrum utilization by permitting secondary usage using cognitive radios. Cognitive radios use spectrum sensing to determine frequency bands that are vacant of licensed signal transmissions and transmit on such portions to meet regulatory constraints of avoiding harmful interference to licensed systems. Future cognitive radios will be capable of scanning a wide band of frequencies, in the order of a few GHz, and employ adaptive waveforms for transmission depending on the estimated spectrum of licensed systems. In this thesis, we address the problem of estimating the spectrum of the wide-band signal received at the cognitive radio sensing receiver using compressive sampling coupled with a multiband spectrum detector to determine the spectrum occupancy of the licensed system. Since individual cognitive radios might not be able to reliably detect weak primary signals due to channel fading/shadowing, we also propose a distributed compressive scheme based on joint recovery of the license occupancy for application scenarios involving geographically distributed radios. In such a distributed approach, the spectrum occupancy is determined by the joint work of cognitive radios (exploiting spatial diversity), as opposed to being determined individually by each cognitive radio.

In a different direction, here is another intriguing paper on a reweighted algorithm dealing with l_q problems: An unconstrained lq minimization for sparse solution of under determined linear systems by Ming-Jun Lai and Jingyue Wang. The abstract reads:

We study an unconstrained version of the ℓq minimization for the sparse solution of under-determined linear systems for 0 \lt q \le 1. Although the minimization is nonconvex, we introduce a regularization and develop an iterative algorithm. We show that the iterative solutions converge to the sparse solution. Numerical experiments will be demonstrated to show that our approach works very well.

I note the following from their paper:

According to our theory, we can completely determine a sparse solution without any conditions, e.g., the restricted isometry property (RIP) on matrix A. This is an another advantage of the ℓq minimization for 0 \lt q \lt 1 over the classic ℓ1 minimization approach.

Their algorithm looks like a reweighted scheme and as one can read from the paper, it takes a long time to converge, much like the IRLS scheme. Finally, let us note the success of this algorithm with uniform random matrices.

And finally from the Rice Compressive Sensing Repository we have:

A simple proof that random matrices are democratic by Mark Davenport, Jason Laska, Petros Boufounos, and Richard Baraniuk. The abstract reads:

The recently introduced theory of compressive sensing (CS) enables the reconstruction of sparse or compressible signals from a small set of nonadaptive, linear measurements. If properly chosen, the number of measurements can be significantly smaller than the ambient dimension of the signal and yet preserve the significant signal information. Interestingly, it can be shown that random measurement schemes provide a near-optimal encoding in terms of the required number of measurements. In this report, we explore another relatively unexplored, though often alluded to, advantage of using random matrices to acquire CS measurements. Specifically, we show that random matrices are democractic, meaning that each measurement carries roughly the same amount of signal information. We demonstrate that by slightly increasing the number of measurements, the system is robust to the loss of a small number of arbitrary measurements. In addition, we draw connections to oversampling and demonstrate stability from the loss of significantly more measurements.

CS: Compressive Confocal Microscope, Compressive Matched Subspace Detection, Music Classification, Matrix Completion, Metric Learning

Before we get to the meat of today's entry, let me invite y'all to use the customized search engine on the right hand side of this blog to search for entries relevant to your area of interest. The search feature on the top left corner of this blog is buggy at best and does not do a good job of finding relevant entries when you are using only one word. Also, of related interest, I am seeking a Google Wave invite as I am interested to see if one could develop some compressive sensing hardware with some folks of the open hardware community. Irrespective to your ability to send me an Google Wave invite, you are welcome to join that experiment. [Hint to those of you working at Google, I just made a request for an invite]

It seems that I overlooked the work being done by the group of Gonzalo Arce at University of Delaware. I hope to remedy this today. From his group, we have a new compressive sensing hardware, a music classifier, and other relevant studies in between. The hardware first as exposed in : Compressive Confocal Microscopy by Peng Ye, Jose Paredes, Gonzalo Arce, Yichuan Hu , C. Chen, and Dennis Prather.The abstract reads:

In this paper, a new framework for confocal microscopy based on the novel theory of compressive sensing is proposed. Unlike wide field microscopy or conventional parallel beam confocal imaging systems that use charge-coupled devices (CCD) as acquisition devices in addition to complex mechanical scanning system, the proposed compressive confocal microscopy is a kind of parallel beam confocal imaging system which exploits the rich theory of compressive sensing by using a single pixel detector and a digital micromirror device (DMD) to capture linear projections of the in-focus image. With the proposed system, confocal imaging of high optical sectioning ability can be achieved at sub-Nyquist sampling rates. Theoretical analysis, simulations and experimental results are shown to demonstrate the characteristics and potential of the proposed approach.

and the attendant reconstruction paper: Compressive Confocal Microscopy: 3D reconstruction algorithms by Peng Ye, Jose Paredes, Yichuan Hu , C. Chen, Gonzalo Arce and Dennis Prather. The abstract reads:

In this paper, a new approach for Confocal Microscopy (CM) based on the framework of compressive sensing is developed. In the proposed approach, a point illumination and a random set of pinholes are used to eliminate out-of-focus information at the detector. Furthermore, a Digital Micromirror Device (DMD) is used to efficiently scan the 2D or 3D specimen but, unlike the conventional CM that uses CCD detectors, the measured data in the proposed compressive confocal microscopy (CCM) emerge from random sets of pinhole illuminated pixels in the specimen that are linearly combined (projected) and measured by a single photon detector. Compared to conventional CM or programmable array microscopy (PAM), the number of measurements needed for nearly perfect reconstruction in CCM is significantly reduced. Our experimental results are based on a testbed that uses a Texas Instruments DMD (an array of 1024£768; 13:68£13:68 ¹m2 mirrors) for computing the linear projections of illuminated pixels and a single photon detector is used to obtain the compressive sensing measurement. The position of each element in the DMD is defined by the compressed sensing measurement matrices. Three dimensional image reconstruction algorithms are developed that exploit the inter-slice spatial image correlation as well as the correlation between different 2D slices. A comprehensive performance comparison between several binary projection patterns is shown. Experimental and simulation results are provided to illustrate the features of the proposed systems.

I'll add it to the Compressive Sensing Hardware page.

From the same group, we also have: Non-Linear Coding for Improved Performance in Compressive Sensing by Yichuan Hu, Zhongmin Wang, Javier Garcia-Frias, and Gonzalo Arce. The abstract reads:

We propose a system based on the combination of compressive sensing and non-linear processing that shows excellent robustness against noise. The key idea is the use of nonlinear mappings that act as analog joint source-channel encoders, processing the compressive sensing measurements proceeding from an analog source and producing continuous amplitude samples that are transmitted directly through the noisy channel. As we will show in our simulation results, the proposed framework is readily applicable in practical systems such as imaging, and clearly outperforms systems based on stand-alone compressive sensing.

and the next two papers focus in the adaptive detection of signals of interest while in the compressed measurement world: Compressive Matched Subspace Detection by Jose Paredes, Zhongmin Wang, Gonzalo Arce and Brian M. Sadler. The abstract reads:

In this paper, matched subspace detectors based on the framework of Compressive Sensing (CS) are developed. The proposed approach, called compressive matched subspace detectors, exploits the sparsity model of the signal-of-interest in the design of the random projection operator. By tailoring the CS measurement matrix (projection operator) to the subspace where the signal-of-interest is known to lie, the compressive matched subspace detectors can effectively capture the signal energy while the interference and noise effects are mitigated at sub-Nyquist rate. The proposed detection approach is particularly suitable for detection of wideband signals that emerge in modern communication systems that demand high-speed ADCs. The performance of the subspace compressive detectors are studied by analytically deriving closed-form expressions for the detection probability and through extensive simulations.

Variable Density Compressive Image Sampling by Zhongmin Wang, Gonzalo Arce and Jose Paredes. The abstract reads:

Compressed sensing (CS) provides an efficient way to acquire and reconstruct natural images from a reduced number of linear projection measurements at sub-Nyquist sampling rates. A key to the success of CS is the design of the measurement ensemble. This paper addresses the design of a novel variable density sampling strategy, where the “a priori” information about the statistical distributions that natural images exhibit in the wavelet domain is exploited. Compared to the current sampling schemes for compressed image sampling, the proposed variable density sampling has the following advantages: 1) The number of necessary measurements for image reconstruction is reduced; 2) The proposed sampling approach can be applied to several transform domains leading to simple implementations. In particular, the proposed method is applied to the compressed sampling in the 2D ordered discrete Hadamard transform (DHT) domain for spatial domain imaging. Furthermore, to evaluate the incoherence of different sampling schemes, a new metric that incorporates the “a priori” information is also introduced. Extensive simulations show the effectiveness of the proposed sampling methods.

Finally, a continuation of the concepts developed in the classification on faces, shows that music is not the same as faces: Music Genre Classification via Sparse Representation of Auditory Temporal Modulations by Yannis Panagakis, Constantine Kotropoulos, Gonzalo Arce. The abstract reads:

A robust music genre classification framework is proposed that combines the rich, psycho-physiologically grounded properties of slow temporal modulations of music recordings and the power of sparse representation-based classifiers. Linear subspace dimensionality reduction techniques are shown to play a crucial role within the framework under study. The proposed method yields a music genre classification accuracy of 91% and 93.56% on the GTZAN and ISMIR2004 Genre dataset, respectively. Both accuracies outperform any reported accuracy ever obtained by state of the art music genre classification algorithms in the aforementioned datasets.

Finally, in a totally unrelated field, we have: Matrix Completion from Power-Law Distributed Samples by Raghu Meka, Prateek Jain, and Inderjit Dhillon. The abstract reads:

The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, [4],[13] and [5] obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem

for more realistic sampling models. Our method is simpler to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easy to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on random instances where the low-rank matrix is sampled according to the prevalent random graph models for complex networks and present promising preliminary results on the Netflix challenge dataset.

and from the same group, the important: Metric and Kernel Learning using a Linear Transformation by Prateek Jain, Brian Kulis, Jason Davis and Inderjit Dhillon. The abstract reads:

Metric and kernel learning are important in several machine learning applications. However, most existing metric learning algorithms are limited to learning metrics over low-dimensional data, while existing kernel learning algorithms are often limited to the transductive setting and do not generalize to new data points. In this paper, we study metric learning as a problem of learning a linear transformation of the input data. We show that for high-dimensional data, a particular framework for learning a linear transformation of the data based on the LogDet divergence can be efficiently kernelized to learn a metric (or equivalently, a kernel function) over an arbitrarily high dimensional space. We further demonstrate that a wide class of convex loss functions for learning linear transformations can similarly be kernelized, thereby considerably expanding the potential applications of metric learning. We demonstrate our learning approach by applying it to large-scale real world problems in computer vision and text mining.

CS: New version of ISD and attendant video tutorials

You probably recall the concept of ISD, a reconstruction solver that uses all measurements available to compute a solution. Well, Wotao Yin just sent me the following:

I put a very clean and simple ISD code at http://www.caam.rice.edu/~optimization/L1/ISD/. It comes with two video tutorials.

Here is extract of what's new in the package:

Version 1.1 (November 3, 2009). [download]

• This version is much simpler and clearer than ver 1.0 below.
• Video tutorials: Demo [online] or [download]; Main code [online] or [download].
• To adapter the code to your data and sparse/compressible signal and for best results, please (i) tune the thresholding methods and parameters, and (ii) consider replacing YALL1 by one designed for your data. The technical report [pdf] describes ideas of effective thresholding.
• Despite the small problems given in the demos, the code is capable of solving large-scale, multi-dimensional problems. Ver 1.0 below includes large-scale tests. The allowed size of the problem is merely subject to the limit posted by the subproblem solver used.
• The main code can be extended to deal with multi-dimensional signals in a straightforward way.

Enjoy !

The Nuit Blanche Effect

When was the last time you knew for a fact that more than 120 people had read the abstract of your paper within a week of releasing it ?





Back in May 2008 at the Nonlinear L1 meeting at Texas A&M University, I suddenly realized the power of the blog when Adam Oberman mentioned to me over lunch with Anna Gilbert and Simon Foucart that he knew of the blog (first surprise, we are in College Station, Texas and somebody has heard of the blog :-)) through a friend who had seen a spike of downloads of his paper after being mentioned here (second surprise!). Ever since that moment I have been trying to quantify this effect which, it seems, has grown over time. If you have stories about this or any other stories connected to the blog (you can stay anonymous), I would be very happy to hear them. Let us note that this number is a conservative one as it does not include the people being directly mailed the blog entries (237 as we speak), nor the people coming directly to the website nor people using another feed than the one listed above (412).

One more note, the first technincal blog entry after that meeting pointed out the need to understand better the RIP (Restricted Isometry Property: What is it good for ?), a subject of continuing interest.

CS: UWB Through-Wall Imaging Based on Compressive Sensing

I picked this up from Lianlin Li's blog ( translation is here): another UWB radar that can detect moving things through walls: UWB Through-Wall Imaging Based on Compressive Sensing by Qiong Huang, Lele Qu, Bingheng Wu, and Guangyou Fang. The abstract reads:

To achieve high-resolution 2-D images, through-wall imaging (TWI) radar with ultra-wideband and long antenna arrays faces considerable technical challenges such as a prolonged data collection time, a huge amount of data, and a high hardware complexity. This paper presents a novel data acquisition scheme and an imaging algorithm for TWI radar based on compressive sensing (CS), which states that a signal having a sparse representation can be reconstructed from a small number of nonadaptive randomized projections by solving a tractable convex program. Instead of measuring all spatial-frequency data, a few samples, by employing an overcomplete dictionary, are sufficient to obtain reliable target space images even at high noise levels. Preliminary simulated and experimental results show that the proposed algorithm outperforms the conventional delay-and-sum beamforming method even though many fewer CS measurements are used.

I am adding this the Compressive Sensing Hardware page.

CS: A Matrix Completion Entry

After Friday's entry on the subject, here some more matrix completion cods and papers:Yi Ma just sent me the following:

You may want to check out our new website dedicated for low-rank matrix recovery and completion at:

http://perception.csl.illinois.edu/matrix-rank/home.html

Matrix recovery (also known as robust PCA) is arguably a more difficult problem that matrix completion and it reveals some nice tradeoff between rank and sparsity. On the website we gather all up to date work on theory, algorithms, and applications (soon). We also provide the code for the fastest algorithms know todate for both matrix recovery and completion.

I note that they list the other matrix completion approaches here.

and then we have: A Simpler Approach to Matrix Completion by Benjamin Recht. The abstract reads:

This paper provides the best bounds to date on the number of randomly sampled entries required to reconstruct an unknown low rank matrix. These results improve on prior work by Candes and Recht, Candes and Tao, and Keshavan, Montanari, and Oh. The reconstruction is accomplished by minimizing the nuclear norm, or sum of the singular values, of the hidden matrix subject to agreement with the provided entries. If the underlying matrix satisfies a certain incoherence condition, then the number of entries required is equal to a quadratic logarithmic factor times the number of parameters in the singular value decomposition. The proof of this assertion is short, self contained, and uses very elementary analysis. The novel techniques herein are based on recent work in quantum information theory.

and Compressed Quantum Process Tomography by Alireza Shabani, R. L. Kosut, Herschel Rabitz. The abstract reads:

The characterization of a decoherence process is among the central challenges in quantum physics. A major difficulty with current quantum process tomography methods is the enormous number of experiments needed to accomplish a tomography task. Here we present a highly efficient method for tomography of a quantum process that has a small number of significant elements. Our method is based on the compressed sensing techniques being used in information theory. In this new method, for a system with Hilbert space dimension n and a process matrix of dimension n^2 x n^2 with sparsity s, the required number of experimental configurations is O(s log n^4). This heralds a logarithmic advantage in contrast to other methods of quantum process tomography. More specifically, for q-qubits with n=2^q, the scaling of resources is O(sq) linear in the product of sparsity and number of qubits.

CS: Real vs. complex null space properties, Non-Parametric Bayesian Dictionary Learning, Coordinate Descent Optimization code

Today, we have two papers and two codes:

Real vs. complex null space properties for sparse vector recovery by Simon Foucart, Remi Gribonval. The abstract reads:

We identify and solve an overlooked problem about the characterization of underdetermined systems of linear equations for which sparse solutions have minimal `1-norm. This characterization is known as the null space property. When the system has real coefficients, sparse solutions can be considered either as real or complex vectors, leading to two seemingly distinct null space properties. We prove that the two properties actually coincide by establishing a link with a problem about convex polygons in the real plane. Incidentally, we also show the equivalence between stable null space properties which account for the stable reconstruction by `1-minimization of vectors that are not exactly sparse.

Non-Parametric Bayesian Dictionary Learning for Sparse Image Representations by Mingyuan Zhou, Haojun Chen, John Paisley, Lu Ren, Guillermo Sapiro and Lawrence Carin. The abstract reads:

Non-parametric Bayesian techniques are considered for learning dictionaries for sparse image representations, with applications in denoising, inpainting and compressive sensing (CS). The beta process is employed as a prior for learning the dictionary, and this non-parametric method naturally infers an appropriate dictionary size. The Dirichlet process and a probit stick-breaking process are also considered to exploit structure within an image. The proposed method can learn a sparse dictionary in situ; training images may be exploited if available, but they are not required. Further, the noise variance need not be known, and can be nonstationary. Another virtue of the proposed method is that sequential inference can be readily employed, thereby allowing scaling to large images. Several example results are presented, using both Gibbs and variational Bayesian inference, with comparisons to other state-of-the-art approaches.

From the BCS webpage:

BPFA image denoising and inpainting: The package includes the inference update equations and Matlab codes for image denoising and inpainting via the non-parametric Bayesian dictionary learning approach.

Download: BPFA.zip (Last Updated: Oct. 30, 2009)

Back in March I mentioned the following paper Coordinate Descent Optimization for $\ell^1$ Minimization with Application to Compressed Sensing; a Greedy Algorithm by Yingying Li and Stanley Osher. The code is now available on Matlab Central.


Credit: OnOrbit, X-prize, Unreasonable rocket.

CS: Recovering low-rank matrices from few coefficients in any basis, Probability of Unique Integer Solution to a System of Linear Equations

Two items first. In yesterday's entry on the Sudoku paper ( Linear Systems, Sparse Solutions, and Sudoku by Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, and Jian Li) it is interesting to find out that a re-weighted scheme seems to be doing better than some game specific greedy algorithm. Furthermore, at the end of the paper, we can read the following:

The presently known sufficient conditions on A for checking the equivalence of P0 and P1, like the restricted isometry property (RIP) [5] and Kashin, Garnaev, Gluskin (KGG) inequality [6], do not hold for Sudoku. So analyzing the equivalence of l0 and l1 norm solutions in the context of Sudoku requires novel conditions for sparse recovery.

I am not sure that RIP of [5] is the condition to check for here, (RIP-2) more likely the sparsity of the measurement matrix implies some type of RIP-1 condition. I also thought KGG was a necessary and sufficient condition albeit an NP-Hard at that. Other conditions can be found on the Compressive Sensing Big Picture page.

In the super-resolution paper mentioned earlier this week, entitled Super-resolution ghost imaging via compressive sampling reconstruction by Wenlin Gong and Shensheng Han, Wenlin confirms to me that only l1_magic was used not GPSR as the reference would tend to indicate. I am sure we are going to see some improvement in the near future. Other reconstruction solvers can be found in the Compressive Sensing Big Picture page too.

David Gross just sent me the following:

...I'm a physicist and new to the field. Originally, some colleagues and me got interested in compressed sensing and matrix completion in the context of quantum state tomography (meaning the experimental characterization of a quantum system). Our paper arXiv:0909.3304 was mentioned on your blog.

The methods we needed to develop in order to translate known results on matrix completion by Candes, Recht, Tao and others to quantum mechanics proved far more general than anticipated. We can now show that a low-rank (n x n)-matrix may be recovered from basically O(n r log^2 n) randomly selected expansion coefficients with respect to any matrix basis. The matrix completion problem is just a special case.

Most importantly, though, the complexity of the proofs was reduced substantially. The spectacular argument by Candes and Tao in arXiv:0903.1476 covered about 40 pages. The new paper implies these results, but is much simpler to digest.

The first version of the paper went onto the arxiv two weeks ago: arXiv:0910.1879. However, it significantly evolved since then. In some cases the bounds are now down to O(n r log n), which -- I'm happy to say -- is tight up to multiplicative factors.

There is an obvious challenge to be met. The O(n r log n)-bounds do not currently extend to the original matrix completion problem. They come tantalizingly close, though, with only one single lemma obstructing a more general result. The precise problem is pointed out at the end of Section III B.

Before submitting the paper, I plan to add a final note. The statements all continue to be true if instead of a matrix basis a "tight frame" (a.k.a. "overcomplete basis") is used.

I should also point out Benjamin Recht's recent and strongly related pre-print arXiv:0910.0651 to you. He independently translated some of the results in our earlier paper on quantum tomography to the matrix completion problem (apparently overlooking our announcement of exactly the same result in the physics paper).

Let us note that the last preprint of Benjamin Recht was recently updated. But first, here is the new revision entitled: Recovering low-rank matrices from few coefficients in any basis by David Gross

We establish novel techniques for analyzing the problem of low-rank matrix recovery. The methods are both considerably simpler, and more general than previous approaches. It is shown that an unknown n × n matrix of rank r can be efficiently reconstructed given knowledge of only O(nr \nu log2 n) randomly sampled expansion coefficients with respect to any given matrix basis. The number \nu quantifies the “degree of incoherence” between the unknown matrix and the basis. Existing work concentrated mostly on the problem of “matrix completion”, where one aims to recover a low-rank matrix from randomly selected matrix elements. Our result covers this situation as a special case. The proof consists of a series of relatively elementary steps, which stands in contrast to the highly involved methods previously employed to obtain comparable results. In cases where bounds had been known before, our estimates are slightly tighter. We discuss operator bases which are incoherent to all low-rank matrices simultaneously. For these bases, we show that O(nr \nu log n) randomly sampled expansion coefficients suffice to recover any low-rank matrix with high probability. The latter bound is tight up to multiplicative factors. This seems to be the first time the optimal order of the log-factor has been proved to be achievable for a matrix reconstruction problem where neither the basis nor the unknown matrix is randomized. This work is an expanded presentation of the recent pre-print [D. Gross, Y.-K. Liu, S. T. Flammia, S. Becker, and J. Eisert, arxiv:0909.3304] which was aimed at researches working in quantum information theory.

Thanks David !

I also found the following: Probability of Unique Integer Solution to a System of Linear Equations by Olvi Mangasarian and Benjamin Recht. The abstract reads:

We consider a system of m linear equations in n variables Ax = d and give necessary and sufficient conditions for the existence of a unique solution to the system that is integer: x element of {−1,1}^n. We achieve this by reformulating the problem as a linear program and deriving necessary and sufficient conditions for the integer solution to be the unique primal optimal solution. We show that as long as m is larger than n/2, then the linear programming heuristic succeeds for most instances, but if m is less than n/2, the heuristic fails on most instances. We also demonstrate that these predictions match the empirical performance of the linear programming formulation to very high accuracy.

Enjoy!

Credit: NASA / GSFC / ASU, Via The Planetary Society Blog: Apollo 17 lander and flag! An image of the Apollo 17 lander, Challenger, captured by the Lunar Reconnaissance Orbiter Camera on October 1, 2009, includes not only the lander and astronaut tracks but also a fuzzy dark pixel at the location of the American flag erected there by astronauts Jack Schmitt and Gene Cernan.

CS: Linear Systems, Sparse Solutions, and Sudoku, Compressed sensing performance bounds under Poisson noise

Angshul Majumdar just pointed out to me the following paper entitled: Linear Systems, Sparse Solutions, and Sudoku by Prabhu Babu, Kristiaan Pelckmans, Petre Stoica, and Jian Li. The abstract reads:

In this paper, we show that Sudoku puzzles can be formulated and solved as a sparse linear system of equations. We begin by showing that the Sudoku ruleset can be expressed as an underdetermined linear system: ${mmb{Ax}}={mmb b}$, where ${mmb A}$ is of size $mtimes n$ and $n>m$. We then prove that the Sudoku solution is the sparsest solution of ${mmb{Ax}}={mmb b}$, which can be obtained by $l_{0}$ norm minimization, i.e. $minlimits_{mmb x}Vert{mmb x}Vert_{0}$ s.t. ${mmb{Ax}}={mmb b}$. Instead of this minimization problem, inspired by the sparse representation literature, we solve the much simpler linear programming problem of minimizing the $l_{1}$ norm of ${mmb x}$, i.e. $minlimits_{mmb x}Vert{mmb x}Vert_{1}$ s.t. ${mmb{Ax}}={mmb b}$, and show numerically that this approach solves representative Sudoku puzzles.

We have heard about Sudoku before in compressive sensing. The code implementing this can be found here.

I also found the following on arxiv: Compressed sensing performance bounds under Poisson noise by Maxim Raginsky, Zachary Harmany, Roummel Marcia, Rebecca Willett. The abstract reads:

This paper describes performance bounds for compressed sensing (CS) where the underlying sparse or compressible (sparsely approximable) signal is a vector of nonnegative intensities whose measurements are corrupted by Poisson noise. In this setting, standard CS techniques cannot be applied directly for several reasons. First, the usual signal-independent and/or bounded noise models do not apply to Poisson noise, which is non-additive and signal-dependent. Second, the CS matrices typically considered are not feasible in real optical systems because they do not adhere to important constraints, such as nonnegativity and photon flux preservation. Third, the typical $\ell_2$--$\ell_1$ minimization leads to overfitting in the high-intensity regions and oversmoothing in the low-intensity areas. In this paper, we describe how a feasible positivity- and flux-preserving sensing matrix can be constructed, and then analyze the performance of a CS reconstruction approach for Poisson data that minimizes an objective function consisting of a negative Poisson log likelihood term and a penalty term which measures signal sparsity. We show that, as the overall intensity of the underlying signal increases, an upper bound on the reconstruction error decays at an appropriate rate (depending on the compressibility of the signal), but that for a fixed signal intensity, the signal-dependent part of the error bound actually grows with the number of measurements or sensors. This surprising fact is both proved theoretically and justified based on physical intuition.

On his webpage, Roummel Marcia has the following announcement:

Opportunities: Positions for graduate and undergraduate students are available in the areas of optimization, linear algebra, and compressed sensing. These positions are in conjunction with the National Science Foundation grant, DMS-0811062: Second-order methods for large-scale optimization in compressed sensing. Send me an email if you are interested in any of these positions.

CS: Super-resolution ghost imaging via compressive sampling reconstruction

Bada bing, bada boom, when was the last time you had to increase the size of your pixel on a CCD dye in order to obtain a better resolution ? Looks like this is a result coming out of a CS reconstruction in another Ghost Imaging experiment. Enjoy !

Super-resolution ghost imaging via compressive sampling reconstruction by Wenlin Gong and Shensheng Han. The abstract reads:

For ghost imaging, pursuing high resolution images and short acquisition times required for reconstructing images are always two main goals. We report an image reconstruction algorithm called compressive sampling (CS) reconstruction to recover ghost images. By CS reconstruction, ghost imaging with both super-resolution and a good signal-to-noise ratio can be obtained via short acquisition times. Both effect influencing and approaches further improving the resolution of ghost images via CS reconstruction, relationship between ghost imaging and CS theory are also discussed.

CS: A job with Exxon.

As much as it looks like a nice opportunity, this one is not located in Paris so I will pass up on it. Here is a job opportunity that showed up on my radar screen which has been added to the Compressive Sensing Jobs page:

Employer: ExxonMobil
Location: Clinton, NJ United States
Last Updated: 10/26/2009
Job Code: 7382BR

AutoReqId 7382BR
Job or Campus Folder Research Scientists (2) -Wave Propagation and Numerical Methods


Job Description ExxonMobil's Corporate Strategic Research Laboratory is seeking applications from talented individuals in physics, applied mathematics, or engineering with a strong record of achievements in fields related to wave propagation in heterogeneous media, and its associated mathematical and numerical methods.


Research Scientist - Wave propagation and transport in heterogeneous and porous media.

Experience with the physical, mathematical and numerical analyses of one of: wave propagation in heterogeneous media, multi-scale transport phenomena, and/or fluid-structure interactions at the rock pore scale and their impact on the macro scale.

Research Scientist-Compressive sensing.

Experience with the mathematics of signal/image processing, denoising, sub-Nyquist signal reconstruction, and sparse representation of data.

Applicants should have a PhD in applied mathematics, physics, engineering, geophysics, or a related field, with a strong ability in their field of expertise. Proficiency with scientific programming languages and experience with large-scale, parallel, numerical simulations are definite advantages. The ability to communicate and interact with internal and external groups will be an important selection criterion. Candidates should have a strong publication record, excellent oral presentation and writing skills, and show a desire and ability to grow into new science areas.

The successful candidate will join a dynamic, multi-disciplinary group of world-class scientists who focus on performing breakthrough research and creating new approaches to solve our most challenging problems. Technical staff members in this position implement and report on independent research, participate in program development, as well as collaborate internationally with leading engineers and scientists from industry, universities and other technical institutions.

ExxonMobil's Corporate Strategic Research (CSR) laboratory is a powerhouse in energy research focusing on fundamental science that can lead to technologies having a direct impact on solving our biggest energy challenges. Our facilities are centrally located in scienic Annandale, New Jersey, approximately one hour from both New York City and Phildelphia.
ExxonMobil is an Equal Opportunity Employer
Job Location Clinton, NJ