Search

This paper studies the cross-correlation of two real-valued functions whose common domain is a set on which a finite group acts transitively. Such a group action generalizes, e.g., circular time shifts for discrete periodic time signals or spatial translations in the context of image processing. Cross-correlations can be reformulated as convolutions in group algebras and are thus transformable into the spectral domain via Fast Fourier Transforms. The resulting general discrete cross-correlation theorem will serve as the basis for a unified FFT-based approach to maximum assignment problems related to transitive finite group actions. Our main focus is on those assignment problems arising from the actions of symmetric groups on the cosets of Young subgroups. The "simplest" nontrivial representatives of the latter class of problems are the NP-hard symmetric and asymmetric maximum quadratic assignment problem. We present a systematic spectral approach in terms of the representation theory of symmetric groups to solve such assignment problems. This generalizes and algorithmically improves Kondor's spectral branch-and-bound approach (SODA, 2010) to the exact solution of the asymmetric maximum quadratic assignment problem. [ABSTRACT FROM AUTHOR]

This paper introduces new techniques for the efficient computation of discrete Fourier transforms (DFTs) of S n − k -invariant functions on the symmetric group S n. We uncover diamond- and leaf-rake-like structures in Young's seminormal and orthogonal representations leading to relatively expensive diamond and cheaper leaf-rake computations. These local computations constitute the basis of a reduction/induction process. We introduce a new anticipation technique that avoids diamond computations at the expense of only a small arithmetic overhead for leaf-rake computations. This results in local fast Fourier transforms (FFTs). Combining these local FFTs with a multiresolution scheme close related to the inductive version of Young's branching rule we obtain a global FFT algorithm that computes the DFT of S n − k -invariant functions on S n in linear time. More precisely, we show that for fixed k and all n ≥ 2 k DFTs of S n − k -invariant functions on S n can be computed in at most c k ⋅ [ S n : S n − k ] scalar multiplications and additions, where c k denotes a positive constant depending only on k. This run-time is order-optimal and improves Maslen's algorithm. [ABSTRACT FROM AUTHOR]