Only if Mike's dog really ate his frog

I just read and watched this presentation by Eric Weinstein entitled Sheldon Glashow Owes me a Dollar (and 17 years of interest): What happens in the marketplace of ideas when the endless frontier meets the efficient frontier? where he presents his thoughts on a how market type of approach could be applied to science production and in particular disruptive ideas.

"if Mike's dog really ate his frog" is from Attempts to hedge out peer review presented in slide 73-79 of the pdf presentation document. Eric, this was a nice talk. There is a now a second reference in Google to this sentence.

(via BackReaction blog)

Leaving Houston

I have talked about Leaving Houston before when under pressure from the elements. Here are data that did not know existed in 2005. Doppler radar data over houston (Looks like it is avoiding Texas A&M University)





and a view of what a 4 meter or 6 meter flood can do to the Coast and live view of the weather.



Thank you Pedro for the one-week heads-up.

CS: Fast Bayesian Matching Pursuit, new version of L_q reconstruction scheme

Lee Potter, Phil Schniter, and Justin Ziniel propose a new reconstruction technique potentially of interest to the Compressive Sensing community entitled Fast Bayesian Matching Pursuit. It is featured in: Fast Bayesian Matching Pursuit: Model Uncertainty and Parameter Estimation for Sparse Linear Models. The abstract reads:

A low-complexity recursive procedure is presented for model selection and minimum mean squared error (MMSE) estimation in linear regression. Emphasis is given to the case of a sparse parameter vector and fewer observations than unknown parameters. A Gaussian mixture is chosen as the prior on the unknown parameter vector. The algorithm returns both a set of high posterior probability mixing parameters and an approximate MMSE estimate of the parameter vector. Exact ratios of posterior probabilities serve to reveal potential ambiguity among multiple candidate solutions that are ambiguous due to observation noise or correlation among columns in the regressor matrix. Algorithm complexity is linear in the number of unknown coefficients, the number of observations and the number of nonzero coefficients. If hyperparameters are unknown, a maximum likelihood estimate is found by a generalized expectation maximization algorithm. Numerical simulations demonstrate estimation performance and illustrate the distinctions between MMSE estimation and maximum a posteriori probability model selection.

The matlab implementation of the Fast Bayesian Matching Pursuit code used in the paper will be featured here shortly according to the site.

Also, Simon Foucart mentions to me that he has updated his paper entitled Sparsest solutions of underdetermined linear systems via -minimization for . by himself and Ming-Jun Lai. As mentioned before, the code is here.


Since the beginning of this week, we have had several addtion on the reconstruction side of things, I have updated the list of reconstruction codes in the big picture accordingly.

Finally, here is Ike's prediction as of yesterday and how it relates to both Texas A&M University and Rice University. Better information can be found here.





Credit: NASA/JPL/University of Arizona, Hirise camera image of Mars, Ius Chasma's Floor (PSP_009368_1720)

CS: A Checkable Necessary and Sufficient Condition for Testing Measurement Matrices ?

If you have been reading this blog for a little while, you know that there are reasons to be dissatisfied with the current state of affairs with our testing of the restricted isometry property (RIP) given a certain measurement matrix. I believe this is central to unleashing some major hardware implementation. Take for instance Roummel Marcia and Rebecca Willett's coded aperture architecture in Compressive Coded Aperture Superresolution Image Reconstruction (additional material can be found here while the slides are here). Much of the work in this paper goes into fitting a Toeplitz-like configuration on the mask so that it eventually fulfills the RIP condition. As we also know there are problems with the RIP itself in that it just a sufficient condition. And so one wonders if a checkable necessary and sufficient condition on the measurement matrix would simplify this problematic and enable more versatile applications.

If you recall, in a previous entry, a paper by Weiyu Xu, Babak Hassibi entitled Compressed sensing over the Grassmann manifold: A unified analytical framework provided a necessary and sufficient condition for solving the L1 problem with a matrix A that followed a certain null-space property. I was intrigued by that property and went ahead and asked the authors whether they knew "of an algorithm that is not NP-hard and that would allow that property [property (4) of theorem 1] to be tested given a certain matrix ?" I also added that I was sure that they knew about Testing the Nullspace Property using Semidefinite Programming by Alexandre d'Aspremont and Laurent El Ghaoui and wondered if a similar approach could be used.

One of the authors, Weiyu Xu, kindly responded and allowed me to post his response:

...How to test the discussed property using a non-exponential complexity algorithm is not discussed in our paper yet. Currently we do not know any polynomial-time algorithm for testing it. The paper by d'Aspremont etc. is very interesting and can possibly be used to test this null-space property....

As featured earlier, Yin Zhang devised a necessary and sufficient property bypassing RIP in On theory of compressive sensing via ell-1-minimization: Simple derivations and extensions. So I went ahead and naively asked him:

