Technical Program

Paper Detail

Paper:SPTM-P7.7
Session:Signal Enhancement and Reconstruction
Time:Thursday, May 20, 09:30 - 11:30
Presentation: Poster
Topic: Signal Processing Theory and Methods: Signal Restoration, Reconstruction, and Enhancement
Title: PROBABILISTIC ANALYSIS FOR BASIS SELECTION VIA lp DIVERSITY MEASURES
Authors: David Wipf; University of California, San Diego 
 Bhaskar Rao; University of California, San Diego 
Abstract: Finding sparse representations of signals is an important problem in many application domains. Unfortunately, when the signal dictionary is overcomplete, finding the sparsest representation is NP-hard without some prior knowledge of the solution. However, suppose that we have access to such information. Is it possible to demonstrate any performance bounds in this restricted setting? Herein, we will examine this question with respect to algorithms that minimize general $\ell_p$-norm-like diversity measures. Using randomized dictionaries, we will analyze performance probabilistically under two conditions. First, when $0 \leq p<1$, we will quantify (almost surely) the number and quality of every local minimum. Next, for the $p=1$ case we will extend the deterministic results of Donoho and Elad (2003) by deriving explicit confidence intervals for a theoretical equivalence bound, under which the minimum $\ell_1$-norm solution is guaranteed to equal the maximally sparse solution. These results elucidate our previous empirical studies applying $\ell_p$ measures to basis selection tasks.
 
           Back


Home -||- Organizing Committee -||- Technical Committee -||- Technical Program -||- Plenaries
Paper Submission -||- Special Sessions -||- ITT -||- Paper Review -||- Exhibits -||- Tutorials
Information -||- Registration -||- Travel Insurance -||- Housing -||- Workshops

©2015 Conference Management Services, Inc. -||- email: webmaster@icassp2004.org -||- Last updated Wednesday, April 07, 2004