Neural Fourier Transform: A General Approach to Equivariant Representation Learning

We would also like to try alleviating the following concern about our title.

I find the title "Neural Fourier Transform" a bit misleading, as the Fourier transform is an extremely general signal processing tool, where in this work it is used as an example of finding linear representations of a group.

As we describe in Section 2, we introduce NFT as an extension of FT, which is mathematically formulated with linear representation of a group. In an effort to better justify NFT as a general extension of FT, we would like to further elaborate Section 2 by associating each component of DFT with a notion of group representation, and show that DFT is in fact about linear representations of a group. First, we would like to recall that DFT is defined in signal processing as the linear map $\Phi : f \in C^T \to \hat{f} \in C^T$, where

$f[j] = \frac{1}{\sqrt{T}} \sum_{k=0}^{T-1} e^{2\pi i \frac{kj}{T}} \hat{f}[k]$ and $\hat{f}[k] =\frac{1}{\sqrt{T}} \sum_{j=0}^{T-1} e^{- 2\pi i \frac{kj}{T}} f[j]$

and the map $\Phi$ is usually described by a DFT matrix $[DFT]$, so that $\Phi(f) = [DFT]f = \hat{f}$.

Frequency:

First, we would like to begin by interpreting DFT as a case of a change of basis operation from standard basis $B$ to a new basis $\hat B$. If the standard basis consists of $e_i$(one hot vector for $i$th coordinate), then $\hat B$ can be read from the entries of IDFT. Namely, the $k$th vector of $\hat B$ is given by $v_k = \frac{1}{\sqrt{T}}[e^{ 2 \pi i kj /T} ; j=0:T]$. Because the $k$th coordinate under DFT is called the $k$th frequency, we are safe to identify $span(v_k)$ or $v_k$ itself with the $k$th frequency.

As we explain above eq.(2) in the manuscript, $v_k$ has a special property with respect to “shift” action (cyclic group) . Namely, if $(m \circ v)[j] = v[ (j-m)mod\ T]$ is the shift by $m$ coordinates, then $m \circ v_k = e^{2\pi i m k /T} v_k$ for all $m$. Note that $m$-shift can be expressed as a shift matrix $[M_m]$ (permutation matrix) in the standard basis, and $m \to [M_m]$ is a group representation. This means that $[M_m] v_k = e^{2\pi i m k /T} v_k$ and $v_k$ is an eigenvector for the shift operation of all sizes. Thus the $k$th frequency can be regarded as a one dimensional $k$th eigenspace, which in group representation is called “irreducible representation”. This way, the $k$th frequency is the $k$th irreducible representation, and DFT emerges as decomposition of a signal into irreducible representations (frequencies) via $f = \sum_k \hat f[k] v_k$.

Filter:

In signal processing, filter is used as a major tool in application of DFT, and its basic form functions by deciding a set of frequencies $S$ and using $f_S =\sum_{k \in S} \hat f[k] v_k$ to approximate $f$. When $S$ is chosen from low frequencies, this operation is called “low-pass filter”. Now, with the association of the frequency to irreducible representation, this is equivalent to choosing the set of irreducible representations $S$. In the context of classic FT, theorem 4.2 claims that when the output dimension of $\Phi$ is restricted and when $S$ is not specified, the MSE loss in NFT tends to train $(\Phi, \Psi)$ so that $\Psi \Phi (f) = f_S$, where $S$ is chosen to be able to best reconstruct the signal $f$ from $f_S$.

Neural FT vs FT :

So far, we have described FT as a transform that decomposes a signal into irreducible representations, when the action on the signal is linear/known. Now, as we state in our work, the mission of our research is to decompose a signal into irreducible representations when the action is possibly nonlinear/unknown/partially known. When the action is nonlinear/unknown, we need two modifications to the classic FT: (1) allowing $\Phi$ to be nonlinear and (2) learning the Fourier basis $\hat B$ from the observations. Indeed, when the action is known and linear, $\Phi$ in our framework agrees by definition with that of FT (More particularly, the case of g-NFT with linear action). This is indeed the way we constructed our NFT.

This discussion extends naturally to the case of continuous FT. Please also see (Clausen and Baum, Fast Fourier transforms, 1993) and (Fourier Analysis on Groups, Walter Rudin) for more detailed group-theoretic explanation of FT. We hope this explanation better justifies our title.

Thank you very much for the feedback. We would like to respond to the weakness concerns and questions below.

The experiments could have been detailed a bit more clearly. I.e., what are the objectives, the loss functions used, the in/outputsmathematicall to the model, etc. How did you combine the autoencoder framework with the downstream (e.g. classification) objective? Did you have to weight the two objectives? How did you find the hyperparameters?

We are sorry for the lack of clarity about the objectives in the experimental section. We changed the wording in the experimental section and added more elaborations in the Appendix D. As we describe in Appendix D, the inputs to $\Phi$ are time series in 5.1, and the inputs are image arrays in 5.2.

