One more word on monitoring the Deepwater Horizon well.

Following up on the recent entries on BP's Deepwater Horizon well and the need for its monitoring, it occurred to me that most petroleum engineers would recognize the words "compressive sensing" as being the technique that uses the l_1 sparsity inducing norm to reconstruct signals for seismic waves probing. It isn't so. Compressive Sensing is really about mixing the right type of probing waves (seismic, ultrasonic,...) or nuclear sources (neutron, gammas,...). By this I mean several sources located in different locations being fired in parallel (not sequentially). The way you mix them is what compressive sensing is really about. Much of the work that started since 2004 on the subject should allow interested parties to get the information they are looking for much faster. In effect, if mixing is done right, compressive sensing should provide some sorts good resolution in space or time of the changes happening under the seabed floor while the relief well is being dug.

To whom it may concern: this blog is being read by more than a thousand specialists from universities and industry everyday. If there is an interest I am sure that some of them could sign an NDA to provide guidance on how to do this right. Also, since the summer session is coming up, it is a good opportunity to get the academic folks to be working full time on this.

Image of burning methane at the Deepwater site courtesy of David Valentine (via Scientific American)

Monitoring the Deepwater Horizon well.

Following up on yesterday's entry (Deepwater Horizon should not become our Event Horizon), here is one set-up that could be used to monitor the conditions of the Deepwater Horizon well and its surroundings as the relief well gets close to the main well. In this configuration, the wave is seismic but it can be adapted with nuclear and other types of probing measurements. Compressive Sensing provides a nice way to demultiplex all these signals but more importantly it can detect with few measurements changes in the configuration of the soil.

Credit: I am taking as an example a figure found from one of Felix Herrmann's presentation, SLIM/UBC . More can be found here.

Deepwater Horizon should not become our Event Horizon

If the situation is as bad a movie as what some people describe then it looks like it could be important to know when the whole 2 billion barrels reservoir will be wide open gushing into the Gulf of Mexico ... or/and if there is a plan F that can be developed as the seabed floor collapses. BP's current approach of drilling a relief well also requires to have a good idea of how the seabed conditions change with time as the relief drill bit gets closer to the primary broken well. In both instances, BP needs to have the means of monitoring and making sense of the very rapid conditions taking place underneath the seafloor. So let me make a statement:

I am sure BP has the right people to do it with either nuclear, seismic, electromagnetic or sonic measurement capabilities; I am sure BP can perform these inverse problems with the best codes/algos there are.

However, if there are any doubts, or if there is a need for innovative and robust ways to monitor the situation at a higher sampling rate or with higher resolution, with the current assets, then I suggest some of the BP folks get in touch with some of the people of the community reading this blog. It is being read by the best minds in the world when it comes to sampling issues using any kind of probes (particles, electromagnetic, acoustic, seismic...). I am sure they can also sign NDAs if the situation requires it.

CS: Extreme Sampling

The generic story that goes into using compressive sensing is generally that it can provide sampling at a lower cost and lower complexity. While reading the news this week, I have been made aware of several extreme sampling and I am wondering how compressive sensing could or could have helped in these endeavors. The fascinating part is how extreme these sampling exercise were. Sometimes, the main constraints are:

• Money
• Citizen balloon mapping the Gulf oil spill ( we did a similar survey and set a world record of photographing 150km in New Mexico). More here.
  
• Build a high resolution synthetic aperture radar (SAR) in your backyard for under $240
• Deepwater spill and Catastrophic fires:
• Sampling water columns under a night sky lit up by a large jet of burning methane
• Outer space
  
• The broken Hayabusa: a sample returns home (via Emily)
• The IKAROS separation camera designed only for a few pictures. (IKAROS is a solar sail drifting in space using photons to move)
  
• In microgravity under a catastrophic power failure: Finding the moment of inertia of Mir after it's been hit by a Progress.
• Location: the Eyeborg camera. (Thanks Olivier).
  

Do you have any other example of extreme sampling ? I'd like to hear about them.

Credit photo: JAXA.

CS: CS SPDE, Cramér-Rao Bound In Noisy CS, Compressive Fourier Transform Spectroscopy, compressive terahertz imaging and a job at Exxon

Here are four papers that showed up on my radar screen and finally a job from ExxonMobil:

A non-adapted sparse approximation of PDEs with stochastic inputs by Alireza Doostan, Houman Owhadi. The abstract reads:

We propose a method for the approximation of solutions of PDEs with stochastic coefficients based on the direct, i.e., non-adapted, sampling of solutions. This sampling can be done by using any legacy code for the deterministic problem as a black box. The method converges in probability (with probabilistic error bounds) as a consequence of sparsity and a concentration of measure phenomenon on the empirical correlation between samples. We show that the method is well suited for truly high-dimensional problems (with slow decay in the spectrum).

