CS: Bob's questions, MPTK, flat-panel-detector cone-beam CT, A data-driven sparse GLM for fMRI analysis, Off-axis compressed holographic microscopy, LDPC Codes for Compressed Sensing

Let give Bob some props for putting near real time his investigation on the CMP algorithm and putting up his doubts..I am sure that some of you can help him out in answering these questions, don't be shy:

• So, l_1 minimization works fine, but greedy methods perform much better for certain sparse signals?
• Why Isn't BP Working?

As mentioned yesterday, The Matching Pursuit Tool Kit (MPTK) provides a fast implementation of the Matching Pursuit algorithm for the sparse decomposition of multichannel signals. It comprises a C++ library, standalone command line utilities, and some scripts for running it and plotting the results through Matlab. Some more informations can be found here : http://mptk.irisa.fr/. The downloads can be found here : https://gforge.inria.fr/frs/?group_id=36 .

Here are the two papers mentioned yesterday by Emil Sidky and Jong Chul Ye:

Evaluation of sparse-view reconstruction from flat-panel-detector cone-beam CT by Junguo Bian, Jeffrey H Siewerdsen, Xiao Han, Emil Y Sidky, Jerry L Prince, Charles A Pelizzari and Xiaochuan Pan. The attendant presentation is here. The abstract reads:

Flat-panel-detector x-ray cone-beam computed tomography (CBCT) is used in a rapidly increasing host of imaging applications, including image-guided surgery and radiotherapy. The purpose of the work is to investigate and evaluate image reconstruction from data collected at projection views significantly fewer than what is used in current CBCT imaging. Specifically, we carried out imaging experiments using a bench-top CBCT system that was designed to mimic imaging conditions in image-guided surgery and radiotherapy; we applied an image reconstruction algorithm based on constrained total-variation (TV)-minimization to data acquired with sparsely sampled view-angles and conducted extensive evaluation of algorithm performance. Results of the evaluation studies demonstrate that, depending upon scanning conditions and imaging tasks, algorithms based on constrained TV-minimization can reconstruct images of potential utility from a small fraction of the data used in typical, current CBCT applications. A practical implication of the study is that the optimization of algorithm design and implementation can be exploited for considerably reducing imaging effort and radiation dose in CBCT.

A data-driven sparse GLM for fMRI analysis using sparse dictionary learning with MDL criterion by Kangjoo Lee, Sungho Tak, Jong Chul Ye. The abstract reads:

We propose a novel statistical analysis method for functional MRI to overcome the drawbacks of conventional datadriven methods such as the independent component analysis (ICA). Although ICA has been broadly applied to functional MRI due to its capacity to separate spatially or temporally independent components, the assumption of independence has been challenged by recent studies showing that ICA does not guarantee independence of simultaneously occurring distinct activity patterns in the brain. Instead, sparsity of the signal has been shown to be more promising. This coincides with biological findings such as sparse coding in V1 simple cells, electrophysiological experiment results in the human medial temporal lobe, and etc. The main contribution of this paper is, therefore, a new data driven fMRI analysis that is derived solely based upon the sparsity of the signals. A compressed sensing based data-driven sparse generalized linear model is proposed that enables estimation of spatially adaptive design matrix as well as sparse signal components that represent synchronous, functionally organized and integrated neural hemodynamics. Furthermore, an MDL based model order selection rule is shown to be essential in selecting unknown sparsity level for sparse dictionary learning. Using simulation and real fMRI experiments, we show that the proposed method can adapt individual variation better compared to the conventional ICA methods.

I also just found the following hardware development: Off-axis compressed holographic microscopy in low light conditions by Marcio Marim, Elsa Angelini, Jean-Christophe Olivo-Marin and Michael Atlan. The abstract reads;

