Physical Principles for Scalable Neural Recording

The following is an analysis of what would be needed to have access to most events of interest in the brain. 

Physical Principles for Scalable Neural Recording by Adam H. Marblestone, Bradley M. Zamft, Yael G. Maguire, Mikhail G. Shapiro, Thaddeus R. Cybulski, Joshua I. Glaser, Ben Stranges, Reza Kalhor, David A. Dalrymple, Dongjin Seo, Elad Alon, Michel M. Maharbiz,Jose Carmena, Jan Rabaey, Edward S. Boyden, George M. Church, Konrad P. Kording

Simultaneously measuring the activities of all neurons in a mammalian brain at millisecond resolution is a challenge beyond the limits of existing techniques in neuroscience. Entirely new approaches may be required, motivating an analysis of the fundamental physical constraints on the problem. We outline the physical principles governing brain activity mapping using optical, electrical,magnetic resonance, and molecular modalities of neural recording. Focusing on the mouse brain, we analyze the scalability of each method, concentrating on the limitations imposed by spatiotemporal resolution, energy dissipation, and volume displacement. We also study the physics of powering and communicating with microscale devices embedded in brain tissue.

I note the following:

While optics might seem to require a number of photodetectors, fibers or waveguide ports comparable to the number of neurons, new developments suggest ways of imaging with fewer elements. For example, compressive sensing or ghost imaging techniques based on random mask projections [20, 38, 57, 100] might allow a smaller number of photodetectors to be used. In an illustrative case, an imaging system may be constructed simply from a single photodetector and a transmissive LCD screen presenting a series of random binary mask patterns [12], where the number of required mask patterns is much smaller than the number of image pixels due to a compressive reconstruction. Furthermore, it is possible to directly image through gradient index of refraction (GRIN) lenses [34] or optical fibers [13, 65, 103], thus multiplexing multiple observed neurons per fiber.

Yes. mutliplexing would be good :-) and reading this chart,

I am thinking there might be other good reasons as to why you'd want compressive sensing related techniques. More on that later.

Join the CompressiveSensing subreddit or the Google+ Community and post there !
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.

Mirror, mirror, who's the sparsest of them all ?

The dark part shows the region where we think finding the sparsest solution to an underdetermined system of linear equations is NP. As time goes, it sure looks like this line is receding. In other words, for every new algorithms shown to work and busting the old limit, the territory of combinatorial problems shrinks and the NP vs P line in the sand shifts.

Liked this entry ? subscribe to the Nuit Blanche feed, there's more where that came from

CS: Sparse Brain Network Recovery under Compressed Sensing, Compressive Radar Imaging Using White Stochastic Waveforms, Compressive Sensing in the Limit

Wow! just Wow! We have two very application oriented interesting papers today:

Sparse Brain Network Recovery under Compressed Sensing by Hyekyoung Lee, Dong Soo Lee, Hyejin Kang, Boong-Nyun Kim, Moo K. Chung. The abstract reads:

Partial correlation is a useful connectivity measure for brain networks, especially, when it is needed to remove the confounding e ffects in highly correlated networks. Since it is difficult to estimate the exact partial correlation under the small-n large-p situation, a sparseness constraint is generally introduced. In this paper, we consider the sparse linear regression model with a l1-norm penalty, a.k.a., least absolute shrinkage and selection operator (LASSO), for estimating sparse brain connectivity. LASSO is a well-known decoding algorithm in the compressed sensing (CS). The CS theory states that LASSO can reconstruct the exact sparse signal even from a small set of noisy measurements. We briefly show that the penalized linear regression for partial correlation estimation is related with CS. It opens a new possibility that the proposed framework can be used for a sparse brain network recovery. As an illustration, we construct sparse brain networks of 97 regions of interest (ROIs) obtained from FDG-PET data for the autism spectrum disorder (ASD) children and the pediatric control (PedCon) subjects. As a model validation, we check their reproducibilities by leave-one-out cross validation and compare the clustered structures derived from the brain networks of ASD and PedCon.

