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