TY - JOUR

T1 - Orbit Computation for Atomically Generated Subgroups of Isometries of Z

AU - Yu, Haizi

AU - Mineyev, Igor

AU - Varshney, Lav R.

N1 - Funding Information:
\ast Received by the editors October 22, 2020; accepted for publication (in revised form) April 27, 2021; published electronically September 9, 2021. https://doi.org/10.1137/20M1375127 Funding: This work was funded in part by the IBM-Illinois Center for Cognitive Computing Systems Research (C3SR), a research collaboration as part of the IBM AI Horizons Network; and in part by grant 2018-182794 from the Chan Zuckerberg Initiative DAF, an advised fund of Silicon Valley Community Foundation. \dagger Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (haiziyu7@illinois.edu, varshney@illinois.edu). \ddagger Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801 USA (mineyev@ illinois.edu).
Publisher Copyright:
© 2021 Society for Industrial and Applied Mathematics

PY - 2021

Y1 - 2021

N2 - Partitions of a set play an important role in automatic knowledge discovery algorithms that learn human-like concepts from human-like innate priors. One such type of prior is isometries, the recognition of which is considered a part of innate human cognitive ability. In this paper, we consider isometries of Zn and compute isometry-subgroup-induced partitions as orbit computations under various isometry-subgroup actions on Zn. For both computational (to avoid infinity) and practical (to consider an application domain) reasons, we restrict the set of orbits, i.e., a partition of Zn, to a finite subset, i.e., a partition of Z \subseteq Zn. However, not only is the orbit relation still defined on the entire Zn, but the algorithm has no control over Z which is specified a priori by an application or a data set. Our main contribution is an efficient algorithm solving this restricted orbit-computation problem exactly, in the special case of atomically generated subgroups-a new notion motivated from building human-like artificial intelligence. Technically, the atomic property is key to preserving the semidirect-product structure-the core structure we leverage to make our algorithm outperform generic approaches. Besides algorithmic merit, our approach enables parallel-computing implementations in many subroutines, which can further benefit from hardware boosts. Moreover, our algorithm works efficiently for any finite subset Z regardless of its shape or its location in Zn. Therefore, this algorithmic efficiency is application-independent.

AB - Partitions of a set play an important role in automatic knowledge discovery algorithms that learn human-like concepts from human-like innate priors. One such type of prior is isometries, the recognition of which is considered a part of innate human cognitive ability. In this paper, we consider isometries of Zn and compute isometry-subgroup-induced partitions as orbit computations under various isometry-subgroup actions on Zn. For both computational (to avoid infinity) and practical (to consider an application domain) reasons, we restrict the set of orbits, i.e., a partition of Zn, to a finite subset, i.e., a partition of Z \subseteq Zn. However, not only is the orbit relation still defined on the entire Zn, but the algorithm has no control over Z which is specified a priori by an application or a data set. Our main contribution is an efficient algorithm solving this restricted orbit-computation problem exactly, in the special case of atomically generated subgroups-a new notion motivated from building human-like artificial intelligence. Technically, the atomic property is key to preserving the semidirect-product structure-the core structure we leverage to make our algorithm outperform generic approaches. Besides algorithmic merit, our approach enables parallel-computing implementations in many subroutines, which can further benefit from hardware boosts. Moreover, our algorithm works efficiently for any finite subset Z regardless of its shape or its location in Zn. Therefore, this algorithmic efficiency is application-independent.

KW - Atomic

KW - Isometry

KW - Restricted orbit computation

KW - Semidirect product

UR - http://www.scopus.com/inward/record.url?scp=85115932617&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85115932617&partnerID=8YFLogxK

U2 - 10.1137/20M1375127

DO - 10.1137/20M1375127

M3 - Article

AN - SCOPUS:85115932617

VL - 5

SP - 479

EP - 505

JO - SIAM Journal on Applied Algebra and Geometry

JF - SIAM Journal on Applied Algebra and Geometry

SN - 2470-6566

IS - 3

ER -