Compressed Sensing

 

Compressed Sensing

CS People

CS Publications

Software

Links

Sparse Signal Representations

Sparse People

Sparse Publications

 

Compressed Sensing @ IDCoM

 

(a)

(b)

(c)

Compressed Sensing in Dynamic MRI

These movies demonstrate the power of compressed sensing for rapid acquisition in dynamic MRI. (a) shows an image sequence of a mouse heart beating that has been densely sampled. Were we to attempt to sub-sample it say by a factor of 5 (20% of Nyquist) and use linear reconstruction techniques we would experience large qualities of aliasing interference (b). However using nonlinear reconstruction algorithms, in this case our recently developed Stagewise Conjugate Gradient Pursuit algorithm, we can generate a good reconstruction without aliasing, (c).

 

What is compressed sensing?

Compressed sensing is a new rapidly growing research field emerging primarily in the USA, which investigates ways in which we can sample signals at roughly the “information rate” rather than the Nyquist rate. For example compressed sensing theory has already enabled a 4-fold reduction in acquisition time for MRI images by allowing the under-sampling of k-space (Lustig et al. 2007). It is potentially a very disruptive technology and provides a new way of thinking about how to acquire and code signals in the most efficient manner.  Its growing popularity is evident in the forthcoming special issue in IEEE Signal Processing Magazine (Eds: Donoho, Baranuik and Vetterli), the large number of research papers (see the Rice University web resource on compressed sensing for example: http://www.dsp.ece.rice.edu/cs) and the growing number of applications that are being explored across a range of disciplines, including:

·         Medical imaging

·         Seismic imaging

·         Distributed and remote sensing

·         Analogue to Information (Digital) Conversion

The foundations for compressed sensing emerged over the last two years from theoretical work developed within the field of sparse signal representations. A sparse representation is one which accounts for most or all of the information of a signal with a linear combination of a small number of elementary signals called atoms. The Fourier transform, for example, can represent a signal containing a single frequency with a single non-zero frequency component. This sparseness is one of the reasons for the extensive use of popular transforms such as the discrete Fourier transform (DFT) and the wavelet transform in practical signal source coding schemes. The aim of these transforms is often to reveal certain structures of a signal and to represent these structures in a compact form. Sparse representations extend this idea by also considering more flexible redundant representations (called dictionaries) where the linear analysis transform is replaced by a nonlinear sparse representation operator.

Recent theoretical results on sparse representations asserted that under certain conditions various sub-optimal algorithms could find the optimal sparse representation of a signal for a redundant dictionary. However compressed sensing (Candes, Romberg & Tao 2006; Donoho 2006) turns this idea on its head and asserts that if one “simply” projects a compressible signal down to a much smaller observation space, using an appropriate observation matrix, then the nonlinear reconstruction techniques developed for building sparse representations can be used to decode the signal. Furthermore it has been shown that, both in terms of the number of samples (Candes, Romberg & Tao 2006; Donoho 2006), and the number of bits required to encode the samples (Candes & Romberg DCC 2006), compressed sensing can be almost as efficient as using a sparse transform representation with traditional sampling.

 

Compressed Sensing in MRI

One of the most promising application areas for compressed sensing is in reduced rate sampling for Medical Imaging. MRI scanners sequentially sample lines within “k-space” (the spatial Fourier domain of the image). Each line sample takes time and injects energy into the patient. Rapid acquisition of MRI sequences is limited by physical (e.g. gradient strength and slew rate) and physiological (e.g. nerve stimulation) constraints. Yet, as MRI technology has advanced, there has been an increasing desire to use higher field strengths (better SNR but increased radio–frequency exposure) and to analyze larger data sets, such as dynamic imaging (2D CINE) and 3D brain imaging. Dynamic imaging requires sampling “k-t space”. A naive strategy for this can require hours of scanning for a single data set, which is clearly impractical. While a number of reduced sampling techniques have been developed, for example k-t BLAST, k-t SENSE and k-t vDUST, these exploit the linear spatiotemporal correlations within the image sequences. In contrast, Lustig et al. have produced preliminary results showing that a compressed sensing strategy that exploits the sparsity of the spatiotemporal data is also possible.

 

How do you do compressed sensing?

There are two main components to compressed sensing: the sampling strategy and the reconstruction algorithm.

Sampling - While conventional sampling involves measuring a quantity at regular intervals (so as to satisfy Nyquist), the concept of sampling in compressed sensing is much more general. sampling in compressed sensing consists of making a random linear projection of the signal into a low dimensional space. While this is essentially what is required for the theory researchers have found empirically that the same ideas can often be used in much more conventional sampling scenarios. For example MRI scanners sample lines within the spatial Fourier domain of the image and there are already initial examples of compressed sensing techniques for MRI using randomized trajectories and even deterministic trajectories (sampling a small number of radial lines) in the Fourier space.

Reconstruction - The key difference between conventional sampling and compressed sensing is that the reconstruction operator is nonlinear. Essentially this selects the significant coefficients for the data in some sparse representation and then calculates a Least squares approximation using the associated basis functions. While this sounds relatively easy it should be noted that finding the significant coefficients is a combinational search problem and in practice cannot be solved directly. Instead much of the theory of compressed sensing has concentrated on proving that near optimal performance is possible by using either a convex relaxation that boils down to solving a linear or quadratic program or greedy algorithms that iteratively select the coefficients in a greedy way one at a time or in groups.

 

Our work at Edinburgh

At Edinburgh we are working on a number of projects that relate to compressed sensing.

·         Sparse Representations for Signal Processing and Coding (EPSRC funded)

·         Compressed Sensing in Synthetic Aperture Radar (MOD funded)

·         Sparse Models Algorithms and Learning for Large-Scale Data (EU submitted)

·         Extensions to Compressed Sensing with Applications to Dynamic MRI (EPSRC submitted)

We have also developed an interesting family of greedy algorithms that we call Gradient Pursuits.  The idea is to try to obtain the algorithm performance of Orthogonal Matching Pursuits (OMP) without having to do the orthogonalization at each step (which is many real world problems provides the computational bottleneck). Recently we have also developed a stagewise version of these techniques (Stagewise Conjugate Gradient Pursuit) that enables us to solve huge reconstruction problems such as occur in dynamic MRI imaging (see top of page) at a very practical speed.

 

 

 

 

 

 

 

 

The School of Engineering and Electronics, The University of Edinburgh, The King's Buildings, Mayfield Road, Edinburgh, EH9 3JL
Tel: 0131 650 5567      Fax: 0131 650 6554      Email: see@ed.ac.uk
Originally designed by The Learning Technology Section    © 2002-2006 Copyright The University of Edinburgh. All rights reserved.