Algorithms for Data Simplicity
Lead Research Organisation:
University of Oxford
Department Name: Mathematical Institute
Abstract
Most of the information we encounter on a day to day basis has some inherent simplicity, from music having a limited number of dominant frequencies at any given time and natural images being composed of smooth regions separated by relatively few abrupt edges. This inherent simplicity can be leveraged to allow extraction of meaningful information from the vast data and for more efficient information acquisition. For example, consider consumer grade mega-pixel digital cameras. The camera has a carefully constructed array of millions of photodiodes, but as soon as the image is taken the camera compresses the data to a much smaller JPG format. This compression is crucial to allow for efficient storage and transmission of the image, but it is wasteful to have acquired millions of pixels and then to immediately compress and remove the measured image. Compressed sensing and matrix completion are techniques by which the camera can measure the image at a rate proportional to the size of the final compressed image, dramatically increasing the efficiency of the camera. Taking advantage of this technology requires the design of computationally efficient algorithms for the recovery of the image from the compressed measurements. This proposal concerns the design, analysis, and application of fast algorithms able to act on large data sets.
Planned Impact
Compressed sensing and matrix completion are widely applicable to the mission of the UK defence and security establishment as well as UK commercial interests.
Prominent defence applications include the more efficient imaging acquisition by a single photodiode camera and more efficient signal acquisition through condensed bandwidth analog to digital converters. The latter is an established DARPA funded programme partnering academic researchers with defence contractors; including Prof. Tanner and HRL Laboratories (a defence research consortium). The former application has proven to be effective with a first generation camera design at Rice University. SELEX Galileo has performed due diligence of this technique through a joint EPSRC/MoD sponsored internship, and have now commissioned the construction of a single pixel camera and sponsored a CASE studentship involved with the project, supervised by Prof. Tanner. This existing collaboration will allow rapid adoption of the gains from this proposed research, by an established sensor provider to MoD.
These techniques are also widely applicable to the UK digital economy. Matrix completion has been used to predict consumer preferences, and fill in missing/obscured information in images. The proposed algorithms are also more widely applicable to inverse problems and large scale operations research problems where traditional algorithms require unacceptably large computer resources. Dr. Richtarik is actively engaged in the Digital Economy theme, serving as an Co-Investigator on the EPSRC funded "Mathematics for Vast Digital Resources" grant. Dr. Richtarik also serves as project coordinator for the University of Edinburgh Operations Research MSc, where he places approximately 40 masters students in industrial internships. This network of industrial connections will allow the rapid adoption of these powerful new optimisation techniques. Preliminary discussions are underway with the Edinburgh branch of Amazon for the placement of a team of MSc student interns to apply these techniques.
Prominent defence applications include the more efficient imaging acquisition by a single photodiode camera and more efficient signal acquisition through condensed bandwidth analog to digital converters. The latter is an established DARPA funded programme partnering academic researchers with defence contractors; including Prof. Tanner and HRL Laboratories (a defence research consortium). The former application has proven to be effective with a first generation camera design at Rice University. SELEX Galileo has performed due diligence of this technique through a joint EPSRC/MoD sponsored internship, and have now commissioned the construction of a single pixel camera and sponsored a CASE studentship involved with the project, supervised by Prof. Tanner. This existing collaboration will allow rapid adoption of the gains from this proposed research, by an established sensor provider to MoD.
These techniques are also widely applicable to the UK digital economy. Matrix completion has been used to predict consumer preferences, and fill in missing/obscured information in images. The proposed algorithms are also more widely applicable to inverse problems and large scale operations research problems where traditional algorithms require unacceptably large computer resources. Dr. Richtarik is actively engaged in the Digital Economy theme, serving as an Co-Investigator on the EPSRC funded "Mathematics for Vast Digital Resources" grant. Dr. Richtarik also serves as project coordinator for the University of Edinburgh Operations Research MSc, where he places approximately 40 masters students in industrial internships. This network of industrial connections will allow the rapid adoption of these powerful new optimisation techniques. Preliminary discussions are underway with the Edinburgh branch of Amazon for the placement of a team of MSc student interns to apply these techniques.
Organisations
Publications
Antonucci G
(2019)
Multispectral Snapshot Demosaicing Via Non-Convex Matrix Completion
Blanchard J
(2015)
Conjugate Gradient Iterative Hard Thresholding: Observed Noise Stability for Compressed Sensing
in IEEE Transactions on Signal Processing
Blanchard J
(2015)
CGIHT: conjugate gradient iterative hard thresholding for compressed sensing and matrix completion
in Information and Inference
Richtárik P
(2015)
Parallel coordinate descent methods for big data optimization
in Mathematical Programming
Tanner J
(2019)
Matrix Rigidity and the Ill-Posedness of Robust PCA and Matrix Completion
in SIAM Journal on Mathematics of Data Science
Tanner J
(2013)
Normalized Iterative Hard Thresholding for Matrix Completion
in SIAM Journal on Scientific Computing
Description | Algorithms which directly try and solve the rank constrained matrix completion problem are more effective, computationally and in terms of the number of entries needed, than is solving the convex relaxation. These results are now being evaluated in MRI through an industrial case studentship sponsored by Siemens and joint with Dr. Aaron Hess (Oxford Cardiology). |
Exploitation Route | Collaboration with practitioners using these techniques for their particular applications. |
Sectors | Aerospace, Defence and Marine,Agriculture, Food and Drink,Digital/Communication/Information Technologies (including Software),Healthcare |