\chapter{Introduction}

\section{The Fourier transform}

The Fourier transform is known to most scientists and engineers as a
tool for data analysis.  Given a signal, the classical Fourier
transform recovers its spectrum, which describes how the signal can be
broken into sines and cosines, or, equivalently, complex exponentials.
In the discrete case, where the signal consists of a finite number of
data points, there are well-known computational techniques for this;
most notable is the discrete fast Fourier transform (FFT) algorithm
due to Cooley and Tukey \cite{cooley-tukey}.  The FFT allows the
Fourier transform to be computed efficiently, and has become an
extremely important tool for digital signal processing in fields
ranging from physics and engineering to electronic music.

However, complex exponentials are not the only ``pieces'' into which
we might wish to decompose a signal.  The crucial feature of functions
like $e^{it}$ is that they are in a sense invariant under translation;
shifting $t$ changes the function only by a (complex) constant
multiple.  So the classical Fourier transform extracts from the signal
components which fit nicely into this translational structure.  But
there are other sorts of structure we might seek.  In fact, this
structure can be described by a group, and the idea of the Fourier
transform generalizes to cover the case of an arbitrary group.
Unfortunately, though, if computational efficiency is needed, more
work must be done.  Although the Cooley-Tukey FFT algorithm can be
generalized to some extent (see for instance
\cite{maslen:cooley-tukey}), for many groups, efficient Fourier
transform algorithms are not obvious or not known.

The Fourier transform can be thought of as a change of basis; in fact,
this is how it is often characterized in analysis.  In essence, we are
decomposing our signal space into one-dimensional subspaces, and
looking at the components of the signal that lie in these subspaces.
In some cases, it can be helpful if we relax this condition somewhat,
and decompose the signal into larger components which nevertheless
retain the important structural information we seek.  This is the idea
of isotypic projections, which we discuss in Chapter \ref{reptheory}.

\section{Eigenspaces and our approach}

One disadvantage of generalizations the Cooley-Tukey FFT is that it
relies heavily on algebraic facts about the group involved, making it
rather complicated to implement.  We shall describe an approach to
isotypic projections which relies on straightforward techniques from
linear algebra.  In particular, it can be possible to compute isotypic
projections with respect to some group via an algorithm for eigenspace
projections, if the appropriate eigenspaces are used.  The goal, then,
is to find a ``separating set'' of simultaneously diagonalizable
linear transformations whose eigenspaces are the subspaces we seek.
Chapter \ref{eigen} explains the details of this approach.  Of course,
finding such a set will necessarily require an algebraic understanding
of the group in question; but once it is found, implementation of the
projection algorithm becomes elementary.

We will be working with the automorphism groups of binary trees, to be
described in Chapter \ref{auto}.  These groups are of interest for
several tasks in signal processing; see for instance Section
\ref{haar}, as well as \cite{foote:image1} and
\cite{rockmore:wreath-fft}.  In addition, the decomposition of their
signal spaces has interesting combinatorial properties; see Section
\ref{wn-reptheory} and \cite{orrison:root}.

\section{Previous work}

The idea of using eigenspaces to compute isotypic projections was
explored in detail in \cite{orrison:thesis}.  Its inspiration comes
from the one of the myriad properties of the Jucys-Murphy elements
from the symmetric group (Section \ref{jucys-murphy} and
\cite{diaconis:murphy}), which can be applied for just this purpose.
Generalizations of these elements exist (\cite{diaconis:murphy},
\cite{russian}, \cite{ram}), but by no means have they been
generalized to all groups.

Much is known about the structure of the automorphism groups of binary
trees, and wreath product groups in general (see Section
\ref{wreath}).  Their representation theory is examined in
\cite{kerber1} and \cite{kerber2}, and more recently a combinatorial
approach to the more specific case of iterated wreath products of
cyclic groups is in \cite{orrison:root}.  Spectral analysis on these
groups has been considered in \cite{foote:image1} and
\cite{rockmore:wreath-fft}, with applications to signal and image
processing.

Computational details about the linear algebra involved have also been
considered.  \cite{orrison:thesis} gives bounds on the computational
complexity of using separating sets for several groups.
\cite{norton:thesis} presents an important optimization in the case of
the symmetric group, which is generalized in \cite{summer}.

\section{Structure of this paper}

In Chapter~\ref{reptheory} we review necessary concepts and facts from
the representation theory of finite groups.  Chapter~\ref{eigen}
discusses the ``eigenspace approach'' to isotypic projections, through
which the necessary computations for isotypic projections can be done
using simple linear algebra tools.  Chapter~\ref{auto} describes the
automorphism groups with which we shall concern ourselves.  Finally,
Chapter~\ref{sepset} constructs some separating sets for small cases.
{"config": "arxiv", "file": "1406.6403/intro.tex"}