Breaking the coherence barrier: asymptotic incoherence and asymptotic sparsity in compressed sensing

Let's put this in context, in optical imaging we had this scheme by Justin Romberg featured in "Imaging via CS", the issue of bicubic interpolation articulated by Leslie Smith, the failure of any CS reconstruction scheme to do well on the Matlab programming contest, the rise of variable density schemes in MRI (see the work of Miki Lustig), This mismatch between reality and the theory is why we need more math not less (see Negative reviews and the weak minded). You also probably recall these recent discussions

• A Q&A with Ben Adcock and Anders Hansen: Infinite Dimensional Compressive Sensing, Generalized Sampling, Wavelet Crimes, Safe Zones and the Incoherence Barrier.
• Additional insights on the Q&A with Ben Adcock and Anders Hansen

If those issues have been bothering you, you might very much like this new paper by Ben Adcok, Anders Hansen, Clarice Poon and Bogdan Roman. First Ben introduced the subject as follows:

Dear Igor, 

I hope you are well. I very much enjoyed our discussion a few months ago on infinite-dimensional compressed sensing. I'm very pleased that you're taking an interest in our work.

This email is to let you know about our new paper. When we spoke in December Anders mentioned that we were about to launch some new stuff on how to break the coherence barrier. Well, it's now finished:

http://www.math.purdue.edu/~adcock/Papers/BreakingCoherence.pdf

We think it will be of broad interest to the CS community. A brief description is as follows:

In the paper we show how to overcome the coherence barrier in compressed sensing by introducing a mathematical framework where the traditional pillars of CS theory, namely sparsity, incoherence and uniform random subsampling, are replaced by three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random sampling. These assumptions are more relevant for many problems, in particular, imaging. As a result, our main theorems bridge a gap between existing CS theory and its current use in applications such as MRI. In particular, our theory explains the abundance of numerical evidence demonstrating the advantage of so-called variable density sampling strategies.

Our theory and experiments also allow us to draw some important conclusions. First, the success of CS in applications such as these is highly dependent on the problem resolution. Second, the optimal sampling strategy is completely dependent on signal structure. We refer to such structure as asymptotic sparsity in levels. And third, the RIP, whilst a standard tool in CS theory, is of little relevance in such problems. In other words, for realistic parameter choices (resolution, subsampling percentage, sparsity) the corresponding matrices do not satisfy the RIP. Our results are based solely on coherence (or, more precisely, local coherence), and in that sense are RIPless theories.

In addition to the paper we are about to launch a website:

www.subsample.org

It should be up and running soon. It will contain numerical experiments in addition to those found in the paper, and will soon be populated with matlab code, test images, descriptions of the project and various other things.

Anyway, if you have any comments or suggestions, then please do let me know.

Best wishes,

Ben

Thanks Ben ! He talso tells me that the site is not yet running but I will keep you posted when it is. Breaking the coherence barrier: asymptotic incoherence and asymptotic sparsity in compressed sensing by Ben Adcok, Anders Hansen, Clarice Poon and Bogdan Roman. The introduction starts with:

1 Introduction

In this paper we bridge the substantial gap between existing compressed sensing theory and itscurrent use in real-world applications.

1 We do so by introducing a new mathematical framework for overcoming the so-called coherence barrier. Our framework generalizes the three traditional pillars of compressed sensing|namely, sparsity, incoherence and uniform random subsampling|to three new concepts: asymptotic sparsity, asymptotic incoherence and multilevel random subsampling. As we explain, asymptotic sparsity and asymptotic incoherence are more representative of real-world problems|e.g. imaging| than the usual assumptions of sparsity and incoherence. For instance, problems in Magnetic Resonance Imaging (MRI) are both asymptotically sparse and asymptotically incoherent, and hence amenable to our framework.

The second important contribution of the paper is an analysis of a novel and intriguing e ect that occurs in asymptotically sparse and asymptotically incoherent problems. Namely, the success of compressed sensing is resolution dependent.

