Monday, November 30, 2009

CS: Low-Dimensional Models for Dimensionality Reduction, Joint Manifolds, Group Testing Strategies, New Algos and Codes.

I am putting in one page all the links to the entries from the generic thread entitled "These Technologies Do Not Exist".

There are some news about the PACS camera on Herschel, from the project website:
Status summary: Herschel was successfully launched together with Planck on 14 May 2009. After a successful Commissioning phase, including cryocover opening 1 month after launch, the Performance Verification phase commenced in mid-July. An approximate overview of the early mission phases includes Commissioning Phase (COP) 2 months, Performance Verification Phase (PVP) 3 months, followed by the Science Demonstration Phase (SDP) and a gradual transition into Routine Science Phase (RSP). Currently as of late November, except for HIFI the PVP activities have basically been completed, SDP has been underway for some time, and gradually more and more RSP observations are being executed. See also the HSC Operations (B)Log.

Let's hope that the Compressive Sensing encoding scheme for PACS has yielded good results.

I found the following on the interwebs:

Low-Dimensional Models for Dimensionality Reduction and Signal Recovery: A Geometric Perspective by Richard Baraniuk, Volkan Cevher, Michael Wakin. The abstract reads:
We compare and contrast from a geometric perspective a number of low-dimensional signal models that support stable information-preserving dimensionality reduction. We consider sparse and compressible signal models for deterministic and random signals, structured sparse and compressible signal models, point clouds, and manifold signal models. Each model has a particular geometrical structure that enables signal information to be stably preserved via a simple linear and nonadaptive projection to a much lower dimensional space; in each case the projection dimension is independent of the signal’s ambient dimension at best or grows logarithmically with it at worst. As a bonus, we point out a common misconception related to probabilistic compressible signal models, namely, by showing that the oft-used generalized Gaussian and Laplacian models do not support stable linear dimensionality reduction.

Joint Manifolds for Data Fusion by Mark Davenport, Chinmay Hegde, Marco Duarte and Richard Baraniuk. The abstract reads:
The emergence of low-cost sensing architectures for diverse modalities has made it possible to deploy sensor networks that capture a single event from a large number of vantage points and using multiple modalities. In many scenarios, these networks acquire large amounts of very high-dimensional data. For example, even a relatively small network of cameras can generate massive amounts of high-dimensional image and video data. One way to cope with such a data deluge is to develop low-dimensional data models. Manifold models provide a particularly powerful theoretical and algorithmic framework for capturing the structure of data governed by a low-dimensional set of parameters, as is often the case in a sensor network. However, these models do not typically take into account dependencies among multiple sensors. We thus propose a new joint manifold framework for data ensembles that exploits such dependencies. We show that joint manifold structure can lead to improved performance for a variety of signal processing algorithms for applications including classification and manifold learning. Additionally, recent results concerning random projections of manifolds enable us to formulate a network-scalable dimensionality reduction scheme that efficiently fuses the data from all sensors.
Group Testing Strategies for Recovery of Sparse Signals in Noise by Mark Iwen. The abstract reads:
We consider the recovery of sparse signals, f 2 RN, containing at most k \lt\lt N nonzero entries using linear measurements contaminated with i.i.d. Gaussian background noise. Given this measurement model, we present and analyze a computationally efficient group testing strategy for recovering the support of f and approximating its nonzero entries. In particular, we demonstrate that group testing measurement matrix constructions may be combined with statistical binary detection and estimation methods to produce efficient adaptive sequential algorithms for sparse signal support recovery. Furthermore, when f exhibits sufficient sparsity, we show that these adaptive group testing methods allow the recovery of sparse signals using fewer noisy linear measurements than possible with non-adaptive methods based on Gaussian measurement ensembles. As a result we improve on previous sufficient conditions for sparsity pattern recovery in the noisy sublinear-sparsity regime.

Now on the reconstruction solvers side we also have:

