A fast algorithm for adapted time-frequency tilings (Q1917554)

Orthonormal bases of \(\mathbb{R}^N\), with \(N\) a power of 2, are considered which consist of discretized rescaled Walsh functions. A fast algorithm of order \(O(N\log N)\) is presented, for selecting the best basis among all these bases, given a signal and an additive cost function. Instead of relying on dyadic interval segmentations, the algorithm operates directly in the time-frequency plane by constructing a tiling of minimal cost among all possible tilings with dyadic rectangles of area 1. In the second part of the paper, generalizations replacing the Walsh group are dicussed. Libraries of bases attached to other finite Abelian groups are introduced, and an analoguous algorithm for picking the minimal cost function can be found. The basis elements in these libraries correspond to subsets of the plane that are no longer rectangles, but spread over the plane. The main example involves the fast Fourier transform.