I don't think I have this type of quality work in Autism related studies. Kudos to this team. On a related note,  if you are interested in going for a PhD that deals with how compressed sensing translates into medical application, you may want to check the PhD program at King's College in London. Check the title of Dr. Batchelor. More information can be found here.

In a different direction, we get to use the Donoho-Tanner phase transition to calibrate a hardware system. I like very much this idea:

Compressive Radar Imaging Using White Stochastic Waveforms by Mahesh C. Shastry, Ram M. Narayanan and Muralidhar Rangaswamy. The abstract reads:

In this paper, we apply the principles of compressive sampling to ultra-wideband (UWB) stochastic waveform radar. The theory of compressive sampling says that it is possible to recover a signal that is parsimonious when represented in a particular basis, by acquiring few projections on to an appropriate basis set. Drawing on literature in compressive sampling, we develop the theory behind stochastic waveformbased compressive imaging. We show that using stochastic waveforms for radar imaging, it is possible to estimate target parameters and detect targets by sampling at a rate that is considerably slower than the Nyquist rate and recovering using compressive sensing algorithms. Thus, it is theoretically possible to increase the bandwidth (and hence the spatial resolution) of an ultra-wideband radar system using stochastic waveforms, without significant additions to the data acquisition system. Further, there is virtually no degradation in the performance of a UWB stochastic waveform radar system that employs compressive sampling. We present numerical simulations to show that the performance guarantees provided by theoretical results are achieved in realistic scenarios.

And finally a poster on  Compressive Sensing in the Limit by Yaser Eftekhari, Amir H. Banihashemi, IoannisLambadaris whose goal is to

Study the asymptotic behaviour of Node-Based Verification-Based (NBVB) algorithms over random regular bipartite graphs in the context of compressive sensing.

CS: IADM_NNLS code, data streams research, where to go, RESCUME, Optical imaging using binary sensors. Multiarray Signal Processing, CS -SD-OCT, blogs

Junfeng Yang just let me know of the availability of the IADM_NNLS code: IADM_NNLS stands for Inexact Alternating Direction Method for Nuclear Norm regularized Least Squares problems. It solves the following problems:

Currently, the code applies to three types of A-operators:

• (1) Projection onto a subset of indices (common matrix completion problems);
  
• (2) Partial discrete cosine transform (DCT) operator;
• (3) Partial discrete Walsh-Hadamard transform (DWHT) operator.

The attendant paper is: An Inexact Alternating Direction Method for Trace Norm Regularized Least Squares Problem by Junfeng Yang and Xiaoming Yuan. The abstract reads:

The trace norm regularized least squares problem (TNRLSP) captures a broad spectrum of applications including the multi-task learning problem in machine learning. However, it is challenging to solve TNRLSP efficiently, especially for large-scale cases. In this paper, we show that the classical alternating direction method (ADM) is readily applicable for TNRLSP. Each iteration of the resulted ADM algorithm consists of three subproblems, one of which is difficult in the sense that the analytical solution is not available. We suggest to linearize the difficult subproblem and thus obtain the linearized approximated subproblem whose analytical solution can be easily derived. Hence, the inexact ADM approach is developed in this paper to treat TNRLSP. We then show that the inexact ADM approach can be easily extended to solve some other trace-norm-involved problems which are closely related to TNRLSP. Numerical results are reported to demonstrate the feasibility and efficiency of the inexact ADM approach.

Thanks Junfeng for the heads-up!

Here is a video of David Gross on Non-commutative compressed sensing: theory and applications for quantum tomography. I mentioned the paper before ( Quantum state tomography via compressed sensing ) and David also gave us some insight on its genesis recently.


Muthu Muthukrishnan wrote a whitepaper on data streams research, where to go. If you have meat you want him to address, you may want to mention that to him directly.

Graham Cormode reports from the fourth Bristol Algorithms Days on Andrew Mc Gregor's blog:

