Block coordinate relaxation methods for nonparamatric signal denoising

An important class of nonparametric signal processing methods is to form a set of predictors from an overcomplete set of basis functions associated with a fast transform. In these methods, the number of basis functions can far exceed the number of samples values in the signal, leading to an ill-posed prediction problem. The 'basis pursuit' denoising method of Chen, Donoho, and Saunders regularizes the prediction problem by adding an L1 penalty term on the coefficients for the basis functions. Use of an L1 penalty instead of L2 has significant benefits, including higher resolution of signals close in time/frequency and a more parsimonious representation. The L1 penalty, however, poses a challenging optimization problem that was solved by Chen, Donoho and Saunders using a novel application of interior point methods. In this paper, we investigate an alternative optimization approach based on 'block coordinate relaxation' (BCR) techniques. We show that BCR is globally convergent, and empirically, BCR is faster than interior point methods for a variety of signal de- noising problems.