**Monday**,
March 6, 2006, 3:40 p.m. PSA 113

###
Dept. Math., Univ. of Utah

##
Phase Transitions for Sparse Approximation via L1 Minimization

**Abstract**
In many applications, high dimensional data sets can be well approximated
by objects lying upon much lower dimensional subspaces. This is analogous
to there being a transformation in which the object is compressible. For
instance, many signals/images are well approximated by comparatively few
wavelet/curvelet coefficients, indicating that the signal/image lays primarily
upon the space spanned by the few wavelets/curvelets. In this talk we
consider a stronger notion of compressibility, sparsity, which measures
the number of non-zero entries. For data sets which are sparse (possibly
following a transformation), the data can often be recovered efficiently,
with relatively few randomized measurements, by utilizing highly non-linear
reconstruction techniques. This talk will present recent results for sparse
reconstruction via linear programming.
Specifically, consider an underdetermined system of linear equations y=Ax
with known y and a d*n matrix A with d less than n. We seek the sparsest
solution, i.e., the x with fewest nonzeros satisfying y=Ax. In general
this problem is NP-hard. However, for many matrices A there is a threshold
phenomenon: if the sparsest solution is sufficiently sparse, it can be found
by linear programming. Quantitative values for a strong and weak threshold
will be presented. The strong threshold guarantees the recovery of the
sparsest solution x_o, whereas a weaker sparsity constraint ensures the
recovery of the sparsest solution for most x_o. Interesting properties
used in the proof of these results include the neighborliness of polytopes
in high dimensions.
This work is joint with David L. Donoho.

For further information please contact:
Anne Gelb