Performance of a Fast Algorithm for FIR System Identification Using Least-Squares Analysis

In previous papers,1"4 two system identification methods, the classical least-squares analysis (LSA) and a short-time spectral analysis (SSA) procedure, had their performance compared and contrasted in the presence of high noise levels and in situations where the input signal was band-limited (nonwhite noise and speech). This earlier work found that, while the LSA method produced better performance than the SSA procedure, the computational burden of the Cholesky solution of the equations of the LSA method became prohibitive when com* Schlumberger Well Services, Houston, Texas. 717 pared to the SSA method as the system order became large (as it can be in speech processing, where the filter order can be on the order of 1000). This factor weighed in favor of the SSA method. However, the development of fast algorithms for the solution of the LSA normal equations5-8 has greatly reduced the computational complexity. This paper evaluates the performance of the LSA procedure in the context of these fast algorithms. The fast algorithm that we will consider for solving normal equations for the least-squares FIR system identification has computational complexity proportional to M2, where M is the filter order, and storage that grows linearly (rather than quadratically) with M. A byproduct of the computation is an estimate of the linear prediction coefficients of the input process. The fast algorithm also has simple, built-in, numerical ill-conditioning checks. If the model order is uncertain, the fast algorithm recursively provides all optimum least-squares solutions from filter order 1 up to some user-selected maximum order, M, thereby providing a built-in search capability for finding the appropriate system order without having to start over.