• Reporting from Bristol Algorithms Days
• BAD Day 2: Energy Efficiency

On James Lee's not-a-blog theoretical computer science blog, we can get educated about:

• Open problem: Dimension reduction in L_1
• The need for non-linear mappings

Andrew Gelman mentions some recent work on One of the fastest generalized linear model implementations

The Wired Article on compressed sensing entitled Fill in the Blanks: Using Math to Turn Lo-Res Datasets Into Hi-Res Samples by Jordan Ellenberg was featured on his blog. It led to many spam blogs re-using the story as is. It also looks like a good many folks misunderstood some concepts but this a good experiment for crowdsourcing a FAQ. Let us note for instance that a misunderstood view of compressed sensing is embodied in the misleading title: Fancy Math Allows For Near-Perfect Enhancement of Poor-Quality Images [Math]. The Google helped me find some of the more interesting blogs commenting on the subject. One of them is Andrew Hires' Brain Windows that featured a paper I missed entirely it seems from NIPS 2009 entitled: Reconstruction of Sparse Circuits Using Multi-neuronal Excitation (RESCUME) by Tao Hu and Dmitri B. Chklovskii. The abstract of the paper reads:

One of the central problems in neuroscience is reconstructing synaptic connectivity in neural circuits. Synapses onto a neuron can be probed by sequentially stimulating potentially pre-synaptic neurons while monitoring the membrane voltage of the post-synaptic neuron. Reconstructing a large neural circuit using such a “brute force” approach is rather time-consuming and inefficient because the connectivity in neural circuits is sparse. Instead, we propose to measure a post-synaptic neuron’s voltage while stimulating sequentially random subsets of multiple potentially pre-synaptic neurons. To reconstruct these synaptic connections from the recorded voltage we apply a decoding algorithm recently developed for compressive sensing. Compared to the brute force approach, our method promises significant time savings that grow with the size of the circuit. We use computer simulations to find optimal stimulation parameters and explore the feasibility of our reconstruction method under realistic experimental conditions including noise and non-linear synaptic integration. Multineuronal stimulation allows reconstructing synaptic connectivity just from the spiking activity of post-synaptic neurons, even when sub-threshold voltage is unavailable. By using calcium indicators, voltage-sensitive dyes, or multi-electrode arrays one could monitor activity of multiple postsynaptic neurons simultaneously, thus mapping their synaptic inputs in parallel, potentially reconstructing a complete neural circuit.

And Andrew Hires may be right when he says that:

Unfortunately, I don’t think it [Compressed Sensing] is very applicable to situations where signal/noise is poor, like counting action potentials in shot-noise limited in vivo calcium imaging.

but you never really know until you look at the problem deeper or with different sensors.

Sometimes when I read the Wired article, I feel like something of inimaginable wonder has been missed. Let me take the example of the 1-bit compressive sensing example as featured in Optical imaging using binary sensors by Aurelien Bourquard, Francois Aguet, and Michael Unser. The abstract reads:

This paper addresses the problem of reconstructing an image from 1-bit-quantized measurements, considering a simple but nonconventional optical acquisition model. Following a compressed-sensing design, a known pseudo-random phase-shifting mask is introduced at the aperture of the optical system. The associated reconstruction algorithm is tailored to this mask. Our results demonstrate the feasibility of the whole approach for reconstructing grayscale images.

Next, we have from arxiv: Multiarray Signal Processing: Tensor decomposition meets compressed sensing by Lek-Heng Lim and Pierre Comon. The abstract reads:

We discuss how recently discovered techniques and tools from compressed sensing can be used in tensor decompositions, with a view towards modeling signals from multiple arrays of multiple sensors. We show that with appropriate bounds on coherence, one could always guarantee the existence and uniqueness of a best rank-r approximation of a tensor. In particular, we obtain a computationally feasible variant of Kruskal's uniqueness condition with coherence as a proxy for k-rank. We treat sparsest recovery and lowest-rank recovery problems in a uniform fashion by considering Schatten and nuclear norms of tensors of arbitrary order and dictionaries that comprise a continuum of uncountably many atoms.