.. can you confirm to me that you know of no non-NP-Hard algorithm that given a measurement matrix A, would verify theorem 2 (i.e. find a standard normal B such that BA^T = 0 ) or proposition 2 of your paper.

Yin kindly responded

Yes, I don't think proposition 2 can be verified in polynomial time. The bound in Theorem 2 is probabilistic, and I don't think it can be verified deterministically for a given matrix in poly time either. So I agree with you.

So it looks like an answer to this post's title is: No and as we say in Texas, it's not just a shame, it's a damn shame.


Credit: NASA/JPL-Caltech/University of Arizona/Texas A&M, clouds on Mars as seen from Phoenix on sol 98.

CS: MPTK Codec, Sparse Sampling, Learning, Compressed Counting, Separation of stereo speech signals, Wikimization

Today, we mostly have talks/codes and presentations dealing with sparsity and sometimes compressed sensing. Here they are:

Remi Gribonval points us to the fact that Emmanuel Ravelli has just released two packages based on MPTK:

mptkcodec: audio codec based on MPTK (C++)

• Presentation: This software is a fine-grain scalable audio codec based on MPTK. It is an implementation of the algorithms described in the paper "Union of MDCT bases for audio coding". It includes a modified version of MPTK 0.5.2, a C++ library for coding/decoding MPTK books and several standalone utilities.

mdctmex: Matlab functions for audio signal representations and coding (Matlab/C++)

• Presentation: Matlab functions (MEX-files and M-files) including: MDCT, fast MDCT, Matching Pursuit in a union of MDCT/MCLT bases, modified Matching Pursuit (pre-echo control, adaptive dictionary), coefficients interleaving, bitplane coding (simple, adaptive). Algorithms are described in the publications "Union of MDCT bases for audio coding" and "Matching Pursuit in adaptive dictionaries for scalable audio coding". The Matching Pursuit functions are based on MPTK (modified version of MPTK 0.5.2).
  

Martin Vetterli, talks about the finite rate of innovation in his ITA'08 talk entitled Sparse Sampling: Variations on a Theme by Shannon. The slides are here (12Mb). The abstract of the presentation reads:

Sampling is not only a beautiful topic in harmonic analysis, with an interesting history, but also a subject with high practical impact, at the heart of signal processing and communications and their applications. The question is very simple: when is there a one-to-one relationship between a continuous-time function and adequately acquired samples of this function?

A cornerstone result is of course Shannon's sampling theorem, which gives a sufficient condition for reconstructing the projection of a signal onto the subspace of bandlimited functions, and this by taking inner products with a sinc function and its shifts. Many variations of this basic framework exist, and they are all related to a subspace structure of the classes of objects that can be sampled.

Recently, this framework has been extended to classes of non-bandlimited sparse signals, which do not have a subspace structure. Perfect reconstruction is possible based on a suitable projection measurement. This gives a sharp result on the sampling and reconstruction of sparse continuous-time signals, namely that 2K measurements are necessary and sufficient to perfectly reconstruct a K-sparse continuous-time signal. In accordance with the principle of parsimony, we call this sampling at Occam's rate.

We first review this result and show that it relies on structured Vandermonde measurement matrices, of which the Fourier matrix is a particular case. It also uses a separation into location and value estimation, the first being non-linear, while the second is linear. Because of this structure, fast, O(K^3) methods exist, and are related to classic algorithms used in spectral estimation and error correction coding. We then generalize these results to a number of cases where sparsity is present, including piecewise polynomial signals, as well as to broad classes of sampling or measurement kernels, including Gaussians and splines.

Of course, real cases always involve noise, and thus, retrieval of sparse signals in noise is considered. That is, is there a stable recovery mechanism, and robust practical algorithms to achieve it. Lower bounds by Cramer-Rao are given, which can also be used to derive uncertainty relations with respect to position and value of sparse signal estimation. Then, a concrete estimation method is given using an iterative algorithm due to Cadzow, and is shown to perform close to optimal over a wide range of signal to noise ratios. This indicates the robustness of such methods, as well as their practicality.

Next, we consider the connection to compressed sensing and compressive sampling, a recent approach involving random measurement matrices, a discrete set up, and retrieval based on convex optimization. These methods have the advantage of unstructured measurement matrices (actually, typically random ones) and therefore a certain universality, at the cost of some redundancy. We compare the two approaches, highlighting differences, similarities, and respective advantages.

Finally, we move to applications of these results, which cover wideband communications, noise removal, and superresolution imaging, to name a few. We conclude by indicating that sampling is alive and well, with new perspectives and many interesting recent results and developments.