In the OOD experiment of the classification of rotated images section 5.2, $(\Phi, \Psi)$ and classifiers are 'not' trained at the same time. Instead, NFT is used as an unsupervised representation learning method, and we separately trained the linear classifier to be applied to the learned representation $\Phi(X)$.
More particularly, we first trained the autoencoder $\Phi, \Psi$ using g-NFT on the pairs of images on the in-distribution dataset as described in section 3. After then, with the 'fixed' trained pair $(\Phi, \Psi)$, we computed the logistic regression problem of minimizing the Cross Entropy Loss about the regression weight $W$ on the test (out of distributions) set. $CrossEntropy(SoftMax(W^T\Phi(X)), Class(X)).$

In our comparison to SteerableCNN, however, we first trained the Steerable network by minimizing $CrossEntropy(SoftMax(W^T SteerableNet(X)), Class(X))$ over both the parameters of the SteerableNet and $W$ on the training set, and “fine tuned” the $W$ part on the test set to evaluate the OOD performance.

As we explain in the Appendix Section(D.4), we also optimized the hyperparameters using Optuna Software. We made the reference to Appendix in the main manuscript as well.

Do you have an idea of how to get the tuples of nonlinear group actions in the wild?

We believe that tuples of nonlinear group actions can be obtained for example from the video sequences or, from the observation of dynamical systems in which the underlying group actions are group driven, such as robot arms or other physical systems in the wild. When the videos are sampled with relatively high temporal resolution, the transitions over triplet shall be small enough to be able to satisfy our constant velocity assumption over triplet/tuple $(x , g\circ x, g^2 \circ x)$
Also, when the camera position is known in the 2D rendering of the 3D object, or more generally, in the sim2real setting, we shall be able to obtain the information about the acting group element $g$ and hence obtain the dataset of form $(x, g\circ x)$ together with $g$ to perform g-NFT.

Thank you very much for the comment! In Theorem 4.2 of the original manuscript, we stated to seek $(\Phi^*, \Psi^*)$ “among the set of autoencoders of a fixed latent dimension that can linearlize the actions in the latent space.” We are sorry for the confusion that might have been caused by this expression. By the phrase “an autoencoder that can linearlize the actions”, we meant an equivariant autoencoder $(\Phi, \Psi)$ for which there is $M(g)$ such that $\Phi(g \circ X) = M(g) \Phi(X)$ for each $g$. Indeed, we are therefore discussing here the minimization of the loss over the restricted pool of equivariant $(\Phi, \Psi)$ with fixed latent dimensions and linear latent action. We reworded this part in the revision.

Thank you very much for the positive feedback and comments. Thank you for pointing out the typography; we checked again the manuscript and fixed the typos in the revision.

In U-NFT and G-NFT setting, the trained model shall share the same property as in MSP(Miyato et al) in terms of intra-orbital homogeneity and inter-orbital homogeneity, given the same condition regarding the continuity and the compactness of the group assumed in their statements.
When the algorithm “finds' ' one equivariant solution with invertible autoencoder, however, our theory (in particular, Theorem 4.1) does guarantee that it is the unique equivariant solution up-to G-isomorphism. Meanwhile, g-NFT setting has the guarantee of enjoying the full equivariance when the datasets are sufficiently large, because g-NFT pre-defines the representation to be shared across different orbits.

Thank you very much for the feedback. We would like to make several comments in response to the concern below about the applicability of our method.

The primary weakness of this paper is that it relies on data triplets of tuples that gives a sense of the underlying group action. This is a weakness, since such data isn't easily available in most real-world settings. This is also the reason why the paper pivots to applications in time series in the experimental section.

• Datasets with underlying group action

Indeed, the theory of NFT requires that there is some group action that can describe the transformation between a pair of observations, and NFT learns the structure derived from the underlying group.
We believe that such datasets may occur in nature, for example, when the dataset is derived from 3D space; much structure of such datasets may be described implicitly by SE(3) or SO(3), just like how translations-based structures in the natural images play an important role as evidenced by the success of CNN. 　

Also, as mentioned in the related works section (Sec 6), Koopman-operator-based approaches are much related to our framework as well especially when the transitions are invertible, and applications to the physical systems investigated by these methods are also within the scope of NFT.

• Scope of Datasets

We would like to note that, depending on the level of inductive bias, we do not necessarily need a dataset that is of time series form. For example, in the example of 2D rendering of 3D objects (Sec 5.2), we are using a pair $(x , g\circ x)$ with the information of $g$. This type of information is available in Sim2Real situations, for example. We believe that we can also obtain this type of dataset from experiments concerned with control, such as those involving robots. We would also like to point out that the task in the rendering example is not necessarily of time series as well, because the task here is to predict a rendering from a given angle.

While not cited, there is quite some work on non-neural variants of this, such as by Reisert and Bukhardt, JMLR 2007

Thank you for pointing out the related result; however, we did indeed cite this work in the related work section (Section 6)!