Year: 2021

Abstract:
Machine learning under the constraint of symmetries, given by group invariances or equivariances, has emerged as a topic of active interest in recent years. Natural settings for such applications include the multi-reference alignment and cryo electron microscopy, multi-object tracking, spherical images, and so on. A fundamental paradigm among such symmetries is the action of a group by symmetries, which often pertains to change of basis or relabelling of objects in pure and applied mathematics. Thus, a naturally significant class of functions consists of those that are intrinsic to the problem, in the sense of being independent of such base change or relabelling; in other words invariant under the conjugation action by a group. In this work, we investigate such functions, known as class functions, leveraging tools from group representation theory. A fundamental ingredient in our approach are given by the so-called irreducible characters of the group, which are canonical tracial class functions related to its irreducible representations. Such functions form an orthogonal basis for the class functions, extending ideas from Fourier analysis to this domain, and accord a very explicit structure. Exploiting a tensorial structure on representations, which translates into a multiplicative algebra structure for irreducible characters, we propose to efficiently approximate class functions using polynomials in a small number of such characters. Thus, our approach provides a global, non-linear coordinate system to describe functions on the group that is intrinsic in nature, in the sense that it is independent of local charts, and can be easily computed in concrete models. We demonstrate that such non-linear approximation using a small dictionary can be effectively implemented using a deep neural network paradigm. This allows us to learn a class function efficiently from a dataset of its outputs.

heading: 1 INTRODUCTION
text: Learning under group actions. Learning under group actions has emerged as a topic of key interest in recent years. The natural motivation for this paradigm comes from the many applications in which there is a canonical action of a group of symmetries, often arising as isometries or invariances of the model under consideration (Jebara & Kondor, 2008; Wein, 2018).
Instances of learning models that admit natural group actions are manifold. Examples range from natural image data that exhibit symmetries accorded by rotations and translations (Kondor, 2007; Kakarala, 2012); data arising in tomography (Vasco, 2007; Moroder et al., 2012); network based data (Giridhar & Kumar, 2006; Herzig et al., 2018); synchronization problems in robotics (Rosen et al., 2020); computer vision (Agrawal et al., 2006); problems like multi object tracking where many natural questions are invariant under the rearrangements of object labels (Kondor et al., 2007); atomic physics (Seko et al., 2019); learning permutations (Huang et al., 2009); Gaussian mixture models under group actions (Brunel, 2019), among many others (Bandeira et al., 2015b). Significant recent trends include neural networks that are equivariant under group actions on the data (Kondor & Trivedi, 2018; Worrall et al., 2016; Weiler et al., 2018a; Thiede et al., 2021) and related convolutional neural networks (CNNs) (Kondor et al., 2018; Cohen et al., 2018b; Niepert et al., 2016; Defferrard et al., 2016; Cohen & Welling, 2016; Cohen et al., 2018a; Esteves et al., 2018; Weiler et al., 2018b); multi-reference alignment (MRA) (Bandeira et al., 2014; Perry et al., 2019; Bendory et al., 2017; Sorzano et al., 2010; Abbe et al., 2018; Fan et al., 2020) and cryo electron microscopy (cryo EM)
under the action of the relevant Euclidean isometries (Singer et al., 2018; Hadani & Singer, 2011; Bendory et al., 2020; Bandeira et al., 2015a); and so forth.
Invariant functionals. A significant class of observables (i.e., functionals of the data) that attract natural interest in this setting consist of those that are invariant with respect to the group action under consideration; e.g., mutual distances under the action of a group of isometries, or the relative order of two objects under the permutation of their labels. In this work, we focus on a fundamental category of such observables, called class functions, that are invariant under the conjugation action of a group.
The conjugation action. Group action by conjugation is one of the foundational ways in which a group can act, and usually corresponds to a change of basis, or relabelling of objects or indices. A simple example is accorded by data in the form of matrices, where conjugation by an invertible matrix translates into a change of Euclidean basis, leading to the presentation of the information in a different co-ordinate system. In this setting, any function of the spectrum of the data matrix remains invariant under the change of basis (i.e., the conjugation action), and is clearly a significant feature to study. Yet another ready example is accorded by the permutation of the node labels in a network, which leaves invariant important network properties, such as diameter, subgraph counts and other aspects of network geometry, as well as the spectral properties of the network.
Symmetries, group representations and Fourier analysis. Fourier analysis is a central tool in fundamental machine learning tasks, entailing a vast collection of concepts including bandlimited functions and low pass filters, productively focussing on the low frequency part of the Fourier spectrum of a signal as the most significant component. At a conceptual level, much of this originates from the actions of the translational group of symmetries acting canonically on signals defined on Euclidean spaces; in particular, the structural simplicity is largely a consequence of the fact that these groups are abelian or commutative.
However, natural learning scenarios where the canonical symmetries form a non-abelian group (i.e., non-commutative) are numerous; even on Euclidean spaces, the translational symmetries when augmented with rotations constitute a ready example. In such settings, group representation theory (Simon, 1996) accords an extension of many of the Fourier analytic concepts; for instance the expansion of a function in terms of matrix-valued Fourier coefficients indexed by the so-called irreducible representations of the group. For a more detailed discussion on the fundamental synergies between Fourier analysis and group representations, we refer the reader to Sec. E in the appendix.
A non-linear conjugation invariant learning paradigm with neural networks. In the present work, we are focussed on learning conjugation invariant functions (i.e., class functions), which happen to accord a much simpler version of the non-commutative Fourier analysis discussed above. This is realised via an orthogonal linear basis of the so-called irreducible characters, which are essentially traces of certain minimal matrix representations of the group, and are well-understood in many concrete applications (c.f. Sec. E in appendix for details). It turns out that the space of irreducible characters exhibit a much richer structure in the form an algebra, which entails that it is closed under polynomial combinations. As an upshot, using polynomials of a few irreducible characters of relatively low order, one is able to express much more complicated characters of substantially higher order; leading to an approximation paradigm for general class functions via non-linear, polynomial combinations of a small alphabet of irreducible characters.
In implementing our programme, a fundamental role is played by neural networks, which allow us to effectively implement this non-linear approximation scheme. Our approach, in essence, leads to a global co-ordinate system for learning conjugation invariant functions on groups. Viewed from the perspective of function space approximation, our paradigm may be seen as a kind of non-linear dimension reduction tool for class functions.
Groups acting on homogeneous spaces. In some applications, the group of symmetries G acts on a set X of objects (e.g., rotations acting on a sphere) ; such a set (under a mild transitivity assumption) is referred to as a homogeneous space of the group. Our setup may be extended to cover such settings, using a canonical ‘lift’ of any function f : X 7→ R to a function f̃ : G 7→ R that satisfies f̃ = f ◦ π, for a standard quotient map π : G 7→ X (Dummit & Foote, 2004). Stipulating that f̃ is conjugation-invariant is equivalent to f being [G,G]-invariant on X , where [G,G] is the so-called commutator subgroup of G (c.f. Lemma C.1 in appendix). This covers the setting of functions f that are constant on the orbits of [G,G] acting on X . Such functions include binary classifiers on the permutation group Sn, classification problems on the dihedral group D2n, and so on. For a detailed
discussion, we refer the reader to Sec. C in the appendix. Further applications of our paradigm to groups acting on homogeneous spaces can be obtained via a general averaging paradigm, e.g. in the context of image alignment problems (c.f. Proposition 2.1).
Related literature. Class functions have appeared in various forms as useful methodological tools in the machine learning literature. These include the study of bi-invariant kernels in the context of RKHS on groups and homogeneous spaces (Jebara & Kondor, 2008); applications to problems of multi-object tracking Kondor et al. (2007); learning permutations (Jebara & Kondor, 2008); diffusion kernels on graphs Kondor & Lafferty (2002); Saloff-Coste (2001), and so on. Yarotsky (2021) examines an invariant theory based approach to learning under general symmetries via two layer neural nets with rather complex polynomial inputs; in contrast our approach inputs the ubiquitous group characters and approximates polynomials of high degree, via a few-layer network architecture that exploits the compositional aspect of neural nets in a non-trivial way. To the best of our knowledge, our approach to efficient learning of conjugation invariant functions through the lens of group character theory appears to be rather novel, and prior literature in a similar vein appears to be highly limited.

