Posts

Showing posts from March, 2011

Decimate Brands of Banded matrices

Image
About one year ago Gilbert Strang published a first paper Fast transforms: Banded matrices with banded inverses at Proceedings of the National Academy of Science (PNAS), with the following abstract: It is unusual for both $A$ and $A^{-1}$ to be banded — but this can be a valuable property in applications. Block-diagonal matrices $F$ are the simplest examples; wavelet transforms are more subtle. We show that every example can be factored into $A = F_1 \dots F_N$ where $N$ is controlled by the bandwidths of $A$ and $A^{-1}$ (but not by their size, so this extends to infinite matrices and leads to new matrix groups).  Banded matrices (or band matrices) are somewhat related to implementations of discrete wavelet transforms (see for instance Short Wavelets and Matrix Dilation Equations , 1995 by G. Strang and V. Strela). The 2010 PNAS  sparked some interest as a means to implement fast local linear filters in both the forward and inverse transforms (an ascribed tandem , first anagram t