Title :
A sparse solution to the bounded subset selection problem: a network flow model approach
Author :
Alghoniemy, Masoud ; Tewfik, Ahmed H.
Author_Institution :
Dept. of Electr. Eng., Alexandria Univ., Egypt
Abstract :
We reformulate the problem of finding the sparsest representation of a given signal using an overcomplete dictionary as a bounded error subset selection problem. Specifically, the reconstructed signal is allowed to differ from the original signal by a bounded error. We argue that this bounded error formulation is natural in many applications, such as coding. Our novel formulation guarantees the sparsest solution to the bounded error subset selection problem by minimizing the number of nonzero coefficients in the solution vector. We show that this solution can be computed by finding the minimum cost flow path of an equivalent network. Integer programming is adopted to find the solution.
Keywords :
integer programming; set theory; signal reconstruction; signal representation; bounded reconstruction error; coding; equivalent network minimum cost flow path; integer programming; network flow model; overcomplete dictionary; reconstructed signals; signal sparsest representation; solution vector nonzero coefficient minimization; sparse bounded subset selection method; Audio coding; Computer networks; Costs; Dictionaries; Linear programming; Matching pursuit algorithms; Signal processing; Space power stations; Sparse matrices; Speech coding;
Conference_Titel :
Acoustics, Speech, and Signal Processing, 2004. Proceedings. (ICASSP '04). IEEE International Conference on
Print_ISBN :
0-7803-8484-9
DOI :
10.1109/ICASSP.2004.1327054