Sparse Representation in Redundant Systems

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

Fast Reconstruction from Incoherent Projections via Tree-Structured Greedy Algorithms

Dr. Richard Baraniuk

Electrical / Computer Engineering at Rice University

Abstract:   Recent research has shown that if a length-N signal has a sparse representation of K terms in one basis, then it can be accurately reconstructed from just a few times more than K projections in a second basis that is incoherent with the first. Moreover, the reconstruction can be reduced from a combinatorical problem to a linear program. Unfortunately, linear programming remains computationally intense, and so reconstruction problems with large N remain intractable. In this talk, we develop efficient greedy algorithms that solve the reconstruction problem iteratively. We focus on piecewise-smooth signals and images; these are sparsely represented by tree-structured representations such as wavelets and curvelets. Our key insight is that the significant wavelet coefficients of piecewise-smooth data lie concentrated on a connected tree. Exploiting this fact reduces the computational costs of greedy algorithms considerably; in particular, the speed-up compared with linear programming is up to O((N/K)³), which can be sizeable in many applications. An additional advantage of tree-based algorithms is that they perform an implicit regularization to combat noise in the reconstruction. Complex wavelets are crucial to the construction. This is joint work with Marco Duarte, Michael Wakin, and Hyeokho Choi.