Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked
  Data Analysis
  Ranked data sets, where m judges/voters specify a preference ranking of n
objects/candidates, are increasingly prevalent in contexts such as political
elections, computer vision, recommender systems, and bioinformatics. The vote
counts for each ranking can be viewed as an n! data vector lying on the
permutahedron, which is a Cayley graph of the symmetric group with vertices
labeled by permutations and an edge when two permutations differ by an adjacent
transposition. Leveraging combinatorial representation theory and recent
progress in signal processing on graphs, we investigate a novel, scalable
transform method to interpret and exploit structure in ranked data. We
represent data on the permutahedron using an overcomplete dictionary of atoms,
each of which captures both smoothness information about the data (typically
the focus of spectral graph decomposition methods in graph signal processing)
and structural information about the data (typically the focus of symmetry
decomposition methods from representation theory). These atoms have a more
naturally interpretable structure than any known basis for signals on the
permutahedron, and they form a Parseval frame, ensuring beneficial numerical
properties such as energy preservation. We develop specialized algorithms and
open software that take advantage of the symmetry and structure of the
permutahedron to improve the scalability of the proposed method, making it more
applicable to the high-dimensional ranked data found in applications.