heading: 2 CONJUGATION INVARIANT FUNCTIONS AND THEIR APPLICATIONS
text: Our interest in this paper would be focussed on the so-called class functions, so we begin with a concrete definition.
Definition. Let G be a group. Two elements x, y ∈ G are said to be conjugate if ∃t ∈ G such that txt−1 = y. A function f : G 7→ S for any set S is called a class function if f(txt−1) = f(x) ∀t ∈ G.
Conjugacy is an equivalence relation, partitioning G into equivalence classes which are referred to as conjugacy classes. It follows from the definition that conjugation-invariant functions are constant on these conjugacy classes, hence the name class functions.
Class functions on SO(3) and Sn. Elements of the 3-D rotation group SO(3) are precisely 3 × 3 orthogonal matrices with determinant equal to 1. Two elements of SO(3) are conjugate if and only if they are similar matrices. This means that class functions on SO(3) only depend on the matrix spectrum of the elements of SO(3). In fact, every R ∈ SO(3) is similar (via conjugation) to a block
diagonal matrix of the form ( cos θ − sin θ 0 sin θ cos θ 0 0 0 1 ) . In geometric terms, the conjugacy classes of SO(3) are the sets of rotations by the same angle θ about different axes. The trace of these matrices is an example of a class function; tr(R) = 1 + 2 cos θ.
In the case of the symmetric group Sn, two permutations lie in the same conjugacy class if and only if they have the same cycle shape. Since cycle shapes are conveniently labelled using partitions, the conjugacy classes of Sn are most commonly labelled using partitions of n.
Class functions arise in many natural settings in machine learning. We provide below several such scenarios where class functions are of key importance.
A general averaging paradigm. We first provide a general setting where class functions arise naturally through a process of averaging over the group; conjugation invariant functionals often emerge in practical problems through such a procedure. Let G be a group acting on a space X; that is for every g ∈ G, we may associate a map Tg : X → X such that Te = idX is the identity map on the space X (where e is the identity element in the group G), and Tgh = Tg ◦ Th ∀g, h ∈ G. Let µ be the left Haar measure on the group G, i.e., dµ(g · h) = dµ(h) for all g, h ∈ G. Then we may state: Proposition 2.1. Let f : X ×X 7→ R be such that f(g(x), g(y)) = f(x, y) ∀x, y ∈ X, g ∈ G. For any pair x, y ∈ X and T ∈ G, define f̃x,y(T ) := ∫ G f(Tg(x), g(y))dµ(g). Then f̃x,y is a class function.
Functions f as in Proposition 2.1 that are invariant under the diagonal action of G naturally occur in a wide array of settings; prominent among them being in the form of distances (or angles) on a Euclidean space X under the action of a group of isometries G. For a concrete use-case, we refer to the image alignment application below.
Proof of Proposition 2.1. Given any h, T ∈ G, we have
f̃x,y(hTh −1) = ∫ G f(hTh−1g(x), g(y))dµ(g) = ∫ G f(Th−1g(x), h−1g(y))dµ(g)
= ∫ G f(Tg′(x), g′(y))dµ(g′) = f̃x,y(T ).
The third equality is due to left-invariance of µ and setting g′ = h−1g.
Image Alignment. Image alignment problems have received considerable attention in recent years, and furnish a natural example of class functions. To set the stage, we consider spherical images, which are well-motivated by projections of planar images onto the northern sphere (Kondor et al., 2018; Jebara & Kondor, 2008), images in the form of photos taken using a 360◦ camera, and so on. In the setting of Proposition 2.1, we set G = SO(3), X = S2 and f(x, y) to be the Euclidean distance between x and y, which would naturally be rotation invariant. Then f̃x,y(T ) is a measure of how well an image centered at x is aligned with an image centered at y after applying the rotation operator T . The quantityMx,y = minT f̃x,y(T ) captures the maximal alignment between the images, and can be used e.g. for classification tasks (e.g., if x is a prototype and y is a new image, then we classify y to the category of x ifMx,y smaller than a threshold). Proposition 2.1 demonstrates that f̃x,y is a class function on SO(3).
Quadratic Assignment Problem. Let Pn denote the group of n× n permutation matrices; that is matrices having exactly one entry equal to 1 in each row and column, and the remaining entries being 0. The quadratic assignment problem (QAP) is a fundamental problem in combinatorial optimization Koopmans & Beckmann (1957), where the goal is to find argmin
X∈Pn tr(AXBXT ); we will consider
this problem in the setting where A ∈ Pn and B is a general n× n matrix. Proposition 2.2. Let f : Pn 7→ R be given by f(A) := min
X∈Pn tr(AXBXT ), and B be an n × n
matrix. Then f is a class function.
Proof. We verify that f is a class function. Fix any Q,A ∈ Pn. Note that QT = Q−1.
f(QAQ−1) = min X∈Pn tr(QAQTXBXT ) = min X∈Pn tr(QT (QAQTXBXT )Q)
= min X∈Pn tr(AQTXBXTQ) = min X∈Pn tr(A(QTX)B(QTX)T )
= f(A).
This gives us a stopping algorithm (or target) for QAP in the following sense. Once we learn the function f , we could obtain or approximate the objective minimum f(A) for the QAP. We can then use some optimization algorithm (such as gradient descent) to update the matrixX in order to decrease the objective tr(AXBXT ), and terminate the optimization process once tr(AXBXT )− f(A) < for some acceptable error tolerance threshold > 0.
Testing on comparative rankings. Denote {1, 2, . . . , n} by [n]. Let Sn be the symmetric group on [n]. Suppose that we have two real-valued functions f1, f2 : [n]→ R. Then, f1 and f2 would induce orderings σ1 and σ2 respectively of [n]. For instance, we could have n individuals and f1(k), f2(k) are resp. the height and weight of individual k, leading to their ranking by heights or weights (denoted resp. by σ1, σ2). A natural question is the comparative analysis of such rankings, e.g. testing whether they are approximately similar. In such considerations, of natural interest are statistics like the number of individuals having the same rank, given by Ln := 1n ∑ k∈[n] 1[σ1(k)=σ2(k)] = 1 n ∑ k∈[n] 1[σ−12 σ1(k)=k] , where 1 is the indicator function.
Let f : Sn → R be the function f(σ) = 1n ∑ k∈[n] 1[σ(k)=k] for all σ ∈ Sn; notice that
Ln = f(σ−12 σ1). For any π, σ ∈ Sn, we may compute f(πσπ−1) = 1n ∑ k∈[n] 1[πσπ−1(k)=k] = 1 n ∑ k∈[n] 1[σπ−1(k)=π−1(k)] = f(σ). This demonstrates that the important statistic Ln = f is a class function.
Multi-object tracking. In the multi-object tracking problem, there are k objects with labels {1, . . . , k}, and we observe their arrangement which evolves with time; e.g. the evolution of the formation of jets flying in an air show. The data is succinctly described in terms of a permutation σ(t) mapping each label to its position in the arrangement at time t. Most of the fundamental questions about this model are actually independent of the labels; e.g., whether the starting and the final arrangements are the same, or the first time t = t0 at which σ(t) undergoes a change. etc. Any change in object labels amounts to a conjugation σ(t) 7→ πσ(t)π−1 for some permutation π, leading to the fact that the answer to the above natural questions pertaining to relative order are all class functions.

