Greedy RLS for sparse filters

We present an adaptive version of the greedy least squares method for finding a sparse approximate solution, with fixed support size, to an overdetermined linear system. The information updated at each time moment consists of a partial orthogonal triangularization of the system matrix and of partial scalar products of its columns, among them and with the right hand side. Since allowing arbitrary changes of the solution support at each update leads to high computation costs, we have adopted a neighbor permutation strategy that changes at most a position of the support with a new one. Hence, the number of operations is lower than that of the standard RLS. Numerical comparisons with standard RLS in an adaptive FIR identification problem show that the proposed greedy RLS has faster convergence and smaller stationary error.