The next paper is behind a paywall: Compressed sensing in optical coherence tomography by Nishant Mohan, Ivana Stojanovic, and W. C. Karl, Bahaa E. A. Saleh, Malvin Teich. The abstract reads:

Optical coherence tomography (OCT) is a valuable technique for non-invasive imaging in medicine and biology. In some applications, conventional time-domain OCT (TD-OCT) has been supplanted by spectral-domain OCT (SD-OCT); the latter uses an apparatus that contains no moving parts and can achieve orders of magnitude faster imaging. This enhancement comes at a cost, however: the CCD array detectors required for SD-OCT are more expensive than the simple photodiodes used in TD-OCT. We explore the possibility of extending the notion of compressed sensing (CS) to SD-OCT, potentially allowing the use of smaller detector arrays. CS techniques can yield accurate signal reconstructions from highly undersampled measurements, i.e., data sampled significantly below the Nyquist rate. The Fourier relationship between the measurements and the desired signal in SD-OCT makes it a good candidate for compressed sensing. Fourier measurements represent good linear projections for the compressed sensing of sparse point-like signals by random under-sampling of frequency-domain data, and axial scans in OCT are generally sparse in nature. This sparsity property has recently been used for the reduction of speckle in OCT images. We have carried out simulations to demonstrate the usefulness of compressed sensing for simplifying detection schemes in SD-OCT. In particular, we demonstrate the reconstruction of a sparse axial scan by using fewer than 10 percent of the measurements required by standard SD-OCT.

My webcrawler alerted me to an upcoming paper by Maxim Raginsky, Sina Jafarpour, Rebecca Willett and Robert Calderbank entitled Fishing in Poisson streams: focusing on the whales, ignoring the minnows. I am eager to read it but what is interesting is that it reminded of an example I wanted to use to explain compressive sensing. The measurements were the loading measured by fishnets of different sizes while being pulled by a boat. In the end, with fishnets of different sizes, being tried and released, one could evaluate the number and size of the fish population. This is the closest I could think of a physical embodiement of diracs and sinusoids.


And finally what looks like a course blog, we can read about Multiple Target Localization Using Compressive Sensing while Gordon Anderson blogs on Matching Buyers & Sellers – solving NxN problem with chaos.

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: 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: The EPFL CMOS CS Imager, Compressive Sampling of Pulse Trains : Spread the Spectrum !

Today, we have two papers from EPFL in Switzerland. Both papers have been submitted to ICASSP '09. One of the author also provided me some context. Since I am very much interested in hardware development, I couldn't help myself from asking questions. I know it's a bad habit but there is a cure: it's called an answer and the authors were kind enough to provide one. woohoo.

The first paper is CMOS Compressed Imaging by Random Convolution (also here) by Laurent Jacques, Pierre Vandergheynst, Alexandre Bibet, Vahid Majidzadeh, Alexandre Schmid, Yusuf Leblebici. The abstract reads:

We present a CMOS imager with built-in capability to perform Compressed Sensing. The adopted sensing strategy is the random Convolution due to J. Romberg. It is achieved by a shift register set in a pseudo-random configuration. It acts as a convolutive filter on the imager focal plane, the current issued from each CMOS pixel undergoing a pseudo-random redirection controlled by each component of the filter sequence. A pseudo-random triggering of the ADC reading is finally applied to complete the acquisition model. The feasibility of the imager and its robustness under noise and non-linearities have been confirmed by computer simulations, as well as the reconstruction tools supporting the Compressed Sensing theory.

Laurent puts the paper in context:

