The Digital Signal Processing Lab @ UCSD


Thesis Title

Subset Selection Algorithms with Applications

Thesis Abstract

In this work, we consider general algorithms for solving the subset selection problem which requires obtaining sparse solutions to linear inverse problems. The problem arises in signal representation where we wish to represent a signal of interest by using a small number of signals from a much larger set of signals, often termed a dictionary. Other applications include magneto encephalography (MEG) and compression of audio and video signals.

We present novel modifications to algorithms based on a forward sequential or matching pursuit (MP) search through the available dictionary which greatly improve the computational complexity of these algorithms. An extension to a backward elimination algorithm to allow for overcomplete dictionaries is developed. The computational complexity and performance of each of these algorithms is comprehensively examined. Two new variants of the MP methodology are presented which trade-off performance and computational complexity.

The strong connection between the minimization of diversity (or anti-sparsity) measures and the subset selection problem is discussed. The FOCUSS algorithm is described which finds sparse signal representations through minimization of diversity measures. The initialization and termination of this algorithm are considered and a linesearch function is incorporated into the algorithm which improves the performance and the speed of convergence of the algorithm. In some applications, there are multiple measurement vectors available. The FOCUSS and MP classes of algorithm are extended to address such problems, by considering appropriate cost functions, and their performance is compared.

Finally, we demonstrate the benefits of using subset selection methods in the estimation and equalization of communication channels which exhibit a sparse impulse response. Exploiting the sparsity of the channel, we show bow MP methods may be used to obtain an accurate channel estimate which improves on least squares based estimates. The improvement in the channel estimation is quantified by the improved equalization of the estimated sparse channels. Extending the MP algorithm to a time-varying environment, the Adaptive Matching Pursuit (AMP) algorithm is introduced. This algorithm is intermediate in complexity between the LMS and RLS algorithms and the ability of AMP, LMS and RLS to track sparse time-varying channels is compared.

Year of Graduation: 2001