heading: 3 TENSOR PRODUCTS AND THE ALGEBRA OF CHARACTERS
text: The theoretical foundations of our approach are underlaid by the theory of tensor products of group representations, which manifests itself in the form of a polynomial algebra structure on group characters. Below, we provide a rudimentary outline of this theory, focussing on aspects that are fundamental to our approach. For an account of group representation theory essential for our approach, we refer the reader to Sec. E in the appendix.
The character χρ of a matrix representation ρ of a group G is the function χ : G → C defined by χ(x) = tr(ρ(x)). The characters inherit the inner product from the L2 structure on the group G. We call dρ the order of ρ or χρ. If ρ is an irreducible representation, we say that χρ is an irreducible character. Since tr(T−1AT ) = tr(A), it is evident that χρ is a class function. By the celebrated Peter-Weyl theorem (Simon, 1996), the set of irreducible characters form an orthonornal basis for the space of square integrable class functions.
Let ρ1 and ρ2 be two representations of G with corresponding characters χ1 and χ2 respectively. The tensor product representation is defined as ρ1 ⊗ ρ2(g):= ρ1(g) ⊗ ρ2(g) for all g ∈ G (to be understood in the form of tensor products of matrices). In general, if ρ1 ⊗ ρ2 is not an irreducible representation of G even if ρ1 and ρ2 are irreducible. However, the theorem of complete reducibility (Simon, 1996) tells us that it must decompose uniquely as a direct sum of irreducible representations of G.
ρ1(g)⊗ ρ2(g) ∼= ⊕
ρ∈R(G)
ρ⊕cρ1,ρ2,ρ , (1)
where ρ⊕m just means the direct sum ofm copies of ρ, ⊕m
k=1 ρ, andR(G) is the set of all irreducible representations ofG; we also note the simple relation χρ1⊕ρ2 = χρ1 +χρ2 . Let χ1⊗2 be the character corresponding to ρ1 ⊗ ρ2. An important observation is that χ1⊗2(g) = χ1(g)χ2(g), a relation that may be understood in the context of the tracial identity for matrix tensor products; namely, tr(A⊗B) = tr(A)tr(B). Thus, we have
χ1(g)χ2(g) = ∑ ρ cρ1,ρ2,ρχρ(g). (2)
(2) induces a canonical polynomial algebra structure on characters, which we will exploit in our approach. In the literature, the coefficients cρ1,ρ2,ρ are known as the Clebsch-Gordan coefficients; they are well understood for many groups (Costa & Fogli, 2012). These coefficients are known to be of fundamental importance in quantum mechanics, where they arise in the consideration of independent quantum systems.

heading: 4 OUR PARADIGM : NON-LINEAR APPROXIMATION VIA NEURAL NETWORKS

heading: 4.1 LINEAR VS NON-LINEAR APPROXIMATION
text: In this work, we focus on the task of effective approximation of class functions with a limited alphabet (i.e., dictionary or collection) of irreducible characters, thereby achieving a kind of nonlinear dimension reduction. Peter-Weyl theory guarantees that the set χ(G) of irreducible characters form an orthonormal basis for the space of class functions on G. Therefore, in principle, any class function f can be learned simply by linear regression onto χ(G). However, χ(G) is finite if and only if G is finite; so for infinite compact groups (such as SO(3)) or even large finite groups, we
can only aspire to learn f from irreducible characters upto sufficiently high order while maintaining a reasonable computational expense. In natural applications, the class function of interest may be highly irregular (e.g. a finite linear combination of indicators in a classification problem); since characters are generally highly regular (e.g., smooth) functions, we would require a very large number of characters to obtain effective linear approximation of irregular functions.

heading: 4.2 NON-LINEARITY VIA NEURAL NETS
text: The cornerstone of our approach is to exploit the non-linear, polynomial tensor algebra structure of the group characters in order to amplify and augment the expressive power of a small alphabet of irreducible characters (c.f., Section 3). In implementing our programme, a key role is played by neural networks, which allow us to obtain effective non-linear approximations of class functions in an efficient manner. Apart from their well-known effectiveness in tackling non-linearities, we do not need to a-priori specify explicit polynomial expressions of higher order characters in terms of those in the alphabet; such expressions can be complicated to compute explicitly.

heading: 4.3 A NEURAL NETWORK BASED CONJUGATION INVARIANT LEARNING PROTOCOL WITH A SMALL ALPHABET
text: We delineate below the main steps of our procedure to approximate a class function f on a group G.
Input. A small subset of irreducible characters {χ1, χ2, . . . , χw} ⊂ R(G) as alphabet; input data in the form of pairs {(gi, f(gi)) : gi ∈ G; 1 ≤ i ≤ m}. Step 1. For each 1 ≤ i ≤ m, compute vi = (χ1(gi), χ2(gi), . . . , χw(gi)). Step 2. Use {(vi, f(gi)) : 1 ≤ i ≤ m} as the training dataset to train a neural network with width w for the initial layer, and width 1 for the final layer. Step 3. For any new input argument g ∈ G, we compute the prediction f̂(g) as follows: Step 3a. Compute vg = (χ1(g), χ2(g), . . . , χw(g)). Step 3b. Perform forward propagation in the neural network output in Step 2 above, with input vg . Step 3c. Output the result of Step 3b above as the estimate f̂(g).

heading: 4.4 A GLOBAL COORDINATE SYSTEM AND NON-LINEAR DIMENSION REDUCTION
text: Our approach, in essence leads to a global co-ordinate system for learning conjugation invariant functions on groups (see Sec. B in appendix for detailed discussion). The global co-ordinates of a point g ∈ G would be given by (χ1(g), . . . , χw(g)), where {χi}wi=1 is our small alphabet of characters. This stands in contrast to local co-ordinate systems on manifolds or Lie group, which are based on local charts and therefore are effective only in small neighbourhoods; for discrete groups, even such local charts are not available. Further, our alphabet can effectively approximate general class functions via non-linear combinations, thereby according us a low dimensional non-linear co-ordinate system to approximate the infinite dimensional space of class functions. From this perspective, our limited alphabet of characters may be seen as a non-linear dimension reduction tool for class functions.

heading: 5 THE EXPRESSIVE POWER OF SMALL ALPHABETS AND NON-LINEARITY
text: In this section, we explore the expressive power of small alphabets of characters for some significant groups. We demonstrate that non-linear, polynomial functions of a very small collection of irreducible characters in groups such as SO(3) and SU(3) are sufficient to generate all characters in these groups, thereby leading to an approximation of arbitrary class functions. This provides a strong theoretical basis to substantiate our approach of learning arbitrary class functions using deep neural networks with a small set of low order irreducible characters as global coordinates. Although the results presented in this section focus on SO(3) and SU(3), we believe that similar analysis can be extended to other groups of practical significance. Such groups often admit a detailed representation theory in general, and an explicit Clebsch-Gordan tensorial decomposition in particular, stemming from their importance in physics and applied mathematics. We refer the reader to Sec. A in the appendix for
discussion on the symmetric group Sn. For computational techniques for general groups, see Unger (2006); Babai & Rónyai (1990) in the discrete and Blaha (1969); Green (1971) in the continuum setting. The degree of the polynomial in a small alphabet that is needed to express a higher order character may be taken as a measure of the expressive power of the alphabet, with a low degree signifying high expressive power. Below, we demonstrate that for groups of fundamental interest in applications, we are able to obtain high expressive power with a very small alphabet of irreducible characters.
5.1 EXPRESSIVE POWER AND CLEBSCH-GORDAN STRUCTURE FOR SO(3).
The irreducible representations of SO(3), the 3D rotation group, may be conveniently labelled by {ρj | j ∈ Z≥0}, where each ρj is of order 2j + 1 (ρ0 is the one-dimensional trivial representation). Let χj be the corresponding irreducible character. The Clebsch-Gordan decomposition for SO(3) turns out to be very explicit. For l ≥ m, we have
ρl ⊗ ρm ∼= ρl+m ⊕ ρl+m−1 ⊕ · · · ⊕ ρl−m.
In terms of characters, we have for l ≥ m
χl · χm = χl+m + χl+m−1 + · · ·+ χl−m. (3)
Theorem 5.1. Fix any l ≥ 0. Then, χl ∈ Z[χ1]. Moreover, χl is a polynomial of degree l.
Proof. Setting m = 1 in (3) yields
χl+1 = χl · χ1 − χl − χl−1, l ≥ 1. (4)
We will prove this result by induction on l.
Base case l ≤ 1 : χ0 is the trivial character, which is the constant function χ0(g) = 1 ∀g ∈ SO(3), so it is a polynomial of degree 0. We of course have that χ1 is a polynomial of degree 1 in Z[χ1].
Suppose that for every 0 ≤ j ≤ l, χj lies in Z[χ1] and that it is a polynomial of degree j. We want to prove that χl+1 lies in Z[χ1] and that it is a polynomial of degree l + 1.
By (4), we have χl+1 = χl · χ1 − χl − χl−1. By our inductive hypothesis, the right-hand side is evidently a polynomial of degree l + 1 in Z[χ1].

