A fast Fourier transform for the Johnson graph

DOI10.1007/S00041-022-09952-4MaRDI QIDQ2154368zbMATH OpenOpenAlexFDO

Authors Rodrigo Iglesias, Mauro Natale

Publication date 19 July 2022

Published in The Journal of Fourier Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.09243

zbMATH Keywords

Johnson graphRobinson-Schensted correspondenceGelfand-Tsetlin basesJucys-Murphy operatorsnonabelian fast Fourier transformspectral analysis of ranked data

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms on nonabelian groups and on semigroups, etc. (43A30) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: The set $X$ of $k$-subsets of an $n$-set has a natural graph structure where two $k$-subsets are connected if and only if the size of their intersection is $k-1$. This is known as the Johnson graph. The symmetric group $S_n$ acts on the space of complex functions on $X$ and this space has a multiplicity-free decomposition as sum of irreducible representations of $S_n$, so it has a well-defined Gelfand-Tsetlin basis up to scalars. The Fourier transform on the Johnson graph is defined as the change of basis matrix from the delta function basis to the Gelfand-Tsetlin basis. The direct application of this matrix to a generic vector requires $$ arithmetic operations. We show that this matrix can be factorized as a product of $n-1$ orthogonal matrices, each one with at most two nonzero elements in each column. The factorization is based on the construction of $n-1$ intermediate bases which are parametrized via the Robinson-Schensted insertion algorithm. This factorization shows that the number of arithmetic operations required to apply this matrix to a generic vector is bounded above by $$. We show that each one of these sparse matrices can be constructed using $$ arithmetic operations. Our construction does not depend on numerical methods. Instead, they are obtained by solving small linear systems with integer coefficients derived from the Jucys-Murphy operators. Then both the construction and the succesive application of all these $n-1$ matrices can be performed using $$ operations. As a consequence, we show that the problem of computing all the weights of the isotypic components of a given function can be solved in $$ operations, improving the previous bound $$ when $k$ asymptotically dominates $sqrtn$.

Recommendations

• scientific article; zbMATH DE number 475354
• Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
• The efficient computation of Fourier transforms on the symmetric group
• Efficient Computation of the Fourier Transform on Finite Groups
• Separation of variables and the computation of Fourier transforms on finite groups. II

Cites work

• scientific article; zbMATH DE number 1001729 (Why is no real title available?)
• scientific article; zbMATH DE number 5605063 (Why is no real title available?)
• scientific article; zbMATH DE number 3925109 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 475357 (Why is no real title available?)
• A generalization of spectral analysis with application to ranked data
• An Algorithm for the Machine Calculation of Complex Fourier Series
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Association schemes and coding theory
• Computational bounds for doing harmonic analysis on permutation modules of finite groups
• Computing Isotypic Projections with the Lanczos Iteration
• Efficient quantum algorithms for (gapped) group testing and junta testing
• Graph isomorphism in quasipolynomial time (extended abstract)
• Harmonic analysis on finite groups. Representation theory, Gelfand pairs and Markov chains
• Symmetric chains, Gelfand--Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme
• The efficient computation of Fourier transforms on semisimple algebras
• The efficient computation of Fourier transforms on the symmetric group

Cited in

(3)

• Inclusion matrices for rainbow subsets
• Fast Discrete Polynomial Transforms with Applications to Data Analysis for Distance Transitive Graphs
• On reconstruction of eigenfunctions of Johnson graphs

This page was built for publication: A fast Fourier transform for the Johnson graph

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