# Universality of Group Convolutional Neural Networks Based on Ridgelet
Analysis on Groups

Sho Sonoda
RIKEN AIP
<EMAIL_ADDRESS>Ishikawa
Ehime University
<EMAIL_ADDRESS>Ikeda
RIKEN AIP
<EMAIL_ADDRESS>
###### Abstract

We show the universality of depth-2 group convolutional neural networks
(GCNNs) in a unified and constructive manner based on the ridgelet theory.
Despite widespread use in applications, the approximation property of (G)CNNs
has not been well investigated. The universality of (G)CNNs has been shown
since the late 2010s. Yet, our understanding on how (G)CNNs represent
functions is incomplete because the past universality theorems have been shown
in a case-by-case manner by manually/carefully assigning the network
parameters depending on the variety of convolution layers, and in an indirect
manner by converting/modifying the (G)CNNs into other universal approximators
such as invariant polynomials and fully-connected networks. In this study, we
formulate a versatile depth-2 continuous GCNN $S[\gamma]$ as a nonlinear
mapping between group representations, and directly obtain an analysis
operator, called the _ridgelet trasform_ , that maps a given function $f$ to
the network parameter $\gamma$ so that $S[\gamma]=f$. The proposed GCNN covers
typical GCNNs such as the cyclic convolution on multi-channel images, networks
on permutation-invariant inputs (Deep Sets), and $\mathrm{E}(n)$-equivariant
networks. The closed-form expression of the ridgelet transform can describe
how the network parameters are organized to represent a function. While it has
been known only for fully-connected networks, this study is the first to
obtain the _ridgelet transform for GCNNs_. By discretizing the closed-form
expression, we can systematically generate a constructive proof of the _$cc$
-universality of finite GCNNs_. In other words, our universality proofs are
more unified and constructive than previous proofs.

##  1 Introduction

In the research field of geometric deep learning [1], _group convolutional
neural networks (GCNNs)_ have been developed to capture the inductive bias
behind a variety of datasets such as sets and point clouds [2, 3], graphs [4,
5], manifolds, groups, and homogeneous spaces [6, 7, 8, 4]. Despite the rapid
growth of diversity, the _approximation property_ of CNNs is less investigated
than that of fully-connected neural networks (FNNs). To this date, several
authors have shown the universality of (G)CNNs. That is, they can approximate
some class of continuous maps with any precision [9, 10, 11, 12, 13, 14, 15].
These studies are still limited because the proofs are shown (1) in a case-by-
case manner by manually assigning the parameters for a network to approximate
a given function $f$, which means that once the network architecture is
modified, then we need to reassign the parameters from scratch, and (2) in an
indirect manner by converting/modifying the (G)CNNs into other universal
approximators such as invariant polynomials and FNNs, which means that we know
only indirectly about (G)CNNs.

The approximation property of _FNNs_ has been investigated in the 1990s, with
gradually increasing the resolution of proofs from abstract to concrete,
starting from purely _existential_ proofs based on the Hahn-Banach theorem
[16] and the Stone-Weierstrass theorem [17], _indirect_ proofs based on the
Fourier transform [18, 19], the Radon transform [20, 21], $B$-splines [22,
23], to more _constructive_ proofs based on the integral representation [24],
ridge functions [25], and the _ridgelet transform_ [26, 27, 28]. For deep-
ReLU-FNNs, further approximation properties have been investigated [29, 30,
31] in the 2010s. In this context, (G)CNN studies are at the stage of case-by-
case and indirect proofs. (See § 6.1 for more details).

In this study, we show the universality of depth-2 GCNNs by devising a general
notion of group convolution and developing the _ridgelet transform for GCNNs_
—an analysis operator that maps a given function $f$ to the weight parameter
$\gamma$ in a single hidden layer of a neural network. Consequently, our
universality proof is more _unified and constructive_ because our GCNN covers
a wide range of typical GCNNs, and the ridgelet transform can describe how to
assign the network parameters.

In the following, we describe the formulation of GCNNs to overview our main
contributions.

#### A Typical Convolution Layer for Images.

Given an $m_{1}\times m_{2}$-dimensional $n_{in}$-channel input image
${\bm{x}}\in\mathbb{R}^{m_{1}\times m_{2}\times n_{in}}$, a typical
_convolution layer_ with $w_{1}\times w_{2}$-dimensional $n_{in}\times
n_{out}$-channel filter ${\bm{a}}\in\mathbb{R}^{w_{1}\times w_{2}\times
n_{in}\times n_{out}}$ and $n_{out}$-channel bias
${\bm{b}}\in\mathbb{R}^{n_{out}}$ followed by an elementwise activation
function $\sigma:\mathbb{R}\to\mathbb{R}$ and the aggregation with output
coefficients ${\bm{c}}\in\mathbb{R}^{n_{out}}$ is given by

$\displaystyle
S[{\bm{a}},{\bm{b}},{\bm{c}}]({\bm{x}})(i,j)=\sum_{\ell=1}^{n_{out}}c^{\ell}\sigma\left(\sum_{k=1}^{n_{in}}\sum_{p=1}^{w_{1}}\sum_{q=1}^{w_{2}}a_{pq}^{k\ell}x_{i+p,j+q}^{k}-b^{\ell}\right)$
(1)

for each pixel at $(i,j)\in[m_{1}-w_{1}+1]\times[m_{2}-w_{2}+1]$.

For technical reasons, we assume that the output channels (indexed by
$\ell\in[n_{out}]$) are aggregated soon after the activation function, which
may be slightly different from an ordinary formulation of CNNs, but we can
understand this as a part of the subsequent layer.

In the standard formulation of GCNNs, a multi-channel image is understood as a
vector-valued function on a group $G$ or a homogeneous space $G/H$, such as a
product group $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$ of cyclic groups
$\mathbb{Z}_{m_{i}}:=\mathbb{Z}/m_{i}\mathbb{Z}\ (i=1,2)$. (More
geometrically, Cohen and Welling [32] phrased it as ‘a section of a fiber
bundle’). The convolution in the pixel directions $(i,j)$ is reformulated as a
group convolution with respect to the product group, and the inner product in
the channel direction $k$ is understood as the convolution with respect to the
trivial action of $G$ on a ‘fiber’ $\mathbb{R}^{n_{in}}$.

#### The Integral Representation $S[\gamma]$ of Group Convolution Layer.

Let $G$ be an _arbitrary_ group, $\sigma:\mathbb{R}\to\mathbb{R}$ be an
_arbitrary_ nonlinear function, $\mathcal{X}$ be an _arbitrary_ Hilbert space
of feature vector $x$ and filter $a$, and
$\gamma:\mathcal{X}\times\mathbb{R}\to\mathbb{C}$ be an _arbitrary_ function,
called the _parameter distribution_. We formulate a group convolution layer in
an integral form, called the _integral representation_ , as

$\displaystyle
S[\gamma](x)(g):=\int_{\mathcal{X}\times\mathbb{R}}\gamma(a,b)\sigma\big{(}(a*x)(g)-b\big{)}\mathrm{d}a\mathrm{d}b,\quad
x\in\mathcal{X},\ g\in G.$ (2)

This is an infinite-dimensional reparametrization of a depth-2 GCNN; namely,
each function $x\mapsto\sigma((a*x)(g)-b)$ represents a single convolutional
neuron, or a feature map of input $x$ parametrized by $(a,b)$, the integration
over $(a,b)$ means that all the neurons are assigned, and a single function
$\gamma$—the _parameter distribution_ —parameterizes the assignment of each
parameters $(a,b)$. Hence, $S[\gamma]$ can be understood as a _continuous
neural network_. We note that, however, if we put $\gamma$ as a finite sum of
Dirac’s measures such as
$\gamma_{n}:=\sum_{\ell=1}^{n}c^{\ell}\delta_{(a^{\ell},b^{\ell})}$, then the
integral representation can also represent a finite model

$\displaystyle
S[\gamma_{n}](x)(g)=\sum_{\ell=1}^{n}c^{\ell}\sigma((a^{\ell}*x)(g)-b^{\ell}),\quad
x\in\mathcal{X},\ g\in G.$ (3)

In summary, $S[\gamma]$ is a mathematical model of shallow neural networks
with _any_ width ranging from finite to continuous. In particular, the
sparsity/low-rankness of parameters are reflected as the
localization/concentration of parameter distribution $\gamma$.

An advantage to use the integral representation is the _linearization trick_.
Whereas a finite network $S[\gamma_{n}]$ is _nonlinear_ in the original
parameters $(a,b)$, the integral representation $S[\gamma]$ is _linear_ in the
parameter distribution $\gamma$. It is first emerged in the 1990s to
investigate the expressive power of infinitely-wide shallow FNNs [18, 19, 20,
21, 24, 26, 27, 28]; and it is as well common in today’s deep learning theory,
for example, to investigate the learning dynamics of SGD such as neural
tangent kernel (NTK) [33, 34, 35], lazy learning [36], lottery tickets [37],
mean field theory [38, 39, 40, 41, 42], and Langevin dynamics [43].

#### The Ridgelet Transform $R[f;\rho](a,b)$

is a right inverse (or pseudo-inverse) operator of the integral representation
operator $S$. As an outcome of this study, we have obtained its closed-form
expression:

$\displaystyle R[f;\rho](a,b):=\int_{\mathcal{X}}f(x)(e)\overline{\rho(\langle
a,x\rangle_{\mathcal{X}}-b)}\mathrm{d}a\mathrm{d}b,\quad(a,b)\in\mathcal{X}\times\mathbb{R},$
(4)

where $f:\mathcal{X}\to\mathbb{C}^{G}$ is a target vector-valued nonlinear
function to be approximated, called a _feature map_ , $e\in G$ is the identity
element, and $\rho:\mathbb{R}\to\mathbb{C}$ is an auxiliary function, called
the _ridgelet function_. Provided that $f$ is _group equivariant_ , then under
mild regularity assumptions, it satisfies the _reconstruction formula_

$\displaystyle S[R[f;\rho]]=(\\!(\sigma,\rho)\\!)f,$ (5)

where $(\\!(\cdot,\cdot)\\!)$ denote a scalar product of $\sigma$ and $\rho$.
Therefore, as long as the product $(\\!(\sigma,\rho)\\!)$ is neither $0$ nor
$\infty$, we can normalize $\rho$ to satisfy $(\\!(\sigma,\rho)\\!)=1$ so that
$S[R[f;\rho]]=f$.

In other words, $R$ and $S$ are _analysis and synthesis operators_ , and thus
play the same roles as the Fourier ($F$) and inverse Fourier ($F^{-1}$)
transforms, respectively. Particularly, the reconstruction formula
$S[R[f;\rho]]=(\\!(\sigma,\rho)\\!)f$ corresponds to the Fourier inversion
formula $F^{-1}[F[f]]=f$.

An advantage of the ridgelet transform is the _closed-form expression_.
Despite the common belief that neural network parameters are a blackbox, the
closed-form expression can clearly describe how the network parameters are
organized. Previous studies on the CNN universality have also provided several
construction algorithms of parameters, but these are only _particular_
solutions for a CNN to represent a target function $f$, and not necessary
related to, for example, deep learning solutions. For _FNNs_ , on the other
hand, Sonoda et al. [44] have shown that any parameter distribution $\gamma$
satisfying $S[\gamma]=f$ can always be represented as (not always single but)
a linear combination of ridgelet transforms, and they [45] have shown that
finite networks trained by regularized empirical risk minimization (RERM)
converges to a certain unique ridgelet transform. (We note that NTK and the
Gibbs distribution can also describe the parameter distribution, but NTK is
limited to the kernel regime, and the Gibbs distribution is given only
implicitly.) As an application, Savarese et al. [46] and their followers [47,
48, 49] have established the _representer theorems_ for ReLU-FNNs by using the
ridgelet transform. Although the parallel results for CNNs have not yet been
published, we anticipate that the ridgelet transform could facilitate our
understanding of deep learning solutions.

#### Challenges and Contributions.

