A unified Fourier slice method to derive ridgelet transform for a variety of depth-2 neural networks

The integral representation of a depth-2 fully-connected neural network is defined as below.

Here, for each hidden parameter $({\bm{a}},b)$, feature map ${\bm{x}}\mapsto\sigma({\bm{a}}\cdot{\bm{x}}-b)$ corresponds to a single hidden neuron with activation function $\sigma$, weight $\gamma({\bm{a}},b)$ corresponds to an output coefficient, and the integration implies that all the possible neurons are assigned in advance. Since the only free parameter is parameter distribution $\gamma$, we can identify network $S[\gamma]$ with point $\gamma$ in a function space.

We note that this representation covers both infinite (or continuous) and finite widths. Indeed, while the integration may be understood as an infinite width layer, the integration with a finite sum of point masses such as $\gamma_{p}:=\sum_{i=1}^{p}c_{i}\delta_{({\bm{a}}_{i},b_{i})}$ can represent a finite width layer:

where the third term is the so-called “matrix” representation with matrices $A\in\mathbb{R}^{p\times m},C\in\mathbb{R}^{1\times p}$ and vector $\bm{b}\in\mathbb{R}^{p}$ followed by component-wise activation $\sigma$. Singular measures as above can be mathematically justified without any inconsistency if the class of the parameter distributions are set to a class of Borel measures or Schwartz distributions.

There are at least four advantages to introducing integral representations:

1. (1)

   Aggregation of parameters, say $\{({\bm{a}}_{i},b_{i},c_{i})\}_{i=1}^{p}$, into a single function (parameter distribution) $\gamma({\bm{a}},b)$,

2. (2)

   Ability to represent finite models and continuous models in the same form,

3. (3)

   Linearization of networks and convexification of learning problems, and

4. (4)

   Presence of the ridgelet transform.

Advantages 1 and 2 have already been explained. Advantage 3 is described in the next subsection, and Advantage 4 is emphasized throughout the paper. On the other hand, there are two disadvantages:

1. (1)

   Extensions to deep networks are hard¹¹1Good News: After the initial submission of this manuscript, the authors have successfully developed the ridgelet transform for deep networks in Sonoda et al. (2023a, b)., and

2. (2)

   Advanced knowledge on functional analysis are required.

The third advantage of the integral representation is the so-called linearization (and convexification) tricks. That is, while the network is nonlinear with respect to the raw parameters ${\bm{a}}$ and $b$, namely,

(and similarly for $b$), it is linear with respect to the parameter distribution $\gamma$, namely,

Furthermore, linearizing neural networks leads to convexifying learning problems. Specifically, for a convex function $\ell:\mathbb{R}\to\mathbb{R}$, the loss function defined as $L[\gamma]:=\ell(S[\gamma])$ satisfies the following:

It may sound paradoxical that a convex loss function on a function space has local minima in raw parameters, but we can understand this through the chain rule for functional derivative: Suppose that a parameter distribution $\gamma$ is parametrized by a raw parameter, say $\theta$, then

In other words, a local minimum ($\partial_{\theta}L=0$) in raw parameter $\theta$ can arise not only from the global optimum ($\partial_{\gamma}L=0$) but also from the case when two derivatives $\partial_{\theta}\gamma$ and $\partial_{\gamma}L$ are orthogonal.

The trick of lifting nonlinear objects in a linear space has been studied since the age of Frobenius, one of the founders of the linear representation theory of groups. In the context of neural network study, as well as the recent studies mentioned above, either the integral representation by Barron (1993) or the convex neural network by Bengio et al. (2006) are often referred. In the context of deep learning theory, this linearization/convexification trick has been employed to show the global convergence of the SGD training of shallow ReLU networks (Nitanda and Suzuki, 2017; Chizat and Bach, 2018; Mei et al., 2018; Rotskoff and Vanden-Eijnden, 2018; Sirignano and Spiliopoulos, 2020; Suzuki, 2020; Nitanda et al., 2022), and to characterize parameters in ReLU networks (Savarese et al., 2019; Ongie et al., 2020; Parhi and Nowak, 2021; Unser, 2019).

