Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach

• URL: http://arxiv.org/abs/2203.03036v1
• Date: Sun, 6 Mar 2022 19:41:36 GMT
• Title: Frames for Graph Signals on the Symmetric Group: A Representation Theoretic Approach
• Authors: Kathryn Beck and Mahya Ghandehari
• Abstract summary: We study a 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. Our results generalize frame constructions for the permutahedron to any inverse-closed generating set.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• HeNCler: Node Clustering in Heterophilous Graphs through Learned Asymmetric Similarity [55.27586970082595]
  HeNCler is a novel approach for Heterophilous Node Clustering. We show that HeNCler significantly enhances performance in node clustering tasks within heterophilous graph contexts.
  arXiv  Detail & Related papers  (2024-05-27T11:04:05Z)
• Sampling and Uniqueness Sets in Graphon Signal Processing [136.68956350251418]
  We study the properties of sampling sets on families of large graphs by leveraging the theory of graphons and graph limits. We exploit the convergence results to provide an algorithm that obtains approximately close to optimal sampling sets.
  arXiv  Detail & Related papers  (2024-01-11T22:31:48Z)
• Algebras of actions in an agent's representations of the world [51.06229789727133]
  We use our framework to reproduce the symmetry-based representations from the symmetry-based disentangled representation learning formalism. We then study the algebras of the transformations of worlds with features that occur in simple reinforcement learning scenarios. Using computational methods, that we developed, we extract the algebras of the transformations of these worlds and classify them according to their properties.
  arXiv  Detail & Related papers  (2023-10-02T18:24:51Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Equivariant Representation Learning in the Presence of Stabilizers [13.11108596589607]
  EquIN is suitable for group actions that are not free, i.e., that stabilize data via nontrivial symmetries. EquIN is theoretically grounded in the orbit-stabilizer theorem from group theory.
  arXiv  Detail & Related papers  (2023-01-12T11:43:26Z)
• An efficient algebraic representation for graph states for measurement-based quantum computing [0.0]
  Graph states are main computational building blocks of measurement-based computation. We show how to efficiently express a graph state through the generators of the stabilizer group. We provide a framework to manipulate the graph states with a reduced number of stabilizers.
  arXiv  Detail & Related papers  (2022-12-23T01:40:03Z)
• Isotropic Gaussian Processes on Finite Spaces of Graphs [71.26737403006778]
  We propose a principled way to define Gaussian process priors on various sets of unweighted graphs. We go further to consider sets of equivalence classes of unweighted graphs and define the appropriate versions of priors thereon. Inspired by applications in chemistry, we illustrate the proposed techniques on a real molecular property prediction task in the small data regime.
  arXiv  Detail & Related papers  (2022-11-03T10:18:17Z)
• Approximate Fr\'echet Mean for Data Sets of Sparse Graphs [0.0]
  In this work, we equip a set of graph with the pseudometric matrix defined by the $ell$ norm between the eigenvalues of their respective adjacency. Unlike the edit distance, this pseudometric reveals structural changes at multiple scales, and is well adapted to studying various statistical problems on sets of graphs. We describe an algorithm to compute an approximation to the Fr'echet mean of a set of undirected unweighted graphs with a fixed size.
  arXiv  Detail & Related papers  (2021-05-10T01:13:25Z)
• Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis [1.8352113484137624]
  ranked data sets are increasingly prevalent in contexts such as political elections, computer vision, recommender systems, and bioinformatics. 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.
  arXiv  Detail & Related papers  (2021-03-06T16:32:32Z)
• Articulated Shape Matching Using Laplacian Eigenfunctions and Unsupervised Point Registration [38.16866987817019]
  Spectral graph theory can be used to map these graphs onto lower dimensional spaces and match shapes by aligning their embeddings. We derive a new formulation that finds the best alignment between two congruent $K$-dimensional sets of points by selecting the best subset of eigenfunctions of the Laplacian matrix.
  arXiv  Detail & Related papers  (2020-12-14T08:49:25Z)
• Constraints on Maximal Entanglement Under Groups of Permutations [73.21730086814223]
  Sets of entanglements are inherently equal, lying in the same orbit under the group action. We introduce new, generalized relationships for the maxima of those entanglement by exploiting the normalizer and normal subgroups of the physical symmetry group.
  arXiv  Detail & Related papers  (2020-11-30T02:21:22Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.