A fast algorithm for adapted time-frequency tilings

DOI10.1006/ACHA.1996.0009MaRDI QIDQ1917554zbMATH OpenOpenAlexFDO

Authors Christoph Thiele, Lars F. Villemoes

Publication date 20 February 1997

Published in Applied and Computational Harmonic Analysis (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1006/acha.1996.0009

zbMATH Keywords

adapted time frequency tilingsbest basis algorithmfast algorithmfast Fourier transformfinite Abelian groupsWalsh functions

Mathematics Subject Classification ID

Finite abelian groups (20K01) Fourier series in special orthogonal functions (Legendre polynomials, Walsh functions, etc.) (42C10) Numerical methods for discrete and fast Fourier transforms (65T50)

Review text

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.

Recommendations

• Tilings of the time-frequency plane: construction of arbitrary orthogonal bases and fast tiling algorithms
• Adapted bases of time-frequency local cosines.
• Fast algorithm for best anisotropic Walsh bases and relatives
• Modulated Malvar-Wilson bases
• Absolute optimal time - frequency basis - a research tool

Cited in

(13)

• A fast transform for spherical harmonics
• Wedgelets: Nearly minimax estimation of edges
• The norm of the Fourier transform on finite abelian groups
• Fast algorithm for best anisotropic Walsh bases and relatives
• eGHWT: the extended generalized Haar-Walsh transform
• The quartile operator and pointwise convergence of Walsh series
• Tilings of the time-frequency plane: construction of arbitrary orthogonal bases and fast tiling algorithms
• Examples of sets with large trigonometric sums
• Noiselets
• Adapted bases of time-frequency local cosines.
• The spectral barycentre of a set of graphs with community structure
• Natural graph wavelet packet dictionaries
• Self-regulated complexity in neural networks

This page was built for publication: A fast algorithm for adapted time-frequency tilings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1917554)