The closed-form expression of the ridgelet transform has been known only for
FNNs, which was discovered in the 1990s independently by Murata [26], Candès
[27] and Rubin [28]. (We refer to [50, 51, 52] for ridgelet analysis in the
2000s, and [53, 54, 55] for more recent results.) One of the difficulties to
obtain the ridgelet transform for CNNs is that there is no unique way to
formulate an “integral representation of CNNs”. We note that some authors
claim the “equivalence of CNNs and FNNs” (see e.g. [13]), but it is somewhat
misleading because such an equivalence holds only when both CNNs and FNNs are
very carefully designed. While FNNs are defined on the Euclidean space
$\mathbb{R}^{m}$, GCNNs are defined on a more abstract space $\mathcal{X}$.
For example, since the convolution on the Euclidean space can be written using
Töplitz matrices, one could consider a formulation such as
$\int_{\mathbb{R}^{k\times
m}\times\mathbb{R}^{k}}\gamma(A,b)\sigma(Ax-b)\mathrm{d}A\mathrm{d}b$ where
the parameter $A$ is an $k\times m$-matrix. However, this only leads to
another ridgelet transform that covers less symmetries $G$. In fact, it is a
version of the so-called $k$-plane ridgelet transform developed in the 2000s
[50].

To circumvent this difficulty, we formulate GCNNs as general as possible by
dealing with the feature space $\mathcal{X}$, group $G$, and representation
$T$ in a coordinate-free manner. Eventually, we have shown the reconstruction
formula for a wide range of GCNNs (as displayed in § 5), with a relatively
_simple_ proof. This study is the first to obtain the ridgelet transform for a
general class of GCNNs. As an application, we show the $cc$-universality of
GCNNs for a general class of group equivalent continuous vector-valued
functions in a unified and constructive manner.

##  2 Notation and Basic Terminologies

#### Notation.

For any integer $n>0$, $[n]$ denotes the set $\\{1,\ldots,n\\}$. For any sets
$G$ and $\mathbb{K}$, $\mathbb{K}^{G}$ denotes the collection
$\\{G\to\mathbb{K}\\}$ of all mappings from $G$ to $\mathbb{K}$. For any
topological space $X$, $C(X)$ and $C_{c}(X)$ denote the collections of all
continuous functions on $X$, and continuous functions on $X$ with compact
support, respectively. We note that when $X$ is compact, then $C(X)=C_{c}(X)$.
For any measure space $X$ and number $p\in[1,\infty]$, $L^{p}(X)$ denotes the
space of $p$-integrable functions on $X$.

###  2.1 Fourier Analysis on $\mathbb{R}^{d}$

We refer to [56, 57, 53] for more details on Fourier transform and tempered
distributions ($\mathcal{S}^{\prime}$).

#### Schwartz Distributions.

For any integer $d>0$, $\mathcal{S}(\mathbb{R}^{d})$ and
$\mathcal{S}^{\prime}(\mathbb{R}^{d})$ denote the classes of Schwartz test
functions (or rapidly decreasing functions) and tempered distributions on
$\mathbb{R}^{d}$, respectively. Namely, $\mathcal{S}^{\prime}$ is the
topological dual of $\mathcal{S}$. In this study,
$\mathcal{S}^{\prime}(\mathbb{R})$ and $\mathcal{S}(\mathbb{R})$ are assigned
as classes of activation and ridgelet functions, respectively. We note that
$\mathcal{S}^{\prime}(\mathbb{R})$ includes truncated power functions
$\sigma(b)=b_{+}^{k}=\max\\{b,0\\}^{k}$ such as step function for $k=0$ and
ReLU for $k=1$.

#### Fourier Transform.

The Fourier transform on the Euclidean space $\mathbb{R}^{d}$ and its
inversion formula has been defined on (at least) three different function
classes: $L^{1}(\mathbb{R}^{d}),L^{2}(\mathbb{R}^{d})$ and
$\mathcal{S}^{\prime}(\mathbb{R}^{d})$. When $f\in L^{1}(\mathbb{R}^{d})$ and
$\widehat{f}\in L^{1}(\mathbb{R}^{d})$, the inversion formula holds “at every
continuous point ${\bm{x}}$ of $f$”, which is a pointwise equation. When $f\in
L^{2}(\mathbb{R}^{d})$, the inversion formula holds “in $L^{2}$”, which is not
a pointwise equation because the equation “$f=g$ in $L^{2}$” is defined as
“$f({\bm{x}})=g({\bm{x}})$ a.e.”. Similarly, when
$f\in\mathcal{S}^{\prime}(\mathbb{R}^{m})$, the inversion formula holds “in
$\mathcal{S}^{\prime}$”. We use the third definition for computing the Fourier
transform of activation functions $\sigma\in\mathcal{S}^{\prime}(\mathbb{R})$
such as ReLU and $\tanh$.

###  2.2 Group Representation

Let $G$ be a group, let $\mathcal{X}$ be a vector space over a field
$\mathbb{K}$, and let $GL(\mathcal{X})$ be the general linear group on
$\mathcal{X}$. A _group representation_ $T$ of the group $G$ on the vector
space $\mathcal{X}$ is a group homomorphism from $G$ to $GL(\mathcal{X})$,
that is, a map $T:G\to GL(\mathcal{X});g\mapsto T_{g}$ satisfying
$T_{gh}=T_{g}T_{h}$ for all $g,h\in G$. When $G$ is a topological group, we
further assume that the action $G\times\mathcal{X}\to\mathcal{X};(g,x)\mapsto
T_{g}[x]$ be continuous. Here, $\mathcal{X}$ is called the _representation
space_. We refer to [58] for more details on group representation.

#### Regular Representation.

Let $\mathcal{X}$ be the vector space of all functions on $G$, i.e.,
$\mathcal{X}=\mathbb{K}^{G}$. The _(left) regular representation_ $L$ is a
group representation defined on $\mathcal{X}$ as

$\displaystyle L_{g}[x](h):=x(g^{-1}h),\quad g,h\in G,\
x\in\mathcal{X}=\mathbb{K}^{G}.$ (6)

In particular, when $G$ is a locally compact Haussdorf (LCH) group, then it
has a (left) invariant measure $\mu$, and we can define the collection
$L^{2}(G)$ of all square integrable functions on $G$ with respect to the
canonical inner product $\langle
x,y\rangle_{L^{2}(G)}:=\int_{G}x(g)\overline{y(g)}\mathrm{d}\mu(g)$ for any
measurable functions $x,y:G\to\mathbb{C}$. It is known that the regular
representation on $\mathcal{X}=L^{2}(G)$ is a unitary representation.

#### Dual Representation.

For any group representation $T:G\to GL(\mathcal{X})$, the _dual
representation_ $T^{*}:G\to GL(\mathcal{X}^{\prime})$ is a group
representation defined on the dual vector space $\mathcal{X}^{\prime}$ as the
transpose of $T_{g^{-1}}$, that is, $T_{g}^{*}=T_{g^{-1}}^{\top}$. When
$\mathcal{X}$ is a Hilbert space with inner product
$\langle\cdot,\cdot\rangle_{\mathcal{X}}$, then it satisfies the following
relation:

$\displaystyle\langle T_{g}[x],y\rangle_{\mathcal{X}}=\langle
x,T_{g^{-1}}^{*}[y]\rangle_{\mathcal{X}},\quad g\in G,\ x,y\in\mathcal{X}.$
(7)

#### Matrix Element.

For any group representation $T:G\to GL(\mathcal{X})$, the _matrix element_
(or the _matrix coefficient_) of $T$ is a bilinear functional $f_{a,x}$ on $G$
defined by

$\displaystyle f_{a,x}(g):=a[T_{g}[x]],\quad g\in G,\ x\in\mathcal{X},\
a\in\mathcal{X}^{\prime}$ (8)

where $x$ is a vector in $\mathcal{X}$ and $a\in\mathcal{X}^{\prime}$ is a
continuous linear functional on $\mathcal{X}$. When $\mathcal{X}$ is a Hilbert
space, then (identifying $\mathcal{X}^{\prime}$ with $\mathcal{X}$) it can be
written as

$\displaystyle f_{a,x}(g)=\langle T_{g}[x],a\rangle_{\mathcal{X}},\quad g\in
G,\ a,x\in\mathcal{X}.$ (9)

In the next section, we use this quantity as the generalized form of the
_group convolution_.

###  2.3 Universality

The notion of _universality_ in machine learning can be rephrased as the
_density_ in mathematics, and thus it has several definitions. (See, e.g.,
[59, 60]). In this study, we show the so-called _$cc$ -univesality_, one of
the standard universalities in the machine learning theory.

####  $cc$-Universality.

Let $X$ be a topological space, and let $\mathtt{NN}$ be a collection of
functions (e.g., neural networks) on $X$. The $cc$-univesality of
$\mathtt{NN}$ is defined as the density of $\mathtt{NN}$ in $C(X)$ endowed
with the topology of _compact convergence_ , that is, for any compact subset
$K\subset X$, continuous function $f\in C(K)$, and all $\varepsilon>0$, there
exists a function $g\in\mathtt{NN}$ such that

$\displaystyle\big{\|}f-g|_{K}\big{\|}_{C(K)}:=\sup_{x\in
K}|f(x)-g(x)|<\varepsilon,$ (10)

where $g|_{K}$ denotes the restriction of $g$ to $K$.

##  3 Functions on Abstract Hilbert Space $\mathcal{X}$

We introduce an extended group convolution on $\mathcal{X}$, a uniform norm
and the group-equivariance for functions on $\mathcal{X}$, an induced measure
and an induced Fourier transform on $\mathcal{X}$, and a projection to
$\mathcal{X}_{m}$.

###  3.1 $(G,T)$-Convolution
$*_{T}:\mathcal{X}\times\mathcal{X}\to\mathbb{C}^{G}$

######  Definition 1.

Let $G$ be a group, let $\mathcal{X}$ be a Hilbert space with inner product
$\langle\cdot,\cdot\rangle_{\mathcal{X}}$ over a field $\mathbb{K}$, and let
$T:G\to GL(\mathcal{X})$ be a representation of $G$ on $\mathcal{X}$. For any
$a,x\in\mathcal{X}$ and $g\in G$, we define the _$(G,T)$ -convolution_ as

$\displaystyle(a*_{T}x)(g):=\langle
x,T_{g}^{*}[a]\rangle_{\mathcal{X}}=\langle
T_{g^{-1}}[x],a\rangle_{\mathcal{X}}.$ (11)

We remark (1) that this is simply a paraphrase of the _matrix element of a
group representation_ (see the previous section), and (2) that this is _not
necessarily_ a binary operation because $\mathcal{X}\neq\mathbb{C}^{G}$ in
general. Nevertheless, we call it a _convolution_ simply because it covers a
wide range of ‘group convolutions’ in today’s GCNN literature.

######  Example 1.

An orthodox group convolution is reproduced when $T$ is the regular
representation (of a LCH group $G$) on $\mathcal{X}=L^{2}(G)$, i.e.,
$T_{g}^{*}[a](h)=a(g^{-1}h)$. In fact,

$\displaystyle\langle
x,T_{g}^{*}[a]\rangle_{L^{2}(G)}=\int_{G}x(h)\overline{a(g^{-1}h)}\mathrm{d}\mu(h)=\int_{G}x(h)\widetilde{a}(h^{-1}g)\mathrm{d}\mu(h)=(x*_{G}\widetilde{a})(g),$
(12)

where $\widetilde{a}(g):=\overline{a(g^{-1})}$ is an involution.

######  Example 2.

The cyclic convolution for an $n$-channel image
${\bm{x}}=(x_{ij}^{k})\in\mathbb{R}^{m_{1}\times m_{2}\times n}$ is understood
as the case when $G=\mathbb{Z}_{m_{1}}\times\mathbb{Z}_{m_{2}}$,
$\mathcal{X}=\mathbb{R}^{m_{1}\times m_{2}\times n}$, and
$T_{(p,q)}^{*}[{\bm{a}}](i,j,k)=a_{i-p,j-q}^{k}$, then

$\displaystyle\langle{\bm{x}},T_{(p,q)}^{*}[{\bm{a}}]\rangle_{\mathbb{R}^{m_{1}\times
m_{2}\times n}}=\sum_{i,j,k}x_{ij}^{k}a^{k}_{i-p,j-q}.$ (13)

While the post-activation feature $\sigma((a*x)(g)-b)$ is a function on $G$,
the input feature $x$ can be an arbitrary abstract vector, which is more
general than typical GCNN formulations where feature $x$ is supposed to be a
vector-valued function on $G$ or $G/H$. This is an advantage for a more
geometric understanding of CNNs, since the theory becomes free from the
specification of $x$.

###  3.2 Continuous $(G,T)$-Equivariant Vector-Valued Function
$f:\mathcal{X}\to C(G)$

######  Definition 2.

We say a vector-valued function $f:\mathcal{X}\to\mathbb{C}^{G}$ is _$(G,T)$
-equivariant_ when