The first paper is about the design of a CMOS imager embedding random measurements, i.e. in the electronic analog processing of the signal. The sensing strategy used is the recent Random Convolution of J. Romberg (working without Fourier however).
We have noticed that this sensing simplifies not only the decoding/reconstruction process (where any sensing matrix-vector multiplication is resumed to some FFTs) but is is also straightforward to implement in the electronics of an imager. The convolutive filter is provided here by a simple shift-register (SR) set in a pseudo-random (LFSR controlled) configuration. This shift register results simply from the linking of 1-bit memories, one per pixel, and the convolution is reached by shifting (in few clock signals) the SR pseudo-random configuration. The random filter acts on the light gathered by the CMOS photodiodes by flipping the direction of the output current according to the stored bit. Kirchoff's law allows then to gather the measurements by summing the currents on wires (here, column by column to limit the current value). There are of course similarities between our imager and other projects as the "one pixel camera" of Rice's group, or the Georgia Tech Imager. Our architecture is however characterized by its specialization to the convolutive aspect of the selected sensing.

I then asked Laurent the following:

In the CMOS imager paper, do I understand correctly that the \phi x operation is the one given under the figure 1.

[the reason I asked is that I feel it is important for the folks involved with hardware development to give as much detail as possible to the theoretical/applied community in order to maybe push some other boundaries].

To which Laurent responded:

Yes. A random convolution is random in two aspects : in the filter used in the convolution, and in the random sampling of the final convolution to provide M

In furthering this thought, I then asked if they thought that the RIP-1 random matrices of Indyk, Gilbert
et al could also be easily implemented in this technology (an implementation is here but there are others)

Laurent replied with:

Well. I'm not sufficiently familiar with this kind of sparse random matrices.
I'm not sure we could implement as simply with a shift-register as we do for the random convolution.
If big storage are needed for the sensing matrix, i.e. bigger than the number of pixels, then the Georgia Tech Analog imager is for me better (they included for instance the Noiselet sensing).
If this storage is smaller than N bits, e.g. if two rows of the sensing matrix are connected by a known permutation, then perhaps a particular SR configuration is possible. A careful study has to be done.

However, our system is very easily adaptable to Toeplitz sensing matrix (see Jarvis Haupt,Waheed Bajwa, Gil Raz and Robert Nowak , Toeplitz compressed sensing matrices with applications to sparse channel estimation). To reach that, it is sufficient to generate a pseudo-random sequence larger than the number of pixels, i.e. using a LFSR with a looping period larger than 2N (with N pixels).

Let us note that this Toeplitz matrix has also been used in the context of Coded aperture by Roummel Marcia and Rebecca Willett in Compressive Coded Aperture Superresolution Image Reconstruction (additional information can be found here)

Finally, I asked:

How can one map the trade study performed by the Rice folks on their camera to your camera ?
( http://nuit-blanche.blogspot.com/2007/12/compressed-sensing-single-pixel-imaging.html
) In other words, do you have issues with dynamical range since you seem to have limit on the current, etc...

Laurent responded with the following insight:

BTW, I think that Georgia Tech imager met the same issue and this is probably one reason they use a 16x16 block separation (This is not the only reason for such block: the basis functions stored in their imager take also less memory). However, we are currently in discussion with our collaborators in the EPFL Microelectronic lab (LSM) to see how to increase the number of summed pixels (this will be mandatory for a new prototype with a larger number of pixels, e.g. 256x256)

For the rest, we haven't yet realized a deep trade study of this CS imager. What we can say however :

* this CS imager is definitely **not** the kind of imager that will be put inside an end-user device (e.g. mobile phone). CS cannot fight with imaging device able to embed a coder like JPEG2K.

* following the key principles of CS and the conclusions arose by other groups, we foresee that such a camera will be perfect for devices with low CPU power and targeting low energy consumption. I have in mind applications like a small "camera pill" designed to visualize the whole digestive system (see [1]), or flying robotic system that need a very light camera (e.g. for egomotion analysis)

