Fast algorithms for computation of inverse filters, complex cepstra, and minimum phase spectral factors
A.E. Yagle · 2002
Computation of the inverse filter s(n) to a signal r(n) (so the convolution of r(n) and s(n) is an impulse) can require a surprisingly large amount of computation. The obvious approach of taking the reciprocal of the discrete Fourier transform (DFT) of r(n) may result in aliasing unless a large order DFT is used. O(Nlog(N)) operations are required, where s(N) is negligible. We develop a new algorithm which requires O(M/sup 2/log(N)) operations, where M is the length of r(n), and so is faster if N>M/sup 2/, as is often the case. The algorithm uses successive polynomial division to identify vectors orthogonal to the stable part of 1/R(z); it requires the solution of a resultant-like Toeplitz-plus-Hankel linear system of equations, which requires O(M/sup 2/) operations. The inverse filter can then be used to compute the complex cepstrum and minimum phase spectral factor in O(M/sup 2/) operations.