This article reports a demonstration of off-axis compressed holography in low light level imaging conditions. An acquisition protocol relying on a single exposure of a randomly undersampled diffraction map of theoptical field, recorded in high heterodne gain regime, is proposed. The image acquisition scheme is based on compressed sensing, a theory establishing that near-exact recovery of an unknown spare signal is possible from a small number of non-structured measurements. Image reconstruction is further enhanced by inroducing an off-axis spatial support constraint to the image estimation algorithm. We report accurate experimental recovering of holographhic images of a resolution target in low light conditions with a frame exposure of 5 microseconds, scaling down measurment to 9 % of random pixels within the array detector.

and this arxiv paper: LDPC Codes for Compressed Sensing by Alexandros G. Dimakis, Roxana Smarandache, Pascal O. Vontobel. The abstract reads:

We present a mathematical connection between channel coding and compressed sensing. In particular, we link, on the one hand, \emph{channel coding linear programming decoding (CC-LPD)}, which is a well-known relaxation of maximum-likelihood channel decoding for binary linear codes, and, on the other hand, \emph{compressed sensing linear programming decoding (CS-LPD)}, also known as basis pursuit, which is a widely used linear programming relaxation for the problem of finding the sparsest solution of an under-determined system of linear equations. More specifically, we establish a tight connection between CS-LPD based on a zero-one measurement matrix over the reals and CC-LPD of the binary linear channel code that is obtained by viewing this measurement matrix as a binary parity-check matrix. This connection allows the translation of performance guarantees from one setup to the other. The main message of this paper is that parity-check matrices of "good" channel codes can be used as provably "good" measurement matrices under basis pursuit. In particular, we show that for basis pursuit the deterministic LDPC matrices constructed by Gallager form the best known sparse measurement matrices, in the sense that they provide the largest provable recovery guarantees for sparse measurement matrices and sparse signals.

Credit: NASA/JPL/University of Arizona, Layering in Exhumed Crater at Meridiani Planum (PSP_001374_1805) on Mars.

CS: Nuit Blanche's readers' Mailbag

Emil Sidky just sent me the following:

Hi Igor,
I would like to point out recent work we did in collaboration with Hopkins on sparse-view CT in Physics of Medicine and Biology:

http://iopscience.iop.org/0031-9155/55/22/001

It's linked also on Jeff's I-STAR page (a lot of nice stuff there on CT image science):

http://www.jhu.edu/istar/news.html

It's a featured article, and therefore free access to anyone. It even got a little press on medicalphysicsweb.org

The main points of interest:

• The reconstructed images are evaluated objectively by a number of image quality metrics.
• The next point echo's Mark Neifeld's observation that all digital imaging has always been compressive. We show that even with the standard number of CT views, constrained TV-minimization will, in general, lead to a different image than standard filtered back-projection algorithms. (I always feel uneasy when I see the claim that CS beats the Nyquist sampling theorem, because truly fully-sampled data in CT does not exist.)
• Nonetheless, the CS-motivated idea of employing constrained, TV-minimization does appear to be robust. One criticism we often encounter is that such algorithms apply strictly to piece-wise constant images. Well, due to non-ideality of CT data relative to the X-ray transform image model, reconstructed images are not piecewise constant. Nevertheless, constrained, TV-minimization still yields high image quality for sparse-view CT data.

Jong Chul Ye also sent me this:

You might be interested in our recent paper which will appear in IEEE Trans. on Medical Imaging.

K. Lee, S. Tak, and J. C. Ye, "A data-driven sparse GLM for fMRI analysis using sparse dictionary learning with MDL criterion," IEEE Trans. Medical Imaging, Special issue on "Compressive sensing for biomedical imaging", November 2010, Accepted .

This paper demonstrates that compressive sensing theory is very useful for fMRI signal analysis by enabling a fully data-driven approach.

Finally, Ronan Le Boulch sent me the following:

I am a french engineer working on the Metiss team with Remi Gribonval and I am currently updating the MPTK Pursuit Toolkit. I have updated MPTK Library to a 0.5.9 version since March of this year and I would like to know if it's possible to add a note or an annoucement of this release under the Nuit Blanche website.