This is joint work with Thierry Blu (CUHK), Lionel Coulot, Ali Hormati (EPFL), Pier-Luigi Dragotti (ICL) and Pina Marziliano (NTU).

Francis Bach has some slides of an interesting course entitled learning with sparsity inducing norms given at Ile de Re. Did they have to put the students on an island so they wouldn't escape :)

Ping Li has a talk on Compressed Counting and I am still trying to make sense of it.

The only paper of the list is entitled Separation of stereo speech signals based on a sparse dictionary algorithm by Maria Jafari and Mark Plumbley. The abstract reads:

We address the problem of source separation in echoic and anechoic environments, with a new algorithm which adaptively learns a set of sparse stereo dictionary elements, which are then clustered to identify the original sources. The atom pairs learned by the algorithm are found to capture information about the direction of arrival of the source signals, which allows to determine the clusters. A similar approach is also used here to extend the dictionary learning K singular value decomposition (K-SVD) algorithm, to address the source separation problem, and results from the two methods are compared. Computer simulations indicate that the proposed adaptive sparse stereo dictionary (ASSD) algorithm yields good performance in both anechoic and echoic environments.

Wikimization has a series of compressed sensing related papers and presentations here. Out of the ones I haven't listed before here is a selection:

• Compressed Sensing with Contiguous Fourier Measurements: Presented by Jean-François Mercier with Laurent Demanet and George Papanicolaou at the Applied Mathematics Seminar, Stanford University, July 21, 2008
• Optimization Problems in Compressed Sensing: by Jalal Fadili, CNRS, ENSI Caen France, at the Applied Mathematics Seminar, Stanford University, July 21, 2008
• Compressed Sensing in Astronomy: Presented by Jean-Luc Starck with Jérôme Bobin at the Applied Mathematics Seminar, Stanford University, July 21, 2008

• Highly Undersampled 0-Norm Reconstruction: Presented by Christine Law at Lucas Center for Imaging, Stanford University, July 9, 2008 (771KByte)

• Advances in Compressive Sensing for MRI: Presented by Joshua Trzasko with Armando Manduca at the SIAM Conference on Imaging Science 2008, San Diego, California, July 7, 2008

• Nonconvex Compressive Sensing: Presented by Rick Chartrand with Valentina Staneva, Wotao Yin, & Kevin Vixie at the SIAM Conference on Imaging Science 2008, San Diego, California, July 7, 2008

In the video section of the Wikimization site, I found the following two sets of presentations:

• International Society for Magnetic Resonance in Medicine (ISMRM Toronto 2008), Randy Duensing & Feng Huang (requires Adobe Flash Player): Objective Comparison of Alternate Reconstruction Strategies: An Unmet Need. You need to go to the Wikimization site to find out both the username and password.
• Convex Optimization, Stanford University, Stephen Boyd: Tutorials for a graduate level course, 2008

Finally, there are new versions of the following articles:

• Multi-Task Compressive Sensing with Dirichlet Process Priors by Yuting Qi, Dehong Liu, Lawrence Carin, David Dunson
• Necessary and Sufficient Conditions for Success of the Nuclear Norm Heuristic for Rank Minimization, Benjamin Recht, Weiyu Xu, and Babak Hassibi

credit: Steins as seen by Rosetta
These images of asteroid (2867) Steins were captured during the seven minutes surrounding Rosetta's approach to within 800 kilometers of the asteroid on September 5, 2008. Credit: ESA ©2007 MPS for OSIRIS Team MPS / UPD / LAM / IAA / RSSD / INTA / UPM / DASP / IDA / montage by Emily Lakdawalla

CS:Disambiguation of superimposed images for increased FOV, Compressive coded aperture video, EMP, L_p Sparse recovery

First, we have two papers from Duke that are focused on implementing compressive sensing in some new kind of hardware. The first paper entitled Fast disambiguation of superimposed images for increased field of view by Roummel Marcia, Changsoon Kim, Jungsang Kim, David Brady, and Rebecca Willett evaluate reconstruction techniques from multiplexed images. 

The abstract reads:

Many infrared optical systems in wide-ranging applications such as surveillance and security frequently require large fields of view. Often this necessitates a focal plane array (FPA) with a large number of pixels, which, in ge

neral, is very expensive. In this paper, we propose a method for increasing the field of view without increasing the pixel resolution of the FPA by superimposing the multiple subimages within a scene and disambiguating the observed data to reconstruct the original scene. This technique, in effect, allows each subimage of the scene to share a single FPA, thereby increasing the field of view without compromising resolution. To disambiguate the subimages, we develop wavelet regularized reconstruction methods which encourage sparsity in the solution. We present results from numerical experiments that demonstrate the effectiveness of this approach.

I like it because I think this disambiguiation technique c

