Periodicity Transforms

by William A. Sethares and Tom Staley

Humans are very good at identifying complex patterns: the auditory system easily senses intricate periodicities such as the rhythms that normally occur in music and speech, the visual system readily grasps the symmetries and repetitions inherent in textures and tilings, the mind searches for simple underlying regularities to explain phenomena that appear complex and irregular. Computers are comparatively poor at locating such patterns, though several kinds of "transforms" are aimed at automatically identifying underlying patterns. Perhaps the best known is the Fourier Transform, which attempts to explain a data set as a weighted sum of sinusoidal basis elements. When the data can be closely approximated by such elements, the Fourier Transform provides both an explanation and a concise representation of the data. Similarly, the Wavelet Transform decomposes data into a sum of basis elements that are defined by a family of scaling functions. Again, when the data has the assumed scaling properties, this provides a convincing representation and explanation. None of the available methods, however, directly searches for periodicities, repetitions, or regularities in the data. This paper builds on a classical technique called the Buys-Ballot table for the determination of "hidden periodicities" to fill this gap. By analogy with modern wavelet and other transforms, we call these Periodicity Transforms.

Periodicity Transforms decompose a data sequence into a sum of simple periodic sequences by projecting onto a set of periodic subspaces, leaving residuals whose periodicities have been removed. As the name suggests, this decomposition is accomplished directly in terms of periodic sequences and not in terms of frequency or scale, as do the Fourier and Wavelet Transforms. In consequence, the representation is linear-in-period, rather than linear-in-frequency or linear-in-scale. Unlike most transforms, the set of basis vectors is not specified a priori, rather, the Periodicity Transform finds its own "best" set of basis elements. Technically, the collection of all periodic subspaces forms a frame, a more-than-complete spanning set. The Periodicity Transforms specify ways of sensibly handling the redundancy by exploiting some of the general properties of the periodic subspaces.

The algorithms are derived and analyzed, and their output compared to that of the Fourier Transform in a number of examples. One application is the finding and grouping of rhythms in a musical score, another is the separation of periodic waveforms with overlapping spectra, and a third is the finding of patterns in astronomical data. Examples demonstrate both the strengths and weaknesses of the method. A companion paper explores the application of Periodicity Transforms to the automatic detection of rhythm in musical performance.

Click here for more information about periodicity transforms, and to download MATLAB programs.