As suggested by their names, asymptotic incoherence and asymptotic sparsity are only truly witnessed for reasonably large problem sizes. When the problem size is small, there is little to be gained from compressed sensing over classical linear reconstruction techniques. However, as we show in this paper, once the resolution of the problem is su fficiently large, compressed sensing can and will o er a substantial advantage. This is so-called resolution dependence. This phenomenon has the following two important consequences, which are also summarized in Figure 1:

(i) Suppose one considers a compressed sensing experiment where the sampling device, the object to be recovered, the sampling strategy and subsampling percentage are all fixed, but the resolution is allowed to vary. Resolution dependence means that a compressed sensing reconstruction done at high resolutions (e.g. 2048 2048) will yield much higher quality when compared to full sampling than one done at a low resolution (e.g. 256 256). This phenomenon has an important consequence for practitioners investigating the usefulness of compressed sensing algorithms. A scientist carrying out an experiment at low resolution may well conclude that compressed sensing imparts limited bene ts. However, a markedly dfferent conclusion would be reached if the same experiment were to be performed at higher resolution.

(ii) Suppose we conduct a similar experiment, but we now use the same total number of samples N (instead of the same percentage) at low resolution as we take at high resolution. Intriguingly, the above result still holds: namely, the higher resolution reconstruction will yield substantially better results. This is true because the multilevel random sampling strategy successfully exploits asymptotic sparsity and asymptotic incoherence. Thus, with the same amount of total effort, i.e. the number of measurements, compressed sensing with multilevel sampling works as a resolution enhancer : it allows one to recover the ne details of an image in a way that is not possible with the lower resolution reconstruction.

On a broader note, resolution dependence and its consequences suggest the following advisory for practitioners: it is critical that simulations with compressed sensing be carried out with a careful understanding of the influence of the problem resolution. Na ve simulations with standard, low-resolution test images may very well lead to incorrect conclusions about the efficacy of compressed sensing as a tool for image reconstruction.

An important application of our work is the problem of MRI, which turns out to be a highly coherent problem. MRI served as one of the original motivations for compressed sensing, and continues to be a topic of substantial research. Some of the earliest work on this problem| in particular, the research of Lustig et al. [33, 34, 35]|demonstrated that, due to the high coherence, the standard random sampling strategies of compressed sensing theory lead to highly substandard reconstructions. On the other hand, random sampling according to some nonuniform density was shown empirically to lead to substantially improved reconstruction quality. Since the work of Lustig et al. these observations have been confirmed in numerous other investigations [34, 35, 38, 39, 45], and it is now standard in MR applications to use some sort of variable density strategy to overcome the coherence barrier.

This work has culminated in the extremely successful application of compressed sensing to MRI. However, a mathematical theory addressing these sampling strategies is largely lacking. Despite some recent work [31] (see Section 8 for a discussion), a substantial gap exists between the standard theorems of compressed sensing and its implementation in such problems.

The purpose of this paper is to introduce a mathematical foundation for compressed sensing for coherent problems and to rigorously show that the coherence barrier can be broken. In doing so, we provide a rm theoretical basis for the above empirical studies demonstrating the success of nonuniform density sampling. In addition, our main results give insight into how to design e fficient subsampling techniques based on multi-level strategies.

Whilst the MR problem will serve as our main application, we stress that our theory is extremely general in that it holds for almost arbitrary sampling and sparsity systems. As we demonstrate, standard compressed sensing results, such as those of Cand es, Romberg & Tao [14], Cand es & Plan [12], are specifi c instances of our main theorems.

Another facet to our work is that we shall present theorems that cover not only the case of signals and images modelled as vectors in fi nite-dimensional vector spaces, but also elements of 2 separable Hilbert spaces. This continues the work of Adcock & Hansen [2] on in nite-dimensional compressed sensing. In Section 2.2 we explain the importance of this generalisation.

Now let's make the next leap forwaed: what are the hardware architecture enabled or changed by this new understanding ?

Join the CompressiveSensing subreddit or the Google+ Community and post there !

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