[ Search | Site Map | Contact ]

Center for Scientific Computation and Mathematical Modeling

Research Activities > Programs > Sparse Representation in Redundant Systems > Ingrid Daubechies

Sparse Representation in Redundant Systems

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Randomness and Determinism in Sparse Algorithms


 Dr. Ingrid Daubechies & Dr. Vahid Tarokh
(Princeton University & Harvard University)

Abstract:  Supersparse algorithms (see the talks by Gilbert, Tropp, Zou on Tuesday in this workshop) rely on randomness, both in the construction of the "measurement matrix" and in the algorithm that reconstructs the sparse underlying vector from the measurements, and they prove that the desired sparse decomposition or approximation is obtained with high probability. Donoho, Candés & Tao, Rudelson & Vershynin (see the talks on Monday in this workshop) have shown that when l1-minimization algorithms are used (which are not super fast), the measurement matrix need not be random: they prove that there exist (increasingly
frequently among random choices as the dimension N increases) K x N matrices H, with K < N, such that arbitrary M-sparse vectors v (i.e. v Є CN or RN, with #{n;vn≠ 0} ≤ M; M < K, with typically K = O(M logN)) can be recovered completely from y = Hv by l1 - minimization: v = argminu{║u ║;Hu = y }. However, so far no explicit constructions of such matrices H are known - the existence arguments are probabilistic.
In this talk two different approaches will be sketched that construct explicit measurement matrices H, using results and techniques from coding theory. The recovery algorithms are not l1-based.