Block coordinate relaxation methods for nonparametric wavelet denoising

An important class of nonparametric signal processing methods entails formi ng a set of predictors from an overcomplete set of basis functions associat ed with a fast transform (e.g., wavelet packets). In these methods, the num ber of basis functions can far exceed the number of sample values in the si gnal, leading to an ill-posed prediction problem. The "basis pursuit" denoi sing method of Chen, Donoho, and Saunders regularizes the prediction proble m by adding an l(1) penalty term on the coefficients for the basis function s. Use of an l(1) penalty instead of l(2) has significant benefits, includi ng higher resolution of signals close in time/frequency and a more parsimon ious representation. The l(1) penalty, however, poses a challenging optimiz ation problem that was solved by Chen, Donoho and Saunders using a novel ap plication of interior-point algorithms (IP). This article investigates an a lternative optimization approach based on block coordinate relaxation (BCR) for sets of basis functions that are the finite union of sets of orthonorm al basis functions (e.g., wavelet packets). We show that the BCR algorithm is globally convergent, and empirically, the BCR algorithm is faster than t he IP algorithm for a variety of signal denoising problems.