an be used for other purposes. A follow-up of a paper I refer to often is Compressive coded aperture video reconstruction by Roummel Marcia and Rebecca Willett. The abstract reads:

This paper concerns compressive sensing methods for overcoming the pixel-limited resolution of digital video imaging systems. Recent developments in coded aperture mask designs have led to the reconstruction of static images from a single, low-resolution, noisy observation image. Our methods apply these coded mask designs to each video frame and use compressive sensing optimization techniques for enhanced resolution digital video recovery. We demonstrate that further improvements can be attained by solving for multiple frames simultaneously, even when the total computation time budget is held fixed.

MSE values and related videos for each methods used in the paper can be found here.

Here is the arrival of a new and potential very fast solver, the Expander Matching Pursuit algorithm featured and explained in Near-Optimal Sparse Recovery in the L1 norm, by Piotr Indyk and Milan Ruzic. The abstract reads:

We consider the approximate sparse recovery problem, where the goal is to (approximately) recover a high-dimensional vector x element of Rn from its lower-dimensional sketch Ax element of Rm. Specifically, we focus on the sparse recovery problem in the L1 norm: for a parameter k, given the sketch Ax, compute an approximation ^x of x such that the L1 approximation error ||x - ^x||_1 is close to min_x' ||x - x'||_1, where x0 ranges over all vectors with at most k terms. The sparse recovery problem has been subject to extensive research over the last few years. Many solutions to this problem have been discovered, achieving different trade-offs between various attributes, such as the sketch length, encoding and recovery times. In this paper we provide a sparse recovery scheme which achieves close to optimal performance on virtually all attributes (see Figure 1). In particular, this is the rst scheme that guarantees O(k log(n/k)) sketch length, and near-linear O(n log(n/k)) recovery time simultaneously. It also features low encoding and update times, and is noise-resilient.

Also found in the Rice repository  a paper by Rayan Saab and Ozgur Yilmaz entitled Sparse recovery by non-convex optimization - instance optimality. The abstract reads:

In this note, we address the theoretical properties of \Delta_p, a class of compressed sensing decoders that rely on ℓp minimization with p element of (0, 1) to recover estimates of sparse and compressible signals from incomplete and inaccurate measurements. In particular, we extend the results of Candes, Romberg and Tao [3] and Wojtaszczyk [30] regarding the decoder \Delta_1, based on ℓ1 minimization, to \Delta_p with p 2 (0, 1). Our results are two-fold. First, we show that under certain sufficient conditions that are weaker than the analogous sufficient conditions for \Delta_1 the decoders \Delta_p are robust to noise and stable in the sense that they are (2, p) instance optimal. Second, we extend the results of Wojtaszczyk to show that, like \Delta_1, the decoders \Delta_p are (2, 2) instance optimal in probability provided the measurement matrix is drawn from an appropriate distribution. While the extension of the results of [3] to the setting where p element of (0, 1) is straightforward, the extension of the instance optimality in probability result of [30] is non-trivial. In particular, we need to prove that the LQ1 property, introduced in [30], and shown to hold for Gaussian matrices and matrices whose columns are drawn uniformly from the sphere, generalizes to an LQp property for the same classes of matrices. Our proof is based on a result by Gordon and Kalton [18] about the Banach-Mazur distances of p-convex bodies to their convex hulls.

Beyond the good results of the paper, I note the attempt at determining the Restricted Isometry Constants through the use of Monte Carlo method and the fact that the graph above seems to show how in-sufficient the Restricted Isometry Property really is. 

Joel Tropp has a corrigendum out: Corrigendum in 'Just relax: Convex programming methods for identifying sparse signals in noise' the abstract of the note reads:

This note closes a gap in the proof of the main lemma from the paper “Just Relax: Convex Programming Methods for Identifying Sparse Signals in Noise.

And finally, there is a report on New Directions in Complex Data Analysis for Emerging Applications mentioning compressive sensing.

CS: FPC_AS a new solver, Sparse signal recovery using MRF, CS for sensor calibration, CS for multi-view tracking and 3-D voxel reconstruction

From Houston, we have news from two people Wotao Yin and Volkan Cevher . Hurry up and download their papers and codes before Ike strikes and shuts down the whole city.

Wotao Yin lets us know of the new release of FPC_AS written by Zaiwen Wen and himself, a MATLAB solver for the L1 minimization problem, at:

http://www.caam.rice.edu/~optimization/L1/FPC_AS .

Wotao Yin also lets us know that

FPC_AS is very different from the Bregman solver. It is currently faster and much more robust, especially for compressive sensing problems with solutions that have both very large and small nonzero components (i.e., the solutions have very large dynamic range). It was not designed to replace Bregman though; we are going to upgrade the Bregman solver to take advantages of the new algorithms in FPC_AS.