$\displaystyle f(T_{g}[x])(h)=L_{g}[f(x)](h)=f(x)(g^{-1}h),\quad
x\in\mathcal{X},\ g,h\in G.$ (14)

Here, we restrict the definition for a special case of the regular
representation $L$. This is simply due to the fact that our GCNN satisfies
this case.

######  Definition 3.

Let $G$ be a topological group. For any vector-valued function
$f:\mathcal{X}\to\mathbb{C}^{G}$, put

$\displaystyle\|f\|_{C(\mathcal{X};C(G))}:=\|f\|_{C(\mathcal{X})\to
C(G)}:=\sup_{x\in\mathcal{X}}\big{|}\sup_{g\in G}|f(x)(g)|\big{|}.$ (15)

By $C_{equi}(\mathcal{X};C(G))$, we denote the normed vector space of all
_continuous $(G,T)$-equivariant $C(G)$-valued_ functions on $\mathcal{X}$
equipped with the uniform norm $\|\cdot\|_{C(\mathcal{X};C(G))}$.

We note that the topology of uniform norm $\|\cdot\|_{C(\mathcal{X};C(G))}$ is
stronger than the topology of compact convergence, which is employed in the
$cc$-universality argument. In fact, $C_{equi}(\mathcal{X};C(G))$ need not be
complete (or Banach) to show the $cc$-universality.

###  3.3 Induced Lebesgue Measure $\lambda$ and Induced Fourier Transform
$\widehat{\cdot}\,$ on Subspace $\mathcal{X}_{m}$

Let $\mathcal{X}_{m}$ denote an $m$-dimensional subspace of $\mathcal{X}$, and
let $\\{\mathsf{e}_{i}\\}_{i\in[m]}$ be an orthonormal basis of
$\mathcal{X}_{m}$.

#### Induced Lebesgue Measure on $\mathcal{X}_{m}$.

We induce the Lebesgue measure $\lambda$ on $\mathcal{X}_{m}$ by pushing
forward the Lebesgue measure $\mathrm{d}{\bm{x}}$ on $\mathbb{R}^{m}$ via an
isometric linear embedding $\phi:\mathbb{R}^{m}\to\mathcal{X}_{m}$. For
example, take a linear embedding
$\phi({\bm{x}}):=\sum_{i\in[m]}x_{i}\mathsf{e}_{i}$. Then, it preserves the
length, and we can induce the Lebesgue measure $\lambda$ on $\mathcal{X}_{m}$
as the push forward measure $\lambda=\phi_{\sharp}\mathrm{d}{\bm{x}}$ so that
the volume of a hypercube $Q=\\{\sum_{i\in[m]}c_{i}\mathsf{e}_{i}\mid
c_{i}\in[a_{i},b_{i}]\\}$ in $\mathcal{X}_{m}$ is calculated as
$\lambda(Q)=\prod_{i\in[m]}|b_{i}-a_{i}|$, and the integration of a measurable
function $f:\mathcal{X}_{m}\to\mathbb{C}$ over a measurable set
$E\subset\mathcal{X}_{m}$ is calculated as

$\displaystyle\int_{E}f(x)\mathrm{d}\lambda(x)=\int_{\mathbb{R}^{m}}1_{E}\left(\sum_{i=1}^{m}x_{i}\mathsf{e}_{i}\right)f\left(\sum_{i=1}^{m}x_{i}\mathsf{e}_{i}\right)\prod_{i=1}^{m}\mathrm{d}x_{i}=\int_{\phi^{-1}(E)}f\circ\phi({\bm{x}})\mathrm{d}{\bm{x}}.$
(16)

As far as there is no risk of confusion, we denote $\mathrm{d}x$ instead of
$\mathrm{d}\lambda(x)$.

#### Induced Fourier Transform on $\mathcal{X}_{m}$.

Using $\lambda$, we induce the Fourier transform on $\mathbb{R}^{m}$ as below:
For any function $f:\mathcal{X}_{m}\to\mathbb{C}$,

$\displaystyle\widehat{f}(y):=\int_{\mathcal{X}_{m}}f(x)e^{-i\langle
x,y\rangle_{\mathcal{X}_{m}}}\mathrm{d}\lambda(x),\quad
f(x)\overset{\star}{=}\frac{1}{(2\pi)^{m}}\int_{\mathcal{X}_{m}}\widehat{f}(y)e^{i\langle
x,y\rangle_{\mathcal{X}_{m}}}\mathrm{d}\lambda(y).$ (17)

Here, the equality $\overset{\star}{=}$ holds in at least three different
senses (see the comments in § 2.1).

We remark (1) that once the subspace $\mathcal{X}_{m}$ is fixed, the induced
Fourier transform is unique up to the orthogonal transformation of the basis
$\\{\mathsf{e}_{i}\\}_{i\in[m]}$, and (2) that the induced Fourier transform
“on $\mathcal{X}$” should not be confused with the Fourier transform “on group
$G$”. Especially, this _cannot_ map a convolution $x*_{T}a$, an element in
$\mathbb{C}^{G}$, to a point product such as “$\widehat{x}\cdot\widehat{a}$”.

###  3.4 Projection $P:\mathcal{X}\to\mathcal{X}_{m}$ and Extension Operator
$P^{*}\\!$

In order to induce the Lebesgue measure $\lambda$, we assume that the
dimension of $\mathcal{X}_{m}$ to be finite. As a side effect of this
assumption, the image $T_{G}[\mathcal{X}_{m}]:=\\{T_{g}[x]\mid g\in
G,x\in\mathcal{X}_{m}\\}$ can extend toward the outside of $\mathcal{X}_{m}$;
that is, $\mathcal{X}_{m}$ is not necessarily $G$-invariant
($T_{G}[\mathcal{X}_{m}]\subset\mathcal{X}_{m}$). To avoid an “undefined
error” such as to input $x$ outside of $\mathcal{X}_{m}$ for a function $f$
defined only on $\mathcal{X}_{m}$, we introduce projection $P$ and extension
$P^{*}\\!$ as below. When $\dim\mathcal{X}<\infty$, we can omit $P$ by putting
$\mathcal{X}_{m}=\mathcal{X}$ (so $P=\operatorname{Id}$), because by the
definition of the group representation, always
$T_{G}[\mathcal{X}]=\mathcal{X}$.

Let $\mathcal{X}_{m}^{\perp}$ denote the orthogonal complement of
$\mathcal{X}_{m}$ in $\mathcal{X}$. Let $P:\mathcal{X}\to\mathcal{X}_{m}$
denote the orthogonal projection onto $\mathcal{X}_{m}$. For any function
$f:\mathcal{X}_{m}\to\mathbb{C}^{G}$, put

$\displaystyle P^{*}\\!f(z)(g):=f(P(z))(g),\quad z\in\mathcal{X},g\in G.$ (18)

This extends $f$ (on a subspace $\mathcal{X}_{m}$) to the entire space
$\mathcal{X}$ as a constant function on $\mathcal{X}_{m}^{\perp}$; that is,
$P^{*}\\!f(x\oplus y)=f(x\oplus 0)$ for each $x\oplus
y\in\mathcal{X}_{m}\oplus\mathcal{X}_{m}^{\perp}$.

##  4 Main Results

We introduce the $(G,T)$-convolutional neural networks and the corresponding
ridgelet transform, and present the reconstruction formula for continuous
GCNNs and the $cc$-universality for finite GCNNs.

Throughout this section, we fix a representation $T:G\to GL(\mathcal{X})$ of a
group $G$ on a (potentially infinite-dimensional) Hilbert space $\mathcal{X}$
over a field $\mathbb{K}$ endowed with an inner product
$\langle\cdot,\cdot\rangle_{\mathcal{X}}$, and fix an $m$-dimensional closed
subspace $\mathcal{X}_{m}$ of $\mathcal{X}$ equipped with an induced Lebesgue
measure $\lambda$. Let $k:=\dim_{\mathbb{R}}\mathbb{K}$ denote the real
dimension of $\mathbb{K}$, that is, $k=1$ for $\mathbb{K}=\mathbb{R}$ and
$k=2$ for $\mathbb{K}=\mathbb{C}$. Let $e$ denote the identity element of $G$.

###  4.1 Integral Representation of $(G,T)$-Convolutional Neural Network

######  Definition 4.

For any functions $\gamma:\mathcal{X}_{m}\times\mathbb{K}\to\mathbb{C}$ and
$\sigma:\mathbb{K}\to\mathbb{C}$, we define the _integral representation of
$(G,T)$-convolutional neural network_ as a vector-valued function
$\mathcal{X}\to\mathbb{C}^{G}$,

$\displaystyle S[\gamma](x)(g)$
$\displaystyle:=\int_{\mathcal{X}_{m}\times\mathbb{K}}\gamma(a,b)\sigma((a*_{T}x)(g)-b)\mathrm{d}\lambda(a)\mathrm{d}b,\quad
x\in\mathcal{X},\ g\in G.$ (19)

Here, we call $\gamma$ a parameter distribution, and $\sigma$ an activation
function. If there is no risk of confusion, we abbreviate
$\mathrm{d}\lambda(a)$ as $\mathrm{d}a$.

It is easy to see that a $(G,T)$-CNN is $(G,T)$-equivariant. In fact, for
every $g,h\in G$,

$\displaystyle S[\gamma](T_{g}[x])(h)$
$\displaystyle=\int_{\mathcal{X}_{m}\times\mathbb{K}}\gamma(a,b)\sigma(\langle
T_{(g^{-1}h)^{-1}}[x],a\rangle_{\mathcal{X}}-b)\mathrm{d}a\mathrm{d}b=S[\gamma](x)(g^{-1}h).$
(20)

In addition, at the identity element $g=e$, it is reduced to a FNN:

$\displaystyle
S[\gamma](x)(e)=\int_{\mathcal{X}_{m}\times\mathbb{K}}\gamma(a,b)\sigma(\langle
x,a\rangle_{\mathcal{X}}-b)\mathrm{d}a\mathrm{d}b,\quad x\in\mathcal{X}$ (21)

and it satisfies a _projection property_ :

$\displaystyle S[\gamma](P[x])(e)=S[\gamma](x)(e),\quad x\in\mathcal{X}.$ (22)

###  4.2 Ridgelet Transform and Scalar Product of Activation Function

######  Definition 5.

For any functions $f:\mathcal{X}_{m}\to\mathbb{C}^{G}$ and
$\rho:\mathbb{K}\to\mathbb{C}$, we define the _ridgelet transform_ as

$\displaystyle R[f;\rho](a,b)$
$\displaystyle:=\int_{\mathcal{X}_{m}}f(x)(e)\overline{\rho(\langle
x,a\rangle_{\mathcal{X}}-b)}\mathrm{d}x,\quad(a,b)\in\mathcal{X}_{m}\times\mathbb{K}.$
(23)

Here $e$ denotes the identity element of $G$.

######  Definition 6.

For any tempered distribution $\sigma\in\mathcal{S}^{\prime}(\mathbb{K})$ and
function $\rho\in\mathcal{S}(\mathbb{K})$, put a _scalar product_ as

$\displaystyle(\\!(\sigma,\rho)\\!):=(2\pi)^{m-k}\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\overline{\rho^{\sharp}(\omega)}|\omega|^{-m}\mathrm{d}\omega.$
(24)

Here, $\cdot^{\sharp}$ denotes the Fourier transform on $\mathbb{K}$, which is
identified with the Fourier transform on $\mathbb{R}^{k}$ with
$k=\dim_{\mathbb{R}}\mathbb{K}$. We note that $\sigma^{\sharp}$ is defined in
the sense of tempered distributions.

The derivations of the ridgelet transform and the scalar product are clarified
in the proof of the reconstruction formula. Some readers may notice that the
ridgelet transform for GCNN is formally the same as the one for FNNs, and may
wonder why inner product $\langle x,a\rangle_{\mathcal{X}}$ instead of group
convolution $(a*_{T}x)(g)$. Indeed, this is a consequence of two facts (1)
that a group convolution at the identity $e$ is reduced to an inner product:
$(a*_{T}x)(e)=\langle x,a\rangle_{\mathcal{X}}$, and (2) that when $f$ is
$(G,T)$-equivariant, then the value $f(x)(g)$ at each $g\in G$ is determined
by translating the value $f(x)(e)$ at the identity.

###  4.3 Reconstruction Formula, or the Universality of Continuous GCNNs

We state the first half of our main results. For
$f:\mathcal{X}_{m}\to\mathbb{C}^{G}$, we write $f_{e}(x):=f(x)(e)$ for short.