I don't know if you know this library or if you have ever used it but here is a summary :

The Matching Pursuit Tool Kit (MPTK) provides a fast implementation of the Matching Pursuit algorithm for the sparse decomposition of multichannel signals. It comprises a C++ library, standalone command line utilities, and some scripts for running it and plotting the results through Matlab.

Some more informations can be found here : http://mptk.irisa.fr/
The downloads can be found here : https://gforge.inria.fr/frs/?group_id=36
The tracker for Bugs or Support requests can be found here : https://gforge.inria.fr/tracker/?group_id=36

Thanks Ronan, Jong and Emil for providing some context and by the same token making the web a better place. I'll feature your papers and libraries tomorrow. 

Image: NASA/JPL/University of Arizona, Blocks in the Olympus Mons (PSP_003450_1975)

No Comment (Part II)

(From here)

No Comment

From here.

CS: Bombshell announcement from Space: Compressive Sensing IS Relevant in TRL9 mission critical systems: Feasibility and performances of compressed-sensing and sparse map-making with Herschel/PACS data

Forget the Arsenide based life form found in some pond in California, this is bigger. You've watched the launch, you've waited a long time (see the P.S. here, see also here , here, here, here or here) and today is the culmination of all this wait: A Compressed sensing based encoding system can replace other compression encodings used in mission critical TRL9 systems such as those in space exploration. This is big in many respects, one of them is that now our collective narrative  can say that MRI is not the only application in which compressive sensing is highly relevant and mission critical Woohoo! If you know somebody who works in CS and does not read the blog as often as you do, you want to forward this information out to her/him. Without further due, here is the paper, enjoy:

Feasibility and performances of compressed-sensing and sparse map-making with Herschel/PACS data by Nicolas Barbey, Marc Sauvage,Jean-Luc Starck, Roland Ottensamer, Pierre Chanial. The abstract reads:

The Herschel Space Observatory of ESA was launched in May 2009 and is in operation since. From its distant orbit around L2 it needs to transmit a huge quantity of information through a very limited bandwidth. This is especially true for the PACS imaging camera which needs to compress its data far more than what can be achieved with lossless compression. This is currently solved by including lossy averaging and rounding steps on board. Recently, a new theory called compressed-sensing emerged from the statistics community. This theory makes use of the sparsity of natural (or astrophysical) images to optimize the acquisition scheme of the data needed to estimate those images. Thus, it can lead to high compression factors.
A previous article by Bobin et al. (2008) showed how the new theory could be applied to simulated Herschel/PACS data to solve the compression requirement of the instrument. In this article, we show that compressed-sensing theory can indeed be successfully applied to actual Herschel/PACS data and give significant improvements over the standard pipeline. In order to fully use the redundancy present in the data, we perform full sky map estimation and decompression at the same time, which cannot be done in most other compression methods. We also demonstrate that the various artifacts affecting the data (pink noise, glitches, whose behavior is a priori not well compatible with compressed-sensing) can be handled as well in this new framework. Finally, we make a comparison between the methods from the compressed-sensing scheme and data acquired with the standard compression scheme. We discuss improvements that can be made on ground for the creation of sky maps from the data.

CS: CMP continued, Coherence, Compressive Sensing and Random Sensor Arrays

[There are 10 hours left  to solve this business model riddle]

Bob Sturm is continuing his investigation with the CMP reconstruction algorithm in:

• Recovery of Sparse Signals with Cyclic Matching Pursuit and Compressive Measurements: Now With Orthogonal Least Squares
• Recovery of Sparse Signals from Compressive Measurements: Now with Other Flavors

I also just found the following: Coherence, Compressive Sensing and Random Sensor Arrays by Lawrence Carin, Dehong Liu and Bin Guo. The abstract reads:

