| Paper: | SPTM-L3.6 | ||
| Session: | Applications to Speech and Audio | ||
| Time: | Tuesday, May 16, 18:10 - 18:30 | ||
| Presentation: | Lecture | ||
| Topic: | Signal Processing Theory and Methods: Signal Restoration, Reconstruction, and Enhancement | ||
| Title: | Polynomial Time and Stack Decoding Solutions to Bounded Error Subset Selection | ||
| Authors: | Ahmed Tewfik, University of Minnesota, United States; Masoud Alghoniemy, University of Alexandria, Egypt | ||
| Abstract: | The goal of Bounded Error Subset Selection (BESS) is to find the sparsest representation of an Nx1 vector b using vectors from a dictionary A of size NxM, such that the approximation is within a user defined approximation error. The BESS is a reformulation of the classical subset selection problem. We describe two enumeration approaches with bounded complexities that find the optimal solution to the BESS problem. In particular, the paper describes the first exhaustive enumeration solution to subset selection type problems with polynomial complexity. Furthermore, it also describes a lower complexity stack decoding approach that finds a solution to the BESS problem with a complexity that is proportional to that of orthogonal matching pursuit. The approaches described here have a markedly better rate-distortion behavior than any of the other known solutions to the subset selection and BESS problems. | ||
©2018 Conference Management Services, Inc. -||- email: webmaster@icassp2006.org -||- Last updated Friday, August 17, 2012