| 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