(20) |
(21) |
The Toeplitz matrix is highly structured. Whereas an matrix could contain n^{2} different elements, the Toeplitz matrix contains only n elements that are different from each other. When computers had limited memory, this memory savings was important. Also, there are techniques for solving least-squares problems with Toeplitz covariance matrices that are much faster than those for solving problems with arbitrary matrices. The effort for arbitrary matrices is proportional to n^{3}, whereas for Toeplitz matrices it is n^{2}. These advantages of Toeplitz matrices were once overwhelming, although now they are rarely significant. But because old methods linger on, we need to decide if they are warranted. Recall that we wrote three convolution programs, contran() , contrunc() , and convin() . You can verify that a Toeplitz matrix arises only in the first of these. The other two represent different ways of handling boundaries. Let be a diagonal matrix of weighting functions. You can also verify that the covariance matrix is not Toeplitz. Thus, Toeplitz matrices only arise with uniform weighting and transient boundary conditions. If the only tool you have is a hammer, then everything you see starts to look like a nail. In earlier days, and by inertia even today, convolution applications tend to be formulated as uniformly weighted with transient boundaries. This is a pitfall.
Toeplitz matrices are associated with elegant mathematics and rapid numerical solutions. Applications that are solvable by standard methods have historically been cast in Toeplitz form by imposing simplifying assumptions. This is risky. |
The approximation (19) becomes reasonable when the weights are slowly variable, i.e., when w_{t} is a slowly variable function of t. In practice, I think the approximation is often justified for slow t^{2} gain but questionable for automatic gains that are faster. Compared to Toeplitz methods of solving equation (19), the CG method of solving (18) is slower. Here we are going to see how to solve the problem correctly. If you want to solve the correct problem rapidly, perhaps you can do so by solving the approximate problem first by a quasi-analytic method and then doing a few steps of CG.