Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)

DOI10.1016/j.aml.2009.09.009zbMath1197.65233OpenAlexW2066265552MaRDI QIDQ710991

Michael Clausen, Ramakrishna Kakarala

Publication date: 25 October 2010

Published in: Applied Mathematics Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aml.2009.09.009

zbMATH Keywords

FFTdiscrete Fourier transformsymmetric grouphomogeneous spacefast convolution

Mathematics Subject Classification ID

Numerical methods for discrete and fast Fourier transforms (65T50)

Related Items (3)

A unified FFT-based approach to maximum assignment problems related to transitive finite group actions ⋮ Interpreting the phase spectrum in Fourier analysis of partial ranking data ⋮ Linear time Fourier transforms of \(S_{n-k}\)-invariant functions on the symmetric group \(S_n\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Existence and efficient construction of fast Fourier transforms on supersolvable groups
• Fast generalized Fourier transforms
• A generalization of spectral analysis with application to ranked data
• Some Lower and Upper Complexity Bounds for Generalized Fourier Transforms and their Inverses
• The efficient computation of Fourier transforms on the symmetric group
• An Algorithm for the Machine Calculation of Complex Fourier Series

This page was built for publication: Computing Fourier transforms and convolutions of \(S_{n - 1}\)-invariant signals on \(S_n\) in time linear in \(n\)