heading: 5.2 EXPRESSIVE POWER AND CLEBSCH-GORDAN STRUCTURE FOR SU(3).
text: SU(3), the group of 3 × 3 unitary matrices with determinant 1, is of key interest in the celebrated Yang-Mills theory and related areas of physics, and has seen a recent surge of activity from a machine learning perspective (Matsumoto et al., 2021; Anderson et al., 2020). The irreducible representations of SU(3) may be succinctly labelled as {D(p, q) | p, q ∈ Z≥0}; in physical terms, p is the number of quarks and q is the number of antiquarks (D(0, 0) is the trivial representation) (Hall, 2015). D(p, q) is known to have order 12 (p+ 1)(q + 1)(p+ q + 2). There are many algorithms for computing the Clebsch-Gordan coefficients for SU(3) in general; however, they are rather complicated in nature. We list three simple recursive relations which are sufficient for our study of expressive power.
D(p, 0)⊗D(0, q) ∼= D(p, q)⊕ [D(p− 1, 0)⊗D(0, q − 1)], p, q > 0.
D(p, 0)⊗D(1, 0) ∼= D(p+ 1, 0)⊕D(p− 1, 1), p > 0. D(0, q)⊗D(0, 1) ∼= D(0, q + 1)⊕D(1, q − 1), q > 0.
In terms of irreducible characters, we have respectively for p, q > 0; p > 0 and q > 0 :
χp,q = χp,0χ0,q − χp−1,0χ0,q−1; χp+1,0 = χp,0χ1,0 − χp−1,1; χ0,q+1 = χ0,qχ0,1 − χ1,q−1 (5) We now use these recursive relations to prove by induction on p+ q that every irreducible character χp,q occurs as a polynomial of the two lowest order (order 3) non-trivial irreducible characters χ1,0 and χ0,1.
Theorem 5.2. Fix any p, q ∈ Z≥0. Then, χp,q ∈ Z[χ1,0, χ0,1]. Moreover, χp,q is a polynomial of degree at most p+ q.
Proof. We prove the statement by induction on N = p+ q.
Base case N = p+ q ≤ 1 : χ0,0 = 1, χ1,0, χ0,1 ∈ Z[χ1,0, χ0,1]. There is nothing to show here. Suppose that χr,s ∈ Z[χ1,0, χ0,1], having degree ≤ r + s, whenever r + s ≤ N . We want to prove that χp,q ∈ Z[χ1,0, χ0,1], with degree ≤ p+ q, whenever p+ q = N + 1. Case 1: p+ q = N + 1, p, q > 0. By (5), we have χp,q = χp,0χ0,q − χp−1,0χ0,q−1. The right-hand side is a polynomial of the form χr,s such that r + s ≤ N , therefore χp,q ∈ Z[χ1,0, χ0,1] as required. Case 2: p = N+1, q = 0. By (5), we have χN+1,0 = χN,0χ1,0−χN−1,1. Once again, the right-hand side is a polynomial of the form χr,s such that r + s ≤ N , therefore χN+1,0 ∈ Z[χ1,0, χ0,1]. Case 3: p = 0, q = N + 1. By (5), we have χ0,N+1 = χ0,Nχ0,1 − χ1,N−1. Once again, the right-hand side is a polynomial of χr,s such that r + s ≤ N , therefore χ0,N+1 ∈ Z[χ1,0, χ0,1].

