Complexity of the Fourier transform on the Johnson graph

MaRDI QIDQ6285758zbMATH OpenFDO

Authors Rodrigo Iglesias, Mauro Natale

Publication date 20 April 2017

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 --in analogy with the classical Fast Fourier Transform on the discrete circle-- this matrix can be factorized as a product of $n-1$ orthogonal matrices, each one with at most two nonzero elements in each column. This factorization shows that the number of arithmetic operations required to apply this matrix to a generic vector is bounded above by $$. As a consequence, we show that the problem of computing all the weights of the irreducible components of a given function can be solved in $$ operations, improving the previous bound $$ when $k$ asymptotically dominates $sqrtn$ in a non-uniform model of computation. The same improvement is achieved for the problem of computing the isotypic projection onto a single component. The proof is based on the construction of $n-1$ intermediate bases, each one parametrized by certain pairs composed by a standard Young tableau and a word. The parametrization of each basis is obtained via the Robinson-Schensted insertion algorithm.

This page was built for publication: Complexity of the Fourier transform on the Johnson graph

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