# Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis

arXiv: https://arxiv.org/abs/2103.04150 · HTML: https://mlsanity.com/paper/2103.04150/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 110 references that are in the map.
- First posted on arXiv 6 Mar 2021.

## Builds on (most cited first, 3 of 3)

- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Localized Spectral Graph Filter Frames: A Unifying Framework, Survey of Design Considerations, and Numerical Comparison (Extended Cut)](https://mlsanity.com/paper/2006.11220/) (2020)
- [Graph Blind Deconvolution with Sparseness Constraint](https://mlsanity.com/paper/2010.14002/) (2020)

## Built on by (most cited first, 2 of 2)

- [Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach](https://mlsanity.com/paper/2203.03036/) (2022)
- [What is Smoothness?](https://mlsanity.com/paper/2609.03246/) (2026)

## Abstract (arXiv)

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.