######  Theorem 1 (Main Theorem 1/2).

Given a function $f:\mathcal{X}_{m}\to\mathbb{C}^{G}$, assume (A1) that
$P^{*}\\!f:\mathcal{X}\to\mathbb{C}^{G}$ is $(G,T)$-equivariant, i.e.,

$\displaystyle P^{*}\\!f(T_{g}[z])(h)=f(z)(g^{-1}h),\quad\mbox{for every
}z\in\mathcal{X}\mbox{ and }g,h\in G;$ (25)

and (A2) that $f$ satisfies at least one of the following conditions: (A2a)
both $f_{e}$ and $\widehat{f_{e}}$ are absolute-integrable, i.e.,
$f_{e},\widehat{f_{e}}\in L^{1}(\mathcal{X}_{m})$, (A2b) $f_{e}$ is square-
integrable, i.e., $f_{e}\in L^{2}(\mathcal{X}_{m})$, or (A2c) $f_{e}$ is a
tempered distribution, i.e., $f_{e}\in\mathcal{S}^{\prime}(\mathcal{X}_{m})$.
Then, the following reconstruction formula holds:

$\displaystyle
S[R[f;\rho]](x)(g)=\int_{\mathcal{X}_{m}\times\mathbb{K}}R[f;\rho](a,b)\sigma((a*_{T}x)(g)-b)\mathrm{d}a\mathrm{d}b\overset{\star}{=}(\\!(\sigma,\rho)\\!)f(x)(g),$
(26)

where the equality $\overset{\star}{=}$ holds at every continuous point
$x_{c}$ of $f$ for (A2a), in $L^{2}$ for (A2b), and in $\mathcal{S}^{\prime}$
for (A2c), respectively.

The proof is given in Appendix A.1.

###  4.4 $cc$-Universality of Finite GCNNs

Finally, we state the second half of our main results. Let $\mathtt{NN}$ be
the collection of finite GCNNs, that is,

$\displaystyle\mathtt{NN}:=\bigcup_{n\in\mathbb{N}}\left\\{f_{n}(x)(g)=\sum_{i=1}^{n}c_{i}\sigma((a_{i}*_{T}x)(g)-b_{i})\Bigg{|}(a_{i},b_{i},c_{i})\in\mathcal{X}_{m}\times\mathbb{K}\times\mathbb{C},i\in[n]\right\\}.$
(27)

Since the reconstruction formula $S[\gamma_{f}]=f$ with $\gamma_{f}=R[f;\rho]$
holds for an arbitrary function $f$, we can construct a sequence
$\\{f_{n}\\}_{n\in\mathbb{N}}$ of finite $(G,T)$-CNNs that converges to an
arbitrary target function $f$, namely

$\displaystyle f_{n}\to f\quad\mbox{ as }\quad n\to\infty,$ (28)

by discretizing the continuous network $S[\gamma_{f}]$ and distribution
$\gamma_{f}$ into finite sums

$\displaystyle
f_{n}(x)(g):=S[\gamma_{n}](x)(g)=\sum_{i=1}^{n}c_{i}\sigma((a_{i}*_{T}x)(g)-b_{i})\quad\mbox{with}\quad\gamma_{n}:=\sum_{i=1}^{n}c_{i}\delta_{(a_{i},b_{i})}$
(29)

in a ‘nice’ manner so that $\gamma_{n}\to\gamma_{f}=R[f;\rho]$ as
$n\to\infty$. This is the primitive idea behind the constructive proof of the
following $cc$-universality of finite $(G,T)$-CNNs based on ridgelet analysis.

To state a regularity assumption on the activation function $\sigma$, we
introduce the forward difference operator $\Delta_{\theta}^{n}$ with
difference $\theta>0$, defined as

$\displaystyle\Delta_{\theta}^{1}[\sigma](t):=\sigma(t+\theta)-\sigma(t),\quad\Delta_{\theta}^{n+1}[\sigma](t):=\Delta_{\theta}^{1}\circ\Delta_{\theta}^{n}[\sigma](t).$
(30)

######  Theorem 2 (Main Theorem 2/2).

For an activation function $\sigma\in\mathcal{S}^{\prime}(\mathbb{K})$, assume
(A3) that there exist $n\in\mathbb{N}$ and $\theta>0$ such that
$\Delta_{\theta}^{n}[\sigma]$ is bounded and Lipschitz continuous. Then,
$\mathtt{NN}$ is $cc$-universal; that is, for any continuous
$(G,T)$-equivariant $C(G)$-valued function $f\in
C_{equi}(\mathcal{X}_{m};C(G))$, and for any compact sets
$K\subset\mathcal{X}_{m}$ and $L\subset G$, there exists a sequence
$\\{f_{n}\\}_{n\in\mathbb{N}}\subset\mathtt{NN}$ of finite GCNNs satisfying

$\displaystyle\|f-f_{n}\|_{C(K;C(L))}=\sup_{x\in K}\sup_{g\in
L}|f(x)(g)-f_{n}(x)(g)|\to 0,\quad n\to\infty.$ (31)

The proof is given in Appendix A.2. Here, $f\in
C_{equi}(\mathcal{X}_{m};C(G))$ means that $P^{*}\\!f$ is $(G,T)$-equivariant.

##  5 Examples

We display the ridgelet transforms and reconstruction formulas for a few
typical GCNNs. Besides, we calculated in Examples 5 and 8 the ridgelet
transforms of a differential filter, which is often reported to be acquired as
a feature map in the first layer of deep CNNs for image recognition [61, 62].

###  5.1 Finite Periodic Convolution Layer

######  Example 3 (For 1-dimensional periodic signals).

The periodic convolution corresponds to the case when
$\mathbb{K}=\mathbb{R},G=\mathbb{Z}_{m}\cong[m]=\\{0,1,\ldots,m-1\\}$,
$\mathcal{X}=L^{2}(G)\cong\mathbb{R}^{m}$ equipped with the inner product
$\langle x,y\rangle:=\frac{1}{m}\sum_{i\in[m]}x_{i}y_{i}$, and
$T_{i}[x](j):=x_{j-i}$ thus
$(a*_{T}x)(i)=\frac{1}{m}\sum_{j\in[m]}a_{j}x_{i+j}$. Therefore, the ridgelet
transform and the reconstruction formula are given by

$\displaystyle
R[f;\rho](a,b)=\int_{\mathbb{R}^{m}}f({\bm{x}})(0)\overline{\rho\left({\textstyle\frac{1}{m}\sum_{i\in[m]}}a_{i}x_{i}-b\right)}\mathrm{d}{\bm{x}},$
$\displaystyle
S[R[f;\rho]](x)(i)=\int_{\mathbb{R}^{m}\times\mathbb{R}}R[f;\rho]({\bm{a}},b)\sigma\left({\textstyle\frac{1}{m}\sum_{j\in[m]}}a_{j}x_{i+j}-b\right)\mathrm{d}{\bm{a}}\mathrm{d}b=(\\!(\sigma,\rho)\\!)f(x)(i).$

######  Example 4 (For 2-dimensional multi-channel periodic images).

A $2$-dimensional $n$-channel image is identified with a vector-valued
function $x:\mathbb{Z}_{m}^{2}\to\mathbb{R}^{n}$, thus
$\mathcal{X}\cong\mathbb{R}^{m^{2}\times n}$. Let $x_{ij}^{k}$ denote the
$(i,j)$-th component in the $k$-th channel of $x\in\mathcal{X}$. Let
$G=\mathbb{Z}_{m}^{2}$, and put $T_{(p,q)}[x]_{ij}^{k}:=x_{i-p,j-q}^{k}$.
Therefore, the ridgelet transform and the reconstruction formula are given by

$\displaystyle
R[f;\rho](a,b)=\int_{\mathbb{R}^{m^{2}n}}f(x)_{(0,0)}\overline{\rho\left({\textstyle\frac{1}{m^{2}n}\sum_{k\in[n]}\sum_{i,j\in[m]}}a_{ij}^{k}x_{ij}^{k}-b\right)}\mathrm{d}{\bm{x}}.$
$\displaystyle
S[R[f;\rho]](x)_{ij}=\int_{\mathbb{R}^{m^{2}n}\times\mathbb{R}}R[f;\rho](a,b)\sigma\left({\textstyle\frac{1}{m^{2}n}\sum_{k\in[n]}\sum_{p,q\in[m]}}a_{pq}^{k}x_{p+i,q+j}^{k}-b\right)\mathrm{d}{\bm{a}}\mathrm{d}b=(\\!(\sigma,\rho)\\!)f(x)_{ij}.$

######  Example 5 (Difference operator (with cutoff function)).

A difference operator on $x:[m]\to\mathbb{R}$ is given by
$x=\sum_{i\in[m]}x_{i}\delta_{i}\mapsto
f(x)=\sum_{i\in[m]}(x_{i+1}-x_{i})\delta_{i}$, which is $(G,T)$-equivariant:
$f(T_{k}^{*}[x])(i)=T_{k}^{*}[x]_{i+1}-T_{k}^{*}[x]_{i}=x_{i+1-k}-x_{i-k}=f(x)(i-k)$.
Since $f(x)(0)=x_{1}-x_{0}$,

$\displaystyle
R\left[f|_{K};\rho\right](a,b)=\int_{\mathbb{R}^{m}}(x_{1}-x_{0})1_{K}({\bm{x}})\overline{\rho\left({\textstyle\frac{1}{m}\sum_{i\in[m]}}a_{i}x_{i}-b\right)}\mathrm{d}{\bm{x}}.$

We note since ${\bm{x}}\mapsto x_{1}-x_{0}$ is not integrable in
$\mathbb{R}^{m}$, we restrict $f$ to a compact set $K\subset\mathbb{R}^{m}$,
and impose the indicator function $1_{K}$ as an auxiliary cutoff function.

###  5.2 (Deep Sets) Permutation Equivariant Maps on A Finite Set

######  Example 6.

Let $\mathcal{X}=\mathbb{R}^{m},G\leq\mathrm{S}_{m}$ and
$T_{g}[x]=(x_{g^{-1}(1)},x_{g^{-1}(2)},\ldots,x_{g^{-1}(m)})$. Thus $\langle
a,x\rangle_{\mathcal{X}}=\frac{1}{m}\sum_{i\in[m]}a_{i}x_{i}$, and
$(a*_{T}x)(g)=\frac{1}{m}\sum_{p\in[m]}a_{p}x_{g(p)}$. So,

$\displaystyle
R[f;\rho](a,b)=\int_{\mathbb{R}^{m}}f({\bm{x}})(e)\overline{\rho\left({\textstyle\frac{1}{m}\sum_{i\in[m]}}a_{i}x_{i}-b\right)}\mathrm{d}{\bm{x}},$
$\displaystyle
S[R[f;\rho]](x)(g)=\int_{\mathbb{R}^{m}\times\mathbb{R}}R[f;\rho]({\bm{a}},b)\sigma\left({\textstyle\frac{1}{m}\sum_{p\in[m]}}a_{p}x_{g(p)}-b\right)\mathrm{d}{\bm{a}}\mathrm{d}b=(\\!(\sigma,\rho)\\!)f(x)(g).$

###  5.3 Continuous Periodic Convolution Layer

######  Example 7.

Let
$G=\mathbb{T}:=\mathbb{R}/2\pi\mathbb{Z}\cong\\{e^{i\theta}\mid\theta\in[-\pi,\pi]\\}$
be the 1-dimensional torus group, which is one of the most basic continuous
group. As a consequence of the Fourier series expansion, $L^{2}(\mathbb{T})$
is spanned by $\\{e^{in\theta}\mid n\in\mathbb{N}\\}$. Hence, we can take
$\mathcal{X}$ to be an $m$-dimensional subspace
$\mathcal{X}:=\\{\sum_{|n|<m}x_{n}e^{in\theta}\mid
x_{-n}=x_{n}\in\mathbb{R}\\}$ equipped with an inner product $\langle
x,y\rangle_{\mathcal{X}}:=\int_{\mathbb{T}}x(\theta)\overline{y(\theta)}\mathrm{d}\theta$.
We note that the constraint $x_{n}=x_{-n}$ implies
$\sum_{|n|<m}x_{n}e^{in\theta}=\sum_{|n|<m}x_{n}\cos(n\theta)$ and thus any
signal $x\in\mathcal{X}$ is a bandlimited real-valued continuous signal with
each coefficient $x_{n}$ being the $n$-th frequency spectrum. Put
$T_{\alpha}[x](\theta):=x(\theta-\alpha)$, then
$(a*x)(\alpha)=\int_{\mathbb{T}}a(\theta)x(\alpha-\theta)\mathrm{d}\theta=\sum_{|n|<m}a_{n}x_{n}e^{in\alpha}=\sum_{|n|<m}a_{n}x_{n}\cos(n\alpha)$
(by the convolution theorem and the constraint). Therefore,

