Comparison of Wilson-Burg and Kolmogoroff methods

The Kolmogoroff algorithm (, ) is the most widely used spectral factorization algorithm because of its computationally efficiency.

Kolmogoroff method takes operations, where N is the length of the auto-correlation function. The cost of factorizing with the Wilson-Burg, is proportional to the [number of iterations] $\times$ [filter length] . If we keep the filter small and limit the number of iterations, the Wilson-Burg method can be cheaper (linear in N).

Additionally, since the Kolmogoroff method works in the frequency domain, it assumes circular boundary conditions. Auto-correlation functions, therefore, need to be padded with zeros before they are Fourier transformed. For functions with zeros near the unit circle, the padding may need to be many orders of magnitude greater than the original filter length, N (). Wilson-Burg works in the time-domain, so no padding is needed.

Quadratic convergence means Newton's method converges extremely fast, when the initial guess is close to the solution. If we take advantage of this fact (for example, in wave extrapolation, when going from one layer to another), the method might converge in 1 or 2 iterations, reducing the cost even further. There is no way to make use of an initial guess with the Kolmogoroff method.

For 3-D filters, N may be very large, and we may need to factor many filters to account for non-stationarity for example. In these cases, the difference in cost between the two methods may be very important.

The Kolmogoroff method, when applied to helix filtering, involves the dangerous business of truncating the filter coefficients to reduce the size of the filter. If the auto-correlation function has roots close to the unit circle, truncating filter coefficients may easily lead to non-minimum-phase filters. With Wilson-Burg, we can fix the shape of the filter from the very beginning. This doesn't guarantee that we will find the exact solution, but at least we can obtain a reasonable minimum-phase approximation of the desired filter.

In many applications, we need variable (non-stationary) filtering. We believe that extending Wilson-Burg to variable filters should be trivial: just replace all the polynomial multiplications and divisions with their non-stationary equivalents.