The fourth advantage of the integral representation is the so-called the ridgelet transform $R$, or a right inverse operator of the integral representation operator $S$. For example, the ridgelet transform for depth-2 fully-connected network (1) is given as below.

In principle, the ridgelet function $\rho$ can be chosen independently of the activation function $\sigma$ of neural network $S$. The following theorem holds.

From the perspective of neural network theory, the reconstruction formula claims a detailed/constructive version of the universal approximation theorem. That is, given any target function $f$, as long as $(\!(\sigma,\rho)\!)\neq 0$, the network $S[\gamma]$ with coefficient $\gamma=R[f;\rho]$ reproduces the original function, and the coefficient is given explicit.

From the perspective of functional analysis, on the other hand, the reconstruction formula states that $R$ and $S$ are analysis and synthesis operators, and thus play the same roles as, for instance, the Fourier ($F$) and inverse Fourier ($F^{-1}$) transforms respectively, in the sense that the reconstruction formula $S[R[f;\rho]]=(\!(\sigma,\rho)\!)f$ corresponds to the Fourier inversion formula $F^{-1}[F[f]]=f$.

Despite the common belief that neural network parameters are a blackbox, the closed-form expression (2) of ridgelet transform clearly describes how the network parameters are distributed, which is a clear advantage of the integral representation theory (see e.g. Sonoda et al., 2021a). Moreover, the integral representation theory can deal with a wide range of activation functions without approximation, not only ReLU but all the tempered distribution $\mathcal{S}^{\prime}(\mathbb{R})$ (see e.g. Sonoda and Murata, 2017).

The ridgelet transform is discovered in the late 1990s independently by Murata (1996) and Candès (1998). The term “ridgelet” is named by Candès, based on the facts that the graph of a function ${\bm{x}}\mapsto\rho({\bm{a}}\cdot{\bm{x}}-b)$ is ridge-shaped, and that the integral transform $R$ can be regarded as a multidimensional counterpart of the wavelet transform.

In fact, the ridgelet transform can be decomposed into the composite of wavelet transform after the Radon transform, namely,

where $\SS^{m-1}$ denotes the $m$-dimensional unit sphere, $(\mathbb{R}{\bm{u}})^{\perp}\cong\mathbb{R}^{m-1}$ denotes the orthocomplement of the normal vector ${\bm{u}}\in\SS^{m-1}$, $\mathrm{d}{\bm{y}}$ denotes the Hausdorff measure on $(\mathbb{R}{\bm{u}})^{\perp}$ or the Lebesgue measure on $\mathbb{R}^{m-1}$, and ${\bm{a}}\in\mathbb{R}^{m}$ is represented in polar coordinates ${\bm{a}}=a{\bm{u}}$ with $(a,{\bm{u}})\in\mathbb{R}\times\SS^{m-1}$ allowing the double covering: $(a,{\bm{u}})=(-a,-{\bm{u}})$ (see Sonoda and Murata, 2017, for the proof). Therefore, several authors have remarked that ridgelet analysis is wavelet analysis in the Radon domain (Donoho, 2002; Kostadinova et al., 2014; Starck et al., 2010).

In the context of deep learning theory, Savarese et al. (2019); Ongie et al. (2020); Parhi and Nowak (2021) and Unser (2019) investigate the ridgelet transform for the specific case of fully-connected ReLU layers to establish the representer theorem. Sonoda et al. (2021a) have shown that the parameter distribution of a finite model trained by regularized empirical risk minimization (RERM) converges to the ridgelet spectrum $R[f;\rho]$ in an over-parametrized regime, meaning that we can understand the parameters at local minima to be a finite approximation of the ridgelet transform. In other words, analyzing neural network parameters can be turned to analyzing the ridgelet transform.

