FAST DISCRETE POLYNOMIAL-TRANSFORMS WITH APPLICATIONS TO DATA-ANALYSIS FOR DISTANCE-TRANSITIVE GRAPHS

Let P = {P-0,...,Pn-1) denote a set of polynomials with complex coeffi cients. Let 2 = (z(0),...,z(n-1)) subset of C denote any set of sample points. For any f = (f(0),..., f(n-1)) is an element of C-n, the disc rete polynomial transform of f (with respect to P and Z) is defined as the collection of sums, {(f) over cap(P-0),..., (f) over cap(Pn-1)}, where (f) over cap(P-j) = [f, P-j] = Sigma(i=0)(n-1) f(i)P(j)(z(i))w(i ) for some associated weight function to. These sorts of transforms fi nd important applications in areas such as medical imaging and signal processing. In this paper, we present fast algorithms for computing di screte orthogonal polynomial transforms. For a system of N orthogonal polynomials of degree at most N - 1, we give an O(N log(2) N) algorith m for computing a discrete polynomial transform at an arbitrary set of points instead of the N-2 operations required by direct evaluation. O ur algorithm depends only on the fact that orthogonal polynomial sets satisfy a three-term recurrence and thus it may be applied to any such set of discretely sampled functions. In particular, sampled orthogona l polynomials generate the vector space of functions on a distance tra nsitive graph. As a direct application of our work, we are able to giv e a fast algorithm for computing subspace decompositions of this vecto r space which respect the action of the symmetry group of such a graph . This has direct applications to treating computational bottlenecks i n the spectral analysis of data on distance transitive graphs, and we discuss this in some detail.