MathKoll. am 15.6./Prof. Candes

[Institut für Mathematik]

Mathematisches Kolloquium

EINLADUNG

zu einem

VORTRAG

von

Prof. Dr. Emmanuel J. Candes
(California Institute of Technology)

mit dem Thema:

''Robust Uncertainty Principles and Signal Recovery from Incomplete
Measurements''

Abstract:
In many fields of science and technology, one is often able to make only a
limited number of measurements about an object of interest. Obvious examples
are problems in medicine or astrophysics such as Magnetic Resonance Imaging
(MRI) or Computed Tomography (CT). Hence, we face a fundamental challenge:
is it possible to reconstruct a signal in R^N, or at least certain types of
images, from vastly undersampled data, i.e. from K linear measurements, with
K much much smaller than N? if so, which types of images would allow
substantial undersampling? what are the limits of performance (in terms of
resolution) one can expect from a reconstruction algorithm, when unlimited
computational costs are allowed? are there practical methods whose
performance approaches these limits?
This talk introduces a newly emerged mathematical theory which surprisingly
addresses many of these questions. In particular, we show that if the signal
can be written as a superposition of a small number of vectors in some fixed
basis, then (1) exact recovery is possible, and (2) the unknown signal is
the solution to a simple convex optimization problem. Further, if the
unknown signal is only well-approximated by a sparse object, then the
reconstruction is guaranteed to be very accurate.  This phenomenon has far
reaching implications. Consider the following claim for example: from the
knowledge of about K (perhaps up to a logarithmic factor) nonadaptive random
measurements, 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, stable (in the sense that they
degrade smoothly as the noise level increases) and practical; in fact, they
only involve solving convenient convex optimization programs.
This work interacts significantly with the agenda of information theory and
especially coding theory, theoretical computer science, signal processing
and with the field of random matrix theory. If time allows, I will discuss
some of these connections together with tantalizing opportunities in
engineering and in the applied sciences.
(Parts of this work are joint with Justin Romberg and Terence Tao.)

Zeit: Mittwoch, 15. Juni 2005,
	15.45 Uhr (Kaffeejause), anschlieszend 16.15 Uhr Vortrag

Ort: Fakultaet fuer Mathematik der Universitaet Wien, Nordbergstr. 15,
       Seminarraum C 2.09

Harald Rindler
Karl Heinz Groechenig