* the system we use is very flexible in the sense that it could be translated to other 2-D grid of sensors currently limited in resolution because of each "pixel" circuitry. For instance, as mentionned in our paper, in collaboration with the LSM lab, we are going to apply this system to a grid of biosensors recording the electrical signal produced by a network of neuronal cells grown on the grid. Some studies proves that the signal to record will be both sparse in space and time [2]. Current CMOS biosensors recording such signals are limited in their resolution since each pixel needs a very complex electronic. A "CS analog electronic" could give access to higher resolution by reducing this complexity, i.e. a kind of economy of scale by working on a group of pixels, using random linear combinations of currents, instead of duplicating the same circuitry for each pixels.


References :

[1] : http://query.nytimes.com/gst/fullpage.html?res=9C00E6DC163CF933A05756C0A9669C8B63&sec=&spon=&pagewanted=1

[2] : M Jenkner, M Tartagni, A Hierlemann, and R Thewes, “Cell-based cmos sensor and actuator arrays,” IEEE Journ. Solid-State Circuits, vol. 39, no. 12, pp. 2431 – 2437, Dec 2004.

This hardware is now listed in the Compressive Sensing Hardware page.

The second paper is Compressive Sampling of Pulse Trains : Spread the Spectrum ! (also here) by Farid Naini, Rémi Gribonval, Laurent Jacques and Pierre Vandergheynst. The abstract reads:

In this paper we consider the problem of sampling far below the Nyquist rate signals that are sparse linear superpositions of shifts of a known, potentially wide-band, pulse. This signal model is key for applications such as Ultra Wide Band (UWB) communications or neural signal processing. Following the recently proposed Compressed Sensing methodology, we study several acquisition strategies and show that the approximations recovered via minimization are greatly enhanced if one uses Spread Spectrum modulation prior to applying random Fourier measurements. We complement our experiments with a discussion of possible hardware implementation of our technique.

To give some context, Laurent points out the following:

The second paper aims at showing how the use of a simple spread spectrum method can lead to good compressive measurements of Ultra WideBand Signals (UWB). Our study is restricted to the model of a pulse train signal, i.e. sparse in a shift-invariant dictionary generated by a short pulse. We show experimentally that, for this signal model, a SS strategy combined with the random selection of Fourier frequencies is as good as a Gaussian random sensing when the reconstruction quality is expressed in the signal domain (rather than in the dictionary coefficients). In addition, replacing the Fourier matrix by a Walsh-Hadamard transform reduces only slightly the performance and the robustness of the method, while this alternative is more appealing for the building of an analog UWB sensor (for which we provide also an idealized electronic scheme). On the theoretical side, it seems that our approach is very similar to the one of T. Do et al. about "Fast compressive sampling with structurally random matrices" (ICASSP'08), recently quoted on NB. Unfortunately, we were not aware of this work at the writing of our ICASSP paper and we will add for sure a reference to it in the revision.

On top what was kindly said about the utility of this blog, I note the use of SPARCO and SPGL1.

Finally, the Terahertz imaging technique devised at Rice and using the one pixel camera ( we mentioned it here ) has hit the wires here and here.

CS: Necessary and Sufficient Conditions on Sparsity Pattern Recovery, Seeing Speech: Capturing Vocal Tract Shaping using Real-time MR and a talk

Here is a fascinating paper . We are generally accustomed to big O notation for the number of measurements necessary to recover signals in CS, this paper addresses the issue of the functional dependence of the constant that goes into the big O notation as a function of the signal-to-noise ratio (SNR) and mean-to-average ratio (MAR). The paper is Necessary and Sufficient Conditions on Sparsity Pattern Recovery and was written by Alyson Fletcher, Sundeep Rangan, and Vivek Goyal. The abstract reads:

The problem of detecting the sparsity pattern of a k-sparse vector in Rn from m random noisy measurements is of interest in many areas such as system identification, denoising, pattern recognition, and compressed sensing. This paper addresses the scaling of the number of measurements m, with signal dimension n and sparsity-level nonzeros k, for asymptotically-reliable detection. We show a necessary condition for perfect recovery at any given SNR for all algorithms, regardless of complexity, is m = (k log(n − k)) measurements. Conversely, it is shown that this scaling of (k log(n − k)) measurements is sufficient for a remarkably simple “maximum correlation” estimator. Hence this scaling is optimal and does not require more sophisticated techniques such as lasso or matching pursuit. The constants for both the necessary and sufficient conditions are precisely defined in terms of the minimum-to average ratio of the nonzero components and the SNR. The necessary condition improves upon previous results for maximum likelihood estimation. For lasso, it also provides a necessary condition at any SNR and for low SNR improves upon previous work. The sufficient condition provides the first asymptotically-reliable detection guarantee at finite SNR.

Much more can be gathered from reading the paper.

The next paper does not make a specific headline with respect to Compressed Sensing. This is good, it means that the Compressed Sensing approach is becoming mature (at least in fMRI) to the point where it enables new ways of obtaining data thereby producing new ways of matching different types of data (here MRI and voice recording). It's a paper by Erik Bresch, Yoon-Chul Kim, Krishna S. Nayak, Dani Bird, and Shrikanth Narayanan entitled Seeing Speech: Capturing Vocal Tract Shaping using Real-time Magnetic Resonance Imaging (also here). The beginning of the paper reads:

Understanding human speech production is of great interest from engineering, linguistic, and several other research points of view. While several types of data available to speech understanding studies lead to different avenues for research, in this article we focus on real-time (RT) magnetic resonance imaging (MRI) as an emerging technique for studying speech production. We discuss the details and challenges of RT magnetic resonance (MR) acquisition and analysis, and modeling approaches that make use of MRI data for studying speech production.

Here is an interesting new approach whereby compressed sensing is used not to reconstruct an image but to grab essential characteristics of the phenomena being monitored. This is along the lines of the manifold techniques (red arrows in the graph in the Compressed Sensing Big Picture graphic). As we all know the reconstruction is a testimony on how many samples are needed to get an information, the real eldorado is in using these compressed measurements directly. In fMRI, there has much work in finding the right trajectories in the k-space to produce adequate full images, the next steps is obviously a patchwork of techniques using different measurement tools and machine learning techniques to enable the right data fusion process and thereby produce new methodologies and new discoveries ( I have yet to write on the process which I think needs a very good data fusion effort).



On a different note, Trac Tran will give a talk at Simon Fraser University on Fast, Efficient, and Practical Algorithms for Compressed Sensing. Let us note the emergence of a new greedy algorithm: GOMP.

Date: Thursday, May 22, 2008
Time: , 3:00 pm to 4:00 pm
Location: SFU ASSC-1: Room 10041

It is going to be listed on the CS calendar. The abstract of the talk is:

In the conventional uniform sampling framework, the Shannon/Nyquist theorem tells us to sample a signal at a rate at least two times faster than its bandwidth for the original signal to be perfectly reconstructed from its samples. Recently, compressed sensing has emerged as a revolutionary signal sampling paradigm which shows that Shannon theorem is indeed overly pessimistic for signals with a high degree of sparsity or compressibility. The compressed sensing framework demonstrates that a small number of random linear projections, called measurements, contains sufficient information for signal reconstruction, even exactly. The two key components of compressed sensing are: (i) the sensing matrix at the encoder must be highly incoherent with the sparsifying signal transformation; and (ii) sophisticated non-linear algorithms such as basis pursuit or orthogonal matching pursuit are employed at the decoder to recover the sparsest signal from the received measurements.

The first part of this talk gives an overview of the new compressed sensing framework along with the most elegant breakthrough results in the field. The second part focuses on two recent compressed sensing discoveries from the JHU Digital Signal Processing Lab. Particularly, a fast and efficient sampling algorithm for compressed sensing based on structurally random matrices will be presented. Our proposed sampling scheme provides several crucial features for practical implementation: fast computable, memory efficient, streaming capable, and hardware friendly while retaining comparable theoretical performance bounds with current state-of-the-art techniques. Secondly, at the decoder side, we present a novel iterative reconstruction algorithm for compressed sensing called Generalized Orthogonal Matching Pursuit (GOMP) that can adaptively, at each iteration step, admit new atoms to join the current selected set from a small candidate set while discard from the selected set atoms that might be highly regarded in previous steps. Simulation results show that GOMP’s performance far exceeds the best existing iterative algorithms with reasonable complexity overhead. Finally, future research directions in compressed sensing are also discussed if time permits.

Compressed Sensing: a blog, Autonomous geometric precision error estimation in low-level computer vision tasks, Neuroscience Datasets

Image via Wikipedia

I just recently found a blog that seems to focus on Compressed Sensing. In all, I have to say that Google is not doing a great job at taking into account labels from its own platform. In particular, I have found some odd discrepancies between the pagerank of some pages and the number of people that use Google reader to view them. Anyway, the blog of Andrés Corrada-Emmanuel entitled De Rerum Natura brings up some interesting applications in the determination of elevation models (DEM) from photographs as he has to deal with underdetermined systems of equations.. The postings are at:

http://www.corrada.com/blog/category/compressed-sensing/

he just had his paper accepted at ICML 08. The title is Autonomous geometric precision error estimation in low-level computer vision tasks by Andrés Corrada-Emmanuel and Howard Schultz. The abstract reads:

Errors in map-making tasks using computer vision are sparse. We demonstrate this by considering the construction of digital elevation models that employ stereo matching algorithms to triangulate real-world points. This sparsity, coupled with a geometric theory of errors recently developed by the authors, allows for autonomous agents to calculate their own precision independently of ground truth. We connect these developments with recent advances in the mathematics of sparse signal reconstruction or compressed sensing. The theory presented here extends the autonomy of 3-D model reconstructions discovered in the 1990s to their errors.

This is new. I don't think I have ever seen anybody talking about precision errors being a sparse signals before.


With the Netflix competition, we saw a lot of very interesting developments. One of them, as Andrew Gelman points out, is the fact that with a flurry of algorithms to choose from, data is paramount in leading to new and improved findings. An example of something similar in Neuroscience is the neuron challenge mentioned before. However, as echoed in this entry by Hal Daume III ( Those Darn Biologists...) there is very little incentive for biologists to publish their results with an analysis using new algorithms: This is not getting their papers published. A new initiative may help in that respect: the CRCNS - Collaborative Research in Computational Neuroscience - Data sharing activity is making biological / neuroscience datasets available for download here. This is prodigious idea. It currently lists datasets in:

• Primary visual cortex
• Auditory cortex
• Avian Auditory
• Hippocampus
• Eye movements

While The following additional data sets will be available by about June 2008:

• V4 responses to synthetic parametric stimuli. (From Jack Gallant lab, UC Berkeley).
• Responses in areas V1, V2 and V4 using precisely the same stimuli. Data collected to facilitate functional comparisons across successive stages of sensory processing. (From Jack Gallant lab, UC Berkeley).
• Tutorial on understanding intracellular recordings in sensory areas and accompanying data. The data are intracellular (whole-cell patch) recordings obtained in vivo from visual, auditory, somatosensory, and motor areas of the neocortex by the laboratories of Judith Hirsch, USC; Anthony Zador, CSHL; Michael DeWeese, UC Berkeley and Michael Brecht, Humboldt University Berlin. These data include not only spikes but also membrane voltages or currents generated by synaptic connections and intrinsic membrane channels.
• Synaptic plasticity data – Cortical slice data acquired in order to examine the effects of complex spike trains in the induction of long-term synaptic modification and recordings of primary visual cortical neurons made during stimulation. (From Yang Dan lab, UC Berkeley).
• Recordings from hippocampal CA1 neurons during open field foraging. (From Buzsáki lab, Rutgers University).