Recovering a group from few orbits
Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Finite automorphism groups of algebraic, geometric, or combinatorial structures (20B25) Ordinary representations and characters (20C15) Hilbert and pre-Hilbert spaces: geometry and topology (including spaces with semidefinite inner product) (46C05)
Let \(V\) be a finite-dimensional Hilbert space over \(\mathbb{F}\in\{\mathbb{R},\mathbb{C}\}\) and let \(G\le \operatorname{Aut}(V)\) be an unknown finite group of automorphisms. The paper studies how many generic \(G\)-orbits in \(V\), observed as unstructured subsets, suffice to recover \(G\) up to isomorphism (abstract recovery) and as a concrete subgroup of \(\operatorname{Aut}(V)\) (concrete recovery).\N\NThe Gram graph of a finite set \(S\subset V\) is the complete directed graph on vertex set \(S\) in which the edge \(s\to t\) is labeled by the inner product \(\langle s,t\rangle\). For abstract recovery, the main complex result (Theorem 2) shows that one generic orbit suffices: for generic \(v\in V\) the isomorphism class of the Gram graph of \(Gv\) determines \(G\) up to isomorphism and the canonical map \(G\to \operatorname{Aut}(Gv)\) is an isomorphism. In the real case, two generic orbits suffice (Theorem 3), while the analogous one-orbit statement remains open as a conjecture.\N\NFor concrete recovery, the authors first show that, for generic \((v_1,\dots,v_k)\in V^k\), the canonical map \(G\to \operatorname{Aut}(Gv_1\cup\cdots\cup Gv_k)\) is an isomorphism provided \(k\ge 1\) if \(\mathbb{F}=\mathbb{C}\) and \(k\ge 2\) if \(\mathbb{F}=\mathbb{R}\) (Theorem~4). They then give sharp representation-theoretic criteria ensuring that \(k\) generic orbits span a subspace of codimension \(<r\), where \(r\) is the dimension of the smallest nontrivial representation of \(G\) (Theorem 5), using the regular representation and multiplicity bounds. Corollary 1 combines these ingredients: if \(k\) satisfies both the orbit-number condition from Theorem 4 and the spanning criterion from Theorem 5, then \(k\) generic orbits determine \(G\) as a concrete subgroup of \(\operatorname{Aut}(V)\); if the spanning criterion fails, then no choice of \(k\) orbits determines \(G\).
- A characterization of projective unitary equivalence of finite frames and applications
- Almost everywhere injectivity conditions for the matrix recovery problem
- An algebraic characterization of injectivity in phase retrieval
- An introduction to finite tight frames
- Bispectrum unbiasing for dilation-invariant multi-reference alignment
- Complete set of translation invariant measurements with Lipschitz bounds
- Doubly transitive lines. I: Higman pairs and roux
- Doubly transitive lines. II: Almost simple symmetries
- Estimation under group actions: recovering orbits from invariants
- Generalized phase retrieval: measurement number, matrix recovery and beyond
- scientific article; zbMATH DE number 3217531 (Why is no real title available?)
- scientific article; zbMATH DE number 3071015 (Why is no real title available?)
- Lie PCA: density estimation for symmetric manifolds
- Machine Learning and Invariant Theory
- Max filtering with reflection groups
- Maximum likelihood for high-noise group orbit estimation and single-particle cryo-EM
- On signal reconstruction without phase
- On the construction of highly symmetric tight frames and complex polytopes
- Orbit recovery for band-limited functions
- SE(3) synchronization by eigenvectors of dual quaternion matrices
- Stable separation of orbits for finite abelian group actions
- The sample complexity of sparse multi-reference alignment and single-particle cryo-electron microscopy
- The symmetry group of a finite frame
- Tight frames and their symmetries
- Towards a bilipschitz invariant theory
- Universally optimal distribution of points on spheres
- Über die dichteste Kugellagerung
This page was built for publication: Recovering a group from few orbits
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6858023)
