Fast algorithm for best anisotropic Walsh bases and relatives (Q1969040)

Best basis searches through homogeneous trees of isotropic subspaces are widely used in wavelet analysis. In this paper, the author introduces new \(N\log N\) algorithms for computing best anisotropic bases from a library, where \(N\) is the number of samples in an image. First, an anisotropic time domain Walsh algorithm is modified to obtain fast algorithms for computing best anisotropic bases which arise from smoothly segmenting a signal, such as best cosine packet bases. Next, an anisotropic frequency domain Walsh algorithm is modified to allow for the fast computation of various anisotropic best bases which arise from employing filters, such as wavelet packet bases. All of these two-dimensional algorithms are extended to higher dimensions.