$\displaystyle
R[f;\rho](a,b):=\int_{\mathbb{R}^{m}}f({\bm{x}})(0)\overline{\rho\left({\textstyle\sum_{|n|<m}}a_{n}x_{n}-b\right)}\mathrm{d}{\bm{x}},$
$\displaystyle
S[R[f;\rho]](x)(\theta)=\int_{\mathbb{R}^{m}\times\mathbb{R}}R[f;\rho]({\bm{a}},b)\sigma\left({\textstyle\sum_{|n|<m}}a_{n}x_{n}\cos(n\theta)-b\right)\mathrm{d}{\bm{a}}\mathrm{d}b=(\\!(\sigma,\rho)\\!)f(x)(\theta).$

######  Example 8 (Differential operator (with convergence factor)).

A differential operator $\frac{\mathrm{d}}{\mathrm{d}\theta}$ is calculated as
$x=\sum_{|n|<m}x_{n}e^{in\theta}\mapsto f(x)=\sum_{|n|<m}nx_{n}e^{in\theta}$.
Since ${\bm{x}}\mapsto f({\bm{x}})(0)=\sum_{|n|<m}nx_{n}$ is not integrable on
$\mathbb{R}^{m}$, we impose a convergence factor $\phi_{t}$ as follows.
$f_{t}(x)(\theta):=f(x)\phi_{t}(x)=\frac{\mathrm{d}}{\mathrm{d}\theta}x(\theta)\phi_{t}(x)=\sum_{|n|<m}nx_{n}\phi_{t}(x)e^{in\theta}$.
Here, $(\phi_{t})_{t>0}\subset\mathcal{S}(\mathcal{X})$ is a family of
convergence factors that satisfies (1) the first moment
$\int_{\mathcal{X}}|x|_{\mathcal{X}}|\phi_{t}(x)|\mathrm{d}x$ exists at every
$t$, (2) $\phi_{t}\to 1$ in the weak sense as $t\to\infty$, and (3)
(continuous and) $(G,T)$-equivariant. For example, we can take a Gaussian
$\phi_{t}(x)=\exp(-|x|^{2}_{\mathcal{X}}/4t)$. Hence,

$R[f_{t};\rho](a,b)=\int_{\mathbb{R}^{m}}\sum_{|n|<m}nx_{n}\phi_{t}({\bm{x}})\overline{\rho\left({\textstyle\sum_{|n|<m}}a_{n}x_{n}-b\right)}\mathrm{d}{\bm{x}}.$

###  5.4 Euclidean group $\mathrm{E}(n)$ equivariant map

######  Example 9.

The Euclidean group $\mathrm{E}(n)$ is a semidirect product
$\mathbb{R}^{n}\rtimes\mathrm{O}(n)$ of the translational group
$\mathbb{R}^{n}$ and the orthogonal group $\mathrm{O}(n)$, which acts on
$\mathbb{R}^{n}$ as $(U,s)\cdot t:=Ut+s$ for any $t\in\mathbb{R}^{n}$ and
$(U,s)\in O(n)\times\mathbb{R}^{n}$. So, put $\mathcal{X}\subset
L^{2}(\mathbb{R}^{n})$ and $T_{(U,s)}[x](t):=x(U^{-1}(t-s))$. Then,

$\displaystyle
R[f;\rho](a,b):=\int_{\mathcal{X}}f(x)(I,0)\overline{\rho\left(\int_{\mathbb{R}^{n}}a(t)\overline{x(t)}\mathrm{d}t-b\right)}\mathrm{d}x$
$\displaystyle
S[R[f;\rho]](x)(U,t)=\int_{\mathcal{X}\times\mathbb{R}}R[f;\rho](a,b)\sigma\left(\int_{\mathbb{R}^{n}}a(U^{-1}(t-s))\overline{x(s)}\mathrm{d}s-b\right)\mathrm{d}a\mathrm{d}b=f(x)(U,t)$

We note that a more memory efficient representation for
$L^{2}(\mathbb{R}^{n})$ and/or a more general representation such as
$L^{2}(\mathrm{SO}(2))$ and $L^{2}(\mathrm{E}(3))$, have been developed in the
context of _steerable_ CNNs [32, 63].

##  6 Discussion

###  6.1 Related Works on (G)CNN Universality

#### Non-Group CNN.

Zhou [9, 10] is the earliest to show the $cc$-universality of deep ReLU (non-
group) CNNs. In [10], he presented (Theorem 1) the $cc$-universality in
$C(\mathbb{R}^{d};\mathbb{R})$ in the limit of depth $J\to\infty$, and
(Theorem 2) an approximation error rate with respect to $J$. The CNN is
carefully designed so that increasing depth also increases width, which is not
covered in our GCNN.

#### Finite Group CNN.

Maron et al. [12], Sannai et al. [64], Keriven and Peyré [65], Ravanbakhsh
[66] and Petersen and Voigtlaender [13] presented the $cc$-(or
$L^{p}$-)universality results of _finite_ -group CNNs. Maron et al. [12] is
often cited as one of the earliest publications, where the input space is
$\mathcal{X}=\mathbb{R}^{n^{k}\times a}$ ($a$-channel $k$-th order
$n$-dimensional tensors), the output space is
$\mathcal{X}\textquoteright=\mathbb{R}^{n^{l}\times b}$ ($b$-channel $l$-th
order $n$-dimensional tensors), the group $G$ is a subgroup of a symmetric
group $\mathrm{S}_{n}$, and the group action (or representation) $T$ is the
left-translation (or left-regular representation). In this setup, they
presented the $cc$-universality of deep-ReLU-GCNNs in the space of continuous
$G$-equivariant functions $C_{equi}(\mathcal{X};\mathcal{X}\textquoteright)$.
The proofs are indirect because they are based on _invariant polynomials_ or
_MLPs_. The finite group cases are essentially covered as Example 6 (Deep
Sets).

#### Lie Group CNN.

Yarotsky [11] carefully designed deep GCNNs with Lie groups acting on
_infinite-dimensional_ input/output spaces, and show a version of universality
in the space of continuous $G$-equivariant functions
$C_{equi}(L^{2}(G;\mathbb{R}^{d});L^{2}(G;\mathbb{R}^{d\textquoteright}))$. To
be precise, $G$ is either a compact group, translation group $\mathbb{R}^{d}$,
or 2-dimensional roto-translation group $\mathrm{SE}(2)$, and the input/output
spaces $\mathcal{X}$ and $\mathcal{X}^{\prime}$ are square-integrable
functions on $G$. The proposed networks are not covered in our GCNNs, but
several infinite group cases are covered in Examples 7 and 9.

Remarkably, Kumagai et al. [14] introduced an integral representation that
covers LCH groups, and showed the universality. The proposed integral
representation is based on the Haar measure, thus slightly different from
ours. The proofs are indirect because the network is converted to an MLP.

###  6.2 Review of Assumptions

#### Group $G$.

We only assume $G$ to be a topological group, to deal with continuous
functions on $G$. Thus, a quite large class of groups are covered, for
example, all the finite groups such as $\mathbb{Z}_{n}$ and $\mathrm{S}_{n}$,
compact groups such as $\mathrm{SO}(n)$ and $\mathrm{U}(n)$, and non-compact
groups such as $\mathbb{R}^{n}$ and $\mathrm{E}(n)$ as well.

#### Representation Space $\mathcal{X}$.

Unlike previous studies, it does _not_ need to be a function space such as
$C(G)$ and $L^{2}(G/H)$, but it only needs to be an abstract Hilbert space,
which is one of the major advantages for geometric understanding of GCNNs. On
the other hand, we introduce an auxiliary finite-dimensional subspace
$\mathcal{X}_{m}$ (and projection $P$), to use the Fourier inversion formula
on the finite-dimensional Euclidean space $\mathbb{R}^{m}$ in the proof. We
conjecture that the extension to an infinite-dimensional setting would be a
routine for some specialists in functional analysis.

#### Group Representation $T$.

It does _not_ need to be unitary, irreducible, nor square-integrable, since
the proof is based only on a few basic properties of the linear group
representation.

#### Network Architecture.

The ridgelet theory supports a wide class of _activation functions_ , namely,
the tempered distributions ($\mathcal{S}^{\prime}$). The extension to _deep
GCNNs_ remains an important open question.

## Acknowledgments and Disclosure of Funding

The authors are grateful to anonymous reviewers for their valuable comments.
This work was supported by JST CREST JPMJCR2015 and JPMJCR1913, JST PRESTO
JPMJPR2125, and JST ACT-X JPMJAX2004.

