Efficient computation of isotypic projections for the symmetric group
Persi W. Diaconis, Daniel N. Rockmore · DIMACS series in discrete mathematics and theoretical computer science · 1993
. Spectral analysis on the symmetric group Sn calls for computing projections of functions defined on Sn and its homogeneous spaces, onto invariant subspaces. In particular, for the analysis of partially ranked data, the appropriate homogeneous spaces are given as quotients by Young subgroups. Here the naive character theoretic approach to computing projections requires O(n \\Delta n!) operations. In this paper two types of polynomial time algorithms (quadratic in the size of the homogeneous space) are presented for partially ranked data. The first approachmakes use of a more careful organization of the character theoretic computation and is applicable to arbitrary finite groups and their homogeneous spaces. The second approach makes use of the techniques of the combinatorial Radon transform. 1. Introduction Let G be a finite group acting transitively on a set X. Often X is called a homogeneous space for G. Let L(X) denote the vector space of complex-valued functions on X. Then L(X) na...