On the Achievability of Cramér-Rao Bound In Noisy Compressed Sensing by Rad Niazadeh, Massoud Babaie-Zadeh, Christian Jutten. The abstract reads:

Recently, it has been proved in [Babadi et. al., 2009] that in noisy compressed sensing, a joint typical estimator can asymptotically achieve the Cram\'er-Rao lower bound of the problem. To prove this result, [Babadi et. al., 2009] used a lemma, which is provided in [Akackaya et. al., 2008], that comprises the main building block of the proof. This lemma contains a mathematical mistake in its statement and proof which should be corrected. One wonders then whether or not the main results of [Babadi et. al., 2009] are correct. In this correspondence, we will first explain the mistake in the mentioned lemma in [Akackaya et. al., 2008] and will then state a new correct form of it. Then we re-study the main results of [1], and we will show that fortunately they remain valid, that is, the Cram\'er-Rao bound in noisy compressed sensing is achievable and a joint typical estimator can achieve it.

Compressive Fourier Transform Spectroscopy by Ori Katz, Jonathan M. Levitt, Yaron Silberberg. The abstract reads:

We describe an approach based on compressive-sampling which allows for a considerable reduction in the acquisition time in Fourier-transform spectroscopy. In this approach, an N-point Fourier spectrum is resolved from much less than N time-domain measurements using a compressive-sensing reconstruction algorithm. We demonstrate the technique by resolving sparse vibrational spectra using less than 25% of the Nyquist rate samples in single-pulse CARS experiments. The method requires no modifications to the experimental setup and can be directly applied to any Fourier-transform spectroscopy measurement, in particular multidimensional spectroscopy.

And behind a paywall: Image reconstruction using spectroscopic and hyperspectral information for compressive terahertz imaging by Zhimin Xu and Edmund Y. Lam. The abstract reads:

Terahertz (THz) time-domain imaging is an emerging modality and has attracted a lot of interest. However, existing THz imaging systems often require a long scan time and sophisticated system design. Recently, a new design incorporating compressed sensing (CS) leads to a lower detector cost and shorter scan time, in exchange for computation in an image reconstruction step. In this paper, we develop two reconstruction algorithms that can estimate the underlying scene as accurately as possible. First is a single-band CS reconstruction method, where we show that by making use of prior information about the phase and the correlation between the spatial distributions of the amplitude and phase, the reconstruction quality can be significantly improved over previously published methods. Second, we develop a method that uses the multi-frequency nature of the THz pulse. Through effective use of the spatial sparsity, spectroscopic phase information, and correlations across the hyperspectral bands, our method can further enhance the recovered image quality. This is demonstrated by computation on a set of experimental THz data captured in a single-pixel THz system.

On a totally unrelated note, the First International Conference on Image Formation in X-Ray Computed Tomography proceedings are here.

A job at Exxon:

AutoReqId 9655BR
Job or Campus Folder Research Scientist-Inversion Methods
Job Description ExxonMobil’s Corporate Strategic Research laboratory is seeking applications from talented individuals in physics, applied mathematics, or engineering with a strong record of achievements in fields related to non-linear inversion, compressive sensing, and their associated mathematical and numerical methods. Specific position is in the following areas of interest:

Research Scientist – Inversion methods and compressive sensing. Position involves developing algorithms involved in large-scale non-linear inversion. Candidates with experience with the mathematics of compressive sensing, signal/image processing, denoising, sub-Nyquist signal reconstruction, and sparse representation of data desired.

Job Requirements:

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

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

ExxonMobil’s Corporate Strategic Research (CSR) laboratory is a powerhouse in energy research focusing on fundamental science that can lead to technologies having a direct impact on solving our biggest energy challenges. Our facilities are centrally located in scenic Annandale, New Jersey, approximately one hour from both New York City and Philadelphia.

ExxonMobil offers an excellent working environment and a competitive compensation and benefits package.

ExxonMobil is an Equal Opportunity Employer
Job Location Clinton, NJ

CS: RIP redux, Around the blog in 80 hours, Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion

From yesterday's presentation we had two comments. One from Laurent Jacques:

Thank you to Jared Tanner for these important references.

I think it is useful to precise that, even if Foucart and Lai's results does not provide the best achievable bounds compared the recent ones obtained by Blanchard and Thompson, they are not wrong anyway (for BP), just weaker.

Moreover, the inequality

b * lower_rip_{(b+1)k} + upper_rip_{bk} \lt b - 1

(e.g. with b=11) is of course still invariant under scaling of the matrix (i.e., A -> cA), since it is equivalent to

(1 + upper_rip_{(b-1)k})/(1 - lower_rip_{bk}) \lt b