## References

  * Bronstein et al. [2021] Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković.  Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges.  _arXiv preprint: 2104.13478_ , 2021.
  * Qi et al. [2017] Charles R Qi, Hao Su, Kaichun Mo, and Leonidas J Guibas.  PointNet: Deep Learning on Point Sets for 3D Classification and Segmentation.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.
  * Zaheer et al. [2017] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep Sets.  In _Advances in Neural Information Processing Systems 30_ , 2017.
  * Kondor and Trivedi [2018] Risi Kondor and Shubhendu Trivedi.  On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups.  In _Proceedings of the 35th International Conference on Machine Learning_ , volume 80, pages 2747–2755, 2018.
  * Maron et al. [2019a] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and Equivariant Graph Networks.  In _International Conference on Learning Representations_ , 2019a.
  * Cohen et al. [2018] Taco S Cohen, Mario Geiger, Jonas Köhler, and Max Welling.  Spherical CNNs.  In _International Conference on Learning Representations_ , 2018.
  * Cohen et al. [2019] Taco S Cohen, Mario Geiger, and Maurice Weiler.  A General Theory of Equivariant CNNs on Homogeneous Spaces.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Kondor et al. [2018] Risi Kondor, Zhen Lin, and Shubhendu Trivedi.  Clebsch-Gordan Nets: a Fully Fourier Space Spherical Convolutional Neural Network.  In _Advances in Neural Information Processing Systems 31_ , 2018.
  * Zhou [2018] Ding-Xuan Zhou.  Deep distributed convolutional neural networks: Universality.  _Analysis and Applications_ , 16(06):895–919, 2018.
  * Zhou [2020] Ding-Xuan Zhou.  Universality of deep convolutional neural networks.  _Applied and Computational Harmonic Analysis_ , 48(2):787–794, 2020.
  * Yarotsky [2021] Dmitry Yarotsky.  Universal Approximations of Invariant Maps by Neural Networks.  _Constructive Approximation_ , 2021.
  * Maron et al. [2019b] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.  On the Universality of Invariant Networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pages 4363–4371, 2019b.
  * Petersen and Voigtlaender [2020] Philipp Petersen and Felix Voigtlaender.  Equivalence of approximation by convolutional neural networks and fully-connected networks.  _Proceedings of the American Mathematical Society_ , 148(4):1567–1581, 2020.
  * Kumagai et al. [2022] Wataru Kumagai, Akiyoshi Sannai, and Makoto Kawano.  Universal approximation with neural networks on function spaces.  _Journal of Experimental & Theoretical Artificial Intelligence_, pages 1–12, 2022.
  * Okumoto and Suzuki [2022] Sho Okumoto and Taiji Suzuki.  Learnability of convolutional neural networks for infinite dimensional input via mixed and anisotropic smoothness.  In _International Conference on Learning Representations_ , 2022.
  * Cybenko [1989] George Cybenko.  Approximation by superpositions of a sigmoidal function.  _Mathematics of Control, Signals, and Systems (MCSS)_ , 2(4):303–314, 1989.
  * Hornik et al. [1989] Kurt Hornik, Maxwell Stinchcombe, and Halbert White.  Multilayer feedforward networks are universal approximators.  _Neural Networks_ , 2(5):359–366, 1989.
  * Irie and Miyake [1988] Bunpei Irie and Sei Miyake.  Capabilities of three-layered perceptrons.  In _IEEE International Conference on Neural Networks_ , pages 641–648, 1988.
  * Funahashi [1989] Ken-Ichi Funahashi.  On the approximate realization of continuous mappings by neural networks.  _Neural Networks_ , 2(3):183–192, 1989.
  * Carroll and Dickinson [1989] S. M. Carroll and B. W. Dickinson.  Construction of neural nets using the Radon transform.  In _International Joint Conference on Neural Networks 1989_ , volume 1, pages 607–611. IEEE, 1989.
  * Ito [1991] Yoshifusa Ito.  Representation of functions by superpositions of a step or sigmoid function and their applications to neural network theory.  _Neural Networks_ , 4(3):385–394, 1991.
  * Mhaskar and Micchelli [1992] H.N Mhaskar and Charles A Micchelli.  Approximation by superposition of sigmoidal and radial basis functions.  _Advances in Applied Mathematics_ , 13(3):350–373, 1992.
  * Mhaskar [1996] H. N. Mhaskar.  Neural Networks for Optimal Approximation of Smooth and Analytic Functions.  _Neural Computation_ , 8:164–177, 1996.
  * Barron [1993] Andrew R Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  _IEEE Transactions on Information Theory_ , 39(3):930–945, 1993.
  * Leshno et al. [1993] Moshe Leshno, Vladimir Ya. Lin, Allan Pinkus, and Shimon Schocken.  Multilayer feedforward networks with a nonpolynomial activation function can approximate any function.  _Neural Networks_ , 6(6):861–867, 1993.
  * Murata [1996] Noboru Murata.  An integral representation of functions using three-layered betworks and their approximation bounds.  _Neural Networks_ , 9(6):947–956, 1996.
  * Candès [1998] Emmanuel Jean Candès.  _Ridgelets: theory and applications_.  PhD thesis, Standford University, 1998.
  * Rubin [1998] Boris Rubin.  The Calderón reproducing formula, windowed X-ray transforms, and Radon transforms in $L^{p}$-spaces.  _Journal of Fourier Analysis and Applications_ , 4(2):175–197, 1998.
  * Telgarsky [2016] Matus Telgarsky.  Benefits of depth in neural networks.  In _29th Annual Conference on Learning Theory_ , pages 1–23, 2016\.
  * Yarotsky [2017] Dmitry Yarotsky.  Error bounds for approximations with deep ReLU networks.  _Neural Networks_ , 94:103–114, 2017.
  * Petersen and Voigtlaender [2018] Philipp Petersen and Felix Voigtlaender.  Optimal approximation of piecewise smooth functions using deep ReLU neural networks.  _Neural Networks_ , 108:296–330, 2018.
  * Cohen and Welling [2017] Taco S Cohen and Max Welling.  Steerable CNNs.  In _International Conference on Learning Representations 2017_ , pages 1–14, 2017.
  * Jacot et al. [2018] Arthur Jacot, Franck Gabriel, and Clement Hongler.  Neural Tangent Kernel: Convergence and Generalization in Neural Networks.  In _Advances in Neural Information Processing Systems 31_ , pages 8571–8580, 2018.
  * Lee et al. [2019] Jaehoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein, and Jeffrey Pennington.  Wide Neural Networks of Any Depth Evolve as Linear Models Under Gradient Descent.  In _Advances in Neural Information Processing Systems 32_ , pages 8572–8583, 2019.
  * Arora et al. [2019] Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang.  Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks.  In _Proceedings of the 36th International Conference on Machine Learning_ , volume 97, pages 322–332, 2019.
  * Chizat et al. [2019] Lénaïc Chizat, Edouard Oyallon, and Francis Bach.  On Lazy Training in Differentiable Programming.  In _Advances in Neural Information Processing Systems 32_ , pages 2937–2947, 2019.
  * Frankle and Carbin [2019] Jonathan Frankle and Michael Carbin.  The Lottery Ticket Hypothesis: Finding Sparse, Trainable Neural Networks.  In _International Conference on Learning Representations_ , pages 1–42, 2019.
  * Nitanda and Suzuki [2017] Atsushi Nitanda and Taiji Suzuki.  Stochastic Particle Gradient Descent for Infinite Ensembles.  _arXiv preprint: 1712.05438_ , 2017.
  * Mei et al. [2018] Song Mei, Andrea Montanari, and Phan-Minh Nguyen.  A mean field view of the landscape of two-layer neural networks.  _Proceedings of the National Academy of Sciences_ , 115(33):E7665–E7671, 2018.
  * Rotskoff and Vanden-Eijnden [2018] Grant Rotskoff and Eric Vanden-Eijnden.  Parameters as interacting particles: long time convergence and asymptotic error scaling of neural networks.  In _Advances in Neural Information Processing Systems 31_ , pages 7146–7155, 2018.
  * Chizat and Bach [2018] Lénaïc Chizat and Francis Bach.  On the Global Convergence of Gradient Descent for Over-parameterized Models using Optimal Transport.  In _Advances in Neural Information Processing Systems 32_ , pages 3036–3046, 2018.
  * Sirignano and Spiliopoulos [2020] Justin Sirignano and Konstantinos Spiliopoulos.  Mean Field Analysis of Neural Networks: A Law of Large Numbers.  _SIAM Journal on Applied Mathematics_ , 80(2):725–752, 2020.
  * Suzuki [2020] Taiji Suzuki.  Generalization bound of globally optimal non-convex neural network training: Transportation map estimation by infinite dimensional Langevin dynamics.  In _Advances in Neural Information Processing Systems 33_ , pages 19224–19237, 2020.
  * Sonoda et al. [2021a] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda.  Ghosts in Neural Networks: Existence, Structure and Role of Infinite-Dimensional Null Space.  _arXiv preprint: 2106.04770_ , 2021a.
  * Sonoda et al. [2021b] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda.  Ridge Regression with Over-Parametrized Two-Layer Networks Converge to Ridgelet Spectrum.  In _Proceedings of The 24th International Conference on Artificial Intelligence and Statistics (AISTATS) 2021_ , volume 130, pages 2674–2682, 2021b.
  * Savarese et al. [2019] Pedro Savarese, Itay Evron, Daniel Soudry, and Nathan Srebro.  How do infinite width bounded norm networks look in function space? In _Proceedings of the 32nd Conference on Learning Theory_ , volume 99, pages 2667–2690, 2019.
  * Ongie et al. [2020] Greg Ongie, Rebecca Willett, Daniel Soudry, and Nathan Srebro.  A Function Space View of Bounded Norm Infinite Width ReLU Nets: The Multivariate Case.  In _International Conference on Learning Representations_ , 2020.
  * Parhi and Nowak [2021] Rahul Parhi and Robert D Nowak.  Banach Space Representer Theorems for Neural Networks and Ridge Splines.  _Journal of Machine Learning Research_ , 22(43):1–40, 2021.
  * Unser [2019] Michael Unser.  A Representer Theorem for Deep Neural Networks.  _Journal of Machine Learning Research_ , 20(110):1–30, 2019.
  * Donoho [2002] David L Donoho.  Emerging applications of geometric multiscale analysis.  _Proceedings of the ICM, Beijing 2002_ , I:209–233, 2002\.
  * Starck et al. [2010] Jean-Luc Starck, Fionn Murtagh, and Jalal M. Fadili.  The ridgelet and curvelet transforms.  In _Sparse Image and Signal Processing: Wavelets, Curvelets, Morphological Diversity_ , pages 89–118. Cambridge University Press, 2010.
  * Kutyniok and Labate [2012] Gitta Kutyniok and Demetrio Labate.  _Shearlets: Multiscale Analysis for Multivariate Data_.  Applied and Numerical Harmonic Analysis. Birkhäuser Boston, 1 edition, 2012.
  * Sonoda and Murata [2017] Sho Sonoda and Noboru Murata.  Neural network with unbounded activation functions is universal approximator.  _Applied and Computational Harmonic Analysis_ , 43(2):233–268, 2017.
  * Kostadinova et al. [2014] S Kostadinova, S Pilipović, K Saneva, and J Vindas.  The ridgelet transform of distributions.  _Integral Transforms and Special Functions_ , 25(5):344–358, 2014.
  * Sonoda et al. [2022] Sho Sonoda, Isao Ishikawa, and Masahiro Ikeda.  Fully-Connected Network on Noncompact Symmetric Space and Ridgelet Transform based on Helgason-Fourier Analysis.  In _Proceedings of the 39th International Conference on Machine Learning_ , volume 162, pages 20405–20422, 2022.
  * Grafakos [2008] Loukas Grafakos.  _Classical Fourier Analysis_.  Graduate Texts in Mathematics. Springer New York, second edition, 2008\.
  * Gel’fand and Shilov [1964] I. M. Gel’fand and G. E. Shilov.  _Generalized Functions, Vol. 1: Properties and Operations_.  Academic Press, New York, 1964.
  * Folland [2015] Gerald B. Folland.  _A Course in Abstract Harmonic Analysis_.  Chapman and Hall/CRC, New York, second edition, 2015.
  * Sriperumbudur et al. [2010] Bharath K. Sriperumbudur, Kenji Fukumizu, and Gert R. G. Lanckriet.  Universality, Characteristic Kernels and RKHS Embedding of Measures.  _Journal of Machine Learning Research_ , 12(Jul):2389–2410, 2010.
  * Pinkus [1999] Allan Pinkus.  Approximation theory of the MLP model in neural networks.  _Acta Numerica_ , 8:143–195, 1999.
  * Krizhevsky et al. [2012] Alex Krizhevsky, Ilya Sutskever, and Geoffrey E. Hinton.  ImageNet Classification with Deep Convolutional Neural Networks.  In _Advances in Neural Information Processing Systems 25_ , pages 1097–1105, 2012.
  * Zeiler and Fergus [2014] Matthew D. Zeiler and Rob Fergus.  Visualizing and Understanding Convolutional Networks.  In _European Conference on Computer Vision_ , pages 818–833, 2014\.
  * Weiler and Cesa [2019] Maurice Weiler and Gabriele Cesa.  General E(2)-Equivariant Steerable CNNs.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Sannai et al. [2019] Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier.  Universal approximations of permutation invariant/equivariant functions by deep neural networks.  _arXiv preprint: 1903.01939_ , 2019.
  * Keriven and Peyré [2019] Nicolas Keriven and Gabriel Peyré.  Universal Invariant and Equivariant Graph Neural Networks.  In _Advances in Neural Information Processing Systems 32_ , 2019.
  * Ravanbakhsh [2020] Siamak Ravanbakhsh.  Universal Equivariant Multilayer Perceptrons.  In _Proceedings of the 37th International Conference on Machine Learning_ , volume 119 of _Proceedings of Machine Learning Research_ , pages 7996–8006, 2020.
  * Kainen et al. [2013] P C Kainen, Vĕra Kůrková, and Marcello Sanguineti.  Approximating multivariable functions by feedforward neural nets.  In _Handbook on Neural Information Processing_ , volume 49 of _Intelligent Systems Reference Library_ , pages 143–181. Springer Berlin Heidelberg, 2013.

## Checklist

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [No]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [N/A]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [N/A]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [N/A]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [N/A]

    2. (b)

Did you mention the license of the assets? [N/A]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [N/A]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

##  Appendix A Proofs

#### Additional Notation

In the proofs, we use two symbols $\widehat{\cdot}$ and $\cdot^{\sharp}$ for
the Fourier transforms in $x\in\mathcal{X}$ and $b\in\mathbb{K}$,
respectively. For example,

$\displaystyle\widehat{f}(\xi):=\int_{\mathcal{X}}f(x)e^{-i\langle\xi,x\rangle_{\mathcal{X}}}\mathrm{d}x,\quad\xi\in\mathcal{X}$
$\displaystyle\rho^{\sharp}(\omega):=\int_{\mathbb{K}}\rho(b)e^{-i\omega
b}\mathrm{d}b,\quad\omega\in\mathbb{K}$
$\displaystyle\gamma^{\sharp}(a,\omega)=\int_{\mathbb{K}}\gamma(a,b)e^{-i\omega
b}\mathrm{d}b,\quad(a,\omega)\in\mathcal{X}\times\mathbb{K}.$

With a slight abuse of notation, when $\sigma$ is a tempered distribution
(i.e., $\sigma\in\mathcal{S}^{\prime}(\mathbb{K})$), then $\sigma^{\sharp}$ is
understood as the Fourier transform of distributions. Namely,
$\sigma^{\sharp}$ is another tempered distribution satisfying
$\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\phi(\omega)\mathrm{d}\omega=\int_{\mathbb{K}}\sigma(\omega)\phi^{\sharp}(\omega)\mathrm{d}\omega$
for any test function $\phi\in\mathcal{S}(\mathbb{K})$.