Non-convexly constrained linear inverse problems by Thomas Blumensath.The abstract reads:
This paper considers the inversion of ill-posed linear operators. To regularise the problem the solution is enforced to lie in a non-convex subset. Theoretical properties for the stable inversion are derived and an iterative algorithm akin to the projected Landweber algorithm is studied. This work extends recent progress made on the efficient inversion of finite dimensional linear systems under a sparsity constraint to the Hilbert space setting and to more general non-convex constraints.
A Unified Primal-Dual Algorithm Framework Based on Bregman Iteration by Xiaoqun Zhang, Martin Burger and Stanley Osher. The abstract reads:
In this paper, we propose a uni¯ed primal-dual algorithm framework for two classes of problems that arise from various signal and image processing applications. We also show the connections to existing methods, in particular Bregman iteration [41] based method, such as linearized Bregman [42, 9, 10, 49] and split Bregman [31]. The convergence of the general algorithm framework is proved under mild assumptions. The applications to `1 basis pursuit, TV¡L2 minimization and matrix completion are demonstrated. Finally, the numerical examples show the algorithms proposed are easy to implement, efficient, stable and °exible enough to cover a wide variety of applications.

Multiplicative noise removal using L1 fidelity on frame coefficients by Durand S., J. Fadili and M. Nikolova. The abstract reads:
We address the denoising of images contaminated with multiplicative noise, e.g. speckle noise. Classical ways to solve such problems are filtering, statistical (Bayesian) methods, variational methods, and methods that convert the multiplicative noise into additive noise (using a logarithmic function), apply a variational method on the log data or shrink their coefficients in a frame (e.g. a wavelet basis), and transform back the result using an exponential function. We propose a method composed of several stages: we use the log-image data and apply a reasonable under-optimal hard-thresholding on its curvelet transform; then we apply a variational method where we minimize a specialized hybrid criterion composed of an ℓ1 data-fidelity to the thresholded coefficients and a Total Variation regularization (TV) term in the log-image domain; the restored image is an exponential of the obtained minimizer, weighted in a such way that the mean of the original image is preserved. Our restored images combine the advantages of shrinkage and variational methods and avoid their main drawbacks. Theoretical results on our hybrid criterion are presented. For the minimization stage, we propose a properly adapted fast scheme based on Douglas-Rachford splitting. The existence of a minimizer of our specialized criterion being proven, we demonstrate the convergence of the minimization scheme. The obtained numerical results clearly outperform the main alternative methods especially for images containing tricky geometrical structures.

If some of the solvers need to be sped up,why not think of GPUs. Some news in that respect include:
How fast would a solution be if one were toimplement the Approximate Message Passing Algorithm of last week on a GPU ?

Finally, specific codes have gotten an update or have just appeared:

* NESTA: The current version of code for NESTA requires that the measurement matrix A is an orthogonal projection. It is sometimes possible to extend NESTA to allow general matrices A; a few special cases have been implemented in the code.

UPDATE: NESTA v.1.1 is released (188 kB zip file, Nov 24 2009). There are no algorithmic changes, but there are some bug fixes, more demos, and more support for complex numbers and the case when A is not a projector. You may view the important changes in the change log.
* Singular Value Thresholding (SVT) is an algorithm to minimize the nuclear norm of a matrix, subject to certain types of constraints. From its webpage we have:
Nov 24 2009: the PROPACK precision error is caused by incompatibility with 64-bit architectures, in particular in dbdsqr. This has been fixed, but the new mex files are not yet in the SVT package. You may download them separately here. Also included is bdsqr in C (before, this relied on some code in fortran), so it is much easier compile on Windows computers; additionally, there is a file XonOmegaTranspose that can be used in place of XonOmega in the unlikely event that XonOmega is a speed bottleneck. For details, email Stephen.
* PPApack version 0 -- a MATLAB software for nuclear norm minimization based on proximal point algorithms by Yongjin Liu, Defeng Sun and Kim-Chuan Toh

The software was first released on 18 Nov 2009. It was last updated in 25 Nov 2009 with some minor bugs corrected. The software is designed to solve nuclear norm minimization problems of the form:
   min_X {sum(svd(X)) : norm(A1(X)-b1) \le delta, A2(X)-b2 \ge0, A3(X)-b3=0}
where delta is a non-negative scalar.

Credit Photo: ESA, PACS Consortium.

Sunday, November 29, 2009

CS: Random Food For Thought

Ever wondered how astronauts flying at 300 kms above the ground on the international space station could take a shot like this one ?

Well they not only have access to the latest gear, they also have access to interesting telescopic lenses as can be seen on this shot:

As some of you know, I am interested in using some of this gear that is already on orbit to propose some type of random lens imager system. The proposed system would make full use of what is already up. This is a follow-up thread to this one.

Credit: NASA, Canadian Space Agency astronaut Robert Thirsk, Expedition 21 flight engineer, works in the Zvezda Service Module of the International Space Station while space shuttle Atlantis (STS-129) remains docked with the station. (Via

Saturday, November 28, 2009

CS: These Technologies Do Not Exist: Random X-ray Collectors in CT

In the previous entry in the newly started series "These Technologies Do Not Exist" I mentioned the National Academy of Sciences report on the Mathematics and Physics of Emerging Biomedical Imaging that came out in 1996. I am going to continue using this report as a basis for at least another entry. Today we'll focus on the instrumentation and technology associated with X-rays CT (Computed Tomography) scans.

The technology is explained here. It is pretty simple compared to PET and SPECT. Roughly speaking, an X-ray source is shone on a human subject. X-ray photons go through the body but the different tissues in the body provide different attenuation. On the other side of the body, there are detectors collecting the X-rays and transforming them into electrical currents. The difference between what was sent and what was received is the subject of the computation in Computed Tomography. That computation does not matter to us today as much as to how the conversion between X-ray photons to electrons is made. Let us recall though that I mentioned that CT ought to be investigated with the Coded Aperture concept to see if there is a way to improve some of the resolution or even guess scattered fluxes yet this is not the subject of this entry as we look at the process that happens after that (the coded could be used on top of what we describe here)

As one can see from the graph above (page 27 of the report), 140 KeV photons that have traveled through the body are then converted down into visible light (four orders of magnitude change - see below-) in a scintillation chamber (akin to what is performed in the Anger Coding Scheme mentioned earlier) or are ionizing elements in a chamber that provides the location (the negative and positive electrodes are location sensitive) of where the atoms where ionized.

A Compressive Scheme can be implemented in both cases. For the scintillation chamber, one could use, as in the case of the Anger Coding Scheme, a scintillation material that is incoherent i.e. that has occlusion, different light scatterers. One could also conceive that we have some amount of material within the scintillation material that also scatters/reflects X-rays (by employing multi-layers materials for instance). In the second case of the ionization chamber, we are confronted with a technology similar to the one used in the A2I very high frequency converter: A compressive sensing scheme could entail the ability to switch the polarity of the electrodes at a high frequency.

Both of these schemes should be investigated by evaluating the different efficiencies of each solutions. Instead of building detectors, one can start a trade studies process by using appropriate Monte Carlo codes such as MCNP, Fluka or Geant4.

Why would we want to do this ? In PET or SPECT, the positron mean free path bounds the resolution to no smaller than 2 mm. Here, our concern is not only to collect X-ray fluxes, but the approach given here could also provide additional information about the direction of that flux. X-rays do scatter in the body and with the current collection system, we don't know very well if the photon has collided several times in the body (and changed direction of energy) or not. The current approach uses different systems in the collection of the flux to make sure the right flux is known with the added help of image processing. In the proposed approach, the need for ad-hoc image processing would probably be decreased while a better 3-D description could be obtained.

Thursday, November 26, 2009

CS: Convex iteration method, Statistical Estimation in High Dimension,, Super-resolution far-field ghost imaging via compressive sampling

Happy Thanksgiving y'all.

First, I hope you are not shell shocked from yesterday's post on the Approximate Message Passing Algorithm. Second, Jon Dattorro sent me the following:
I have published a derivation of direction vector for the convex iteration method of cardinality minimization (compressed sensing) here (p.322):

Specifically: The direction vector has been interpreted in the past, by others, as "yet another weighting" for the compressed sensing problem. The derivation I provide proves that the optimal direction vector is a binary vector complementary to the optimal solution; i.e., the binary values {0,1} of the direction vector are not at all arbitrary, but now have firm theoretical foundation.

Existence of such an optimal direction vector is assured under the assumption that a cardinality-k solution to the compressed sensing problem exists. But finding that direction vector remains a hard problem.

When a direction vector is 1, then convex iteration is equivalent to the conventional compressed sensing problem. But I show, by numerous example, that there are far better directions than 1 that produce significantly better results than compressed sensing alone.

Thanks Jon!

I just started a Google Wave with the provocative title entitled "Compressive Sensing / Compressed Sensing : What is it good for ?", I hope you'll join!

Today I finally met Andrew Gelman who's popular blog is listed on the right hand side of this blog. He was giving a talk at AppliBUGS (the talk is now here). He made an interesting presentation where he talked about building supergraphs of models where each node would be a statistical model and every node (model) would only differ from one another by one feature.

I am going to have to think how some of the machine learning techniques on manifold could be applied to this new meta-formalism.

I met Andrew, but I am afraid I won't meet Buzz Aldrin, too bad, oh well one famous person a day is good enough in my book :-)

Karim Lounici's Ph.D. thesis is out. The summary reads: Statistical Estimation in High Dimension, Sparsity and Oracle Inequalities

We treat two subjects. The first subject is about statistical learning in high-dimension, that is when the number of paramaters to estimate is larger than the sample size. In this context, the generally adopted assumption is that the number of true parameters is much smaller than the number of potential paramaters. This assumption is called the ``\emph{sparsity assumption}''. We study the statistical properties of two types of procedures: the penalized risk minimization procedures with a $l_{1}$ penalty term on the set of potential parameters and the exponential weights procedures. The second subject is about the study of two aggregation procedures in a density estimation problem. We establish oracle inequalities for the $L^{\pi}$ norm, $1\leqslant \pi \leqslant \infty$. Next, we exploit these results to build minimax rate adaptive estimators of the density.

From Arxiv, we finally have the fascinating: Super-resolution far-field ghost imaging via compressive sampling by Wenlin Gong, Shensheng Han. The abstract reads:
For classical source, the uncertainty relation involving the product of conditional variances in position and momentum limits the imaging resolution of optical system. Based on ghost imaging (GI) and compressive sampling (CS) theory, an imaging approach called ghost imaging via compressive sampling (GICS) with thermal light is reported. For the first time, a super-resolution image with high quality is obtained in the far field by GICS reconstruction. Physical principle of GICS and the resolution limit of conventional imaging, GI and GICS are also discussed.

In a different direction, if the Earth had rings, this is what they'd look like from the ground. Breathtaking.

Credit: NASA, Roy Prol.

Wednesday, November 25, 2009

CS: Fourier-transform Ghost Imaging, Message Passing Algorithms for Compressed Sensing

This is new, Nuit Blanche has now a PageRank of 6 but according to Wikipedia, PageRank does not mean anything anymore. Oh well, I hope you liked yesterday's first installment of "These Technologies Do Not Exist" ?

In the meantime, one can only imagine how much of an improvement some of these technologies might bring by looking at some of the current results obtained by David Brady and Scott McCain at Duke and Applied Quantum Technologies respectively.

Thanks to Alex Conrad, I now have a Google Wave account. I have no invitation to give though, a situation which surely could be mapped into another Seinfeld moment but I can't think of one for the moment.

Today, we have three new papers from Arxiv:

Fourier-transform Ghost Imaging for pure phase object based on Compressive Sampling algorithm by Hui Wang, Shensheng Han. The abstract reads:
A special algorithm for the Fourier-transform Ghost Imaging (GI) scheme is discussed based on the Compressive Sampling (CS) theory. Though developed mostly in real space, CS algorithm could also be used for the Fourier spectrum reconstruction of pure phase object by setting a proper sensing matrix. This could find its application in diffraction imaging of X-ray, neutron and electron with higher efficiency and resolution. Simulation and experiment results are also presented to prove the feasibility.

and a continuation of a previous paper on approximate message passing reconstruction algorithm which seems to be fast and seems to also go farther than the regular IST solver:

Message Passing Algorithms for Compressed Sensing: I. Motivation and Construction by David Donoho, Arian Maleki, Andrea Montanari. The abstract reads:
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \cite{DMM}. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the first of two conference papers describing the derivation of these algorithms, connection with the related literature, extensions of the original framework, and new empirical evidence.
In particular, the present paper outlines the derivation of AMP from standard sum-product belief propagation, and its extension in several directions. We also discuss relations with formal calculations based on statistical mechanics methods.

Message Passing Algorithms for Compressed Sensing: II. Analysis and Validation by David Donoho, Arian Maleki, Andrea Montanari. The abstract reads:
In a recent paper, the authors proposed a new class of low-complexity iterative thresholding algorithms for reconstructing sparse signals from a small set of linear measurements \cite{DMM}. The new algorithms are broadly referred to as AMP, for approximate message passing. This is the second of two conference papers describing the derivation of these algorithms, connection with related literature, extensions of original framework, and new empirical evidence.
This paper describes the state evolution formalism for analyzing these algorithms, and some of the conclusions that can be drawn from this formalism. We carried out extensive numerical simulations to confirm these predictions. We present here a few representative results.

Tuesday, November 24, 2009

CS: These Technologies Do Not Exist: A Random Anger Coding Scheme for PET/SPECT cameras

While I try to bring the most updated information on compressive sensing by finding the latest and greatest, I am also toying with figuring out how new compressive sensing schemes could be implemented. Because some of these technologies are bold, it is unlikely you will find any reference to them anywhere but here. I also mentioned another reason for doing this before so without further wait, here we go.

Back in the middle of the 90's while I was involved with some Excess Weapons Plutonium disposition studies and discovered what the National Academies of Science really did in the U.S. During that time, I came across the National Academy Press website that featured a general study by the National Academy of Sciences on the Mathematics and Physics of Emerging Biomedical Imaging. I never got into that field but I bought and kept the book on the side just in case. The proceedings were a very thorough list of the current state of the art of all the imaging technologies at that point in time. The document also included a "to do" list highlighting how one could improve each of these technologies.

Anyway, today I'll focus on the Positron Emission Tomography technology, it starts here in the proceedings. Briefly speaking, a decaying isotope is inserted in the body. The element decays by emitting a positron (an anti-electron) which quickly interacts with the surrounding matter (since it is anti-matter) to produce two photons. These photons have the nice characteristics of being emitted 180 degrees away from each other. The PET camera is devised to detect these photons traveling opposite from each other. Some amount of synchronization is used to do that but the main issue is making sure that there is a good spatial resolution so that the photons are detected in pairs. The only way of detecting 511 KeV photons is through a two stage process. First, the photons need to be converted to visible light, then either a Photo Multiplier Tubes (PMT) or an Avalanche PhotoDiode (APD) convert that light into a current to be eventually used in the electronic chain.

One of the issue faced by this technology is the mismatch between the small size of the photon-to-light converter and the larger size of the PMT detector. The converter is also a diffusive material for light. The small size of the converter is due to the need to provide the spatial resolution to the overall detector. Therefore, one needs to find a way to translate the fine grained spatial information of the photon-to-light converter and the coarse grained PMT device. The figure above shows the issue at hand. This translation is performed with the Anger Coding Scheme or Anger logic named after Hal Anger who developed this technique in the original PET camera in 1958.

An example of it can be found in figure 2 of [3] and in the following figures (from [5] and [4]):

The top figure shows the response of the BGO-LSO (converter) block being fully illuminated. If a single conversion were to be identified, one would get just a portion of the figure above. The figure below shows a more complete scheme where the response of the converter is then adequately summed with weights after light has interacted with the PMTs.

Both processes compose the Anger logic. The Technology That Does Not Exist that is the subject of this entry could adequately be called a Random Anger Logic or Random Anger Coding Scheme whereby one could have a combination of Randomly altered converter materials (different widths, materials, reflective occlusions,...) and random "positional" weights.

Potential advantage of this approach:
  • Superresolution capabilities
  • Better 3-D resolution when including Energy.
Potential disadvantage

Sometimes, it takes more time to explain what exists than what is proposed :-)

You can also check this presentation to understand the Anger logic:

[1] Overview of Nuclear Medical Imaging Instrumentation and Techniques, William W. Moses, 1997
[2] Nuclear Medical Imaging - Techniques and Challenges, William W. Moses, 2005
[3] PET Imaging Physics and Instrumentation, Christopher J Thompson
[4] Nuclear Medicine Anger Camera
[5] Photodetectors for Nuclear Medical Imaging, William W. Moses, 2008
[7] A new high signal-noise-ratio Anger method using non-preamplifier weight-sum circuit
Jiguo Liu, Shitao Liu, Hongdi Li, Yu Wang, Soonseok Kim, Yuxuan Zhang, Hossain Baghaei, Rocio Ramirez and Wai-Hoi Wong

Monday, November 23, 2009

CS: Sparse Reconstruction of Complex Signals in Compressed Sensing Terahertz Imaging, Compressive Sensing for Sparsely Excited Speech Signals

Laurent Jacques just released a presentation he made recently entitled: A Compressed Introduction to Compressed Sensing: Combining Sparsity and Sampling. It's a good compressed introduction to the subject. Thanks Laurent for the mention at the very end. Today, we have two new papers: one concerns the use of the compressive sensing single pixel camera concept to get away from the raster mode, while the second paper applies CS to speech. Enjoy!

Sparse Reconstruction of Complex Signals in Compressed Sensing Terahertz Imaging by Zhimin Xu, Wai Lam Chan, Daniel M. Mittleman and Edmund Y. Lam. The Abstract reads:
In reconstructing complex signals, many existing methods apply regularization on the magnitude only. We show that by adding control on the phase, the quality of the reconstruction can be improved. This is demonstrated in a compressed sensing terahertz imaging system.

Compressive Sensing for Sparsely Excited Speech Signals by Thippur V. Sreenivas and W. Bastiaan Kleijn. The abstract reads:
Compressive sensing (CS) has been proposed for signals with sparsity in a linear transform domain. We explore a signal dependent unknown linear transform, namely the impulse response matrix operating on a sparse excitation, as in the linear model of speech production, for recovering compressive sensed speech. Since the linear transform is signal dependent and unknown, unlike the standard CS formulation, a codebook of transfer functions is proposed in a matching pursuit (MP) framework for CS recovery. It is found that MP is efficient and effective to recover CS encoded speech as well as jointly estimate the linear model. Moderate number of CS measurements and low order sparsity estimate will result in MP converge to the same linear transform as direct VQ of the LP vector derived from the original signal. There is also high positive correlation between signal domain approximation and CS measurement domain approximation for a large variety of speech spectra.

Friday, November 20, 2009

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 Jeff rey 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.

Thursday, November 19, 2009

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.

Wednesday, November 18, 2009

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

Today we have three papers:
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.

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:

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.

Tuesday, November 17, 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 di raction. 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 di erent 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:
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.

Monday, November 16, 2009

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:

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:
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.

Saturday, November 14, 2009

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:

frequency of words (Zipf's law)

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

HTTP session sizes
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.

Friday, November 13, 2009

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.