Algorithms for Data Simplicity

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.

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.