On the other hand, one of the major shortcomings of ridgelet analysis is that the closed-form expression is known for relatively small class of networks. Indeed, until Sonoda et al. (2022b, a), it was known only for depth-2 fully-connected layer: $\sigma({\bm{a}}\cdot{\bm{x}}-b)$. In the age of deep learning, a variety of layers have become popular such as the convolution and pooling layers (Fukushima, 1980; LeCun et al., 1998; Ranzato et al., 2007; Krizhevsky et al., 2012). Furthermore, the fully-connected layers on manifolds have also been developed such as the hyperbolic network (Ganea et al., 2018; Shimizu et al., 2021). Since the conventional ridgelet transform was discovered heuristically in the 1990s, and the derivation heavily depends on the specific structure of affine map ${\bm{a}}\cdot{\bm{x}}-b$, the ridgelet transforms for those modern architectures have been unknown for a long time.

In this study, we explain a systematic method to find the ridgelet transforms via the Fourier expression of neural networks, and obtain new ridgelet transforms in a unified manner. The Fourier expression of $S[\gamma]$ is essentially a change-of-frame from neurons $\sigma({\bm{a}}\cdot{\bm{x}}-b)$ to plane waves (or harmonic oscillators) $\exp(i{\bm{x}}\cdot{\bm{\xi}})$. Since the Fourier transform is extensively developed on a variety of domains, once a network $S[\gamma]$ is translated into a Fourier expression, we can systematically find a particular coefficient $\gamma_{f}$ satisfying $S[\gamma_{f}]=f$ via the Fourier inversion formula. In fact, the traditional ridgelet transform is re-discovered. Associated with the change-of-frame in $S[\gamma]$, the ridgelet transform $R[f]$ is also given a Fourier expression, but this form is known as the Fourier slice theorem of ridgelet transform $R[f]$ (see e.g. Kostadinova et al., 2014). Hence, we call our proposed method as the Fourier slice method.

Besides the classical networks, we deal with four types of networks:

1. (1)

   Networks on finite fields $\mathbb{F}_{p}$ in § 3,

2. (2)

   Group convolution networks on Hilbert spaces $\mathcal{H}$ in § 4,

3. (3)

   Fully-connected networks on noncompact symmetric spaces $G/K$ in § 5, and

4. (4)

   Pooling layers (also known as the $d$-plane ridgelet transform) in § 6.

The first three cases are already published thus we only showcase them, while the last case (pooling layer and $d$-plane ridgelet) involves new results.

For all the cases, the reconstruction formula $S[R[f]]=f$ is understood as a constructive proof of the universal approximation theorem for corresponding networks. The group convolution layer case widely extends the ordinary convolution layer with periodic boundary, which is also the main subject of the so-called geometric deep learning (Bronstein et al., 2021). The case of fully-connected layer on symmetric spaces widely extends the recently emerging concept of hyperbolic networks (Ganea et al., 2018; Gulcehre et al., 2019; Shimizu et al., 2021), which can be cast as another geometric deep learning. The pooling layer case includes the original fully-connected layer and the pooling layer; and the corresponding ridgelet transforms include previously developed formulas such as the Radon transform formula by Savarese et al. (2019) and related to the previously developed “$d$-plane ridgelet transforms” by Rubin (2004) and Donoho (2001).

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}$. 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$.

The following procedure is valid, for example, when $\sigma\in\mathcal{S}^{\prime}(\mathbb{R}),\rho\in\mathcal{S}(\mathbb{R}),f\in L^{2}(\mathbb{R}^{m})$ and $\gamma\in L^{2}(\mathbb{R}^{m}\times\mathbb{R})$. See Kostadinova et al. (2014) and Sonoda and Murata (2017) for more details on the valid combinations of function classes.

For any positive integers $n,m$, let $\mathbb{Z}_{n}^{m}:=(\mathbb{Z}/n\mathbb{Z})^{m}$ denote the product of cyclic groups. We note that the set of all real functions $f$ on $\mathbb{Z}_{n}^{m}$ is identified with the ($n\times m$)-dimensional real vector space, i.e. $\{f:\mathbb{Z}_{n}^{m}\to\mathbb{R}\}\cong\mathbb{R}^{n\times m}$, because each value $f(i,j)$ of function $f$ at $(i,j)\in\mathbb{Z}_{n}^{m}$ can be identified with the $(i,j)$th component $a_{ij}$ of vector ${\bm{a}}=(a_{ij})\in\mathbb{R}^{n\times m}$. In particular, $L^{2}(\mathbb{Z}_{n}^{m})=\mathbb{R}^{n\times m}$.

