Mathematical Analysis of Large Data Sets

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

Jared Tanner

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