Analysis and Probability Seminar April 10, 2015

Friday, April 10, 2015 (1:00 p.m. in Yost 306)

Title: Banded Matrices and Fast Inverses

Speaker: Gilbert Strang (Professor of Mathematics, MIT)

Abstract: The inverse of a banded matrix A has a special form with low rank submatrices except at the main diagonal. That form comes directly from the Nullity Theorem. Then the inverse of that matrix A^-1 is the original A, which can be found by a remarkable “local” inverse formula. This formula uses only the banded part of A^-1 and it offers a very fast algorithm to produce A.

That fast algorithm has a potentially valuable application. Start now with a banded matrix B. (Possibly B is the positive definite beginning of a covariance matrix C, but covariances outside the band are unknown or too expensive to compute). It is a poor idea to assume that those unknown covariances are zero. Much better to complete B to C by a rule of maximum entropy; for Gaussians this rule means maximum determinant.
As statisticians and also linear algebraists discovered, the optimally completed matrix C is the inverse of a banded matrix. Best of all, the matrix actually needed in computations is that banded C^-1 (which is not B !). And C^-1 comes quickly and efficiently from the local inverse formula.
A very special subset of banded matrices contains those whose inverses are also banded. These arise in studying orthogonal polynomials and also in wavelet theory|the wavelet transform and its inverse are both banded ( = FIR flters). We describe a factorization for all banded matrices that have banded inverses.

Leave a Reply

Your email address will not be published. Required fields are marked *