Greedy Sparse RLS

Abstract

Starting from the orthogonal (greedy) least squares method, we build an adaptive algorithm for finding online sparse solutions to linear systems. The algorithm belongs to the exponentially windowed recursive least squares (RLS) family and maintains a partial orthogonal factorization with pivoting of the system matrix. For complexity reasons, the permutations that bring the relevant columns into the first positions are restrained mainly to interchanges between neighbors at each time moment. The storage scheme allows the computation of the exact factorization, implicitly working on indefinitely long vectors. The sparsity level of the solution, i.e., the number of nonzero elements, is estimated using information theoretic criteria, in particular Bayesian information criterion (BIC) and predictive least squares. We present simulations showing that, for identifying sparse time-varying FIR channels, our algorithm is consistently better than previous sparse RLS methods based on the <formula formulatype="inline" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex Notation="TeX">$\ell_1$</tex></formula> -norm regularization of the RLS criterion. We also use our sparse greedy RLS algorithm for computing linear predictions in a lossless audio coding scheme and obtain better compression than MPEG4 ALS using an RLS-LMS cascade.