Research project: When greed is good: greedy algorithms for Signal Processing and Compressed Sensing
Currently Active:
Yes
We are flooded by digital data. Mobile phones, computers, cameras, medical scanner, satellites and many other sensors constantly record, store, transmit and analyse unprecedented amounts of information. In many cases, we are no longer able to simply store all the raw data and instead use algorithms to significantly reduce the input data to a more manageable load. This reduction is often possible, because we are either not interested in all of the information or, more commonly, the original data contained a significant amount of redundancy. A good example is a modern digital camera. The actual imaging sensor in a digital camera is able to record the light intensity for millions of different pixels, yet camera storage is still limited and image compression algorithms are used to store the data more efficiently.
Project Overview
Greedy algorithms
Greedy algorithms are a class of computational methods that allow us to efficiently exploit certain types of structures in data. Sparsity is the canonical example. Sparsity here means that either, the data itself only constrains few significant non-zero values, or, that there is a simple transformation of the data that can be used to represent the original data in a new sparse data format. A good example here is the wavelet transform (see the image above), which transforms most images into a representation in which most information is concentrated in few values.
Greedy algorithms are used to find efficient representations of data sets and in advanced data acquisition methods known as compressed sensing, where data acquisition and compression are combined and where greedy algorithms are used to recover the original data from the measurements.
The IHT algorithm
We have developed several efficient greedy strategies, including the Iterative Hard Thresholding algorithm and Gradient Pursuits.
Other contributions include the study of a range of different data structures that can be exploited using these greedy methods. Focus here has been on a geometric class of structures known as union of subspace models.
Impact
Greedy algorithms have wide ranging applications. For example, they have allowed us to significantly speed up medical MRI scanners, which has the potential to speed up medical diagnosis and reduce healthcare cost. We are now also starting to use similar ideas for problems in x-ray computed tomography, where these techniques promise significant improvements in several manufacturing applications, where x-ray computed tomography scanners are increasingly used for the control of the internal integrity and dimensional accuracy of complex manufactured components.
The mouse heart data is curtsey of Ian Marshall and Yuehui Tao from the University of Edinburgh's Magnetic Resonance Physics Group.
Funding
This work is funded by EPSRC grants:
EP/K037102/1 Constrained low rank matrix recovery: from efficient algorithms to brain network imaging
EP/D000246/1 Sparse Representations for Signal Processing and Coding
Publications
T. Blumensath; "The geometry of compressed sensing,"in A. Y. Carmi , L. S. Mihaylova and S. J. Godsill Eds.,Compressed Sensing and Sparse Filtering, Springer, in press
T. Blumensath, M.E. Davies and G. Rilling; "Greedy Algorithms for Compressed Sensing,"in Y. Eldar and G. Kutyniok Eds.,Compressed Sensing: Theory and Applications, Cambridge University Press, 2012
T. Blumensath;"Compressed Sensing with Nonlinear Observations and Related Nonlinear Optimisation Problems,"IEEE Transactions on Information Theory, vol. 59(6), pp. 3466-3474, 2013.
T. Blumensath;"Accelerated Iterative Hard Threshoding,"Signal Processing, 92 (2012), pp.752-756, 2011
T. Blumensath;"Sampling and reconstructing signals from a union of linear subspaces,"IEEE Transactions on Information Theory, 57(7), pp. 4660-4671, 2011
T. Blumensath, M. E. Davies;"NormalisedIterative Hard Thresholding; guaranteed stability and performance"IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 298 -309, 2010
T. Blumensath, M. E. Davies;"Stagewise Weak Gradient Pursuits",IEEE Transactions on Signal Processing, vol. 57, no. 11, pp. 4333-4346, 2009
T. Blumensath, M. E. Davies;"Iterative Hard Thresholding for Compressed Sensing",Applied and Computational Harmonic Analysis, vol. 27, no. 3, pp. 265-274, 2009
M. Yaghoobi, T. Blumensath, M. E. Davies;"Dictionary Learning for Sparse Approximations with the Majorization Method", IEEE Transactions on Signal Processing, vol. 57, no. 6, pp. 2178 - 2191, 2009
T. Blumensath, M. E. Davies;"Sampling Theorems for Signals from the Union of Finite-Dimensional Linear Subspaces",IEEE Transactions on Information Theory, vol. 55, no. 4, pp. 1872-1882, April 2009
T. Blumensath, M. E. Davies;"Iterative Thresholding for Sparse Approximations".The Journal of Fourier Analysis and Applications, vol.14, no 5, pp. 629-654, December 2008.
T. Blumensath, M. E. Davies;"Gradient Pursuits",IEEE Transactions on Signal Processing, vol. 56, no. 6, pp. 2370-2382, June 2008.
T. Blumensath and M. E. Davies;"Compressed sensing signal models - to infinity and beyond?", in Proc. of SAMPTA'09, Marseille, France, 2009.
T. Blumensath and M. E. Davies;"How to use the Iterative Hard Thresholding algorithm", in Proc. of SPARS09, Saint-Malo, France, 2009.
T. Blumensath and M. E. Davies;"A Simple, Efficient and Near Optimal Algorithm for Compressed Sensing", ICASSP, 2009
T. Blumensath and M. E. Davies;"Gradient Pursuit for Non-Linear Sparse Signal Modelling", European Signal Processing Conference (EUSIPCO), Lausanne, Switzerland, April 2008.
M. Yaghoobi, T. Blumensath, M. E. Davies;"Regularized Dictionary Learning for Sparse Approximation", European Signal Processing Conference (EUSIPCO), Lausanne, Switzerland, April 2008.
M.E. Davies and T. Blumensath;"Faster & Greedier: algorithms for sparse reconstruction of large datasets ", invited paper to the third IEEE International Symposium on Communications, Control, and Signal Processing, St Julians, Malta, March 2008
T. Blumensath, M. E. Davies;"In Greedy Pursuit of New Directions: (Nearly) Orthogonal Matching Pursuit by Directional Optimisation", European Signal Processing Conference (EUSIPCO), Pozna, Poland, September 2007
T. Blumensath, M. Yaghoobi, M. E. Davies;"Iterative Hard Thresholding and L0 Regularisation", IEEE International Conference on Acoustics, Speech and Signal Processing, Honolulu, USA, April 2007.