Random sensor arrays are examined from a compressive sensing (CS) perspective, particularly in terms of the coherence of CS matrices. It is demonstrated that the maximum sidelobe level of an array corresponds to the coherence of interest for CS. This understanding is employed to explicitly quantify the accuracy of array source localization, as a function of the number of sources and the noise level. The analysis demonstrates that the CS theory is applicable to arrays in vacuum as well as in the presence of a surrounding linear media; further, the presence of a surrounding media with known properties may be used to improve array performance, with this related to phase conjugation and time reversal. Several numerical results are presented to demonstrate the theory.

Image Credit: NASA/JPL/Space Science Institute, N00165424.jpg was taken on December 01, 2010 and received on Earth December 01, 2010. The camera was pointing toward SATURN at approximately 861,657 kilometers away, and the image was taken using the CL1 and CL2 filters.

Real-time People detection and tracking with multiple Kinect cameras

From Pierre Vandergheynst's tweet stream: Real-time People detection and tracking with multiple Kinect cameras





What type of compressive sensing could we do on top of these Kinect cameras ?

CS: CMP, Depth, EEGs, l_p versus l_1, JPEG + CS, Some matrix results and a seminar.

We have many papers today, but first Bob Sturm has a new entry on tests he has performed on the CMP reconstruction algorithm in: Recovery of Sparse Signals with Cyclic Matching Pursuit and Compressive Measurements .

Many of the papers are related to matrix completion at the end but with all the talk about 3d in the past few entries, something equally exciting is getting into the business of learning depth information as in Learning sparse representations of depth by Ivana Tosic, Bruno A. Olshausen, Benjamin J. Culpepper. The abstract reads:

We propose a method for learning sparse representations of depth (disparity) maps, which is able to cope with noise and unreliable depth measurements. The proposed algorithm relaxes the usual assumption of the stationary noise model in sparse coding and enables learning from data corrupted with spatially varying noise or uncertainty. Different noise statistics at each pixel location are inferred from the data, and the learning rule is adapted with respect to the noise level. The effectiveness of the method is demonstrated by denoising depth maps obtained from laser range scanners and a time of flight camera. We then propose a two-layer graphical model for inferring depth from stereo by including a sparsity prior on local depth features learned by the algorithm. Depth inference is defined as a maximum aposteriori estimation problem on this graph. In contrast to smoothness priors that are based on pairwise correlations, sparse priors capture higher-order dependencies in the depth structure. Our results demonstrate that sparse priors reduce the depth estimation error obtained by the state of the art graph cut algorithm.

then we have a paper on a continuing interest of mine: Quantifying the performance of compressive sensing on scalp EEG signals by  Amir M. Abdulghani, Alexander J. Casson and Esther Rodriguez-Villegas. The abstract reads: 

Compressive sensing is a new data compression paradigm that has shown significant promise in fields such as MRI. However, the practical performance of the theory very much depends on the characteristics of the signal being sensed. As such the utility of the technique cannot be extrapolated from one application to another. Electroencephalography (EEG) is a fundamental tool for the investigation of many neurological disorders and is increasingly also used in many non-medical applications, such as Brain-Computer Interfaces. This paper characterises in detail the practical performance of different implementations of the compressive sensing theory when applied to scalp EEG signals for the first time. The results are of particular interest for wearable EEG communication systems requiring low power, real-time compression of the EEG data.

The next paper has a surprising statement on comparing l_p and l_1 recovery:

On the Performance of Sparse Recovery via L_p-minimization (0 \le p \le 1) by Meng Wang, Weiyu Xu, Ao Tang. The abstract reads:

It is known that a high-dimensional sparse vector x* in R^n can be recovered from low-dimensional measurements y= A^{m*n} x* (m \lt n) . In this paper, we investigate the recovering ability of l_p-minimization (0 \le p \le1) as p varies, where l_p-minimization returns a vector with the least l_p ``norm'' among all the vectors x satisfying Ax=y. Besides analyzing the performance of strong recovery where l_p-minimization needs to recover all the sparse vectors up to certain sparsity, we also for the first time analyze the performance of ``weak'' recovery of l_p-minimization (0 \le p \lt1) where the aim is to recover all the sparse vectors on one support with fixed sign pattern. When m/n goes to 1, we provide sharp thresholds of the sparsity ratio that differentiates the success and failure via l_p-minimization. For strong recovery, the threshold strictly decreases from 0.5 to 0.239 as p increases from 0 to 1. Surprisingly, for weak recovery, the threshold is 2/3 for all p in [0,1), while the threshold is 1 for l_1-minimization. We also explicitly demonstrate that l_p-minimization (p \lt 1) can return a denser solution than l_1-minimization. For any m/n \lt 1, we provide bounds of sparsity ratio for strong recovery and weak recovery respectively below which l_p-minimization succeeds with overwhelming probability. Our bound of strong recovery improves on the existing bounds when m/n is large. Regarding the recovery threshold, l_p-minimization has a higher threshold with smaller p for strong recovery; the threshold is the same for all p for sectional recovery; and l_1-minimization can outperform l_p-minimization for weak recovery. These are in contrast to traditional wisdom that l_p-minimization has better sparse recovery ability than l_1-minimization since it is closer to l_0-minimization. We provide an intuitive explanation to our findings and use numerical examples to illustrate the theoretical predictions.

Image representation by compressive sensing for visual sensor networks by Bing Han, Feng Wu, Dapeng Wu. The abstract reads:

This paper addresses the image representation problem in visual sensor networks. We propose a new image representation method for visual sensor networks based on compressive sensing (CS). CS is a new sampling method for sparse signals, which is able to compress the input data in the sampling process. Combining both signal sampling and data compression, CS is more capable of image representation for reducing the computation complexity in image/video encoder in visual sensor networks where computation resource is extremely limited. Since CS is more efficient for sparse signals, in our scheme, the input image is firstly decomposed into two components, i.e., dense and sparse components; then the dense component is encoded by the traditional approach (JPEG or JPEG 2000) while the sparse component is encoded by a CS technique. In order to improve the rate distortion performance, we leverage the strong correlation between dense and sparse components by using a piecewise autoregressive model to construct a prediction of the sparse component from the corresponding dense component. Given the measurements and the prediction of the sparse component as initial guess, we use projection onto convex set (POCS) to reconstruct the sparse component. Our method considerably reduces the number of random measurements needed for CS reconstruction and the decoding computational complexity, compared to the existing CS methods. In addition, our experimental results show that our method may achieves up to 2dB gain in PSNR over the existing CS based schemes, for the same number of measurements.

Detection of sparse variable functions by Ghislaine Gayraud, Yuri Ingster. The abstract reads:

We consider the problem of detection of smooth high variable signal function in the white noise model. We assume that the struture of the signal function is additive sparse. In order to detect the signal, we wish to test the null hypothesis characterized by no signal against composite nonparametric alternative which is composed of smooth additive sparse signal functions. The testing problem is solved according to the minimax approach. We prove that the results for detection of sparse high dimensional vectors can be extended to the problem under consideration.

The Minimum-Rank Gram Matrix Completion via Fixed Point Continuation Method by Yue Ma, Lihong Zhi. The abstract reads:

In this paper we present a modified FPC-BB algorithm for solving the minimum-rank Gram matrix completion problem, i.e., computing a representation for a positive semidefinite polynomial as a sum of minimum number of squares of polynomials in $Q[x_1,...,x_s]$. We prove the convergence of the algorithm under some conditions. Numerical results show that our algorithm is efficient and robust.

New Null Space Results and Recovery Thresholds for Matrix Rank Minimization by Samet Oymak, Babak Hassibi. The abstract reads:

Nuclear norm minimization (NNM) has recently gained significant attention for its use in rank minimization problems. Similar to compressed sensing, using null space characterizations, recovery thresholds for NNM have been studied in \cite{arxiv,Recht_Xu_Hassibi}. However simulations show that the thresholds are far from optimal, especially in the low rank region. In this paper we apply the recent analysis of Stojnic for compressed sensing \cite{mihailo} to the null space conditions of NNM. The resulting thresholds are significantly better and in particular our weak threshold appears to match with simulation results. Further our curves suggest for any rank growing linearly with matrix size $n$ we need only three times of oversampling (the model complexity) for weak recovery. Similar to \cite{arxiv} we analyze the conditions for weak, sectional and strong thresholds. Additionally a separate analysis is given for special case of positive semidefinite matrices. We conclude by discussing simulation results and future research directions.

Nuclear norm penalization and optimal rates for noisy low rank matrix completion by Vladimir Koltchinskii, Alexandre B. Tsybakov, Karim Lounici. The abstract reads:

This paper deals with the trace regression model where $n$ entries or linear combinations of entries of an unknown $m_1\times m_2$ matrix $A_0$ corrupted by noise are observed. We propose a new nuclear norm penalized estimator of $A_0$ and establish a general sharp oracle inequality for this estimator for arbitrary values of $n,m_1,m_2$ under the condition of isometry in expectation. Then this method is applied to the matrix completion problem. In this case, the estimator admits a simple explicit form and we prove that it satisfies oracle inequalities with faster rates of convergence than in the previous works. They are valid, in particular, in the high-dimensional setting $m_1m_2\gg n$. We show that the obtained rates are optimal up to logarithmic factors in a minimax sense and also derive, for any fixed matrix $A_0$, a non-minimax lower bound on the rate of convergence of our estimator, which coincides with the upper bound up to a constant factor. Finally, we show that our procedure provides an exact recovery of the rank of $A_0$ with probability close to 1. We also discuss the statistical learning setting where there is no underlying model determined by $A_0$ and the aim is to find the best trace regression model approximating the data.

Finally, there was a seminar some days ago on compressive sensing. The reason I am mentioning it is because of the speaker and company:

Compressed Sensing: Overview, and Applications in Imaging
Abdorreza Heidari
T-Ray Science Inc., Waterloo, Ontario

Compressed Sensing or Compressive Sampling (CS) uses a fairly small number of linear projections of a multi-dimensional signal (such as image) to reconstruct the signal. It is an efficient sampling scheme which utilizes sparsity, and improves the acquisition process by not sampling redundant data as is done in conventional sensing methods. The CS approach has been introduced recently, yet it is revolutionizing many fields such as imaging and sensing, data acquisition, compression and coding, etc. Currently there are several active fields in imaging, including MRI, low-light and sensitive cameras, and single-pixel cameras, which are utilizing the tools that mathematicians have developed under the CS umbrella.

A general overview of the compressed sensing method is presented. Conventionally data acquisition process is complex, costly, and time-consuming which is not attractive for practical applications. However, in CS, the acquisition process is fairly simple, and most processing is done at the data recovery. In other words, in conventional sensing methods, we usually have smart encoders and dumb decoders, while in CS, we have dumb encoders and smart decoders. CS acquisition and recovery processes are numerically stable. Furthermore, same software or hardware implementation can be used for any compressible signal class (Universality).

We study the single-pixel camera concept as an example of a CS-based imaging system. A single-pixel camera uses a set of random masks to acquire the projection measurements. To implement a terahertz camera, we propose a novel method for a compact mask design, and prove the feasibility of the method and the image recovery.

An Insect-Eye Like Panoptic Camera (3D / 360 degrees)

I am sure y'all are enjoying the different hacks using the Kinect at the Kinect Hacks blog. In the meantime, Serguey Ten just gave an explanation of how the Kinect camera works. In a different direction, Daniel Reetz also pointed this camera built in Switzerland, but more impressive is the , also built in Switzerland, camera that Pierre Vandergheynst just mentioned on his tweet stream and that he is presenting in this video:

Thanks Pierre.

A cash prize in the RMM blog

If you feel that this riddle can be solved (I don't), you may get 500 euros or about US$650. You have until December 3rd, 5PM Paris time (GMT+1) -that would be 10AM US Central Time-