Figure: The benefits of optimal sampling.  Left: conventional compressed sensing using a scrambled orthogonal transform.  Right: improved compressed sensing using multilevel Walsh sampling.  Both methods use 6% measurements.  Image courtesy of Elizabeth Sawchuk.  Experiment performed by Vegard Antun (University of Oslo).

Getting more from less: optimal sampling strategies for compressive imaging

The motivation Fast, high-quality image reconstruction is a key task throughout science, engineering and industry.  Over the last decade, solutions to this problem have been revolutionized by the development of compressed sensing.  Compressed sensing has led to significant advances in a wide range of applications where accurate image reconstruction is key, including medical (e.g. magnetic resonance imaging or ‘MRI’ and computerized tomography or ‘CT’), scientific (e.g. electron microscopy and radio interferometry) and industrial (e.g. seismic imaging and optical imaging) modalities.

A fundamental question in image reconstruction is: which measurements should be acquired?  Naturally, it is best to take as many measurements as possible so as to ensure a high-quality recovery, but this must be balanced with the constraints of the modality, including time (e.g. in MRI), power, cost or exposure to radiation (e.g. X-rays in CT). Compressed sensing aims to push this boundary. It uses sophisticated, nonlinear reconstruction algorithms and novel sampling strategies to obtain higher-quality image recovery than is possible with classical approaches.

The purpose of this study was to develop new mathematics for determining the optimal measurements for image reconstruction via compressed sensing.  Since the introduction of compressed sensing in 2006, many heuristic sampling strategies have been proposed; these were largely lacking mathematical theory, and thus there was no understanding of whether they were optimal, and if not, how they could be improved to deliver better practical performance.

The discovery – Dr. Ben Adcock (Simon Fraser University) and Chen Li (New York University) demonstrated that so-called multilevel random sampling strategies—introduced previously by Adcock and collaborators—satisfied the so-called Restricted Isometry Property in Levels. This is a key mathematical property that guarantees accurate reconstruction in compressed sensing.  Their main theorem not only satisfies this property, but it also provides novel insights into the design of sampling strategies in practice.

Its significance – This work, initially conducted in summer 2015 as part of an undergraduate research project, laid the theoretical foundation for what has since developed into a comprehensive mathematical understanding of optimal sampling in compressed sensing.  It led to a series of discoveries that enables scientists to determine the optimal measurements for image reconstruction via compressed sensing. Further, it has helped to devise new approaches in imaging modalities such as MRI, NMR, fluorescence microscopy and helium atom scattering that offer significant performance gains.

This work forms the core of a book that is currently being finalized by Dr. Adcock and Dr. Anders Hansen (University of Cambridge), entitled Compressive Imaging, to be published by Cambridge University Press.

Read the paper“Compressed sensing with local structure: Uniform recovery guarantees for the sparsity in levels class” by Li, C; Adcock, B. Applied and Computational Harmonic Analysis 46(3):453-477 (2019). DOI: 10.1016/j.acha.2017.05.006.

Website article compiled by Jacqueline Watson with Theresa Kitos