We use the Fourier transform on a product of cyclic groups as below.

The proof is immediate from the so-called orthogonality of characters, an identity $\sum_{g\in\mathbb{Z}_{n}}e^{2\pi ig(t-s)/n}=|\mathbb{Z}_{n}|\delta_{ts}\ (t,s\in\mathbb{Z}_{n})$, where $\delta_{ts}$ being the Kronecker’s $\delta$.

We note that despite the Fourier transform itself can be defined on any cyclic group $\mathbb{Z}_{n}$, namely $n$ needs not be prime, a finite field $\mathbb{F}_{p}(=\mathbb{Z}_{p})$ is assumed to perform the change-of-variables step.

Remarkably, the $\mathbb{F}_{p}$-version of arguments is obtained by formally replacing every integration in the $\mathbb{R}$-version of arguments with summation.

Again, in Yamasaki et al. (2023), it is introduced as a discretized version of a function on a continuous space $\mathbb{R}^{m}$.

In other words, the fully-connected network on finite field $\mathbb{F}_{p}^{m}$ can strictly represent any square integrable function on $\mathbb{F}_{p}^{m}$.

Finally, the following proof shows that a new example of neural networks can be obtained by systematically following the same three steps as in the original arguments.

Since the input to CNNs is a signal (or a function), the Fourier transform corresponding to a naive integral representation is the Fourier transform on the space of signals, which is typically an infinite-dimensional space $\mathcal{H}$ of functions. Although the Fourier transform on the infinite-dimensional Hilbert space has been well developed in the probability theory, the mathematics tends to become excessively advanced for the expected results. One of the important ideas of this study is to induce the Fourier transform of $\mathbb{R}^{m}$ in a finite-dimensional subspace $\mathcal{H}_{m}$ of $\mathcal{H}$ instead of using the Fourier transform on the entire space $\mathcal{H}$. To be precise, we simply take an $m$-dimensional orthonormal frame $F_{m}=\{h_{i}\}_{i=1}^{m}$ of $\mathcal{H}$, put the linear span $\mathcal{H}_{m}:=\operatorname{span}F_{m}=\{\sum_{i=1}^{m}c_{i}h_{i}\mid c_{i}\in\mathbb{R}\}$, and identify each element $f=\sum_{i=1}c_{i}h_{i}\in\mathcal{H}_{m}\subset\mathcal{H}$ with point ${\bm{c}}=(c_{1},\ldots,c_{m})\in\mathbb{R}^{m}$. Obviously, this embedding depends on the choice of $m$-frame $F_{m}$, yet drastically simplifies the main theory itself.

Then, obviously from the construction, we have the following.

Another important idea is to deal with various group convolutions in a uniform manner by using the linear representation of groups.

Here, the integration runs all the possible convolution filters $a$. For the sake of simplicity, however, the domain $\mathcal{H}_{m}$ of filters is restricted to an $m$-dimensional subspace of entire space $\mathcal{H}$.

In the following, $e\in G$ denotes the identity element.

We note that the proposed network is inherently $(G,T)$-equivariant

It is remarkable that the product of $a$ and $x$ inside the $\rho$ is not convolution $a*x$ but scalar product $\langle a,x\rangle$. This is essentially because (1) $f$ will be assumed to be group equivariant, and (2) the network is group equivariant by definition.

In other words, a continuous GCNN can represent any square-integrable group-equivariant function. Again, the proof is performed by systematically following the three steps as below.

General convolution networks for geometric/algebraic domains have been developed for capturing the invariance/equivariance to the symmetry in a data-efficient manner (Bruna and Mallat, 2013; Cohen and Welling, 2016; Zaheer et al., 2017; Kondor and Trivedi, 2018; Cohen et al., 2019; Kumagai and Sannai, 2020). To this date, quite a variety of convolution networks have been proposed for grids, finite sets, graphs, groups, homogeneous spaces and manifolds. We refer to Bronstein et al. (2021) for a detailed survey on the so-called geometric deep learning.