It is true nevertheless that the insightful relations provided in the other referenced Blanchard et al. paper for different reconstruction methods (IHT, ROMP, ...) are not scale invariant. Except perhaps for CoSaMP.

Best,
Laurent

and the other from Salman:

When talking about RIP, it is very important to see the relationship between dimensions of the matrix (say MxN) and sparsity of signal (say K). If RIP constant \delta = O(1/sqrt(K)), then number of measurements scale as M ~ K^2 poly(log N). And in this range there is little difference (if any) between coherence and RIP based results.

I also had to apologize to Ray for butchering the end of his message. See Blogger, the service that runs this blog has a real problem with the \lt and \gt signs.

Other blog entries of relevant to some of the subject covered here include:

Djalil Chafai:

• Spectrum of non-Hermitian heavy tailed random matrices

Terry Tao

• Future mini-polymath project: 2010 IMO Q6?

Gonzalo Vazquez Vilar

• Testing and certification of Cognitive Radio equipment

John Langford

• The Good News on Exploration and Learning

Jason Moore has a take on the failure of GWAS, Seth has another.

Finally, there is a preprint on arxiv:

Subspace Evolution and Transfer (SET) for Low-Rank Matrix Completion by Wei Dai, Olgica Milenkovic, Ely Kerman. The abstract reads:

We describe a new algorithm, termed subspace evolution and transfer (SET), for solving low-rank matrix completion problems. The algorithm takes as its input a subset of entries of a low-rank matrix, and outputs one low-rank matrix consistent with the given observations. The completion task is accomplished by searching for a column space on the Grassmann manifold that matches the incomplete observations. The SET algorithm consists of two parts -- subspace evolution and subspace transfer. In the evolution part, we use a gradient descent method on the Grassmann manifold to refine our estimate of the column space. Since the gradient descent algorithm is not guaranteed to converge, due to the existence of barriers along the search path, we design a new mechanism for detecting barriers and transferring the estimated column space across the barriers. This mechanism constitutes the core of the transfer step of the algorithm. The SET algorithm exhibits excellent empirical performance for both high and low sampling rate regimes.

CS: Providing insight on RIP by Jared Tanner and Ray Maleh

We have some communications from two people today. First Jared Tanner adds some additional insight on a question about the RIP. Then, Ray Maleh wanted me to write a small piece on what is known with regards to RIP and recoverability of greedy algorithms but since I am not a specialist, I yielded the floor to him on the subject. Please note that the underlying reason for making a result known on this blog stems from the inability of current journals to go fast enough in publishing in a field that is growing as fast as compressive sensing. I guess the blog provides an avenue to make some results known more quickly to this community.

Thanks Jared and Ray, I always look forward to contributions that provide some context in our current state of knowledge. With no further babbling, first here is Jared 's contibution:

Dear Igor,

I read today a question/comment about the RIP and its lack of scale invariance. It was remarked that the important quantity is the ratio, which is scale invariant. This was the interpreted from Foucart and Lai's work. However, this is not the case. For most algorithms the best rip based proof involves a condition that depends on some function of the upper and lower rip constants, often of different degrees. For details on this see:

http://ecos.maths.ed.ac.uk/papers/BCTT_Greedy.pdf

and

http://ecos.maths.ed.ac.uk/papers/BlTh_SSRIC.pdf

In this second, letter, you will read on pages 5 and 6 that, as best we know, the best known rip condition for l1 is: 11 * lower_rip_{12k} + upper_rip_{11k} less than 10 and not the more recent result of Foucart and Lai.

There is a lot of confusion about the RIP. It would be advisable for people to look at the bounds we provided in: http://ecos.maths.ed.ac.uk/papers/RIP_BT.pdf
so that they have a better idea how the RIP constants, at least for Gaussian, behave.

All the best,
Jared

and then Ray's contribution:

Orthogonal Matching Pursuit (OMP) has long been considered a versatile and robust heuristic for solving compressive sensing problems. Up until lately, the only known theoretical results governing OMP's performance depended on the notion of dictionary coherence (see Tropp 04 and Gilbert et al. 03). It was not until last year that it was first shown that OMP can recover a $K$-sparse vector $x$ from measurements $y = \Phi x$ if the measurement matrix $\Phi$ satisfies a restricted isometry property (RIP).

In August 2009, Mark Davenport and Michael Wakin released a pre-print of the paper "Analysis of Orthogonal Matching Pursuit using the Restricted Isometry Property" where they show that given a measurement matrix $\Phi$ with a restricted isometry number $\delta_K$ satisfying $$\delta_K < \frac{1}{3sqrt{K}},$$ then OMP will recover any signal that is K-sparse from its measurements. They further conjecture the following \emph{unachievable} lower bound