heading: 6 EXPERIMENTS
text: In this section, we provide a brief description of demonstrative numerical experiments to show the feasibility and efficacy of our learning paradigm in several distinct contexts, . The reader may refer to the appendix Sec. F for a more detailed description and additional experiments. We used TensorFlow (Apache License 2.0) and Keras (MIT License) to run our experiments Abadi et al. (2015); Chollet et al. (2015) on an Intel i7-5500U chip.
The group SO(3) is the standard rotation group on the Euclidean space R3, significant in many applications such as imaging. Let χj be the irreducible character of SO(3) as mentioned in Sec. 5.1. We use a fully connected neural network with 3 hidden layers (ConjInv) with the ReLU activation function at every layer except the last and input alphabet {χ0, χ1, . . . , χ10} (see Sec. 4.3) to learn class functions f (specified below) on SO(3). For each experiment, 24000 points g = (α, β, γ) ∈ [0, 2π]× [0, π]× [0, 2π] on SO(3) are picked uniformly at random to generate our data of the form (g, f(β)) (note that class functions on SO(3) only depend on β). We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively. Throughout this section, we minimize the squared error loss (MSE) using Adam Kingma & Ba (2017). Hyperparameters are tuned according to the validation set and the final performance is measured on the test set.
We benchmark our results against a fully connected neural network with 6 hidden layers (DeepEuler) that takes the group elements g = (α, β, γ) ∈ SO(3) directly as inputs as well as a linear regression model (Regression) with input alphabet {χ0, χ1, . . . , χ32}. The Euler angles fully describe the group elements in SO(3), and thus a comparison of DeepEuler with ConjInv provides a concrete measure of the effectiveness of an alphabet of irreducible characters. On the other hand, since characters form a linear basis of the space of conjugation-invariant functions, regression on characters will provide nearly exact learning if the number of characters is high, which suggests such regression as another benchmark to compare against. Our experiments demonstrate that conjugation invariant learning with group characters outperforms both DeepEuler and Regression.
Learning continuous class functions on SO(3). We randomly generate 100 class functions f as Gaussian linear combinations of χ50, χ51, . . . , χ59 to be learned by ConjInv, DeepEuler and Regression as described above. The three models are compared based on their log-loss on the test set. See Fig. 1.
Learning discontinuous class functions on SO(3). We randomly generate 100 discontinuous class functions f by taking Gaussian linear combinations of some binary valued indicator func-
tions 10,11, . . . ,19, where 1k(α, β, γ) = { 1 if 0.1πk ≤ β ≤ 0.1πk + 0.12π, 0 otherwise. These functions are learned by ConjInv, DeepEuler and Regression as described above. The three models are compared based on their log-loss on the test set. See Fig. 2.
Learning class functions on Sn. This is an important model of a highly non-commutative discrete group that arises in various applications. For the detailed experiment, we refer the reader to Section F.1 the appendix.
Learning discontinuous class functions on SU(3). This is a crucial model of a Lie group that has significant physical applications, including in particular in quantum chromodynamics Halzen &
Figure 1
Figure 2
Martin (2008); additional computational challenges result from the matrix entries being complex numbers. We refer the reader to the Section F.4 in the appendix.

heading: 7 DISCUSSION
text: We investigate conjugation invariant functions on groups, and propose an effective learning paradigm for such functions via non-linear functions of a small alphabet of characters. We substantiate our approach via theoretical analysis on several groups significant in applications, and via synthetic experiments using neural networks to efficiently capture the non-linearities.
To our knowledge, the present submission is the first work to explore the problem of learning conjugation invariant functions. Another key aspect of our work is to propose the extensive use of group characters, particularly their non-linear polynomial functionals, as a tool in machine learning under group action. Further, we set up our approach to be applicable in the context of the actions of any group, whereas many of the popular methods (such as CNNs) are tailored to specific kinds of group actions, or specific application domains. As such, there is very little benchmark to compare against for the problem at hand. We emphasize that, given that this is the first exploration in this area, our experiments are more for demonstrative purposes to provide proof-of-concept for our paradigm; the main contributions of the paper being in the realm of theory and ideas.
The investigations in the present paper call forth natural directions for future work, including experiments with real-life data, a theoretical as well as experimental study of how to optimally choose the size of the input character alphabet in relation to the computational budget available (e.g., depth of the neural net), a theoretical analysis of expressive power that subsumes general classes of group actions, and domain-specific applications such as graph neural networks Maron et al. (2018); Azizian & Lelarge (2020); Keriven & Peyré (2019). We believe that our work will motivate new perspectives within the general ambit of learning under group actions.

heading: APPENDIX TO CONJUGATION INVARIANT LEARNING WITH NEURAL NETWORKS
text: Anonymous authors Paper under double-blind review

heading: A EXPRESSIVE POWER AND CLEBSCH-GORDAN STRUCTURE FOR SYMMETRIC GROUPS.
text: Let Sn be the symmetric group on n letters. Two permutations in Sn are conjugate if and only if they have the same cycle shape.
Definition. We say that an m-tuple (λ1, λ2, . . . , λm) is a partition of n if λi ∈ Z>0, λi+1 ≤ λi and m∑ i=1 λi = n. The number of parts of λ is denoted by l(λ) = m.
We denote the set of all partitions of n by P(n). A natural ordering of P(n) is the lexicographic order.
Definition. If λ and µ are partitions of n, we write λ > µ if and only if the least j for which λj 6= µj satisfies λj > µj .
Cycle shapes may be canonically represented by partitions of n. It is a well known fact that for any finite group G, the set of irreducible representations of G over C is in bijection with the conjugacy classes of G (in particular, character tables for finite groups are square). Therefore, it is not surprising that the irreducible representations of Sn may be conveniently labelled by the partitions of n. For each λ ∈ P(n), there is an associated irreducible representation V λ (known as Specht modules in the literature) of Sn. Some examples are the one-dimensional trivial representation V (n) and the one-dimensional sign representation V (1
n), where (1n) is a shorthand for the partition (1, 1, . . . , 1) ∈ P(n). For a more detailed description of the Specht modules, the reader may refer to Gordan James’s classical textbook James (2006).
Definition. Let λ ∈ P(n). The Young diagram of λ is defined to be the set
[λ] = {(a, b) ∈ Z>0 × Z>0 | 1 ≤ a ≤ l(λ), 1 ≤ b ≤ λa}.
The elements of [λ] are called the nodes of λ.
Definition. The conjugate of a partition λ is the partition λ′ = (λ′1, λ′2, . . . ) such that λ′i = #{j ≥ 1 | λj ≥ i}.
In other words, the Young diagram [λ′] may be obtained by swapping the rows and columns of [λ]:
[λ′] = {(b, a) ∈ Z>0 × Z>0 | (a, b) ∈ [λ]}.
In particular, we note that (λ′)′ = λ. This induces a pairing of partitions in P(n). The Young diagram of a partition λmay be represented pictorially by a diagram. For each (i, j) ∈ [λ], we insert a box into the ith row and jth column of the diagram.
Example. Suppose that λ = (7, 6, 5, 5, 1) ∈ P(24) so that l(λ) = 5. [λ] :
λ′ = (5, 44, 2, 1). [λ′] :
The Clebsch-Gordan coefficients for Sn are also known as the Kronecker coefficients in the literature. A fundamental problem in the representation theory of Sn is to understand the Kronecker coefficients. Apart from some special cases Bowman et al. (2015); Tewari (2015); Hamermesh (2012) such as when the partitions have only two parts or are hook-shaped, there are more questions than answers in general.
A fundamental yet simple method of constructing representations of Sn is by taking an existing representation and tensoring it with the one-dimensional sign representation V (1
n). Doing this for the irreducible Specht module V λ produces its conjugate Specht module V λ ′ :
V λ ⊗ V (1 n) ∼= V λ ′ ∀λ ∈ P(n).
Let χλ be the irreducible character corresponding to V λ. In terms of characters, the above result is simply
χλχ(1 n) = χλ ′ . (1)
LetR(G) denote the set of irreducible characters of a group G. This means that we may pick a single representative character χλ for every pair of characters (χλ, χλ ′ ) when curating an alphabet X to generateR(Sn) as a polynomial in R[X]. In other words, the size of the minimal generating alphabet X is at most about half that ofR(Sn). We believe that in most cases, the minimal generating alphabet size will be even smaller. However, due to the difficulty of working with Kronecker coefficients, a general result of this form is beyond the scope of this paper and may be discussed in a future work. We demonstrate this with a small example using only one more basic fact Hamermesh (2012) about Kronecker coefficients. For any n ∈ Z>0 and λ ∈ P(n),
χλχ(n−1,1) = (#{λi} − 1)χλ + ∑ µ χµ, (2)
where the sum is over all partitions µ whose Young diagram [µ] is obtained from the Young diagram [λ] by removing a node and adding another node, and #{λi} − 1 is one less than the number of different row lengths of [λ]. Example. Let n = 6. We list all 11 partitions of 6 in the following table:
λ (6) (5, 1) (4, 2) (4, 1, 1) (3, 3) (3, 2, 1) λ′ (16) (2, 1, 1, 1, 1) (2, 2, 1, 1) (3, 1, 1, 1) (2, 2, 2) (3, 2, 1)
Recall that χ(6) is the trivial character that takes constant value 1. By (1), we have R[R(S6)] = R[χ(5,1), χ(4,2), χ(4,1,1), χ(3,3), χ(3,2,1), χ(16)]. We show that in fact,
R[R(S6)] = A := R[χ(5,1), χ(4,2), χ(1 6)].
It suffices to show that χ(4,1,1), χ(3,3) and χ(3,2,1) ∈ A. By (2), we have χ(5,1)χ(5,1) = 1 + χ(5,1) + χ(4,2) + χ(4,1,1), thus χ(4,1,1) ∈ A.
Using (2) again, we obtain
χ(5,1)χ(4,2) = χ(5,1) + χ(4,2) + χ(4,1,1) + χ(3,3) + χ(3,2,1) and
χ(5,1)χ(4,1,1) = χ(5,1) + χ(4,2) + χ(4,1,1) + χ(3,2,1) + χ(3,1,1,1).
Hence, χ(3,3) + χ(3,2,1) ∈ A and χ(3,2,1) + χ(3,1,1,1) ∈ A. Since (3, 1, 1, 1) = (4, 1, 1)′, we have χ(3,1,1,1) = χ(4,1,1)χ(1 6) ∈ A by (1).
Therefore, χ(3,2,1) ∈ A and χ(3,3) ∈ A.
This completes the proof that R[R(S6)] = R[χ(5,1), χ(4,2), χ(1 6)]. Remark. Similarly, one can show using (1) and (2) that R[R(S7)] = R[χ(6,1), χ(5,2), χ(1 7)]. Note that |P(7)| = 15.

heading: B GLOBAL COORDINATES VIA IRREDUCIBLE CHARACTERS
text: In the main text, Sec. 4.4, we indicated that our approach, in essence leads to a global co-ordinate system for learning conjugation invariant functions on groups. To be precise, the global co-ordinates of a point g ∈ G would be given by (χ1(g), . . . , χw(g)), where {χi}wi=1 is our small alphabet of characters. Herein, we discuss further details and geometric implications of this, which we needed to abbreviate in the main text. We emphasize that, these global co-ordinates are with a view to learning conjugation invariant functions on the group G. We recall here that conjugation invariant functions are constant on the conjugacy classes, which are the orbits of the conjugation action of G on itself. For optimality of representation, it is natural that a coordinate system for efficient learning of class functions would be constant on the conjugacy classes of the group. This is satisfied by our characterinduced coordinate system (χ1(·), . . . , χw(·)), which is constant on the conjugacy classes ofG. Thus, in precise terms, these global coordinates parametrize the space of conjugacy classes of the group, which is minimally sufficient for describing class functions on G. On a Lie group (such as SO(n) or SU(n)), the conjugation action of the group is a smooth action, i.e. the map τ(g, x) = gxg−1 is a smooth map taking G × G 7→ G. The decomposition of the group into conjugacy classes corresponds to a foliation of G (viewed as a manifold, c.f. (Lawson Jr, 1974; Walschap, 2012)) into submanifolds (called the leaves of the foliation) corresponding to the conjugacy classes, on which any class functions is constant. Thus, from a geometric point of view, the coordinates induced by the irreducible characters provide a global parametrization for the leaves of the foliation of G into its conjugacy classes.

heading: C LIFTING FUNCTIONS ON HOMOGENEOUS SPACES TO GROUPS
text: In this section, we elaborate on the ideas articulated in the main text, pertaining to the lifting of functions from homogeneous spaces to groups, thereby substantiating our focus on studying functions defined on groups.
In our considerations, we mostly focus on the scenario where the conjugation invariant function is defined on the group, and the group is envisaged to be acting on itself. In many situations of interest in ML, the group of symmetries actually happen to act on a set of objects that are directly not elements of the group itself. Such a set on which the group acts is sometimes referred to as a homogeneous space of the group. However, we demonstrate that our setup is easily extended to cover such situations.
In the common situation where the group G acts transitively on the homogeneous space X (i.e. any pair of elements in X can be mapped to each other by appropriate group elements, e.g. the Euclidean rotation group acting on the sphere), it is known that the homogeneous space X can be identified with a quotient of the group G by a certain subgroup (the stabilizer subgroup of any given point in X). This is entailed by the celebrated Orbit-Stabilizer Theorem. In fact, this essentially identifies X as the coset space of such a stabilizing subgroup of G.
In the context of our work, the upshot of this is that, any function f : X 7→ R can be ‘lifted’ to a function on G, which is to say that there is a function f̃ : G 7→ R and a surjective quotient map π : G 7→ R such that f̃(g) = f(π(g))∀g ∈ G. Since π is surjective, the functional value of f at
any point x ∈ X can be obtained from f̃ in accordance with the above formula. This procedure is completely canonical, and can be easily carried out explicitly in a general setting. The lifting
construction is succinctly summarized in the following commutative diagram: G
X R
π f̃
f
A simple yet informative example of the above scenario is accorded by the action of the permutation group Sn on the labels [n] of a setX of n objects. If we fix a specific object, then its label is stabilized or left unchanged under this action by a Stab subgroup of Sn that permutes only the labels of the remaining n− 1 objects, and is thus isomorphic to Sn−1. The set X , by the preceding discussion, is therefore in bijective correspondence with the coset space Sn/Stab; notice that since Stab ∼= Sn−1, we have |Sn/Stab| = |Sn/Sn−1| = n. The cosets of the subgroup Stab form a disjoint partition of Sn: in other words, Sn = ⋃̇ Stabi, where Stabi are the disjoint cosets of Stab inside Sn. Any function f : X 7→ R can be lifted to a function f̃ according to the above recipe as follows. Any σ ∈ Sn belongs to a unique coset Stabiσ above. On the other hand, each coset Stabi maps to a unique element xi ∈ X under the Orbit-Stabilizer paradigm. We construct f̃ by setting f̃(σ) = f(xiσ ). It is easy to verify that f̃ indeed satisfies the requirements of the commutative diagram above, thereby verifying that it is a legitimate lift of f from X to Sn, as desired.
We conclude this section with a theoretical analysis of how the group action on a homogeneous space X decomposes X into a disjoint union of commutator orbits.
Lemma C.1. Let the groupG act transitively on the homogeneous spaceX . Let f : X 7→ R, with the lift f̃ : G 7→ R such that f̃ = f ◦π, where π : G 7→ X is the canonical projection map. Then f̃ being conjugation invariant under G is equivalent to f being invariant under the induced action of [G,G] on X , where [G,G] is the commutator subgroup of G generated by {[g, h] = ghg−1h−1 : g, h ∈ G}.
Proof. Fix x0 ∈ X . We define f̃(g) = f(g · x0) for g ∈ G. f̃ is conjugation invariant if f̃(ghg−1) = f̃(h)∀g, h ∈ G. In terms of f , we have f(ghg−1 · x0) = f(h · x0)∀g, h ∈ G. Writing x = h · x0, we may write f(ghg−1h−1x) = f(x)∀g, h ∈ G, that is, f([g, h] · x) = f(x) ∀g, h ∈ G, where [g, h] = ghg−1h−1 is the commutator of g and h. Thus, f̃ is conjugation invariant implies that f is [G,G] invariant. It is easy to see that we can reverse this argument to obtain the converse implication.
To summarize, the full group G acts transitively on the homogeneous space X , enabling a lift of the function f to a function f̃ on G. This function being conjugation invariant on G amounts to the function f being invariant to the induced action of the commutator subgroup [G,G] on X . We may view this as the homogeneous space X being partitioned into [G,G]-orbits, whereby f is constant on each [G,G]-orbit.
For any group G, the commutator subgroup [G,G] is the smallest normal subgroup N of G such that G/N is abelian. In some sense, [G,G] captures all the non-abelian attributes of G.
Commutators are well-studied objects in group theory. For example, it is known that the commutator of the symmetric group Sn is the alternating group An. For the dihedral group D2n, which is generated by a reflection x and a rotation y satisfying the relations x2 = yn = 1, xyx = y−1, the commutator [G,G] is the cyclic subgroup generated by y2.

heading: D COMPACT VS NON-COMPACT GROUPS
text: We emphasize that, in the present work, we focus on the case of compact groups; finite groups trivially belonging to that category in particular. Compact groups are, in a sense, a natural point of departure for investigations such as ours for an array of reasons. On one hand, compact groups (such as rotations or permutations) provide some of the most fundamental models for learning under non-abelian group actions. On the other hand, compact groups allow for a very concrete and wellunderstood representation theory and character theory, as outlined in the main text. However, the action of non-compact groups does arise as symmetries in many interesting applications. Of course,
for locally compact abelian groups, we have an elaborate theory of commutative Fourier analysis on groups, as discussed in the main text (also c.f. (Rudin, 1962)); a ready example being provided by the commutative action of the group of real numbers (or that of Rd in general) in many natural learning set ups. A natural application of locally compact non-abelian groups is accorded by the group of Euclidean isometries (denoted E(n) or ISO(n)), generated by translations and rotations acting on Euclidean space. In more advanced physical applications, depending on the energy scale and relativistic effects involved, it is also of interest to investigate the action of the Galilean group or the Poincare group (c.f. (Arnol’d, 2013; Nadjafikhah & Forough, 2007; Tung, 1985)). While the representation theory and the character theory of general classes of non-compact non-abelian groups poses a formidable mathematical challenge, the investigation of specific groups relevant to applications opens a natural direction for future work.

heading: E GROUP REPRESENTATIONS, IRREDUCIBLE CHARACTERS AND FOURIER ANALYSIS
text: E.1 GROUP REPRESENTATIONS, IRREDUCIBLE CHARACTERS AND PETER-WEYL THEORY
We provide here the very broad contours of only a few aspects of the deep theory of group representations Simon (1996), focussing on ingredients that would be germane to our approach. We will consider ρ to be a matrix representation of G. That is, ρ : G → Cdρ×dρ ; ρ(xy) = ρ(x)ρ(y) for any x, y ∈ G; and ρ(e) = I , where e is the identity element of G and I is the identity matrix. The character χρ of ρ is the function χ : G → C defined by χ(x) = tr(ρ(x)). We call dρ the order of ρ or χρ. We say that ρ is reducible if it decomposes into a direct sum of smaller representations as
ρ(x) = Q−1(ρ1(x)⊕ρ2(x))Q = Q−1 ( ρ1(x) 0 0 ρ2(x) ) Q ∀x ∈ G for some invertible matrix Q ∈ Cdρ×dρ which is independent of x. Otherwise, we say that ρ is irreducible. If ρ is an irreducible representation, we say that χρ is an irreducible character. Since tr(T−1AT ) = tr(A), it is evident that χρ is a class function. By the celebrated Peter-Weyl theorem (Simon, 1996), the set of irreducible characters form an orthonornal basis for the space of square integrable class functions.
E.2 REPRESENTATION THEORY AND NON-COMMUTATIVE FOURIER ANALYSIS.
Classical Fourier analysis, in its simplest avatar, entails that given a function f : S1 7→ C, we may decompose f as f(x) = ∑∞ k=−∞ f̂(k)e
ikx, with the Fourier coefficients being defined as f̂(k) = 12π ∫ 2π 0 f(x)e−ikxdx. Representation theory allows us to undertake Fourier analysis on groups. If f : G 7→ C (where G is a locally compact abelian group with Haar measure µ), we may decompose f as f(x) = ∫ Ĝ f̂(χ)χ(x−1)dµ̂(χ), with f̂(χ) = ∫ G f(x)χ(x)dµ(x); here where χ ranges over the the space of irreducible characters ofG (equalling in this case the so-called Pontryagin dual Ĝ). It is known that the irreducible representations of an abelian group are all one-dimensional, so each f̂(χ) is still a scalar.
If G is non-abelian but is compact, then the set of irreducible representations, also denoted asR(G), is known to be countable, and the representing matrices ρ may be taken to be unitary matrices. Given a function f : G→ C, we may decompose f as
f(x) = 1
µ(G) ∑ ρ∈R(G) dρtr[f̂(ρ)ρ(x−1)], with f̂(ρ) = ∫ G f(x)ρ(x)dµ(x). (3)
It may be noted in this case that each Fourier coefficient f̂(ρ) is a matrix, leading to the notion of non-commutative Fourier analysis stemming from the fundamentally non-commutative nature of matrix multiplication.
E.3 PLANCHEREL’S THEOREM AND BAND-LIMITED FUNCTIONS.
In classical Fourier analysis, Plancherel’s Theorem tells us that the Fourier transform preserves energy; namely, ∫∞ −∞ |f(x)| 2dx = ∑∞ k=−∞ |f̂(k)|2. Since the sum on the right is finite, |f̂(k)|2 → 0 as
k →∞. Thus, f(x) is well-approximated by ∑k0 k=k0 f̂(k)eikx for sufficiently large k0. This is akin
to band-limiting f , a device that is extremely useful in signal processing and many other areas of applied mathematics. In the case of compact groups, it is known that the non-commutative Fourier transform f 7→ f̂ defined above satisfies a non-commutative Plancherel’s theorem. Indeed,
1
µ(G) ∫ G |f(x)|2dµ(x) = 1 [µ(G)]2 ∑ ρ∈R(G) dρ‖f̂(ρ)‖2Frob. (4)
Since the sum on the right of (4) is finite, ‖f̂(ρ)‖2Frob → 0 as dρ → ∞. Thus, f(x) is wellapproximated by 1µ(G) ∑ dρ≤k0 dρtr[f̂(ρ)ρ(x
−1)] for sufficiently large k0, leading to a notion of non-commutative bandlimiting for functions defined on non-abelian groups.

heading: F EXPERIMENTS
text: Using the ideas in Sec. 4.3, we implement several numerical experiments to show how neural networks with small alphabet can be used to approximate various class functions. Our experiments are implemented using TensorFlow (Apache License 2.0), Keras (MIT License) Abadi et al. (2015); Chollet et al. (2015) and SageMath (GPLv3) Stein et al. (2021). Tensorflow and Keras was used to train our models. SageMath was used to compute the irreducible characters of S30.
F.1 LEARNING CLASS FUNCTIONS ON Sn
Since the conjugacy classes of Sn are canonically labelled by partitions A, class functions on Sn can be realised as functions on P(n). Set n = 30. There are 5604 partitions of 30. We generate 100 class functions on S30 by taking Gaussian linear combinations of 10 irreducible characters χ(18,4,2,2,1,1,1,1), χ(18,4,2,1,1,1,1,1,1), . . . , χ(18,3,3,1,1,1,1,1,1); (18, 4, 2, 2, 1, 1, 1, 1) > (18, 4, 2, 1, 1, 1, 1, 1, 1) > · · · > (18, 3, 3, 1, 1, 1, 1, 1, 1) are the 251st, 252nd, . . . , 260th elements of P(30) in the lexicographic order A. Our training data comprises 1400 (∼25% of |P(30)|) function evaluations (λ, f(λ)), where the partitions λ are sampled uniformly at random from P(30). To approximate this, we train a fully connected neural network with 3 hidden layers of width 180, 120 and 50 respectively. The input layer consists of the 50 irreducible characters χ(30), χ(29,1), . . . , χ(22,6,1,1), χ(1
30); these are the irreducible characters corresponding to the first 49 elements of P(30) in the lexicographic order, on top of the one-dimensional sign character χ(1
30). The SELU non-linear activation function and Gaussian kernel initializer is applied throughout. We minimize the squared error loss (MSE) with L2 regularization parameter α = 0.001 using AdaMax Kingma & Ba (2017).
As a benchmark, we train a linear regression model with 100 input alphabets {χ(30), χ(29,1), . . . , χ(20,9,1), χ(130)}; these are the irreducible characters corresponding to the first 99 elements of P(30) in the lexicographic order plus the sign character χ(130). Gaussian kernel initializer is used and we minimize the squared error loss using Adam Kingma & Ba (2017).
Note that we apply the same hyperparameters (chosen to ensure reasonable convergence) for each of the 100 class functions that we train. Our neural network was trained over 200 epochs using a batch size of 100 for each class function. The linear regression model was also trained over 200 epochs using a batch size of 100. Our models are evaluated using 10-fold cross-validation.
In the scatter plot of Figure 1, each point corresponds to the performance of our models on a fixed class function, with the y-axis representing the mean MSE over 10 folds and the x-axis representing the corresponding standard deviation. Taking the mean MSE over 10 folds as a representative for each scatter point, we obtain the histogram in Figure 1. We display the average of the histogram in its legend. Note that we normalized each of the 100 class functions f so that the mean of squares over the 1400 instances of f(λ) is equal to 1.
We find that the performance of the neural network is far superior to the performance of a linear regression model with double the size of the alphabet. The mean MSE over 100 class functions trained for linear regression is 5.10 times higher than that for the neural network.
F.2 LEARNING CONTINUOUS CLASS FUNCTIONS ON SO(3)
This experiment was described briefly in Section 6. We provide the full details here. Let χj be the irreducible character corresponding to the (2j + 1)-dimensional irreducible representation ρj of SO(3) (see Section 5.1). Then, χj is the real-valued function χj(β) = sin((2j+1)β/2) sin(β/2) for 0 ≤ β ≤ π (note that class functions on SO(3) depend only on a single angle β).
We generate 100 class functions f on SO(3) by taking Gaussian linear combinations of 10 high order irreducible characters χ50, χ51, . . . , χ59. Our data comprises 24000 function evaluations (g = (α, β, γ), f(β)), where g = (α, β, γ) was drawn uniformly at random from [0, 2π]× [0, π]× [0, 2π]. We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively. A fully connected neural network (ConjInv) with 3 hidden layers of width 100, 50 and 20 respectively is fit to the train set over 180 epochs using a batch size of 1000. The input layer consists of the 11 lowest order irreducible characters χ0, χ1, . . . , χ10 of SO(3) (see Sec. 4.3). The ReLU non-linear activation function is used at every layer except the last. Gaussian kernel initializer is applied throughout. We minimize the squared error loss (MSE) with L2 regularization parameter 5× 10−4 using Adam Kingma & Ba (2017) with learning rate 10−3. The hyperparameters were tuned according to the validation set.
Our first benchmark is a fully connected neural network with 6 hidden layers (DeepEuler) of width 150, 120, 80, 60, 30 and 10 respectively. The input layer consists of the three Euler angles g = (α, β, γ). DeepEuler is fit to the train set over 130 epochs using a batch size of 1000. The ReLU non-linear activation function is used at every layer except the last. Gaussian kernel initializer is applied throughout. By tuning hyperparameters according to the validation set, we optimize DeepEuler using Adam Kingma & Ba (2017) with learning rate 8×10−2 subject to L2 regularization parameter 3× 10−12. As a second benchmark, a linear regression model Regression with 33 input alphabets χ0, χ1, . . . , χ32 is fit to the train set over 100 epochs using a batch size of 500. Gaussian kernel initializer is used. By tuning hyperparameters according to the validation set, we optimize Regression using Adam Kingma & Ba (2017) with learning rate 3 × 10−3 and L2 regularization parameter 10−15.
The three models are evaluated on the test set. We compare their log losses in Figure 2. Positive values in our histogram represent instances when ConjInv outperforms its benchmark. Observe that when compared against Regression, ConjInv has superior performance 100 out of 100 times. On the other hand, ConjInv outperforms DeepEuler 98 out of 100 times. By taking the average of the histograms, we conclude that on average, the mean squared error loss for Regression and DeepEuler are e4.30 = 73.7 and e2.76 = 15.8 times that of ConjInv respectively.
F.3 LEARNING DISCONTINUOUS CLASS FUNCTIONS ON SO(3)
We provide the full details to the experiment described in Section 6. Let χj be the irreducible character of SO(3) (see Sec. F.2).
100 discontinuous class functions f on SO(3) are generated by taking Gaussian linear combinations of some binary valued indicator functions 10,11, . . . ,19, where
1k(α, β, γ) = { 1 if 0.1πk ≤ β ≤ 0.1πk + 0.12π, 0 otherwise.
Drawing 24000 instances of g = (α, β, γ) uniformly at random from [0, 2π]× [0, π]× [0, 2π], we obtain 24000 datapoints of the form (g, f(β)). We split our data into train, validation and test sets with 20000, 2000 and 2000 points respectively. We fit ConjInv from Sec. F.2 to the train set over 180 epochs using a batch size of 180. By tuning the hyperparameters according to the validation set, we minimize the mean squared error loss with L2 regularization parameter 10−15 using Adam Kingma & Ba (2017) with learning rate 10−3.
Just like in Sec. F.2, our first benchmark is DeepEuler, which is fit to the train set over 180 epochs using a batch size of 2000. By tuning hyperparameters according to the validation set, we optimize DeepEuler using Adam Kingma & Ba (2017) with learning rate 8×10−2 subject to L2 regularization parameter 10−15.
We also benchmark against Regression, which is fit to the train set over 100 epochs using a batch size of 500. By tuning hyperparameters according to the validation set, we optimize Regression using Adam Kingma & Ba (2017) with learning rate 3× 10−3 subject to L2 regularization parameter 10−15.
The three models are evaluated on the test set. We compare their log losses in Figure 3. Positive values in our histogram represent instances when ConjInv outperforms its benchmark. Observe that when compared against DeepEuler and Regression, ConjInv achieves superior performance 100 out of 100 times. By taking the average of the histograms, we conclude that on average, the mean squared error loss for Regression and DeepEuler are e2.22 = 9.2 and e2.69 = 14.7 times that of ConjInv.
F.4 LEARNING DISCONTINUOUS CLASS FUNCTIONS ON SU(3)
Let χp,q be the irreducible character corresponding to the irreducible representation D(p, q) of SU(3) (see Section 6.2). Then, χp,q is the complex-valued function χp,q(θ, φ) = ei θ 3 (2p+q) ∑p k=0 ∑q l=0 e
−i(k+l)θ( sin((k−l+q+1)φ/2)sin(φ/2) ), for−2π ≤ φ ≤ 2π and−3π ≤ θ ≤ 3π. Since Keras does not support complex valued data types, we use the Complex-Valued Neural Networks library Barrachina (2021) to work with class functions on SU(3).
We generate 100 discontinuous class functions on SU(3) by taking Gaussian linear combinations of 25 binary valued indicator functions 1k,l for 0 ≤ k, l ≤ 4, where
1k,l(θ, φ) =  1 if − 3π + 1.2kπ ≤ θ ≤ −3π + 1.2kπ + 1.32π and −2π + 0.8lπ ≤ φ ≤ −2π + 0.8lπ + 0.88π
0 otherwise.
Our training data comprises 8500 function evaluations (θ, φ, f(θ, φ)), where (θ, φ) was drawn uniformly at random from [−3π, 3π]× [−2π, 2π]. To approximate this, we train a fully connected neural network with 6 hidden layers of width 180, 150, 100, 60, 35 and 10 respectively. The input layer consists of the 25 irreducible characters χp,q for 0 ≤ p, q ≤ 4. The ReLU non-linear activation function is applied throughout, except in the last layer where the activation function takes the absolute values of complex numbers to provide a real-valued output for the purposes of training. We minimize the squared error loss (MSE) with L2 regularization parameter α = 10−8 using AdaMax Kingma & Ba (2017).
As a benchmark, we train a linear regression model with 49 input alphabets χp,q for 0 ≤ p, q ≤ 7 and an activation function that takes the absolute values of complex numbers to provide a real-valued output for the purposes of training. We minimize the squared error loss with L2 regularization parameter α = 10−9 using AdaMax Kingma & Ba (2017).
Note that we apply the same hyperparameters (chosen to ensure reasonable convergence) for each of the 100 class functions that we train. Our neural network was trained over 100 epochs using a batch size of 500 for each class function. The linear regression model was trained over 300 epochs using a batch size of 250. Our models are evaluated on 1500 unseen datapoints (θ, φ) drawn uniformly at random from [−3π, 3π]× [−2π, 2π]. Recording the squared error loss (MSE) of our two models on these 100 class functions, we obtain 200 entries for the histogram in Figure 4. Our neural network performs 160 times better than linear regression with almost double the size of the alphabet, achieving an MSE of just 2.362 as compared to 378.1.

Review summaries:
This paper proposes a strategy to learn class function on groups (and by extension on homogeneous spaces). The paper is motivated by applications in inverse problems and image processing (e.g. particle alignment in CryoEM) as well as integer programming (e.g. the quadratic assignment problem). The authors note that irreducible characters form a basis for square-integrable class functions and then apply a neural network on a set of invariant features chosen as low-order irreducible characters rather than directly on the input, which naturally results in a conjugation-invariant function. They argue that the neural network (thanks to the nonlinear activations functions) can generate the needed high-order characters. The obtained invariant architecture is then applied to several toy problems with synthetic data. 

In this manuscript, the authors develop a DNN paradigm that learns functions on groups as polynomials using canonical tracial class functions as an orthogonal basis for class functions called irreducible representations. Since the basis constitutes a nonlinear coordinate system, it has the potential to efficiently handle complex symmetries. The paper shows analyticaly and numericaly that for simple systems such as SO(3) and SU(3), the proposed paradigm has high expressive power with few bases.

The paper first makes the case that learning conjugation invariant functions is of interest in many machine learning problems, stating in a general form in which they appear. It then presents a simple method, using a MLP, for approximating such functions efficiently using a small number of irreducible characters. This capitalizes on the notion that irreducible characters are closed under polynomial combinations. Thus, using polynomials of a few irreducible characters (of lower order) one can express characters of considerably higher order. It is shown that the method proposed can approximate class functions of interest well numerically.