| Paper: | SPTM-P7.5 | ||
| 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: | OPTIMAL SPARSE REPRESENTATIONS IN GENERAL OVERCOMPLETE BASES | ||
| Authors: | Dmitry Malioutov; Massachusetts Institute of Technology | ||
| Müjdat Çetin; Massachusetts Institute of Technology | |||
| Alan Willsky; Massachusetts Institute of Technology | |||
| Abstract: | We consider the problem of enforcing a sparsity prior in underdetermined linear problems, which is also known as sparsesignal representation in overcomplete bases. The problem iscombinatorial in nature, and a direct approach is computationallyintractable even for moderate data sizes. A number of approximations have been considered in the literature, including stepwise regression, matching pursuit and its variants, and recently, basis pursuit (l1) and also lp-norm relaxations with p<1. Although the exact notion of sparsity (expressed by an l0-norm) is replaced by l1 and lp norms in the latter two, it can be shown that under some conditions these relaxations solve the original problem exactly. The seminal paper of Donoho and Huo establishes this fact for l1 (basis pursuit) for a special case where the linear operator is composed of an orthogonal pair. In this paper, we extend their results to a general underdetermined linear operator. Furthermore, we derive conditions for the equivalence of l0 and lp problems, and extend the results to the problem of enforcing sparsity with respect to a transformation (which includes total variation priors as a special case). Finally, we describe an interesting result relating the sign patterns of solutions to the question of l1-l0 equivalence. | ||
| Back | |||
Home -||-
Organizing Committee -||-
Technical Committee -||-
Technical Program -||-
Plenaries
Paper Submission -||-
Special Sessions -||-
ITT -||-
Paper Review -||-
Exhibits -||-
Tutorials
Information -||-
Registration -||-
Travel Insurance -||-
Housing -||-
Workshops