$$\delta_K < \frac{1}{sqrt{K}}.$$

In January 2010, Entau Liu and V. N. Temlyakov released the preprint "Orthogonal Super Greedy Algorithm and Applications in Compressed Sensing" where they improve the result by showing that OMP can recover any K-sparse signal using a measurement matrix satisfying $$\delta_{K+1} < \frac{1}{(1+sqrt{2})\sqrt{K}}.$$ They mention that achieving a smaller restricted isometry bound is an interesting open problem.

In August 2009, while a Ph.D. student at the University of Michigan, Ray Maleh defended his dissertation "Efficient Sparse Approximation Methods for Medical Imaging." In Chapter 2 of his work, he shows that OMP can recover any K-sparse signal provided that

$$\delta_{K+1} \lt \frac{1}{1+sqrt{K}}.$$

This is an improvement over the results of Davenport et al. and Liu et al. Furthermore, his result very closely approaches the unachievable lower bound $\delta_K \lt 1/sqrt{K}$. In addition, Maleh proves RIP-based performance error bounds that characterize OMP's ability to recover non-sparse vectors possibly in the presence of measurement noise. While still forthcoming as a journal paper, his dissertation can be found at:

http://www.eecs.umich.edu/~fessler/student/diss/09,maleh.pdf

The author can be reached at rmaleh@gmail.com.

Credit: JAXA, The last view of Hayabusa before it crashed. Via the planetary society blog.

The good and the worst this week-end.

The good: The Falcon capsule detached from Hayabusa which had soil sample from the Itokawa asteroid. The capsule was caught on video by a NASA plane over Australia as it reentered the atmosphere. Some people have called it the robotic equivalent of Apollo 13.




The bad: "Well...it is worse". It looks like the well is damaged (read here for more technical details) I am sure a lot many excellent engineers at BP are working overtime but maybe they need to have some outside views on this. I mean, for one, we developed a technology that seems eerily similar to the one that Kevin Costner has been selling to BP because in space we have devised systems that separate liquids of different densities.



and see how it works in microgravity:


But the issue here is not a water-oil separation, it's really about determining how the subsurface flow extend under the sea floor. And if you ask me, it really look like an interesting inverse problem. I don't care much about the politics underlying all this but so far as I can tell, it sure qualifies as the starting point of a catastrophe. Can we rise to this challenge and have a similar outcome as that of Apollo 13 ?

CS: Rocking your world this week

Hayabusa, an impressive robotic equivalent of Apollo 13 is coming back today. woohoo!

To start off the week in good mood here is a large selection of very interesting and new papers related to compressive sensing but first, Laurent Jacques responded in the comment section to a question on RIP:

"... Now if we set A’=cA, where c is a constant, then the singular values are bounded above and below by c^2(1-\delta) and c^2(1-\delta). Thus A and A’ have different \delta. A’ may be not satisfy RIP. But for signal reconstruction, A and A’ are no different. So how do you explain it? Or for a given matrix B, how can we choose a constant c, make matrix cB have the minimum \delta? Do you have any suggestions?...."


Multiplication by a constant is not a problem. what matters actually is the ratio of the two bounds, which is scale invariant by definition. This can be made clear from the l2-l1 instance optimality of Basis Pursuit (DeNoise), as described for instance in Candes' paper "The restricted isometry property and its implications for compressed sensing", or the paper from Simon Foucart and Ming-Jun Lai, "Sparsest solutions of underdetermined linear systems via ell-q minimization for 0 \lt q \le 1".

What is more problematic is the mutiplication of a RIP matrix by another matrix, i.e., BA seems to have a different ratio of bounds than A. This motivated research on the null space property, as in the papers of Zhang et al., e.g.

Yin Zhang, "On theory of compressive sensing via ell-1-minimization: Simple derivations and extensions"

and other related precursor studies (e.g. from J.-J. Fuchs).

Thanks Laurent.

So here we go, here is the list of papers and presentation that will rock your world this week Enjoy!

The MUSIC Algorithm for Sparse Objects: A Compressed Sensing Analysis by Albert C. Fannjiang. The abstract reads:

The MUSIC algorithm, with its extension for imaging sparse {\em extended} objects, is analyzed by compressed sensing (CS) techniques. The notion of restricted isometry property (RIP) and an upper bound on the restricted isometry constant (RIC) are employed to establish sufficient conditions for the exact localization by MUSIC with or without the presence of noise. In the noiseless case, the sufficient condition gives an upper bound on the numbers of random sampling and incident directions necessary for exact localization. In the noisy case, the sufficient condition assumes additionally an upper bound for the noise-to-object ratio (NOR) in terms of the RIC. Rigorous comparison of performance between MUSIC and the CS minimization principle, Lasso, is given. In general, the MUSIC algorithm guarantees to recover, with high probability, $s$ scatterers with $n=\cO(s^2)$ random sampling and incident directions and sufficiently high frequency. For the favorable imaging geometry where the scatterers are distributed on a transverse plane MUSIC guarantees to recover, with high probability, $s$ scatterers with a median frequency and $n=\cO(s)$ random sampling/incident directions. Numerical results confirm that the Lasso outperforms MUSIC in the well-resolved case while the opposite is true for the under-resolved case. The latter effect indicates the superresolution capability of the MUSIC algorithm. Another advantage of MUSIC over the Lasso as applied to imaging is the former's flexibility with grid spacing and guarantee of {\em approximate} localization of sufficiently separated objects in an arbitrarily fine grid. The error can be bounded from above by $\cO(\lambda s)$ for general configurations and $\cO(\lambda)$ for objects distributed in a transverse plane.

What is Popular Amongst Your Friends? by Kishor Barman, Onkar Dabeer. The abstract reads:

In this paper, we analyze a collaborative filter that answers the simple question: What is popular amongst your friends? While this basic principle seems to be prevalent in many practical implementations, there does not appear to be much theoretical analysis of its performance. In this paper, we partly fill this gap. While recent works on this topic, such as the low-rank matrix completion literature, consider the probability of error in recovering the entire rating matrix, we consider probability of an error in an individual recommendation (bit error rate (BER)). For a mathematical model introduced in [1],[2], we identify three regimes of operation for our algorithm (named Popularity Amongst Friends (PAF)) in the limit as the matrix size grows to infinity. In a regime characterized by large number of samples and small degrees of freedom (defined precisely for the model in the paper), the asymptotic BER is zero; in a regime characterized by large number of samples and large degrees of freedom, the asymptotic BER is bounded away from 0 and 1/2 (and is identified exactly except for a special case); and in a regime characterized by a small number of samples, the algorithm fails. We also present numerical results for the MovieLens and Netflix datasets. We discuss the empirical performance in light of our theoretical results and compare with an approach based on low-rank matrix completion.

A Geometric Approach to Low-Rank Matrix Completion by Wei Dai, Ely Kerman, Olgica Milenkovic. The abstract reads:

The low-rank matrix completion problem can be succinctly stated as follows: given a subset of the entries of a matrix, find a low-rank matrix consistent with the observations. While several low-complexity algorithms for matrix completion have been proposed so far, it remains an open problem to devise search procedures with provable performance guarantees for a broad class of matrix models. The standard approach to the problem, which involves the minimization of an objective function defined using the Frobenius metric, has inherent difficulties: the objective function is not continuous and the solution set is not closed. To address this problem, we consider an optimization procedure that searches for a column (or row) space that is geometrically consistent with the partial observations. The geometric objective function is continuous everywhere and the solution set is the closure of the solution set of the Frobenius metric. We also preclude the existence of local minimizers, and hence establish strong performance guarantees, for special completion scenarios, which do not require matrix incoherence or large matrix size.

Generalized Block Sparse Constraint Based Compressive Wideband Spectrum Sensing for Cognitive Radio by Yipeng Liu, Qun Wan. The abstract reads:

Wideband spectrum sensing detects the unused spectrum holes for dynamic spectrum access of cognitive radios. However the too high sampling rate is the challenge for application. As the survey shows that the monitoring primary signal has sparse representation in frequency domain, compressive sensing can be used to transfer the sampling burden to the digital signal processor. An analog to information converter can randomly sample the received signal with sub-Nyquist rate to obtain the random measurements. In the spectrum recovery, to match the practical situation, an improved block sparse signal model can be formulated in that the static frequency spectrum allocation of primary radios means the bounds between di?erent primary radios is known. The whole monitoring spectrum is divided sections of di?erent length in accordance with di?erent allocated primary radios. The minimization of the l2 norm can encourage the dense distribution locally, while the l1 norm of the l2 norms can give the sparse distribution of the blocks. To further enhance the performance, iterative weights can be added on each block to strength the generalized block sparse distribution. The weights used for the next iteration are computed from the value of the current solution. Simulation demonstrates that the proposed method outperforms standard sparse spectrum estimation in accuracy, denoising ability, etc.

Here is another connection to Random Matrix Theory and this time it has to do with very large measurement matrices and coherence: Limiting Laws of Coherence of Random Matrices with Applications to Testing Covariance Structure and Construction of Compressed Sensing Matrices by Tony Cai and Tiefeng Jiang. The abstract reads:

Testing covariance structure is of significant interest in many areas of statistical analysis and construction of compressed sensing matrices is an important problem in signal processing. Motivated by these applications, we study in this paper the limiting laws of the coherence of an n × p random matrix in the high-dimensional setting where p can be much larger than n. Both law of large numbers and limiting distribution are derived. We then consider testing the bandedness of the covariance matrix of a high dimensional Gaussian distribution which includes testing for independence as a special case. The limiting laws of the coherence of the data matrix play a critical role in the construction of the test. The asymptotic results is also applied to the construction of compressed sensing matrices.

I note their remark 4.2 on page 14 that hints at an error in other people's work.

Proximal Methods for Sparse Hierarchical Dictionary Learning by Rodolphe Jenatton, Julien Mairal, Guillaume Obozinski, Francis Bach. The abstract reads:

We propose to combine two approaches for modeling data admitting sparse representations: on the one hand, dictionary learning has proven effective for various signal processing tasks. On the other hand, recent work on structured sparsity provides a natural framework for modeling dependencies between dictionary elements. We thus consider a tree-structured sparse regularization to learn dictionaries embedded in a hierarchy. The involved proximal operator is computable exactly via a primal-dual method, allowing the use of accelerated gradient techniques. Experiments show that for natural image patches, learned dictionary elements organize themselves in such a hierarchical structure, leading to an improved performance for restoration tasks. When applied to text documents, our method learns hierarchies of topics, thus providing a competitive alternative to probabilistic topic models.

The appendix is here.

Collaborative hierarchical sparse modeling by Pablo Sprechmann, Ignacio Ramírez, Guillermo Sapiro, and Yonina Eldar. The abstract reads:

Sparse modeling is a powerful framework for data analysis and processing. Traditionally, encoding in this framework is done by solving an `1-regularized linear regression problem, usually called Lasso. In this work we first combine the sparsity inducing property of the Lasso model, at the individual feature level, with the block-sparsity property of the group Lasso model, where sparse groups of features are jointly encoded, obtaining a sparsity pattern hierarchically structured. This results in the hierarchical Lasso, which shows important practical modeling advantages. We then extend this approach to the collaborative case, where a set of simultaneously coded signals share the same sparsity pattern at the higher (group) level but not necessarily at the lower one. Signals then share the same active groups, or classes, but not necessarily the same active set. This is very well suited for applications such as source separation. An efficient optimization procedure, which guarantees convergence to the global optimum, is developed for these new models. The underlying presentation of the new framework and optimization approach is complemented with experimental examples and preliminary theoretical results.

Universal sparse modeling by Ignacio Ramírez and Guillermo Sapiro. The abstract reads:

Sparse data models, where data is assumed to be well represented as a linear combination of a few elements from a dictionary, have gained considerable attention in recent years, and their use has led to state-of-the-art results in many signal and image processing tasks. It is now well understood that the choice of the sparsity regularization term is critical in the success of such models. In this work, we use tools from information theory, and in particular universal coding theory, to propose a framework for designing sparsity regularization terms which have several theoretical and practical advantages when compared to the more standard `0 or `1 ones, and which lead to improved coding performance and accuracy in reconstruction and classification tasks. We also report on further improvements obtained by imposing low mutual coherence and Gram matrix norm on the corresponding learned dictionaries. The presentation of the framework and theoretical foundations is complemented with examples in image denoising and classification.

Adaptive group testing strategies for target detection and localization in noisy environments by Mark Iwen and Ahmed Tewfik. The abstract reads:

This paper studies the problem of recovering a signal with a sparse representation in a given orthonormal basis using as few noisy observations as possible. As opposed to previous studies, this paper models observations which are subject to the type of ‘clutter noise’ encountered in radar applications (i.e., the measurements used influence the observed noise). Given this model, the paper develops bounds on the number of measurements required to reconstruct the support of the signal and the signal itself up to any given accuracy level when the measurement noise is Gaussian using non-adaptive and adaptive measurement strategies. Further, the paper demonstrates that group testing measurement constructions may be combined with statistical binary detection and estimation methods to produce practical and computationally efficient adaptive algorithms for sparse signal approximation and support recovery. In particular, the paper proves that a wide class of sparse signals can be recovered by adaptive methods using fewer noisy linear measurements than required by any recovery method based on non-adaptive Gaussian measurement ensembles. This result demonstrates an improvement over previous non-adaptive methods in the compressed sensing literature for sparse support pattern recovery in the sublinear-sparse support regime under the measurement model considered herein.

Multichannel Sampling of Signals with Finite Rate of Innovation by Hojjat Akhondi Asl, Pier Luigi Dragotti and Loic Baboulaz. The abstract reads:

In this paper we present a possible extension of the theory of sampling signals with finite rate of innovation (FRI) to the case of multichannel acquisition systems. The essential issue of a multichannel system is that each channel introduces different unknown delays and gains that need to be estimated for the calibration of the channels. We pose both the synchronization stage and the signal reconstruction stage as a parametric estimation problem and demonstrate that a simultaneous exact synchronization of the channels and reconstruction of the FRI signal is possible. We also consider the case of noisy measurements and evaluate the Cram´er-Rao bounds (CRB) of the proposed system. Numerical results as well as the CRB show clearly that multichannel systems are more resilient to noise than the single-channel ones.

Online and Adaptive Tracking of Subspaces from Highly Incomplete Information by Laura Balzano, Robert Nowak, Benjamin Recht. The abstract reads:

We present GROUSE (Grassmanian Rank-One Update Subspace Estimation), an efficient online algorithm for tracking subspaces from highly incomplete observations. GROUSE requires only basic linear algebraic manipulations at every iteration, and each subspace update can be performed in linear time in the dimension of the subspace. We derive our algorithm by analyzing incremental gradient descent on the Grassmannian manifold of subspaces, and relate this approach to other iterative approaches to subspace tracking that use full measurement information. We also show how a slight modification of our subspace tracking approach allows GROUSE to be used as an online incremental algorithm for the matrix completion problem where one aims to fill in the entries of a low-rank matrix. We show that GROUSE performs

exceptionally well in practice both in tracking subspaces and as an online algorithm for matrix completion.

Here are also some presentations:

by Felix Herrmann.

• Sub-Nyquist sampling and sparsity: getting more information from fewer samples

by Andrew McGregor

• "Data Streams, Dyck Languages, and Detecting Dubious Data Structures" (University
• of Edinburgh, Random Graals '10)
• Annotations in Data Streams
• Graph and Geometry Problems in the Data Stream Model and "Data Streams: Random Order and Multiple Passes
• Robust Lower Bounds for Communication and Stream Computation
• Streaming and Sketching for Distributions

and a presentation of a proposal on CS and communication.

The paper that was the support of the human interest story in Wired and on NPR has been published:

Improved Pediatric MR Imaging with Compressed Sensing.

Vasanawala SS, Alley MT, Hargreaves BA, Barth RA, Pauly JM, Lustig M.

Departments of Pediatric Radiology and Radiology, Stanford University School of Medicine, 725 Welch Rd, Room 1679, Stanford, CA 94305-5913.
Abstract

Purpose: To develop a method that combines parallel imaging and compressed sensing to enable faster and/or higher spatial resolution magnetic resonance (MR) imaging and show its feasibility in a pediatric clinical setting. Materials and Methods: Institutional review board approval was obtained for this HIPAA-compliant study, and informed consent or assent was given by subjects. A pseudorandom k-space undersampling pattern was incorporated into a three-dimensional (3D) gradient-echo sequence; aliasing then has an incoherent noiselike pattern rather than the usual coherent fold-over wrapping pattern. This k-space-sampling pattern was combined with a compressed sensing nonlinear reconstruction method that exploits the assumption of sparsity of medical images to permit reconstruction from undersampled k-space data and remove the noiselike aliasing. Thirty-four patients (15 female and 19 male patients; mean age, 8.1 years; range, 0-17 years) referred for cardiovascular, abdominal, and knee MR imaging were scanned with this 3D gradient-echo sequence at high acceleration factors. Obtained k-space data were reconstructed with both a traditional parallel imaging algorithm and the nonlinear method. Both sets of images were rated for image quality, radiologist preference, and delineation of specific structures by two radiologists. Wilcoxon and symmetry tests were performed to test the hypothesis that there was no significant difference in ratings for image quality, preference, and delineation of specific structures. Results: Compressed sensing images were preferred more often, had significantly higher image quality ratings, and greater delineation of anatomic structures (P < .001) than did images obtained with the traditional parallel reconstruction method. Conclusion: A combination of parallel imaging and compressed sensing is feasible in a clinical setting and may provide higher resolution and/or faster imaging, addressing the challenge of delineating anatomic structures in pediatric MR imaging

Finally, a short course at the next OSA annual meeting:

SC354. Compressive Sensing

Sunday, October 24, 2010

Kevin Kelly; Rice Univ., USA
Level: No level selected.

Course Description

This tutorial will review the mathematical framework of compressive sensing, highlighting its implementation in various optical imaging and spectroscopy systems. The basis of these systems is a well-established body of work which asserts that one can exploit sparsity or compressibility when acquiring signals of general interest, and that one can design non-adaptive sampling techniques that condense the information in a compressible signal using far fewer data points than were thought necessary.
For various systems, this strategy has many advantages over the traditional raster scan method given factors such as sensitivity, resolution, dwell time, and bandwidth limit. Specific examples will include implementation in infrared, hyperspectral, and fluorescence-based imaging systems. Discussions will also include the mathematics behind the reconstruction algorithms. An explicit comparison of each of these strategies on robustness to noise, speed of reconstruction, and specific feature recognition tasks will be presented. Lastly, limitations and future challenges in the field of compressed imaging will be reviewed.

Benefits and Learning Objectives

This course should enable you to:

Appreciate the underlying mathematics of compressive sensing.
Compare different optimization methods employed for image reconstruction.
Describe optical systems using both fixed masks and spatial light modulators.
Identify the limitations and challenges to implementation in real systems.
Discuss the future directions of the field.
Intended Audience

This course is intended for graduate students, post-doctoral researchers, and anyone with an interest in computational based imaging techniques. A familiarity with MATLAB will be beneficial.

This past week, there was a meeting on Sparsity and Computation at the Hausdorff Center for Mathematics. I could not located any video or presentations online. Too bad.

Here is a new DIMACS workshop announcement:

DIMACS Workshop on Network Data Streaming and Compressive Sensing

October 14 - 15, 2010
DIMACS Center, CoRE Building, Rutgers University

Organizers:

Jin Cao, Alcatel-Lucent Bell Labs, cao at research.bell-labs.com

Cristian Estan, NetLogic, estan at netlogicmicro.com

Jun (Jim) Xu, Georgia Tech, jx at cc.gatech.edu

Presented under the auspices of the DIMACS Special Focus on Algorithmic Foundations of the Internet.

---

Data streaming algorithms and compressive sensing techniques, developed originally in theoretical computer science and image-processing contexts respectively, have recently found many applications in computer networking. Single-node data streaming algorithms have been developed to extract important summary information or statistics, such as entropy, flow size distributions, and flow counts, from a single stream of packets passing through a high-speed network link, using a small amount of high-speed memory. Multi-node data streaming algorithms are proposed to extract such summary information from the union of multiple packet streams without the need to physically aggregate these streams together, which may incur prohibitive communication cost. Compressive sensing techniques have been employed to detect sparse (small in the number of affected nodes/links at any moment of time) network events such as sudden dramatic change in traffic volumes and the existence of dirty network measurements, and to recover network statistics vectors (e.g., traffic matrices and flow sizes) that are sparse (containing few large scalars) in nature. Data streaming and compressive sensing are closely related since random projection is the underlying methodology for both.

While both topics have been featured in earlier DIMACS workshops within other special focus series, the majority of the work there do not directly address research challenges faced by the networking community. In this workshop, we aim at bringing together researchers in both networking and theory communities who are interested in solving real-world networking problems using new or existing data streaming and compressive sensing techniques. The workshop will invite/feature such work not only in the more established application domain of Internet measurements, but also in other emerging contexts such as wireless and sensor networks.

We also plan to propose a JSAC (Journal on Selected Areas in Communications) special issue on this topic to JSAC editorial board and serve as guest editors of the issue.

Credit: ESA/NASA Soho.

CS: Convergence Analysis of SART by Bregman Iteration and Dual Gradient Descent

I was recently talking to both Dick Gordon, one of the person who devised the ART algorithm and Ramesh Raskar in different discussions on fast algorithms, hardware and compressive sensing and the following occurred to me. We have Xiaochuan Pan, Emil Sidky and Michael Vannier making the case in Why do commercial CT scanners still employ traditional, filtered back-projection for image reconstruction? that faster algorithms cannot seem to be adopted by the larger CT engineering community. It seems to me that while dose reduction might be a selling point for changing this status-quo as advocated by Dick, the other argument might come from the fact that not much is known with regards to actual guarantees of convergence of the ART, SART,.... algorithm. However, I personally think that the real reason you have not seen faster algorithms taking over large sections of the CT world, stems from the fact that the faster algorithms do not require a change in hardware configuration. This might seem a little counter intuitive but when you change the hardware configuration, you change many processes at the engineering level that necessarily enable new type of thinking. In the meantime, after reading this paper on SART-type Image Reconstruction from a Limited Number of Projections with the Sparisity Constraint by Hengyong Yu and Ge Wang a while back I just came across this new paper on the convergence of the ART and related algorithms: Convergence Analysis of SART by Bregman Iteration and Dual Gradient Descent by Ming Yan. The abstract reads:

In this paper, we provide two approaches to prove the convergence of simultaneous algebraic reconstruction technique (SART): linearized Bregman iteration and dual gradient descent. These proofs can be applied to other Landweber-like schemes such as Cimmino's algorithm and component averaging (CAV). The numerical experiments of these three algorithms are provided to demonstrate the convergence results. In addition, conjugate gradient method based on dual problem is utilized to compare with SART.