For any integer $d>0$ and vector ${\bm{v}}\in\mathbb{R}^{d}$, $|{\bm{v}}|$
denotes the Euclidean norm, and
$\langle{\bm{v}}\rangle:=\sqrt{1+|{\bm{v}}|^{2}}$. For any positive number
$t>0$, $\triangle^{t/2}$ and $\langle\triangle\rangle^{t}$ denote fractional
differential operators defined as Fourier multipliers: for any
$\phi\in\mathcal{S}^{\prime}(\mathbb{R}^{d})$,

$\displaystyle\triangle^{t/2}[\phi]({\bm{v}}):=\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}|{\bm{u}}|^{t}\widehat{\phi}({\bm{u}})e^{i{\bm{u}}\cdot{\bm{v}}}\mathrm{d}{\bm{u}},$
(32)
$\displaystyle\langle\triangle\rangle^{t/2}[\phi]({\bm{v}}):=\frac{1}{(2\pi)^{d}}\int_{\mathbb{R}^{d}}(1+|{\bm{u}}|^{2})^{t/2}\widehat{\phi}({\bm{u}})e^{i{\bm{u}}\cdot{\bm{v}}}\mathrm{d}{\bm{u}}.$
(33)

In particular when $t=2$, $\triangle^{t/2}$ coincides with the ordinary
Laplacian on $\mathbb{R}^{d}$.

###  A.1 Theorem 1

###### Proof.

In the following, we fix a representation $T:G\to GL(\mathcal{X})$ of a group
$G$ on a (potentially infinite-dimensional) Hilbert space $\mathcal{X}$ over a
field $\mathbb{K}$ equipped with inner product
$\langle\cdot,\cdot\rangle_{\mathcal{X}}$, which is a $G$-invariant vector
space: $T_{G}[\mathcal{X}]=\mathcal{X}$, and a finite-dimensional closed
subspace $\mathcal{X}_{m}\subset\mathcal{X}$ equipped with the Lebesgue
measure $\lambda$. Let $\mathcal{X}_{m}^{\perp}$ be the orthogonal complement
of $\mathcal{X}_{m}$ in $\mathcal{X}$, i.e., $x\oplus
y\in\mathcal{X}_{m}\oplus\mathcal{X}_{m}^{\perp}=\mathcal{X}$, and let
$P:\mathcal{X}\to\mathcal{X}_{m}$ denote the orthogonal projection onto
$\mathcal{X}_{m}$. Let $m:=\dim_{\mathbb{R}}\mathcal{X}_{m}$ denotes the real
dimension of $\mathcal{X}_{m}$, and let $k:=\dim_{\mathbb{R}}\mathbb{K}$
denotes the real dimension of $\mathbb{K}$, which is either $1$ or $2$.

Without loss of generality, we can assume (A’) that
$\gamma(a,\bullet)*\sigma\in\mathcal{S}(\mathbb{K})$ for a.e.
$a\in\mathcal{X}_{m}$, and (A”) that $\gamma^{\sharp}\sigma^{\sharp}\in
L^{1}(\mathcal{X}_{m}\times\mathbb{K})$, which will be eventually justified
because later in (38), we set $\gamma^{\sharp}(a,\omega)=\widehat{f}(\omega
a)\overline{\rho^{\sharp}(\omega)}$.

#### Step 1 (Fourier expression).

Using an identity: For any function $\phi\in\mathcal{S}(\mathbb{K})$ and
$b\in\mathbb{K}$,
$\phi(b)=\frac{1}{(2\pi)^{k}}\int_{\mathbb{K}}\phi^{\sharp}(\omega)e^{ib\omega}\mathrm{d}\omega$,
namely the Fourier inversion formula, we can turn $S$ into a _Fourier
expression_ :

$\displaystyle S[\gamma](x)(g)$
$\displaystyle=\frac{1}{(2\pi)^{k}}\int_{\mathcal{X}_{m}}\int_{\mathbb{K}}\gamma(a,b)\sigma(\langle
T_{g^{-1}}[x],a\rangle_{\mathcal{X}}-b)\mathrm{d}b\mathrm{d}a$ (34)
$\displaystyle=\frac{1}{(2\pi)^{k}}\int_{\mathcal{X}_{m}}\int_{\mathbb{K}}\gamma^{\sharp}(a,\omega)\sigma^{\sharp}(\omega)\exp\left(i\omega\langle
T_{g^{-1}}[x],a\rangle_{\mathcal{X}}\right)\mathrm{d}\omega\mathrm{d}a.$ (35)

By the assumption (A’), the first equation holds at every point
$b=(a*_{T}x)(g)$, and by the assumption (A”), the Fourier expression is
_uniformly_ absolutely convergent:

$\displaystyle\int_{\mathcal{X}_{m}\times\mathbb{K}}|\gamma^{\sharp}(a,\omega)\sigma^{\sharp}(\omega)\exp(i\omega(a*x)(g))|\mathrm{d}a\mathrm{d}\omega=\|\gamma^{\sharp}\sigma^{\sharp}\|_{L^{1}(\mathcal{X}_{m}\times\mathbb{K})}<\infty,$
(36)

for _all_ $(x,g)\in\mathcal{X}\times G$. Hence, we can change the order of
integration freely.

#### Step 2 (Reconstruction).

By changing the variables as $(a,\omega)=(\xi/\omega,\omega)$ with
$\mathrm{d}a\mathrm{d}\omega=|\omega|^{-m}\mathrm{d}\xi\mathrm{d}\omega$, we
have

$\displaystyle
S[\gamma](x)(g)=\frac{1}{(2\pi)^{k}}\int_{\mathcal{X}_{m}\times\mathbb{K}}\gamma^{\sharp}(\xi/\omega,\omega)\sigma^{\sharp}(\omega)\exp\left(i\langle
T_{g^{-1}}[x],\xi\rangle_{\mathcal{X}}\right)|\omega|^{-m}\mathrm{d}\omega\mathrm{d}\xi.$
(37)

Hence, using a given $f$ satisfying the assumptions (A1) and (A2), and some
function $\rho\in\mathcal{S}(\mathbb{K})$, suppose that $\gamma_{f,\rho}$
satisfies the following _separation-of-variables_ form:

$\displaystyle\gamma_{f,\rho}^{\sharp}(\xi/\omega,\omega)=\widehat{f}(\xi)(e)\overline{\rho^{\sharp}(\omega)}.$
(38)

Then,

$\displaystyle S[\gamma_{f,\rho}](x)(g)$
$\displaystyle=\frac{1}{(2\pi)^{k}}\int_{\mathcal{X}_{m}\times\mathbb{K}}\widehat{f}(\xi)(e)\overline{\rho^{\sharp}(\omega)}\sigma^{\sharp}(\omega)\exp\left(i\langle
T_{g^{-1}}[x],\xi\rangle_{\mathcal{X}}\right)|\omega|^{-m}\mathrm{d}\omega\mathrm{d}\xi$
(39)
$\displaystyle=\left((2\pi)^{m-k}\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\overline{\rho^{\sharp}(\omega)}|\omega|^{-m}\mathrm{d}\omega\right)$
$\displaystyle\qquad\times\left(\frac{1}{(2\pi)^{m}}\int_{\mathcal{X}_{m}}\widehat{f}(\xi)(e)\exp\left(i\langle
T_{g^{-1}}[x],\xi\rangle_{\mathcal{X}}\right)\mathrm{d}\xi\right)$ (40)
$\displaystyle\overset{\star}{=}(\\!(\sigma,\rho)\\!)f(PT_{g^{-1}}[x])(e)$
(41) $\displaystyle=(\\!(\sigma,\rho)\\!)f(x)(g).$ (42)

where we put

$\displaystyle(\\!(\sigma,\rho)\\!):=(2\pi)^{m-k}\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\overline{\rho^{\sharp}(\omega)}|\omega|^{-m}\mathrm{d}\omega.$
(43)

Here, the equality $\overset{\star}{=}$ holds at every continuous point
$x_{c}$ of $f$ for (A2a), in $L^{2}$ for (A2b), and in $\mathcal{S}^{\prime}$
for (A2c), respectively.

#### Step 3 (Ridgelet transform).

Since we put

$\displaystyle\gamma_{f,\rho}^{\sharp}(a,\omega)=\widehat{f}(\omega
a)(e)\overline{\rho^{\sharp}(\omega)},$ (44)

it is calculated as

$\displaystyle\gamma_{f,\rho}(a,b)$
$\displaystyle=\frac{1}{(2\pi)^{k}}\int_{\mathbb{K}}\widehat{f}(\omega
a)(e)\overline{\rho^{\sharp}(\omega)}e^{i\omega b}\mathrm{d}\omega$ (45)
$\displaystyle=\frac{1}{(2\pi)^{k}}\int_{\mathbb{K}\times\mathcal{X}_{m}}f(x)(e)\overline{\rho^{\sharp}(\omega)}e^{i\omega(b-\langle
a,x\rangle_{\mathcal{X}})}\mathrm{d}\omega\mathrm{d}x$ (46)
$\displaystyle=\int_{\mathcal{X}_{m}}f(x)(e)\overline{\rho(\langle
a,x\rangle_{\mathcal{X}}-b)}\mathrm{d}x,$ (47)

which is the definition of the ridgelet transform for GCNN. ∎

###  A.2 Theorem 2

###### Proof.

Fix arbitrary compact sets $K\subset\mathcal{X}_{m}$ and $L\subset G$,
positive number $\varepsilon>0$, and function $f\in C_{equi}(K;C(G))$. An
$n$-term finite $(G,T)$-CNN is given by

$\displaystyle
f_{n}(x)(g):=\sum_{i=1}^{n}c_{i}\sigma\left((a_{i}*_{T}x)(g)-b_{i}\right),\quad
x\in\mathcal{X}_{m},\ g\in G$ (48)

with parameters
$(a_{i},b_{i},c_{i})\in\mathcal{X}_{m}\times\mathbb{K}\times\mathbb{C}$.
Observe that any finite $(G,T)$-CNN is $(G,T)$-equivariant, that is,

$\displaystyle f_{n}(T_{g}[x])(h)$
$\displaystyle=\sum_{i=1}^{n}c_{i}\sigma\left(\langle
T_{(g^{-1}h)^{-1}}x,a_{i}\rangle_{\mathcal{X}}-b_{i}\right)=f_{n}(x)(g^{-1}h).$
(49)

Put $\overline{K}:=\\{T_{g^{-1}}[x]\mid x\in K,g\in L\\}$, which is compact
because $T$ is continuous, and put $f_{e}(x):=f(x)(e)$, which is compactly
supported, i.e., $f_{e}\in C(K)\subset C(\overline{K})$. By Theorem 3, there
exist a finite number $N\in\mathbb{N}$ and an $N$-term $\mathbb{C}$-valued
fully-connected network $F_{N}(x)=\sum_{i=1}^{N}c_{i}\sigma(\langle
a_{i},x\rangle_{\mathcal{X}}-b_{i})$ satisfying
$\|F_{N}-f_{e}\|_{C(\overline{K})}<\varepsilon$. Put
$f_{N}(x)(g):=F_{N}(T_{g^{-1}}[x])$. Then, it is a $(G,T)$-CNN because

$\displaystyle f_{N}(x)(g)=\sum_{i=1}^{N}c_{i}\sigma\left(\langle
T_{g^{-1}},a_{i}\rangle_{\mathcal{X}}-b_{i}\right)=\sum_{i=1}^{N}c_{i}\sigma\left((a_{i}*_{T}x)(g)-b_{i}\right),$
(50)

and it is an $\varepsilon$-neighbour of $f$ because

$\displaystyle\|f_{N}-f\|_{C(K;C(L))}$ $\displaystyle=\sup_{x\in K}\sup_{g\in
L}|f_{N}(x)(g)-f(x)(g)|$ (51) $\displaystyle=\sup_{x\in K}\sup_{g\in
L}|F_{N}(T_{g^{-1}}[x])-f_{e}(T_{g^{-1}}[x])|$ (52) $\displaystyle=\sup_{g\in
L}\sup_{x^{\prime}\in\overline{K}}|F_{N}(x^{\prime})-f_{e}(x^{\prime})|,\quad
x^{\prime}=T_{g^{-1}}[x]$ (53) $\displaystyle<\varepsilon,$ (54)

which concludes the assertion. ∎

######  Theorem 3 ($cc$-universality of scalar-valued finite fully-connected
NNs on $\mathbb{R}^{m}$).

Suppose that

  1. 1.

$\mathcal{X}=\mathcal{X}_{m}=\mathbb{R}^{m}$,

  2. 2.