Since a universal approximation theorem (UAT) is a corollary of a reconstruction formula, $S[R[f;\rho]]=(\!(\sigma,\rho)\!)f$, the 3-steps Fourier expression method have provided a variety of UATs for $\sigma(ax-b)$-type networks in a unified manner. Here, we remark that the UATs of individual convolution networks have already shown (Maron et al., 2019; Zhou, 2020; Yarotsky, 2022). However, in addition to above mentioned advantages, the wide coverage of activation functions $\sigma$ is also another strong advantage. In particular, we do not need to rely on the specific features of ReLU, nor need to rely on Taylor expansions/density arguments/randomized assumptions to deal with nonlinear activation functions.

We refer to Helgason (1984, Introduction) and Helgason (2008, Chapter III). A noncompact symmetric space is a homogeneous space $G/K$ with nonpositive sectional curvature on which $G$ acts transitively. Two important examples are hyperbolic space $\mathbb{H}^{m}$ (Figure 1) and SPD manifold $\mathbb{P}_{m}$. See also Appendices A and B for more details on these spaces.

Let $G$ be a connected semisimple Lie group with finite center, and let $G=KAN$ be its Iwasawa decomposition. Namely, it is a unique diffeomorphic decomposition of $G$ into subgroups $K,A$, and $N$, where $K$ is maximal compact, $A$ is maximal abelian, and $N$ is maximal nilpotent. For example, when $G=GL(m,\mathbb{R})$ (general linear group), then $K=O(m)$ (orthogonal group), $A=D_{+}(m)$ (all positive diagonal matrices), and $N=T_{1}(m)$ (all upper triangular matrices with ones on the diagonal).

Let $\mathrm{d}g,\mathrm{d}k,\mathrm{d}a$, and $\mathrm{d}n$ be left $G$-invariant measures on $G,K,A$, and $N$ respectively.

Let $\mathfrak{g},\mathfrak{k},\mathfrak{a}$, and $\mathfrak{n}$ be the Lie algebras of $G,K,A$, and $N$ respectively. By a fundamental property of abelian Lie algebra, both $\mathfrak{a}$ and its dual $\mathfrak{a}^{*}$ are the same dimensional vector spaces, and thus they can be identified with $\mathbb{R}^{r}$ for some $r$, namely $\mathfrak{a}=\mathfrak{a}^{*}=\mathbb{R}^{r}$. We call $r:=\dim\mathfrak{a}$ the rank of $X$. For example, when $G=GL(m,\mathbb{R})$, then $\mathfrak{g}=\mathfrak{gl}_{m}=\mathbb{R}^{m\times m}$ (all $m\times m$ real matrices), $\mathfrak{k}=\mathfrak{o}_{m}$ (all skew-symmetric matrices), $\mathfrak{a}=D(m)$ (all diagonal matrices), and $\mathfrak{n}=T_{0}(m)$ (all strictly upper triangular matrices).

We further introduce three geometric objects in noncompact symmetric space $G/X$. In comparison to Euclidean space $\mathbb{R}^{m}$, the boundary $\partial X$ corresponds to “the set of all infinite points” $\lim_{r\to+\infty}\{r{\bm{u}}\mid|{\bm{u}}|=1,{\bm{u}}\in\mathbb{R}^{m}\}$, a horosphere $\xi$ through point $x\in X$ with normal $u\in\partial X$ corresponds to a straight line ${\bm{\xi}}$ through point ${\bm{x}}\in\mathbb{R}^{m}$ with normal ${\bm{u}}\in\SS^{m-1}$, and the vector distance $\langle x,u\rangle$ between origin $o\in X$ and horosphere $\xi(x,u)$ corresponds to the Riemannian distance between origin $\mathbf{0}\in\mathbb{R}^{m}$ and straight line ${\bm{\xi}}({\bm{x}},{\bm{u}})$.