[Statlist] Seminar ueber Statistik

[Christina Kuenzli]

                       ETH and University of Zurich 
      Proff. A.D. Barbour -- P. Buehlmann -- F. Hampel -- H.R. Kuensch 

**************************************************************************
            We are pleased to announce the following seminar
**************************************************************************
Monday, August 30, 2004, 10.15, LEO C 15
       
      Emmanuel J. Candes, California Institute of Technology

      Robust Uncertainty Principles: Exact Signal Reconstruction
      from Highly Incomplete Frequency Information
               
We consider the model problem of reconstructing an object from
incomplete frequency samples --- a problem which arises in many
important medical and/or astrophysical applications.  We ask
whether it is possible to reconstruct a discrete signal from
partial knowledge of its Fourier coefficients, i.e. from 5 or 10 %
of randomly selected coefficients.

We prove that if the signal $f$ may be synthesized out of
relatively few spikes, so that the number of spikes is roughly of
the order of the number of visible Fourier coefficients divided
by $\log N$ ($N$ is the size of the signal), then the signal can
be reconstructed exactly as the solution of a minimization
problem, which among all signals fitting the observed
coefficients, finds that object with minimum $\ell_1$ norm.  In
short, exact recovery may be obtained by solving a convex
optimization problem; except for the logarithmic factor, the
condition on the size of the support is sharp.

The methodology extends to a variety of other setups and higher
dimensions. For example, we show how one can reconstruct a piecewise
constant (one or two-dimensional) object from incomplete frequency
samples --- provided that the number of jumps (discontinuities) obeys
the condition above --- by minimizing other convex functionals such as
the Total-Variation of $f$.

Finally, we show that similar exact reconstruction phenomena hold for
other synthesis/measurement pairs. Suppose one is given a pair of of
bases $({\cal B}_1, {\cal B}_2)$ and randomly selected coefficients of
an object $f$ in one basis, say ${\cal B}_2$.  Then, $f$ can be
recovered exactly provided that it may be synthesized as a sparse
superposition of elements in ${\cal B}_1$. The relationship between
the number of nonzero terms in ${\cal B}_1$ and the number of observed
coefficients depends upon the {\em incoherence} between the two bases.
The more incoherent, the fewer coefficients needed.              
        
**************************************************************************

(LEO (Leonhardstrasse 27, 8006 Zurich) is close to the main building,
across the hill-side station of the 'Polybahn') 
Overview maps of ETH : http://www.ethz.ch/search/orientation_en.asp

Further information: Christina Kuenzli, Statistics Seminar of ETH Zurich 
**************************************************************************

Everybody is kindly invited
 
Eidgenoessische Technische Hochschule Zuerich
Swiss Federal Insitute of Technology Zurich
________________________________________________________
Christina Kuenzli            <kuenzli at stat.math.ethz.ch>
Seminar fuer Statistik      
Leonhardstr. 27,  LEO D11          phone: +41 1 632 3438         
ETH-Zentrum,                       fax  : +41 1 632 1228 
CH-8092 Zurich, Switzerland        http://stat.ethz.ch/~