Adaptive Filters

CHAPTER 37 Fast Array Algorithm

All least-squares algorithms studied so far, including RLS, inverse QR, QR, and extended QR algorithms, do not assume any structure in the data. As a result, the computational complexity of each of these algorithms is O(M²) operations per iteration, where M is the order of the filter. However, when data structure is present, more efficient implementations are possible.

Thus, consider a collection of (N + 1) data {d(j),U_j} where the {U_J} are 1 × M and the d(j) are scalars. All the aforementioned algorithms are recursive procedures for determining the solution W_N, and the minimum cost ξ (N), of the regularized least-squares problem:

(37.1)

where is M × 1, Π > 0 is M × M and 0 << λ ≤ 1. In particular, RLS evaluates w_N recursively as follows (cf. Alg. 30.2). Start with , and repeat for i ≥ 0:

(37.2)

These equations hold irrespective of any structure in the {u_j}.

Now, it is often the case that the regressors {u_i} exhibit some form of structure. In the chapters in this part, we study the case in which the {u_i} arise as regressors of a tapped-delay-line ...