Signal processing on the permutahedron: tight spectral frames for ranked data analysis
From MaRDI portal
Abstract: 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.
Recommendations
- Generalized permutation polytopes and exploratory graphical methods for ranked data
- Canonical decompositions and invariants for data analysis.
- A generalization of spectral analysis with application to ranked data
- Graphical methods for ranking data
- Inverse semigroup spectral analysis for partially ranked data
Cites work
- S_nFFT: a Julia toolkit for Fourier analysis of functions over permutations
- A Fourier space algorithm for solving quadratic assignment problems
- A Fourier-theoretic approach for inferring symmetries
- A generalization of spectral analysis with application to ranked data
- A review of distances for the Mallows and generalized Mallows estimation of distribution algorithms
- A Signal Processing Approach to Fourier Analysis of Ranking Data: The Importance of Phase
- A Spectral Analysis Approach for Experimental Designs
- An introduction to finite tight frames
- Blind Identification of Graph Filters
- Codes, transforms and the spectrum of the symmetric group
- Combining Results of Microarray Experiments: A Rank Aggregation Approach
- Diameter bounds and recursive properties of Full-Flag Johnson graphs
- Efficient Clustering for Orders
- Fast Fourier transform for fitness landscapes
- Fast Fourier Transforms for Symmetric Groups: Theory and Implementation
- Fourier theoretic probabilistic inference over permutations
- Frames and bases. An introductory course
- Gabor-type frames for signal processing on graphs
- Generalized permutation polytopes and exploratory graphical methods for ranked data
- Generating a random permutation with random transpositions
- Graph theory
- scientific article; zbMATH DE number 1600999 (Why is no real title available?)
- scientific article; zbMATH DE number 3126067 (Why is no real title available?)
- scientific article; zbMATH DE number 4076317 (Why is no real title available?)
- scientific article; zbMATH DE number 44579 (Why is no real title available?)
- scientific article; zbMATH DE number 51129 (Why is no real title available?)
- scientific article; zbMATH DE number 177221 (Why is no real title available?)
- scientific article; zbMATH DE number 177225 (Why is no real title available?)
- scientific article; zbMATH DE number 475357 (Why is no real title available?)
- scientific article; zbMATH DE number 1004944 (Why is no real title available?)
- scientific article; zbMATH DE number 847276 (Why is no real title available?)
- Introduction to representation theory
- Inverse semigroup spectral analysis for partially ranked data
- Inversions in ranking data
- Metric methods for analyzing partially ranked data
- Minimal eigenvalue of the Coxeter Laplacian for the symmetric group
- Mixtures of distance-based models for ranking data
- NON-NULL RANKING MODELS. I
- On Cayley graphs on the symmetric group generated by transpositions
- Random shuffles and group representations
- Sampling and learning Mallows and generalized Mallows models under the Cayley distance
- Statistical methods for ranking data
- Symmetry classes of spanning trees of aztec diamonds and perfect matchings of odd squares with a unit hole
- The Discrete Cosine Transform
- The efficient computation of Fourier transforms on semisimple algebras
- The efficient computation of Fourier transforms on the symmetric group
- Transition matrices between Young's natural and seminormal representations
- Wavelets on graphs via spectral graph theory
Cited in
(7)- A noncommutative approach to the graphon Fourier transform
- Inverse semigroup spectral analysis for partially ranked data
- Overview of the topical collection: harmonic analysis on combinatorial graphs
- Interpreting the phase spectrum in Fourier analysis of partial ranking data
- A Signal Processing Approach to Fourier Analysis of Ranking Data: The Importance of Phase
- Frames for signal processing on Cayley graphs
- Unified Fourier transform on graphs sampled from stochastic block models
This page was built for publication: Signal processing on the permutahedron: tight spectral frames for ranked data analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048691)