$f\in C(\mathcal{X};\mathbb{C})$ (not vector-valued
$C(\mathcal{X};\mathbb{C}^{G})$ but scalar-valued), and

  3. 3.

there exists $k\geq 0$ and $\theta>0$ such that
$\Delta_{\theta}^{k}[\sigma]\in L^{\infty}(\mathbb{R})$ and Lipschitz
continuous.

Then, the finite neural networks of the form
$f_{n}({\bm{x}})=\sum_{i=1}^{n}c_{i}\sigma({\bm{a}}_{i}\cdot{\bm{x}}-b_{i})$
are $cc$-universal, that is, for any compact set $K\subset\mathbb{R}^{m}$,
positive number $\varepsilon>0$, and continuous function $f\in C(K)$, there
exists a finite network $f_{n}$ such that $\|f-f_{n}\|_{C(K)}<\varepsilon$.

###### Proof.

Since
$\sum_{i=1}^{n}c_{i}\Delta_{\theta}^{k}[\sigma]({\bm{a}}_{i}\cdot{\bm{x}}-b_{i})$
is rewritten as another finite model
$\sum_{i=1}^{n^{\prime}}c_{i}^{\prime}\sigma({\bm{a}}_{i}^{\prime}\cdot{\bm{x}}-b_{i}^{\prime})$,
it suffice to consider the case $k=0$. In the following, we assume that
$\sigma(=\Delta_{\theta}^{0}[\sigma])$ is bounded and Lipschitz continuous.

#### Step 1 ($f\sim{f_{c}}$).

By the density of $C_{c}^{\infty}(\mathbb{R}^{m})$ in $C(K)$ with respect to
the uniform norm, we can take a compactly-supported smooth function
${f_{c}}\in C_{c}^{\infty}(\mathbb{R}^{m})$ satisfying
$\|f-{f_{c}}\|_{C(K)}<\varepsilon/3$. Since ${f_{c}}$ is sufficiently smooth
and integrable, there exists a compactly-supported smooth function $\rho\in
C_{c}^{\infty}(\mathbb{R})$ such that

$\displaystyle S[R[{f_{c}};\rho]]({\bm{x}})={f_{c}}({\bm{x}})\mbox{ at every
point }{\bm{x}}\in\mathbb{R}^{m}.$ (55)

For example, take a compactly-supported smooth function $\rho_{0}\in
C_{c}^{\infty}(\mathbb{K})$, write $k=\dim_{\mathbb{R}}\mathbb{K}(=1\mbox{ or
}2)$, and put
$\rho(b):=\triangle_{b}^{m/2}[\rho_{0}](b)=(2\pi)^{-k}\int_{\mathbb{K}}|\omega|^{m}\rho_{0}^{\sharp}(\omega)e^{ib\cdot\omega}\mathrm{d}\omega$.
Then,
$(\\!(\sigma,\rho)\\!)=(2\pi)^{m-k}\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\overline{\rho^{\sharp}(\omega)}|\omega|^{-m}\mathrm{d}\omega=(2\pi)^{m-k}\int_{\mathbb{K}}\sigma^{\sharp}(\omega)\overline{\rho_{0}^{\sharp}(\omega)}\mathrm{d}\omega=(2\pi)^{m}\int_{\mathbb{K}}\sigma(b)\overline{\rho_{0}(b)}\mathrm{d}b=\langle\sigma,\rho_{0}\rangle_{L^{2}(\mathbb{K})}$,
which is an ordinary functional inner product, and it is easy to find a
$\rho_{0}$ satisfying $\langle\sigma,\rho_{0}\rangle_{L^{2}(\mathbb{K})}\neq
0$. By normalizing $\rho^{\prime}:=\rho/(\\!(\sigma,\rho)\\!)$, we can find
the $\rho^{\prime}$. We refer to Sonoda and Murata [53] and Sonoda et al. [44]
for more details on the scalar product $(\\!(\sigma,\rho)\\!)$.

Step 2 ($R[{f_{c}};\rho]$). To show a discretization ${f_{n}}$ of the
reconstruction formula converges to ${f_{c}}$ in $C(K)$, it is convenient to
regard the integration
$\int_{\mathbb{R}^{m}\times\mathbb{R}}[\cdots]\mathrm{d}{\bm{a}}\mathrm{d}b$
in $S$ as the Bochner integral, and the integrand
$\gamma({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)$ as a vector-valued
function from $\mathbb{R}^{m}\times\mathbb{R}$ to $C(K)$.

Since ${f_{c}}$ is $C^{\infty}$-smooth, $R[{f_{c}};\rho]({\bm{a}},b)$ is
bounded and decays rapidly in ${\bm{a}}$, and thus
$R[{f_{c}};\rho]\sigma({\bm{a}}\cdot{\bm{x}}-b)$ is Bochner integrable, that
is,

$\displaystyle\int_{\mathbb{R}^{m}\times\mathbb{R}}\sup_{{\bm{x}}\in
K}\big{|}R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)\big{|}\mathrm{d}{\bm{a}}\mathrm{d}b<\infty.$
(56)

To see this, the decay property is estimated as follows. For any positive
numbers $s,t>1$,

$\displaystyle|R[{f_{c}};\rho]({\bm{a}},b)|$
$\displaystyle=\frac{1}{2\pi}\Bigg{|}\int_{\mathbb{R}}\widehat{{f_{c}}}(\omega{\bm{a}})\overline{\rho^{\sharp}(\omega)}e^{i\omega
b}\mathrm{d}\omega\Bigg{|}$
$\displaystyle=\frac{1}{2\pi}\Bigg{|}\int_{\mathbb{R}}\langle\omega{\bm{a}}\rangle^{s}\langle\omega{\bm{a}}\rangle^{-s}\langle
b\rangle^{t}\langle
b\rangle^{-t}\widehat{{f_{c}}}(\omega{\bm{a}})\overline{\rho^{\sharp}(\omega)}e^{i\omega
b}\mathrm{d}\omega\Bigg{|}$
$\displaystyle\leq\frac{1}{2\pi}\Bigg{|}\int_{\mathbb{R}}\langle\omega{\bm{a}}\rangle^{s}\widehat{{f_{c}}}(\omega{\bm{a}})\langle\omega\rangle^{-s}\overline{\rho^{\sharp}(\omega)}\langle\triangle_{\omega}\rangle^{t}e^{i\omega
b}\mathrm{d}\omega\Bigg{|}\langle{\bm{a}}\rangle^{-s}\langle b\rangle^{-t},$
(57)

which asserts the integrability as below

$\displaystyle\int_{\mathbb{R}^{m}\times\mathbb{R}}\sup_{{\bm{x}}\in
K}|R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)|\mathrm{d}{\bm{a}}\mathrm{d}b$
$\displaystyle\lesssim\int_{\mathbb{R}^{m}\times\mathbb{R}}\langle{\bm{a}}\rangle^{-s}\langle
b\rangle^{-t}\mathrm{d}{\bm{a}}\mathrm{d}b<\infty.$ (58)

#### Step 3 (${f_{c}}\sim{f_{Q}}\sim{f_{n}}$).

Next, take a compact domain ($m+1$-dimensional hypercube)
$Q:=\\{({\bm{a}},b)\in\mathbb{R}^{m}\times\mathbb{R}\mid|a_{i}|\leq\delta/2,|b|\leq\delta/2\\}$,
and put a band-limited function

$\displaystyle{f_{Q}}({\bm{x}}):=\int_{Q}R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)\mathrm{d}{\bm{a}}\mathrm{d}b,$
(59)

so that $\|{f_{c}}-{f_{Q}}\|_{C(K)}<\varepsilon/3$ (by letting $\delta$
sufficiently large). Then, let $Q=\bigsqcup_{i\in I_{n}}Q_{ni}$ be a
decomposition of the domain $Q$ into the union of disjoint family of
$|I_{n}|=n^{m+1}$ cubes with volume
$\operatorname{vol}(Q_{n})=(\delta/n)^{m+1}$ and the longest diagonal
$d_{n}=\sqrt{m+1}\delta/n$. From each cube, take a point
$({\bm{a}}_{ni},b_{ni})\in Q_{ni}$ as a center of gravity, that is, so that
$c_{ni}=\int_{Q_{ni}}R[{f_{c}};\rho]({\bm{a}},b)\mathrm{d}{\bm{a}}\mathrm{d}b=R[{f_{c}};\rho]({\bm{a}}_{ni},b_{ni})\operatorname{vol}(Q_{n})$,
and put $w_{ni}:=R[{f_{c}};\rho]({\bm{a}}_{ni},b_{ni})$, then put a finite
network as

$\displaystyle{f_{n}}({\bm{x}}):=\sum_{i\in
I_{n}}c_{ni}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni}).$ (60)

#### Step 4 (${f_{Q}}\sim{f_{n}}$).

We show ${f_{n}}\to{f_{Q}}$ in $C(K)$. First, the integrands converge to the
limit at almost every $({\bm{a}},b)\in Q_{ni}$ as

$\displaystyle\sup_{{\bm{x}}\in
K}\Big{|}R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)-w_{ni}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Big{|}$
(61) $\displaystyle\leq\sup_{{\bm{x}}\in
K}\Big{|}R[{f_{c}};\rho]({\bm{a}},b)\Big{|}\Big{|}\sigma({\bm{a}}\cdot{\bm{x}}-b)-\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Big{|}$
$\displaystyle\qquad+\Big{|}R[{f_{c}};\rho]({\bm{a}}_{ni},b_{ni})-R[{f_{c}};\rho]({\bm{a}},b)\Big{|}\Big{|}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Big{|}$
(62)
$\displaystyle\leq\|R[{f_{c}};\rho]\|_{\infty}\operatorname{Lip}(\sigma)\sup_{{\bm{x}}\in
K}\Big{|}({\bm{a}}-{\bm{a}}_{ni})\cdot{\bm{x}}-(b-b_{ni})\Big{|}$
$\displaystyle\qquad+\operatorname{Lip}(R[{f_{c}};\rho])\Big{|}({\bm{a}}-{\bm{a}}_{ni},b-b_{ni})\Big{|}\Big{|}\|\sigma\|_{L^{\infty}(\mathbb{R})}=O(\delta/n)\to
0\quad n\to\infty.$ (63)

Besides, the integrands are uniformly bounded as

$\displaystyle\sup_{{\bm{x}}\in
K}\Big{|}w_{ni}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Big{|}\leq\Big{|}R[{f_{c}};\rho]({\bm{a}},b)\Big{|}\|\sigma\|_{L^{\infty}(\mathbb{R})},\mbox{
for a.e. }({\bm{a}},b)\in Q_{ni}.$ (64)

Therefore, by the dominated convergence theorem for the Bochner integral, we
have

$\displaystyle\|{f_{Q}}-{f_{n}}\|_{C(K)}$ $\displaystyle=\sup_{{\bm{x}}\in
K}\Bigg{|}\sum_{i\in
I_{n}}\int_{Q_{ni}}R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)\mathrm{d}{\bm{a}}\mathrm{d}b-\sum_{i\in
I_{n}}c_{ni}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Bigg{|}$ (65)
$\displaystyle\leq\sum_{i\in I_{n}}\int_{Q_{ni}}\sup_{{\bm{x}}\in
K}\Big{|}R[{f_{c}};\rho]({\bm{a}},b)\sigma({\bm{a}}\cdot{\bm{x}}-b)-w_{ni}\sigma({\bm{a}}_{ni}\cdot{\bm{x}}-b_{ni})\Big{|}\mathrm{d}{\bm{a}}\mathrm{d}b$
(66) $\displaystyle\to 0,\quad n\to\infty.$ (67)

Hence by letting $n$ sufficiently large, we have
$\|{f_{n}}-{f_{Q}}\|_{C(K)}<\varepsilon/3$.

To sum up, we have shonw the $cc$-universality:

$\displaystyle\|f-{f_{n}}\|_{C(K)}\leq\|f-{f_{c}}\|_{C(K)}+\|{f_{c}}-{f_{Q}}\|_{C(K)}+\|{f_{Q}}-{f_{n}}\|_{C(K)}<\varepsilon.$
(68)

∎

#### Notes.

In the proof, we employed a naive discretization based on the regular grids in
$Q$. However, since we know the closed-form expression of the ridgelet
transform, we can discretize it more effectively. For example, a better
discretization scheme is investigated in the so-called _Maurey-Jones-Barron
(MJB) theory_ and the dimension independent _Barron’s bound_ ([see, e.g.,
67]).