Volkan Cevher has finally updated his webpage and I have updated my webcrawler. Here are three important papers I was looking forward to reading and I think are important when one wants to devise applications for Compressive Sensing.

The first is devoted to developed a new recontruction algorithm in Sparse signal recovery using Markov random fields by Volkan Cevher, Marco Duarte, Chinmay Hegde, and Richard Baraniuk. The abstract reads:

Compressive Sensing (CS) combines sampling and compression into a single sub-Nyquist linear measurement process for sparse and compressible signals. In this paper, we extend the theory of CS to include signals that are concisely represented in terms of a graphical model. In particular, we use Markov Random Fields (MRFs) to represent sparse signals whose nonzero coefficients are clustered. Our new model-based reconstruction algorithm, dubbed Lattice Matching Pursuit (LaMP), stably recovers MRF-modeled signals using many fewer measurements and computations than the current state-of-the-art algorithms.

From the paper:

LaMP requires far fewer measurements and fewer computations for robust signal reconstruction than state-of-the-art greedy and optimization techniques.

The GCOptimization package of Olga Veksler is used in the implementation of the LaMP algorithm developed in the paper. LaMP is compared very advantageously to both CoSAMP and FPC both state of the art greedy and optimization reconstruction algorithms as can be seen in the figures.


Calibration as a sparsity problem, this is intriguing and treated in Compressive sensing for sensor calibration by Volkan Cevher, and Richard Baraniuk. The abstract reads:

We consider a calibration problem, where we determine an unknown sensor location using the known track of a calibration target and a known reference sensor location. We cast the calibration problem as a sparse approximation problem where the unknown sensor location is determined over a discrete spatial grid with respect to the reference sensor. To achieve the calibration objective, low dimensional random projections of the sensor data are passed to the reference sensor, which significantly reduces the inter-sensor communication bandwidth. The unknown sensor location is then determined by solving an ℓ1-norm minimization problem (linear program). Field data results are provided to demonstrate the effectiveness of the approach.

Finally, in what looks like an extension of a previous paper ( Compressive sensing for background subtraction ), Dikpal Reddy, Aswin Sankaranarayanan, Volkan Cevher, and Rama Chellappa expanded their work in Compressed sensing for multi-view tracking and 3-D voxel reconstruction. The abtract reads:

Compressed sensing(CS) suggests that a signal, sparse in some basis, can be recovered from a small number of random projections. In this paper, we apply the CS theory on sparse background-subtracted silhouettes and show the usefulness of such an approach in various multi-view estimation problems. The sparsity of the silhouette images corresponds to sparsity of object parameters (location, volume etc.) in the scene. We use random projections (compressed measurements) of the silhouette images for directly recovering object parameters in the scene coordinates. To keep the computational requirements of this recovery procedure reasonable, we tessellate the scene into a bunch of non-overlapping lines and perform estimation on each of these lines. Our method is scalable in the number of cameras and utilizes very few measurements for transmission among cameras. We illustrate the usefulness of our approach for multi-view tracking and 3-D voxel reconstruction problems.

Many other papers by Volkan can be found here.

CSCommunity: CS MRI tutorial in San Diego and Wikimization presentation.

I have asked Jon Dattorro to write a small presentation for this blog of Wikimization. Here it is:

Wikimization (http://wikimization.org) is a repository and resource for all things Optimization.

It is a wiki; meaning that anyone can edit and create pages. Pages can be protected against hacking by outsiders. So an author can protect their own work, if desired (No editing by adolescents is a guarantee.)

Wikimization is also a blog for mathematicians, scholars, students, and researchers.

Wikimization understands both LaTeX and HTML simultaneously. That is its greatest strength.

Multiple authors can edit their work simultaneously prior to publication.

Wherever there is Internet access, all the authors can see what the others are doing.

It eliminates email of Drafts and the consequent delays in collaboration from a distance.

Right now, Wikimization has become a popular place for biographies of people in Optimization.

Biographies are more narrative than factual since we try to capture the essence of an individual;

e.g., http://www.convexoptimization.com/wikimization/index.php/Osher

http://www.convexoptimization.com/wikimization/index.php/Bertsekas

http://www.convexoptimization.com/wikimization/index.php/Isaac_Newton

We also have a lot of videos by people in Optimization:

http://www.convexoptimization.com/wikimization/index.php/Optimization_Videos

Unlike Wikipedia, we allow speculation, research, and explicit authorship if desired.

The only requirement is that the material be somehow related to Optimization; SEO or mathematical.

We just got started a few months ago, so now is the time to get an account and request Sysop status. But anonymous entries are also allowed.

I hope that students will use it to work on their homework together, pose problems, and ask each other questions.

Professors can post solutions, scholars can post their open problems, definitions, slides from talks, their papers, etc.

Programmers can post their work in Courier font HTML; e.g.,http://www.convexoptimization.com/wikimization/index.php/Candes.m which is an applicaton of Convex Iteration to an example in Compressed Sensing given by Emmanuel Candes at a lecture on June 6, 2007:

http://www.convexoptimization.com/wikimization/index.php/Optimization_Videos

Wikimization was added to the Compressive Sensing 2.0 list. Thanks Jon !

Michael Lustig gives us a "heads up on an upcoming tutorial we are giving on compressed sensing in MRI for non-MRI folks. It is part of the weekend tutorials in ICIP'08 ( http://www.icip08.org/Tutorial_04.asp )" in San Diego on October 12th. The abstract of the tutorial reads:

Magnetic Resonance Imaging (MRI) is a non-invasive imaging modality. Unlike Computed Tomography (CT), MRI does not use ionizing radiation. In addition, MRI provides a large number of flexible contrast parameters. These provide excellent soft tissue contrast. MRI can also be sensitized to many specific parameters. These include imaging brain oxygen saturation changes due to neuronal activity, measuring blood flow velocities, measuring temperature, and measuring the concentration of metabolites. MRI is also the only way to directly image diffusion of water molecules in vivo.

Since its invention more than 30 years ago, MRI has improved dramatically in imaging quality and imaging speed. This has revolutionized diagnostic medicine. Imaging speed is a major part of the revolution and is essential in many of the MRI applications. Improvements in MRI hardware and imaging techniques have enabled faster data collection, and hence faster imaging. However, we are currently at the point where fundamental physical and physiological effects limit our ability to simply encode data more quickly.

This fundamental limit has led many researches to look for methods to reduce the amount of acquired data without degrading image quality. Many of these methods seek to exploit redundancies in the MRI data. For example, using multiple receiver coils provides more useful data per MR acquisition (parallel imaging), requiring fewer acquisitions per scan. Redundancy can also be a known or modeled signal property such as spatial-temporal correlation or the sparsity and compressibility of the image (compressed sensing). The application of these methods leads to significant scan-time reduction, and clear benefits for patients and health care economics.

This tutorial will first review MR imaging from the basic principles of MR physics, signal generation, image formation, and simple image reconstruction. It will then go on to more advanced rapid imaging methods of echo-planar and spiral imaging. Finally it will cover the current state of the art techniques of parallel imaging and compressed sensing. Example applications include angiography, cardiac imaging, brain imaging and spectroscopic imaging.

I added the date to the CS calendar.

CS: SPGL1/TV followup, CS 2.0,Compressive Wave Computation, Toeplitz CS matrices in channel estimation, a book on Optical Imaging and Spectroscopy.

Laurent Jacques has a new entry entitled: SPGL1 and TV: Answers from SPGL1 Authors, it is a follow-up to his previous post: SPGL1 and TV minimization.

On the subject of Knowledge Diffusion, Mark Newman just came out with a provocative study entitled: The first-mover advantage in scientific publication. From the abstract, one can read:

.....On the other hand, there are some papers, albeit only a small fraction, that buck the trend and attract significantly more citations than theory predicts despite having relatively late publication dates. We suggest that papers of this kind, though they often receive comparatively few citations overall, are probably worthy of our attention....

One wonders how initiative like the Compressive Sensing Resources at Rice, this blog or any of the blogs/pages featured in the Compressive Sensing 2.0 page and in the Compressive 2.0 Community page will change the dynamic of the linkage between papers. An enterprising student could already use either the papers listed in the Rice repository  and in the set of recent links of this blog, and perform some naive Latent Sematic Indexing for unstructured documents like the pdfs in these pages and give us an appreciation of the extent of this recent linkage. After reading some of the recent papers or the exchange on blogs mentioned above and looking at the statistics of this blog or that of the Rice sites, I am personally convinced of this acceleration, but this is just a hunch.

It is an interest of mine to see how compressed sensing would fare with the linear transport equation, hence it is a welcoming sight to see much attempts at dealing with the mathematical considerations of compression in the eigenfunction domain of the Helmoltz equation.

 Laurent Demanet and Gabriel Peyré did just that in the impressive Compressive Wave Computation. The abstract reads:

This paper considers large-scale simulations of wave propagation phenomena. We argue that it is possible to accurately compute a wavefield by decomposing it onto a largely incomplete set of eigenfunctions of the Helmholtz operator, chosen at random, and that this provides a natural way of parallelizing wave simulations for memory-intensive applications. Where a standard eigenfunction expansion in general fails to be accurate if a single term is missing, a sparsity-promoting l1 minimization problem can vastly enhance the quality of synthesis of a wavefield from low-dimensional spectral information. This phenomenon may be seen as "compressive sampling in the Helmholtz domain", and has recently been observed to have a bearing on the performance of data extrapolation techniques in seismic imaging [41].

This paper shows that l1-Helmholtz recovery also makes sense for wave computation, and identifies a regime in which it is provably effective: the one-dimensional wave equation with coefficients of small bounded variation. Under suitable assumptions we show that the number of eigenfunctions needed to evolve a sparse wavefield defined on N points, accurately with very high probability, is bounded by 

C(\eta)
logN .
log logN;

where C(\eta) is related to the desired accuracy and can be made to grow at a much slower rate than N when the solution is sparse. The PDE estimates that underlie this result are new to the authors' knowledge and 

may be of independent mathematical interest; they include an L1 estimate for the wave equation, an L_infinity - L2 estimate of extension of eigenfunctions, and a bound for eigenvalue gaps in Sturm-Liouville problems. In practice, the compressive strategy makes sense because the computation of eigenfunctions can be assigned to different nodes of a cluster in an embarrassingly parallel way. Numerical examples are presented in one spatial dimension and show that as few as 10 percents of all eigenfunctions can suce for accurate results. Availability of a good preconditioner for the Helmholtz equation is important and also discussed in the paper. Finally, we argue that the compressive viewpoint suggests a competitive parallel algorithm for an adjoint-state inversion method in reflection seismology.

Using the RIP "compliant" Toeplitz matrices found by themselves and used by others, Jarvis Haupt,Waheed Bajwa, Gil Raz and Robert Nowak used them in another area entitled:  Toeplitz compressed sensing matrices with applications to sparse channel estimation,

Compressed sensing (CS) has recently emerged as a powerful signal acquisition paradigm. In essence, CS enables the recovery of high-dimensional but sparse (or nearly sparse) vectors from relatively few linear observations in the form of projections of the signal onto a collection of test vectors. Existing results show, for example, that if the entries of the test vectors are independent realizations of random variables with certain distributions, such as zero-mean Gaussian, then with high probability the resulting observations sufficiently encode the information in the unknown signal and recovery can be accomplished by solving a tractable convex optimization. This work provides a significant extension of current CS theory. A novel technique is proposed that allows theoretical treatment of CS in settings where the entries of the test vectors exhibit structured statistical dependencies, from which it follows that CS can be effectively utilized in linear, time-invariant (LTI) system identification problems. An immediate application is in the area of sparse channel estimation, where the main results of this work can be applied to the recovery of sparse (or nearly sparse) wireless multipath channels. Specifically, it is shown in the paper that time-domain probing of a wireless channel with a (pseudo-)random binary sequence, along with the utilization of CS reconstruction techniques, provides significant improvements in estimation accuracy when compared with traditional least-squares based linear channel estimation strategies. Abstract extensions of the main results, utilizing the theory of equitable graph coloring to tolerate more general statistical dependencies across the test vectors, are also discussed.

According to Wiley and Sons, David Brady will have a book out in February 2009 entitled: Optical Imaging and Spectroscopy. According to the site it should cost about 69.90 Euros or $84 at Amazon. Additional information include:

450 Pages, Hardcover
ISBN-10: 0-470-04823-9
ISBN-13: 978-0-470-04823-8 - John Wiley & Sons

Detailed description
Optical Imaging and Spectroscopy covers the conceptual basis of optical sensor design. The author's objective in writing Optical Imaging and Spectroscopy is to communicate a novel approach of optical system design to students and to the imaging and spectroscopy research and development community. The new approach includes three components that have not previously been covered in book form:

• Direct and simple exposition of the interface between continuous fields and discrete representations, especially including wavelet analysis, discretization on focal planes, multiplex measurement and compressive sampling.
  
• Straightforward integration of coherence and Fourier analysis, including the van Cittert Zernike theorem, coherence and projection tomography and the constant radiance theorem.
  
• Integrated consideration of imaging and spectroscopy in development of general tools for optical sensor design, including analyses of recent advances in coded wave front imaging as coded aperture spectroscopy as well as comparative system analysis tools.
  

From the contents
Preface.

Acknowledgments.

1. Past, present and future.
1.1 Three revolutions.
1.2 Computational imaging.
1.3 Overview.
1.4 The fourth revolution.
Problems.

2. Geometric imaging.
2.1 Visibility.
2.2 Optical elements.
2.3 Focal imaging.
2.4 Imaging systems.
2.5 Pinhole and coded aperture imaging.
2.6 Projection tomography.
2.7 Reference structure tomography.
Problems.

3. Analysis.
3.1 Analytical tools.
3.2 Fields and transformations.
3.3 Fourier analysis.
3.4 Transfer functions and filters.
3.5 The Fresnel transformation.
3.6 The Whittaker-Shannon sampling theorem.
3.7 Discrete analysis of linear transformations.
3.8 Multiscale sampling.
3.9 B-splines.
3.10 Wavelets.
Problems.

4. Wave imaging.
4.1 Waves and fields.
4.2 Wave model for optical fields.
4.3 Wave propagation.
4.4 Diffraction.
4.5 Wave analysis of optical elements.
4.6 Wave propagation through thin lenses.
4.7 Fourier analysis of wave imaging.
4.8 Holography.

Problems.

5. Detection.
5.1 The Optoelectronic interface.
5.2 Quantum mechanics of optical detection.
5.3 Optoelectronic detectors.
5.3.1 Photoconductive detectors.
5.3.2 Photodiodes.
5.4 Physical characteristics of optical detectors.
5.5 Noise.
5.6 Charge coupled devices.
5.7 Active pixel sensors.
5.8 Infrared focal plane arrays.
Problems.

6. Coherence imaging.
6.1 Coherence and spectral fields.
6.2 Coherence propagation.
6.3 Measuring coherence.
6.4 Fourier analysis of coherence imaging.
6.5 Optical coherence tomography.
6.6 Modal analysis.
6.7 Radiometry.
Problems.

7. Sampling.
7.1 Samples and pixels.
7.2 Image plane sampling on electronic detector arrays.
7.3 Color imaging.
7.4 Practical sampling models.
7.5 Generalized sampling.
Problems.

8. Coding and inverse problems.
8.1 Coding taxonomy.
8.2 Pixel coding.
8.3 Convolutional coding.
8.4 Implicit coding.
8.5 Inverse problems.

Problems.

9. Spectroscopy.
9.1 Spectral measurements.
9.2 Spatially dispersive spectroscopy.
9.3 Coded aperture spectroscopy.
9.4 Interferometric Spectroscopy.
9.5 Resonant spectroscopy.
9.6 Spectroscopic filters.
9.7 Tunable filters.
9.8 2D spectroscopy.

Problems.
10. Computational imaging.
10.1 Imaging systems.
10.2 Depth of field.
10.3 Resolution.
10.4 Multiple aperture imaging.
10.5 Generalized sampling revisited.
10.6 Spectral imaging.
Problems.
References.

We have covered many of these issues before and it is nice that it can be put in one book. I sure would love it to have it on my book shelf. I have added it to my Amazon Wish List.

Credit Photo:  NASA/JPL-Caltech/University of Arizona/Texas A&M, sol 97, shadow of the Sun through some aperture of the Phoenix spacecraft.

CS Community: A new site and a Workshop on Sparsity and its application to large inverse problems, Cambridge, UK.

I just created a site that strives to unify the different pages of interest to the community at large. It is at:

http://compressedsensing.googlepages.com/

feedbacks are welcome. I expect it will be very much static. Please note the creation of the outreach site (reference 11).

On a somewhat related note, as it pertains to the community, Thomas Blumensath just mentioned to me the organization of a Workshop on Sparsity and its application to large inverse problems to be held at Robinson College, Cambridge University, Cambridge UK.

It'll take place on December 14-15, 2008. The pdf is here. It has been added to the CSCalendar.

Abstract:

The aim of this workshop will be to draw together much of the recent work on algorithms which encourage sparsity, such as the minimisation of cost functions involving Lp-norms (typically $$0 \le p \lt 2 $$), with good methods for solving inverse problems on large datasets such as high-resolution images and 3D data. Usually such problems must be solved iteratively and there is a great need to ensure rapid convergence if the dataset is large, in order to avoid long computation times. Of particular interest are a number of recent papers on fast solutions to L1-minimisation problems and also on iterative threshold reduction methods that allow good solutions to be found to the non-convex L0-minimisation problem. Within the iterative context, it is also possible to adjust the weighting functions for terms in an L2-minimisation so that it approximates an L1 or L0 minimisation process.
In addition to well-known applications such as image deconvolution, there are strong links between this work and the emerging field of compressed sensing. The proposed workshop will discuss the above problem areas and attempt to unify the fairly diverse set of techniques that are currently being used into a more fundamental framework. The workshop will include two plenary talks -Prof. Rich Baraniuk of Rice University is the first confirmed plenary speaker – oral presentations and a poster session.

Prospective authors are invited to submit a one-page extended abstract with references to Pier Luigi Dragotti (to see his e-mail click on the link), by 6-October-2008.

Dates: Sunday 14th and Monday 15th December 2008.
Location: Robinson College, Cambridge University, Cambridge UK.
Registration is free and includes meals and dinner on Sunday in the Old Kitchen at Trinity College, Cambridge.
Accommodation: Robinson College, (£63+VAT per night)