Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach
An important problem in the field of graph signal processing is developing appropriate overcomplete dictionaries for signals defined on different families of graphs. The Cayley graph of the symmetric group has natural applications in ranked data analysis, as its vertices represent permutations, while the generating set formalizes a notion of distance between rankings. Taking advantage of the rich theory of representations of the symmetric group, we study a particular class of frames, called Frobenius-Schur frames, where every atom belongs to the coefficient space of only one irreducible representation of the symmetric group. We provide a characterization for all Frobenius-Schur frames on the group algebra of the symmetric group which are "compatible" with respect to the generating set. Such frames have been previously studied for the permutahedron, the Cayley graph of the symmetric group with the generating set of adjacent transpositions, and have proved to be capable of producing meaningful interpretation of the ranked data set via the analysis coefficients. Our results generalize frame constructions for the permutahedron to any inverse-closed generating set.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
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. …
Recommendation SystemsEquivariant Frames and the Impossibility of Continuous Canonicalization
Canonicalization provides an architecture-agnostic method for enforcing equivariance, with generalizations such as frame-averaging recently gaining prominence as a lightweight and flexible alternative to equivariant arch…
Approximately Equivariant Graph Networks
Graph neural networks (GNNs) are commonly described as being permutation equivariant with respect to node relabeling in the graph. This symmetry of GNNs is often compared to the translation equivariance of Euclidean conv…
Image InpaintingPose EstimationTranslationMultiresolution analysis on the symmetric group
There is no generally accepted way to define wavelets on permutations. We address this issue by introducing the notion of coset based multiresolution analysis (CMRA) on the symmetric group; find the corresponding wavelet…
Multi-Object TrackingObject TrackingKnowledge Graph Embedding by Normalizing Flows
A key to knowledge graph embedding (KGE) is to choose a proper representation space, e.g., point-wise Euclidean space and complex vector space. In this paper, we propose a unified perspective of embedding and introduce u…
Graph EmbeddingKnowledge Graph Embedding