|
Applied Math Seminar
Robust Uncertainty Principles and Signal Recovery from Highly Incomplete Information
|
|
In many fields of science and technology, one is often able to make only a limited number of measurements about an object of interest, i.e. a digital signal, a digital image and so on. Many important problems in medicine or astrophysics such as Magnetic Resonance Imaging (MRI) or Computed Tomography (CT) of course all come to mind. This situation raises several fundamental questions: can we recover a digital signal from a small number of linear measurements? how many measurements do we need to make about an object to be able to reconstruct this object to within fixed accuracy? This talk introduces mathematical results showing that it is possible to reconstruct (1) sparse signals excatly and (2)" compressible" signals accurately from limited measurements. Although our methodology extends to a variety of setups and signals in any dimension, consider a special instance of the first claim. We show how one can reconstruct a piecewise constant image from highly incomplete frequency samples---provided that the number of discontinuity point obeys be roughly of the order of the number of observed data points. Further, we demonstrate that from the knowledge of about K log N nonadaptive random measurement, one can essentially reconstruct the K largest coefficients of a signal in any fixed basis. That is, one has an error of approximation which is nearly the same as that one would achieve by knowing ALL the information about the object and selecting the most relevant. Our methods and algorithms are very concrete and practical and only involve solving simple convex optimization programs; in fact and in most cases, linear programs.This work interacts with the agenda of information theory and especially coding theory, theoretical computer science, signal processing and with the field of random matrix theory. Parts of this work are joint with Justin Romberg (Caltech) and Terence Tao (UCLA). |