A fast Fourier transform for the Johnson graph

DOI10.1007/S00041-022-09952-4zbMATH Open1502.65288arXiv1912.09243OpenAlexW2996297914MaRDI QIDQ2154368FDOQ2154368

Rodrigo Iglesias, Mauro Natale

Publication date: 19 July 2022

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

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$.

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

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

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)

Cites Work

• Title not available (Why is that?)
• An Algorithm for the Machine Calculation of Complex Fourier Series
• Title not available (Why is that?)
• Association schemes and coding theory
• Title not available (Why is that?)
• A generalization of spectral analysis with application to ranked data
• An orthogonal basis for functions over a slice of the Boolean hypercube
• Title not available (Why is that?)
• Symmetric chains, Gelfand--Tsetlin chains, and the Terwilliger algebra of the binary Hamming scheme
• Computing Isotypic Projections with the Lanczos Iteration
• The efficient computation of Fourier transforms on the symmetric group
• Graph isomorphism in quasipolynomial time [extended abstract]
• Title not available (Why is that?)
• Title not available (Why is that?)
• The efficient computation of Fourier transforms on semisimple algebras
• Computational bounds for doing harmonic analysis on permutation modules of finite groups
• Efficient Quantum Algorithms for (Gapped) Group Testing and Junta Testing

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)