# Polynomial Width is Sufficient for Set Representation with High-dimensional
Features

Peihao Wang1∗, Shenghao Yang 3, Shu Li 4, Zhangyang Wang 1, Pan Li2,4
1University of Texas at Austin, 2Georgia Tech, 3University of Waterloo,
4Purdue University
<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>Correspondence to: Peihao Wang
and Pan Li.

###### Abstract

Set representation has become ubiquitous in deep learning for modeling the
inductive bias of neural networks that are insensitive to the input order.
DeepSets is the most widely used neural network architecture for set
representation. It involves embedding each set element into a latent space
with dimension $L$, followed by a sum pooling to obtain a whole-set embedding,
and finally mapping the whole-set embedding to the output. In this work, we
investigate the impact of the dimension $L$ on the expressive power of
DeepSets. Previous analyses either oversimplified high-dimensional features to
be one-dimensional features or were limited to analytic activations, thereby
diverging from practical use or resulting in $L$ that grows exponentially with
the set size $N$ and feature dimension $D$. To investigate the minimal value
of $L$ that achieves sufficient expressive power, we present two set-element
embedding layers: (a) linear + power activation (LP) and (b) linear +
exponential activations (LE). We demonstrate that $L$ being
$\operatorname{poly}(N,D)$ is sufficient for set representation using both
embedding layers. We also provide a lower bound of $L$ for the LP embedding
layer. Furthermore, we extend our results to permutation-equivariant set
functions and the complex field.

##  1 Introduction

Enforcing invariance into neural network architectures has become a widely-
used principle to design deep learning models [1, 2, 3, 4, 5, 6, 7]. In
particular, when a task is to learn a function with a set as the input, the
architecture enforces permutation invariance that asks the output to be
invariant to the permutation of the input set elements [8, 9]. Neural networks
to learn a set function have found a variety of applications in particle
physics [10, 11], computer vision [12, 13] and population statistics [14, 15,
16], and have recently become a fundamental module (the aggregation operation
of neighbors’ features in a graph [17, 18, 19]) in graph neural networks
(GNNs) [20, 21] that show even broader applications.

Previous works have studied the expressive power of neural network
architectures to represent set functions [8, 9, 22, 23, 24, 25, 26]. Formally,
a set with $N$ elements can be represented as
$\mathcal{S}=\\{\boldsymbol{x}^{(1)},\cdots,\boldsymbol{x}^{(N)}\\}$ where
$\boldsymbol{x}^{(i)}$ is in a feature space $\mathcal{X}$, typically
$\mathcal{X}={}^{D}$. To represent a set function that takes $\mathcal{S}$ and
outputs a real value, the most widely used architecture DeepSets [9] follows
Eq. (1).

$\displaystyle
f(\mathcal{S})=\rho\left(\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})\right),\text{where
$\phi:\mathcal{X}\rightarrow{}^{L}$ and $\rho:{}^{L}\rightarrow\real$ are
continuous functions.}$ (1)

DeepSets encodes each set element individually via $\phi$, and then maps the
encoded vectors after sum pooling to the output via $\rho$. The continuity of
$\phi$ and $\rho$ ensure that they can be well approximated by fully-connected
neural networks [27, 28], which has practical implications. DeepSets enforces
permutation invariance because of the sum pooling, as shuffling the order of
$\boldsymbol{x}^{(i)}$ does not change the output. However, the sum pooling
compresses the whole set into an $L$-dimension vector, which places an
information bottleneck in the middle of the architecture. Therefore, a core
question on using DeepSets for set function representation is that given the
input feature dimension $D$ and the set size $N$, what the minimal $L$ is
needed so that the architecture Eq. (1) can represent/universally approximate
any continuous set functions. The question has attracted attention in many
previous works [9, 23, 24, 25, 26] and is the focus of the present work.

Table 1: A comprehensive comparison among all prior works on expressiveness analysis with $L$. Our results achieve the tightest bound on $L$ while being able to analyze high-dimensional set features and extend to the equivariance case. Prior Arts | $L$ | $D>1$ | Exact Rep. | Equivariance
---|---|---|---|---
DeepSets [9] | $N+1$ | ✗ | ✓ | ✓
Wagstaff et al. [23] | $N$ | ✗ | ✓ | ✓
Segol et al. [25] | ${N+D\choose N}-1$ | ✓ | ✗ | ✓
Zweig & Bruna [26] | $\exp(\min\\{\sqrt{N},D\\})$ | ✓ | ✗ | ✗
Our results | $\operatorname{poly}(N,D)$ | ✓ | ✓ | ✓

An extensive understanding has been achieved for the case with one-dimensional
features ($D=1$). Zaheer et al. [9] proved that this architecture with
bottleneck dimension $L=N$ suffices to _accurately_ represent any continuous
set functions when $D=1$. Later, Wagstaff et al. proved that accurate
representations cannot be achieved when $L<N$ [23] and further strengthened
the statement to _a failure in approximation_ to arbitrary precision in the
infinity norm when $L<N$ [24].

However, for the case with high-dimensional features ($D>1$), the
characterization of the minimal possible $L$ is still missing. Most of
previous works [9, 25, 29] proposed to generate multi-symmetric polynomials to
approximate permutation invariant functions [30]. As the algebraic basis of
multi-symmetric polynomials is of size $L^{*}={N+D\choose N}-1$ [31]
(exponential in $\min\\{D,N\\}$), these works by default claim that if $L\geq
L^{*}$, $f$ in Eq. 1 can approximate any continuous set functions, while they
do not check the possibility of using a smaller $L$. Zweig and Bruna [26]
constructed a set function that $f$ requires bottleneck dimension
$L>N^{-2}\exp(O(\min\\{D,\sqrt{N}\\}))$ (still exponential in
$\min\\{D,\sqrt{N}\\}$) to approximate while it relies on the condition that
$\phi,\rho$ only adopt analytic activations. This condition is overly strict,
as most of the practical neural networks allow using non-analytic activations,
such as ReLU. Zweig and Bruna thus left an open question _whether the
exponential dependence on $N$ or $D$ of $L$ is still necessary if $\phi,\rho$
allow using non-analytic activations._

Present work. The main contribution of this work is to confirm a negative
response to the above question. Specifically, we present the first theoretical
justification that $L$ being _polynomial_ in $N$ and $D$ is sufficient for
DeepSets (Eq. (1)) like architecture to represent any _continuous_ set
functions with _high-dimensional_ features ($D>1$). To mitigate the gap to the
practical use, we consider two architectures to implement feature embedding
$\phi$ (in Eq. 1) and specify the bounds on $L$ accordingly:

  * •

$\phi$ adopts a linear layer with power mapping: The minimal $L$ holds a lower
bound and an upper bound, which is $N(D+1)\leq L<N^{5}D^{2}$.

  * •

$\phi$ adopts a linear layer plus an exponential activation function: The
minimal $L$ holds a tighter upper bound $L\leq N^{4}D^{2}$.

We prove that if the function $\rho$ could be any continuous function, the
above two architectures reproduce the precise construction of any set
functions for high-dimensional features $D>1$, akin to the result in [9] for
$D=1$. This result contrasts with [25, 26] which only present approximating
representations. If $\rho$ adopts a fully-connected neural network that allows
approximation of any continuous functions on a bounded input space [27, 28],
then the DeepSets architecture $f(\cdot)$ can approximate any set functions
universally on that bounded input space. Moreover, our theory can be easily
extended to permutation-equivariant functions and set functions in the complex
field, where the minimal $L$ shares the same bounds up to some multiplicative
constants.

Another comment on our contributions is that Zweig and Bruna [26] use
difference in the needed dimension $L$ to illustrate the gap between DeepSets
[9] and Relational Network [32] in their expressive powers, where the latter
encodes set elements in a pairwise manner rather than in an element-wise
separate manner. The gap well explains the empirical observation that
Relational Network achieves better expressive power with smaller $L$ [33, 23].
Our theory does not violate such an observation while it shows that the gap
can be reduced from an exponential order in $N$ and $D$ to a polynomial order.
Moreover, many real-world applications have computation constraints where only
DeepSets instead of Relational Network can be used, e.g., the neighbor
aggregation operation in GNN being applied to large networks [21], and
hypergraph neural diffusion operations in hypergraph neural networks [7]. Our
theory points out that in this case, it is sufficient to use polynomial $L$
dimension to embed each element, while one needs to adopt a function $\rho$
with non-analytic activitions.

##  2 Preliminaries

###  2.1 Notations and Problem Setup

We are interested in the approximation and representation of functions defined
over sets 111In fact, we allow repeating elements in $\mathcal{S}$, therefore,
$\mathcal{S}$ should be more precisely called multiset. With a slight abuse of
terminology, we interchangeably use terms multiset and set throughout the
whole paper.. In convention, an $N$-sized set
$\mathcal{S}=\\{\boldsymbol{x}^{(1)},\cdots,\boldsymbol{x}^{(N)}\\}$, where
$\boldsymbol{x}^{(i)}\in{}^{D},\forall i\in[N](\triangleq\\{1,2,...,N\\})$,
can be denoted by a data matrix
$\boldsymbol{X}=\begin{bmatrix}\boldsymbol{x}^{(1)}&\cdots&\boldsymbol{x}^{(N)}\end{bmatrix}^{\top}\in{}^{N\times
D}$. Note that we use the superscript ${(i)}$ to denote the $i$-th set element
and the subscript $i$ to denote the $i$-th column/feature channel of
$\boldsymbol{X}$, i.e.,
$\boldsymbol{x}_{i}=\begin{bmatrix}x_{i}^{(1)}&\cdots&x_{i}^{(N)}\end{bmatrix}^{\top}$.
Let $\Pi(N)$ denote the set of all $N$-by-$N$ permutation matrices. To
characterize the unorderedness of a set, we define an equivalence class over
N×D:

######  Definition 2.1 (Equivalence Class).

If matrices $\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$
represent the same set $\mathcal{X}$, then they are called equivalent up a row
permutation, denoted as $\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$. Or
equivalently, $\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$ if and only if there
exists a matrix $\boldsymbol{P}\in\Pi(N)$ such that
$\boldsymbol{X}=\boldsymbol{P}\boldsymbol{X^{\prime}}$.

Set functions can be in general considered as permutation-invariant or
permutation-equivariant functions, which process the input matrices regardless
of the order by which rows are organized. The formal definitions of
permutation-invariant/equivariant functions are presented as below:

######  Definition 2.2.

(Permutation Invariance) A function $f:{}^{N\times
D}\rightarrow{}^{D^{\prime}}$ is called permutation-invariant if
$f(\boldsymbol{P}\boldsymbol{X})=f(\boldsymbol{X})$ for any
$\boldsymbol{P}\in\Pi(N)$.

######  Definition 2.3.

(Permutation Equivariance) A function $f:{}^{N\times D}\rightarrow{}^{N\times
D^{\prime}}$ is called permutation-equivariant if
$f(\boldsymbol{P}\boldsymbol{X})=\boldsymbol{P}f(\boldsymbol{X})$ for any
$\boldsymbol{P}\in\Pi(N)$.

In this paper, we investigate the approach to designing a neural network
architecture with permutation invariance/equivariance. Below we will first
focus on permutation-invariant functions $f:{}^{N\times D}\rightarrow\real$.
Then, in Sec. 5, we show that we can easily extend the established results to
permutation-equivariant functions through the results provided in [34, 7] and
to the complex field. The obtained results for $D^{\prime}=1$ can also be
easily extended to $D^{\prime}>1$ as otherwise $f$ can be written as
$\begin{bmatrix}f_{1}&\cdots&f_{D^{\prime}}\end{bmatrix}^{\top}$ and each
$f_{i}$ has single output feature channel.

###  2.2 DeepSets and The Proof for the One-Dimensional Case ($D=1$)

The seminal work [9] establishes the following result which induces a neural
network architecture for permutation-invariant functions.

######  Theorem 2.4 (DeepSets [9], $D=1$).

A continuous function $f:{}^{N}\rightarrow\real$ is permutation-invariant
(i.e., a set function) if and only if there exists continuous functions
$\phi:\real\rightarrow{}^{L}$ and $\rho:{}^{L}\rightarrow\real$ such that
$f(\boldsymbol{X})=\rho\left(\sum_{i=1}^{N}\phi(x^{(i)})\right)$, where $L$
can be as small as $N$. Note that, here $x^{(i)}\in\real$.

######  Remark 2.5.

The original result presented in [9] states the latent dimension should be as
large as $N+1$. [23] tighten this dimension to exactly $N$.

Theorem 2.4 implies that as long as the latent space dimension $L\geq N$, any
permutation-invariant functions can be implemented in a unified manner as
DeepSets (Eq.(1)). Furthermore, DeepSets suggests a useful architecture for
$\phi$ at the analysis convenience and empirical utility, which is formally
defined below (in DeepSets, $\phi$ is set as $\psi_{L}$):

######  Definition 2.6 (Power mapping).

A power mapping of degree $K$ is a function $\psi_{K}:\real\rightarrow{}^{K}$
which transforms a scalar to a power series:
$\psi_{K}(z)=\begin{bmatrix}z&z^{2}&\cdots&z^{K}\end{bmatrix}^{\top}$.

However, DeepSets [9] focuses on the case that the feature dimension of each
set element is one (i.e., $D=1$). To demonstrate the difficulty of extending
Theorem 2.4 to high-dimensional features, we reproduce the proof next, which
simultaneously reveals its significance and limitation. Some intermediate
results and mathematical tools will be recalled along the way later in our
proof.

We begin by defining sum-of-power mapping (of degree $K$)
$\Psi_{K}(\boldsymbol{X})=\sum_{i=1}^{N}\psi_{K}(x^{(i)})$, where $\psi_{K}$
is the power mapping following Definition 2.6. Afterward, we reveal that sum-
of-power mapping $\Psi_{K}$ has a continuous inverse. Before stating the
formal argument, we formally define the injectivity of permutation-invariant
mappings:

######  Definition 2.7 (Injectivity).

A set function $f:{}^{N\times D}\rightarrow{}^{L}$ is said to be injective if
and only if $\forall\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$,
$f(\boldsymbol{X})=f(\boldsymbol{X^{\prime}})$ implies
$\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$.

As summarized in the following lemma shown by [9] and improved by [23],
$\Psi_{N}$ (i.e., when $K=N$) is an injective mapping. If we further constrain
the image space to be the range of $\Psi_{N}$:
$\mathcal{Z}=\\{\Psi_{N}(\boldsymbol{X}):\forall\boldsymbol{X}\in{}^{N}\\}\subseteq{}^{N}$,
then $\Psi_{N}$ becomes surjective and is shown to have a continuous inverse.
This result comes from homeomorphism between roots and coefficients of monic
polynomials [35].

######  Lemma 2.8 (Existence of Continuous Inverse of Sum-of-Power [9, 23]).

$\Psi_{N}:{}^{N}\rightarrow\mathcal{Z}$ is injective, thus there exists
$\Psi_{N}^{-1}:\mathcal{Z}\rightarrow{}^{N}$ such that
$\Psi_{N}^{-1}\circ\Psi_{N}(\boldsymbol{X})\sim\boldsymbol{X}$. Moreover,
$\Psi_{N}^{-1}$ is continuous.

Now we are ready to prove necessity in Theorem 2.4 as sufficiency is easy to
check. By choosing $\phi=\psi_{N}:\real\rightarrow{}^{N}$ to be the power
mapping (cf. Definition 2.6), and $\rho=f\circ\Psi_{N}^{-1}$. For any scalar-
valued set
$\boldsymbol{X}=\begin{bmatrix}x^{(1)}&\cdots&x^{(N)}\end{bmatrix}^{\top}$,
$\rho\left(\sum_{i=1}^{N}\phi(x^{(i)})\right)=f\circ\Psi_{N}^{-1}\circ\Psi_{N}(\boldsymbol{x})=f(\boldsymbol{P}\boldsymbol{X})=f(\boldsymbol{X})$
for some $\boldsymbol{P}\in\Pi(N)$. The existence and continuity of
$\Psi_{N}^{-1}$ are due to Lemma 2.8.

Theorem 2.4 gives the exact decomposable form [23] for permutation-invariant
functions, which is stricter than approximation error based expressiveness
analysis. In summary, the key idea is to establish a mapping $\phi$ whose
element-wise sum-pooling has a continuous inverse.

###  2.3 Curse of High-dimensional Features ($D\geq 2$)

We argue that the proof of Theorem 2.4 is not applicable to high-dimensional
set features ($D\geq 2$). The main reason is that power mapping defined in
Definition 2.6 only receives scalar input. It remains elusive how to extend it
to a multivariate version that admits injectivity and a continuous inverse. A
plausible idea seems to be applying power mapping for each channel
$\boldsymbol{x}_{i}$ independently, and due to the injectivity of sum-of-power
mapping $\Psi_{N}$, each channel can be uniquely recovered individually via
the inverse $\Psi_{N}^{-1}$. However, we point out that each recovered feature
channel $\boldsymbol{x^{\prime}}_{i}\sim\boldsymbol{x}_{i}$, $\forall
i\in[D]$, does not imply
$\begin{bmatrix}\boldsymbol{x^{\prime}}_{1}&\cdots&\boldsymbol{x^{\prime}}_{D}\end{bmatrix}\sim\boldsymbol{X}$,
where the alignment of features across channels gets lost. Hence, channel-wise
power encoding no more composes an injective mapping. Zaheer et al. [9]
proposed to adopt multivariate polynomials as $\phi$ for high-dimensional
case, which leverages the fact that multivariate symmetric polynomials are
dense in the space of permutation invariant functions (akin to Stone-
Wasserstein theorem) [30]. This idea later got formalized in [25] by setting
$\phi(\boldsymbol{x}^{(i)})=\begin{bmatrix}\cdots&\prod_{j\in[D]}(x_{j}^{(i)})^{\alpha_{j}}&\cdots\end{bmatrix}$
where $\boldsymbol{\alpha}\in\mathbb{N}^{D}$ traverses all
$\sum_{j\in[D]}\alpha_{j}\leq n$ and extended to permutation equivariant
functions. Nevertheless, the dimension $L={N+D\choose D}$, i.e., exponential
in $\min\\{N,D\\}$ in this case, and unlike DeepSets [9] which exactly
recovers $f$ for $D=1$, the architecture in [9, 25] can only approximate the
desired function.

Figure 1: Illustration of the proposed linear + power mapping embedding layer
(LP) and linear + exponential activation embedding layer (LE).

##  3 Main Results

In this section, we present our main result which extends Theorem 2.4 to high-
dimensional features. Our conclusion is that to universally represent a set
function on sets of length $N$ and feature dimension $D$ with the DeepSets
architecture [9] (Eq. (1)), a dimension $L$ at most polynomial in $N$ and $D$
is needed for expressing the intermediate embedding space.

Formally, we summarize our main result in the following theorem.

######  Theorem 3.1 (The main result).

Suppose $D\geq 2$. For any continuous permutation-invariant function
$f:{}^{N\times D}\rightarrow\real$, there exists two continuous mappings
$\phi:{}^{D}\rightarrow{}^{L}$ and $\rho:{}^{L}\rightarrow\real$ such that for
every $\boldsymbol{X}\in{}^{N\times D}$,
$f(\boldsymbol{X})=\rho\left(\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})\right)$
where

  * •

For some $L\in[N(D+1),N^{5}D^{2}]$ when $\phi$ admits linear layer + power
mapping (LP) architecture:

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\psi_{N}(\boldsymbol{w}_{1}^{\top}\boldsymbol{x})^{\top}&\cdots&\psi_{N}(\boldsymbol{w}_{K}^{\top}\boldsymbol{x})^{\top}\end{bmatrix}$
(2)

for some $\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K}\in{}^{D}$, and $K=L/N$.

  * •

For some $L\in[ND,N^{4}D^{2}]$ when $\phi$ admits linear layer + exponential
activation (LE) architecture:

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\exp(\boldsymbol{v}_{1}^{\top}\boldsymbol{x})&\cdots&\exp(\boldsymbol{v}_{L}^{\top}\boldsymbol{x})\end{bmatrix}$
(3)

for some $\boldsymbol{v}_{1},\cdots,\boldsymbol{v}_{L}\in{}^{D}$.

The bounds of $L$ depend on the choice of the architecture of $\phi$, which
are illustrated in Fig. 1. In the LP setting, we adopt a linear layer that
maps each set element into $K$ dimension. Then we apply a channel-wise power
mapping that separately transforms each value in the feature vector into an
$N$-order power series, and concatenates all the activations together,
resulting in a $KN$ dimension feature. The LP architecture is closer to
DeepSets [9] as they share the power mapping as the main component. Theorem
3.1 guarantees the existence of $\rho$ and $\phi$ (in the form of Eq. (2))
which satisfy Eq. (1) without the need to set $K$ larger than $N^{4}D^{2}$
while $K\geq D+1$ is necessary. Therefore, the total embedding size $L=KN$ is
bounded by $N^{5}D^{2}$ above and $N(D+1)$ below. Note that this lower bound
is not trivial as $ND$ is the degree of freedom of the input $\boldsymbol{X}$.
No matter how $\boldsymbol{w}_{1},...,\boldsymbol{w}_{K}$ are adopted, one
cannot achieve an injective mapping by just using $ND$ dimension.

In the LE architecture, we investigate the utilization of the exponential
activation in set representation, which is also a valid activation function to
build deep neural networks [36, 37]. Each set entry will be linearly lifted
into an $L$-dimensional space via a group of weights and then transformed by
an element-wise exponential activation. The advantage of the exponential
function is that the upper bound of $L$ is improved to be $N^{4}D^{2}$. The
lower bound $ND$ for the LE architecture is a trivial bound due to the degree
of freedom of the inputs. Essentially, a linear layer followed by an
exponential function is equivalent to applying monomials onto exponential
activations. If monomial activations are allowed as used in [26, 25], we can
also replace the exponential function with a series of monomial mappings while
yielding the same upper bound. However, in contrast to [26, 25], where
exponentially many monomials are required, our construction of the linear
weights enables a mere reliance on bivariate monomials of degree $D$, thus
reducing the number of needed monomials to $O(N^{2}D)$.

######  Remark 3.2.

The bounds in Theorem 3.1 are non-asymptotic. This implies the latent
dimensions specified by the corresponding architectures are precisely
sufficient for expressing the input.

######  Remark 3.3.

Unlike $\phi$, the form of $\rho$ cannot be explicitly specified, as it
depends on the desired function $f$. The complexity of $\rho$ remains
unexplored in this paper, which may be high in practice.

##### Importance of Continuity.

We argue that the requirements of continuity on $\rho$ and $\phi$ are
essential for our discussion. First, practical neural networks can only
provably approximate continuous functions [27, 28]. Moreover, set
representation without such requirements can be straightforward (but likely
meaningless in practice). This is due to the following lemma.

######  Lemma 3.4 ( [38]).

There exists a discontinuous bijective mapping between D and if $D\geq 2$.

By Lemma 3.4, we can define a bijective mapping $r:{}^{D}\rightarrow\real$
which maps the high-dimensional features to scalars, and its inverse exists.
Then, the same proof of Theorem 2.4 goes through by letting
$\phi=\psi_{N}\circ r$ and $\rho=f\circ r^{-1}\circ\Psi_{N}^{-1}$. However, we
note both $\rho$ and $\phi$ lose continuity.

##### Comparison with Prior Arts.

Below we highlight the significance of Theorem 3.1 in contrast to the existing
literature. A quick overview has been listed in Table 1 for illustration. The
lower bound in Theorem 3.1 corrects a natural misconception that the degree of
freedom (i.e., $L=ND$ for multi-channel cases) is not enough for representing
the embedding space. Fortunately, the upper bound in Theorem 3.1 shows the
complexity of representing vector-valued sets is still manageable as it merely
scales polynomially in $N$ and $D$. Compared with Zweig and Bruna’s finding
[26], our result significantly improves this bound on $L$ from exponential to
polynomial by allowing non-analytic functions to amortize the expressiveness.
Besides, Zweig and Bruna’s proof idea [26] is hard to be applied to the real
domain, while ours are extensible to complex numbers and equivariant
functions.

##  4 Proof Sketch

In this section, we introduce the proof techniques of Theorem 3.1, while
deferring a full version and all missing proofs to the appendix.

The proof of Theorem 3.1 is constructive and mainly consists of three steps
below:

  1. 1.

For the LP architecture, we construct a group of $K$ linear weights
$\boldsymbol{w}_{1}\cdots,\boldsymbol{w}_{K}\in{}^{D}$ with $K\leq
N^{4}D^{2}$, while for the LE architecture, we construct a group of $L$ linear
weights $\boldsymbol{v}_{1}\cdots,\boldsymbol{v}_{L}\in{}^{D}$ with $L\leq
N^{4}D^{2}$, such that the summation over the associated embeddings
$\Phi(\boldsymbol{X})=\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$ is injective.
Moreover, if $K\leq D$ for LP layer or trivially $L<ND$ for LE layer, such
weights do not exist, which induces the lower bounds.

  2. 2.

Given the injectivity of both LP and LE layers, we constrain the image spaces
to be their ranges $\\{\Phi(\boldsymbol{X}):\boldsymbol{X}\in{}^{N\times
D}\\}$, respectively, and thus, the inverse of the sum-pooling $\Phi^{-1}$
exists. Furthermore, we show that $\Phi^{-1}$ is continuous.

  3. 3.

Then the proof of upper bounds can be concluded for both settings by letting
$\rho=f\circ\Phi^{-1}$ since
$\rho\left(\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})\right)=f\circ\Phi^{-1}\circ\Phi(\boldsymbol{X})=f(\boldsymbol{P}\boldsymbol{X})=f(\boldsymbol{X})$
for some $\boldsymbol{P}\in\Pi(N)$.

Next, we elaborate on the construction idea which yields injectivity for both
embedding layers in Sec. 4.1 with the notion of anchor. In Sec. 4.2, we prove
the continuity of the inverse map for LP and LE via arguments similar to [35].

(a)

(b)

(c)

Figure 2: (a) illustrates the overall idea to construct LP and LE embedding
layers and prove their injectivity. In the forward pass, LP and LE will 1)
construct an anchor with redundant non-anchor channels through a linear layer
(Lemma 4.4), 2) and couple each feature channel with the both anchor and non-
anchor channels with the their own coupling schemes, respectively. To prove
injectivity, the implication follows the converse agenda of construction: 1)
by the properties of coupling schemes specified by LP (Lemma 4.5) and LE
(Lemma 4.8) layers, we obtain pairwise equivalence with anchors, 2) and by
union alignment lemma (Lemma 4.3), we recover the global equivalence. (b)(c)
depict the detailed construction inside the LP and LE embedding layers,
respectively. LP embedding layer utilizes linear combination plus a power
mapping to couple feature channels with the anchor(s) and non-anchors, while
LE adopts a linear combination plus an exponential mapping, which is
essentially an exponential function followed by a bivariate monomial. The
constructed components marked in gray represent the redundant pairs between
feature channels and non-anchor channels, which will not be used in the chain
of implication to prove the injectivity.

###  4.1 Injectivity

The intuition of our construction is to introduce additional feature channels
to encode the relative position and alignment across each channel, such that
only if $\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$, the positional
information after the sum-pooling can be reproduced. The high-level ideas of
construction and proofs are illustrated in Fig. 2(a), in which we first
construct an anchor, a mathematical device introduced in Sec. 4.1.1 to induce
injectivity, and then mix each feature channel with the anchor through
coupling schemes specified by LP (Sec. 4.1.2) and LE (Sec. 4.1.3) layers,
respectively.

####  4.1.1 Anchor

Constructing an anchor stands at the core of our proof. Formally, we define
Anchor as below:

######  Definition 4.1 (Anchor).

Consider the data matrix $\boldsymbol{X}\in{}^{N\times D}$, then
$\boldsymbol{a}\in{}^{N}$ is called an anchor of $\boldsymbol{X}$ if
$\boldsymbol{a}_{i}\neq\boldsymbol{a}_{j}$ for any $i,j\in[N]$ such that
$\boldsymbol{x}^{(i)}\neq\boldsymbol{x}^{(j)}$.

In plain language, by Definition 4.1, two entries in the anchor must be
distinctive if the set elements at the corresponding indices are not equal.
Since an anchor reflects the uniqueness of the set entries, one immediate
result holds:

######  Lemma 4.2.

Consider the data matrix $\boldsymbol{X}\in{}^{N\times D}$ and
$\boldsymbol{a}\in{}^{N}$ an anchor of $\boldsymbol{X}$. Then if there exists
$\boldsymbol{P}\in\Pi(N)$ such that
$\boldsymbol{P}\boldsymbol{a}=\boldsymbol{a}$ then
$\boldsymbol{P}\boldsymbol{x}_{i}=\boldsymbol{x}_{i}$ for every $i\in[D]$.

That being said, a permutation matrix aligning anchors also align all feature
columns. As a consequence, the union alignment property can be derived:

######  Lemma 4.3 (Union Alignment).

Consider two data matrices
$\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$,
$\boldsymbol{a}\in{}^{N}$ is an anchor of $\boldsymbol{X}$ and
$\boldsymbol{a^{\prime}}\in{}^{N}$ is an arbitrary vector. If
$\begin{bmatrix}\boldsymbol{a}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{a^{\prime}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix}$
for every $i\in[D]$, then $\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$.

If we pair each channel with the anchor, then once each coupled pairs are
aligned, two data matrices are globally aligned. Our strategy to generate an
anchor is through a point-wise linear combination of each channel. The
following lemma summaries the idea of anchor construction.

######  Lemma 4.4 (Anchor Construction).

There exists a set of weights
$\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K_{1}}$ where
$K_{1}=N(N-1)(D-1)/2+1$ such that for every data matrix
$\boldsymbol{X}\in{}^{N\times D}$, there exists $j\in[K_{1}]$,
$\boldsymbol{X}\boldsymbol{w}_{j}$ is an anchor of $\boldsymbol{X}$.

It implies that with such a group of $N(N-1)(D-1)/2+1$ many linear weights, no
matter the choice of $\boldsymbol{X}\in{}^{N\times D}$, there must exists a
column in $\\{\boldsymbol{X}\boldsymbol{w}_{j}:j\in[K_{1}]\\}$ satisfying
Definition 4.1 .

####  4.1.2 Injectivity of LP

In this section, we specify $\phi$ following the definition in Eq. (2). Having
the notion of anchors, we introduce the linear coupling technique, which leads
to our construction of the LP architecture.

######  Lemma 4.5 (Linear Coupling).

There exists a group of coefficients $\gamma_{1},\cdots,\gamma_{K_{2}}$ where
$K_{2}=N(N-1)+1$ such that the following statement holds: Given any
$\boldsymbol{x},\boldsymbol{x^{\prime}},\boldsymbol{y},\boldsymbol{y^{\prime}}\in{}^{N}$
such that $\boldsymbol{x}\sim\boldsymbol{x^{\prime}}$ and
$\boldsymbol{y}\sim\boldsymbol{y^{\prime}}$, if
$(\boldsymbol{x}-\gamma_{k}\boldsymbol{y})\sim(\boldsymbol{x^{\prime}}-\gamma_{k}\boldsymbol{y^{\prime}})$
for every $k\in[K_{2}]$, then
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.

##### Construction.

Our construction divides the weights $\\{\boldsymbol{w}_{i},i\in[K]\\}$ into
three groups: $\\{\boldsymbol{w}^{(1)}_{i}:i\in[D]\\}$,
$\\{\boldsymbol{w}^{(2)}_{j}:j\in[K_{1}]\\}$, and
$\\{\boldsymbol{w}^{(3)}_{i,j,k}:i\in[D],j\in[K_{1}],k\in[K_{2}]\\}$. Each
block is illustrated in Fig. 2(b) and outlined as below:

  1. 1.

Let the first group of weights
$\boldsymbol{w}^{(1)}_{1}=\boldsymbol{e}_{1},\cdots,\boldsymbol{w}^{(1)}_{D}=\boldsymbol{e}_{D}$
to buffer the original features, where $\boldsymbol{e}_{i}$ is the $i$-th
canonical basis.

  2. 2.

Design the second group of linear weights,
$\boldsymbol{w}^{(2)}_{1},\cdots,\boldsymbol{w}^{(2)}_{K_{1}}$ for $K_{1}$ as
large as $N(N-1)(D-1)/2+1$, following the specifications in Lemma 4.4. Then,
we know at least one of $\boldsymbol{X}\boldsymbol{w}^{(2)}_{j},j\in[K_{1}]$
forms an anchor of $\boldsymbol{X}$.

  3. 3.

Design a group of weights $\boldsymbol{w}^{(3)}_{i,j,k}$ for
$i\in[D],j\in[K_{1}],k\in[K_{2}]$ with $K_{2}=N(N-1)+1$ that mixes each
original channel $\boldsymbol{x}_{i}$ with each
$\boldsymbol{X}\boldsymbol{w}^{(2)}_{j},j\in[K_{1}]$ by
$\boldsymbol{w}^{(3)}_{i,j,k}=\boldsymbol{e}_{i}-\gamma_{k}\boldsymbol{w}^{(2)}_{j}$,
where $\gamma_{k},\forall k\in[K_{2}]$ is the coefficient defined in Lemma
4.5.

##### Injectivity.

With such configuration, injectivity can be shown by the following steps:
First recalling the injectivity of power mapping (cf. Lemma 2.8), we have:

$\displaystyle\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})=\sum_{n=1}^{N}\phi(\boldsymbol{x^{\prime}}^{(n)})\Rightarrow\boldsymbol{X}\boldsymbol{w}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}_{i},\forall
i\in[K].$ (4)

It is equivalent to expand the RHS of Eq. (4) as:
$\boldsymbol{x}_{i}\sim\boldsymbol{x^{\prime}}_{i}$,
$\boldsymbol{X}\boldsymbol{w}^{(2)}_{j}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j}$,
and
$\boldsymbol{X}\boldsymbol{w}^{(3)}_{i,j,k}=(\boldsymbol{x}_{i}-\gamma_{k}\boldsymbol{X}\boldsymbol{w}^{(2)}_{j})\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(3)}_{i,j^{*},k}=(\boldsymbol{x^{\prime}}_{i}-\gamma_{k}\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j})$
for every $i\in[D],j\in[K_{1}],k\in[K_{2}]$. By Lemma 4.5, we can further
induce:

$\displaystyle\boldsymbol{X}\boldsymbol{w}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}_{i},\forall
i\in[K]\Rightarrow\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}^{(2)}_{j}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix},\forall
i\in[D],j\in[K_{1}]$ (5)

According to Lemma 4.4, there must be $j^{*}\in[K_{1}]$ such that
$\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}$ is an anchor of $\boldsymbol{X}$.
Then by Lemma 4.3, Eq. (5) implies:

$\displaystyle\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix},\forall
i\in[D]\Rightarrow\boldsymbol{X}\sim\boldsymbol{X^{\prime}}.$ (6)

The total required number of weights $K=D+K_{1}+DK_{1}K_{2}\leq N^{4}D^{2}$,
and the embedding length $L=NK\leq N^{5}D^{2}$ as desired.

For completeness, we add the following lemma which implies LP-induced sum-
pooling is injective only if $K\geq D+1$, when $D\geq 2$.

######  Theorem 4.6 (Lower Bound).

Consider data matrices $\boldsymbol{X}\in{}^{N\times D}$ where $D\geq 2$. If
$K\leq D$, then for every $\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K}$,
there exists $\boldsymbol{X^{\prime}}\in{}^{N\times D}$ such that
$\boldsymbol{X}\not\sim\boldsymbol{X^{\prime}}$ but
$\boldsymbol{X}\boldsymbol{w}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}_{i}$
for every $i\in[K]$.

######  Remark 4.7.

Theorem 4.6 is significant in that with high-dimensional features, the
injectivity is provably not satisfied when the embedding space has a dimension
equal to the degree of freedom.

####  4.1.3 Injectivity of LE

In this section, we consider $\phi$ follows the definition in Eq. (3). The key
observation is that each term in the RHS of Eq. (3) can be rewritten as a
monomial of an exponential function:

$\displaystyle\exp(\boldsymbol{v}^{\top}\boldsymbol{x})=\exp(\boldsymbol{u}^{\top}\log(\exp(\boldsymbol{\Omega}^{\top}\boldsymbol{x})))=\prod_{k=1}^{K_{1}+D}\exp(\boldsymbol{\Omega}\boldsymbol{x})_{k}^{\boldsymbol{u}_{k}},$
(7)

where the exponential and the logarithm are taken element-wisely,
$\boldsymbol{v}=\boldsymbol{\Omega}\boldsymbol{u}$ for some
$\boldsymbol{\Omega}\in{}^{D\times(K_{1}+D)}$, and
$\boldsymbol{u}\in{}^{K_{1}+D}$. Recall that $K_{1}$ is the needed dimension
to construct an anchor as shown in Lemma 4.4. Then, the assignment of
$\boldsymbol{v}_{1},\cdots,\boldsymbol{v}_{L}$ amounts to specifying the
exponents for $D$ power functions within the product. Specifically, we choose
$\boldsymbol{v}$, $\boldsymbol{\Omega}$, $\boldsymbol{u}$ as follows.

##### Construction.

We first reindex and rewrite $\\{\boldsymbol{v}_{i}:i\in[L]\\}$ as
$\\{\boldsymbol{v}_{i,j,p,q}=\boldsymbol{\Omega}\boldsymbol{u}_{i,j,p,q}:i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]\\}$,
where
$\boldsymbol{\Omega}=\begin{bmatrix}\boldsymbol{w}^{(1)}_{1}&\cdots&\boldsymbol{w}^{(1)}_{D}&\boldsymbol{w}^{(2)}_{1}&\cdots&\boldsymbol{w}^{(2)}_{K_{1}}\end{bmatrix}\in{}^{D\times(D+K_{1})}$
and $\boldsymbol{u}_{i,j,p,q}\in{}^{D+K_{1}}$ are specified as below. In Fig.
2(c), we depict the forward pass of an LE layer.

  1. 1.

The choice of weights $\boldsymbol{\Omega}$ follows from the construction of
the LP layer, i.e., $\boldsymbol{w}^{(1)}_{i}=\boldsymbol{e}_{i},\forall
i\in[D]$ and $\\{\boldsymbol{w}^{(2)}_{j}:\forall j\in[K_{1}]\\}$ with
$K_{1}=N(N-1)(D-1)/2+1$ are drawn according to Lemma 4.4 so that an anchor is
guaranteed to be produced.

  2. 2.

Design a group of weights
$\boldsymbol{U}=\begin{bmatrix}\cdots&\boldsymbol{u}_{i,j,p,q}&\cdots\end{bmatrix}\in{}^{(D+K_{1})\times
N(N+3)/2}$ for $i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$ such that
$\boldsymbol{u}_{i,j,p,q}=(q-1)\boldsymbol{e}_{i}+(p-q+1)\boldsymbol{e}_{D+j}$.

##### Injectivity.

To show the injectivity of LE, we need the following lemma:

######  Lemma 4.8 (Monomial Coupling).

For any pair of vectors
$\boldsymbol{x},\boldsymbol{y},\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}}\in{}^{N}$,
if
$\sum_{n\in[N]}\boldsymbol{x}_{n}^{l-k}\boldsymbol{y}_{n}^{k}=\sum_{n\in[N]}\boldsymbol{x^{\prime}}_{n}^{l-k}\boldsymbol{y^{\prime}}_{n}^{k}$
for every $l\in[N]$, $0\leq k\leq l$, then
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.

Plugging $\boldsymbol{\Omega}$ and $\boldsymbol{U}$ into Eq. (7), we can
examine each output dimension of the embedding layer:

$\displaystyle\left[\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})\right]_{i,j,p,q}=\sum_{n=1}^{N}\exp(\boldsymbol{x}_{i})_{n}^{q-1}\exp(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j})_{n}^{p-q+1},$
(8)

Then by Lemma 4.8, we have:

$\displaystyle\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})=\sum_{n=1}^{N}\phi(\boldsymbol{x^{\prime}}^{(n)})\Rightarrow$
$\displaystyle\begin{bmatrix}\exp(\boldsymbol{x}_{i})&\exp(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j})\end{bmatrix}\sim\begin{bmatrix}\exp(\boldsymbol{x^{\prime}}_{i})&\exp(\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j})\end{bmatrix},$
(9) $\displaystyle\forall i\in[D],j\in[K_{2}].$

With above implication, the proof can be concluded via the following steps:
Lemma 4.4 guarantees the existence of $j^{*}\in[K_{2}]$ such that
$\boldsymbol{X}\boldsymbol{w}_{j^{*}}$ is an anchor of $\boldsymbol{X}$, and
so is $\exp(\boldsymbol{X}\boldsymbol{w}_{j^{*}})$ due to the strict
monotonicity of $\exp$; Lemma 4.3 and Eq. (9) together imply:

$\displaystyle\begin{bmatrix}\exp(\boldsymbol{x}_{i})&\exp(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}})\end{bmatrix}\sim\begin{bmatrix}\exp(\boldsymbol{x^{\prime}}_{i})&\exp(\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}})\end{bmatrix}\forall
i\in[D]\Rightarrow\exp(\boldsymbol{X})\sim\exp(\boldsymbol{X^{\prime}}).$ (10)

And finally, notice that an element-wise function does not affect equivalence
under permutation. The total number of required linear weights is
$L=DK_{1}(N+3)N/2\leq N^{4}D^{2}$, as desired.

###  4.2 Continuity

In this section, we show that the LP and LE induced sum-pooling are both
homeomorphic. We note that it is intractable to obtain the closed form of
their inverse maps. Notably, the following remarkable result can get rid of
inversing a function explicitly by merely examining the topological
relationship between the domain and image space.

######  Lemma 4.9.

(Theorem 1.2 [35]) Let $(\mathcal{X},d_{\mathcal{X}})$ and
$(\mathcal{Z},d_{\mathcal{Z}})$ be two metric spaces and
$f:\mathcal{X}\rightarrow\mathcal{Z}$ is a bijection such that (a) each
bounded and closed subset of $\mathcal{X}$ is compact, (b) $f$ is continuous,
(c) $f^{-1}$ maps each bounded set in $\mathcal{Z}$ into a bounded set in
$\mathcal{X}$. Then $f^{-1}$ is continuous.

Subsequently, we show the continuity in an informal but more intuitive way
while deferring a rigorous version to the supplementary materials. Denote
$\Phi(\boldsymbol{X})=\sum_{i\in[N]}\phi(\boldsymbol{x}^{(i)})$. To begin
with, we set $\mathcal{X}={}^{N\times D}/\sim$ with metric
$d_{\mathcal{X}}(\boldsymbol{X},\boldsymbol{X}^{\prime})=\min_{\boldsymbol{P}\in\Pi(N)}\|\boldsymbol{X}-\boldsymbol{P}\boldsymbol{X}^{\prime}\|_{\infty,\infty}$
and
$\mathcal{Z}=\\{\Phi(\boldsymbol{X})|\boldsymbol{X}\in\mathcal{X}\\}\subseteq\mathbb{R}^{L}$
with metric
$d_{\mathcal{Z}}(\boldsymbol{z},\boldsymbol{z}^{\prime})=\lVert\boldsymbol{z}-\boldsymbol{z}^{\prime}\rVert_{\infty}$.
It is easy to show that $\mathcal{X}$ satisfies the conditions (a) and
$\Phi(\boldsymbol{X})$ satisfies (b) for both LP and LE embedding layers. Then
it remains to conclude the proof by verifying the condition (c) for the
mapping $\mathcal{Z}\rightarrow\mathcal{X}$, i.e., the inverse of
$\Phi(\boldsymbol{X})$. We visualize this mapping following the chain of
implication to show injectivity:

$\displaystyle\begin{array}[]{lccccc}(LP)&\Phi(\boldsymbol{X})&\xrightarrow{\text{Eq.
\eqref{eqn:channelwise_inverse}}}&\begin{bmatrix}\cdots&\boldsymbol{P}_{i}\boldsymbol{X}\boldsymbol{w}_{i}&\cdots\end{bmatrix},i\in[K]&\xrightarrow{\text{Eqs.
\eqref{eqn:lin_coupling} +
\eqref{eqn:union_align}}}&\boldsymbol{P}\boldsymbol{X}\\\
(LE)&\underbrace{\Phi(\boldsymbol{X})}_{\mathcal{Z}}&\xrightarrow{\text{Eq.
\eqref{eqn:mono_coupling}}}&\underbrace{\exp\begin{bmatrix}\boldsymbol{Q}_{i,j}\boldsymbol{x}_{i}&\boldsymbol{Q}_{i,j}\boldsymbol{a}_{j}\end{bmatrix},i\in[D],j\in[K_{1}]}_{\mathcal{R}}&\xrightarrow{\text{Eq.
\eqref{eqn:union_align_exp}}}&\underbrace{\boldsymbol{Q}\boldsymbol{X}}_{\mathcal{X}}\end{array},$
(13)

for some $\boldsymbol{X}$ dependent $\boldsymbol{P}$,
$\boldsymbol{Q}\in\Pi(N)$. Here, $\boldsymbol{P}_{i}\in\Pi(N),i\in[K]$ and
$\boldsymbol{Q}_{i,j}\in\Pi(N)$,
$\boldsymbol{a}_{j}=\boldsymbol{X}\boldsymbol{w}^{(2)}_{j},i\in[D],j\in[K_{1}]$.
All the weights have been specified as in Sec. 4.1. According to homeomorphism
between polynomial coefficients and roots (Corollary 3.2 in [35]), any bounded
set in $\mathcal{Z}$ will be mapped into a bounded set in $\mathcal{R}$.
Moreover, since elements in $\mathcal{R}$ contain all the columns of
$\mathcal{X}$ (up to some changes of the entry orders), a bounded set in
$\mathcal{R}$ also corresponds to a bounded set in $\mathcal{X}$. Through this
line of arguments, we conclude the proof.

##  5 Extensions

In this section, we discuss two extensions to Theorem 3.1, which strengthen
our main result.

##### Permutation Equivariance.

Permutation-equivariant functions (cf. Definition 2.3) are considered as a
more general family of set functions. Our main result does not lose generality
to this class of functions. By Lemma 2 of [7], Theorem 3.1 can be directly
extended to permutation-equivariant functions with the same lower and upper
bounds, stated as follows:

######  Theorem 5.1 (Extension to Equivariance).

For any permutation-equivariant function $f:\mathcal{K}^{N\times
D}\rightarrow{}^{N}$, $\mathcal{K}\subseteq\real$, there exists continuous
functions $\phi:{}^{D}\rightarrow{}^{L}$ and
$\rho:{}^{D}\times{}^{L}\rightarrow\real$ such that
$f(\boldsymbol{X})_{j}=\rho\left(\boldsymbol{x}^{(j)},\sum_{i\in[N]}\phi(\boldsymbol{x}^{(i)})\right)$
for every $j\in[N]$, where $L\in[N(D+1),N^{5}D^{2}]$ when $\phi$ admits LP
architecture, and $L\in[ND,N^{4}D^{2}]$ when $\phi$ admits LE architecture.

##### Complex Domain.

The upper bounds in Theorem 3.1 is also true to complex features up to a
constant scale. When features are defined over $\mathbb{C}^{N\times D}$, our
primary idea is to divide each channel into two real feature vectors, and
recall Theorem 3.1 to conclude the arguments on an N×2D input. All of our
proof strategies are still applied. This result directly contrasts to Zweig
and Bruna’s work [26] whose main arguments were established on complex
numbers. We show that even moving to the complex domain, polynomial length of
$L$ is still sufficient for the DeepSets architecture [9]. We state a formal
version of the theorem in the supplementary material.

##  6 Related Work

Works on neural networks to represent set functions have been discussed
extensively in Sec. 1. Here, we review other related works on the expressive
power analysis of neural networks.

Early works studied the expressive power of feed-forward neural networks with
different activations [28, 27]. Recent works focused on characterizing the
benefits of the expressive power of deep architectures to explain their
empirical success [39, 40, 41, 42, 43]. Modern neural networks often enforce
some invariance properties into their architectures such as CNNs that capture
spatial translation invariance. The expressive power of invariant neural
networks has been analyzed recently [44, 22, 45].

The architectures studied in the above works allow universal approximation of
continuous functions defined on their inputs. However, the family of
practically useful architectures that enforce permutation invariance often
fail in achieving universal approximation. Graph Neural Networks (GNNs)
enforce permutation invariance and can be viewed as an extension of set neural
networks to encode a set of pair-wise relations instead of a set of individual
elements [20, 46, 47, 21]. GNNs suffer from limited expressive power [18, 17,
5] unless they adopt exponential-order tensors [48]. Hence, previous studies
often characterized GNNs’ expressive power based on their capability of
distinguishing non-isomorphic graphs. Only a few works have ever discussed the
function approximation property of GNNs [49, 50, 51] while these works still
miss characterizing such dependence on the depth and width of the
architectures [52]. As practical GNNs commonly adopt the architectures that
combine feed-forward neural networks with set operations (neighborhood
aggregation), we believe the characterization of the needed size for set
function approximation studied in [26] and this work may provide useful tools
to study finer-grained characterizations of the expressive power of GNNs.

##  7 Conclusion

This work investigates how many neurons are needed to model the embedding
space for set representation learning with the DeepSets architecture [9]. Our
paper provides an affirmative answer that polynomial many neurons in the set
size and feature dimension are sufficient. Compared with prior arts, our
theory takes high-dimensional features into consideration while significantly
advancing the state-of-the-art results from exponential to polynomial.

##### Limitations.

The tightness of our bounds is not examined in this paper, and the complexity
of $\rho$ is uninvestigated and left for future exploration. Besides, deriving
an embedding layer agnostic lower bound for the embedding space remains
another wide open question.

## Acknowledgments and Disclosure of Funding

We would like to express our deepest appreciation to Dr. Manolis C. Tsakiris
for pointing out the connection and useful results in the topics of unlabeled
sensing. P. Li is supported by NSF awards OAC-2117997, IIS-2239565.

## References

  * [1] Yann LeCun, Yoshua Bengio, et al.  Convolutional networks for images, speech, and time series.  The handbook of brain theory and neural networks, 3361(10):1995, 1995.
  * [2] Taco Cohen and Max Welling.  Group equivariant convolutional networks.  In International conference on machine learning, pages 2990–2999. PMLR, 2016.
  * [3] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  * [4] Risi Kondor and Shubhendu Trivedi.  On the generalization of equivariance and convolution in neural networks to the action of compact groups.  In International Conference on Machine Learning, pages 2747–2755, 2018.
  * [5] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman.  Invariant and equivariant graph networks.  In International Conference on Learning Representations (ICLR), 2018\.
  * [6] Alexander Bogatskiy, Brandon Anderson, Jan Offermann, Marwah Roussi, David Miller, and Risi Kondor.  Lorentz group equivariant neural network for particle physics.  In International Conference on Machine Learning, pages 992–1002. PMLR, 2020.
  * [7] Peihao Wang, Shenghao Yang, Yunyu Liu, Zhangyang Wang, and Pan Li.  Equivariant hypergraph diffusion neural operators.  In International Conference on Learning Representations (ICLR), 2023\.
  * [8] 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, pages 652–660, 2017.
  * [9] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola.  Deep sets.  In Advances in Neural Information Processing Systems (NeurIPS), 2017\.
  * [10] Vinicius Mikuni and Florencia Canelli.  Point cloud transformers applied to collider physics.  Machine Learning: Science and Technology, 2(3):035027, 2021.
  * [11] Huilin Qu and Loukas Gouskos.  Jet tagging via particle clouds.  Physical Review D, 101(5):056019, 2020.
  * [12] Hengshuang Zhao, Li Jiang, Jiaya Jia, Philip HS Torr, and Vladlen Koltun.  Point transformer.  In Proceedings of the IEEE/CVF international conference on computer vision, pages 16259–16268, 2021.
  * [13] Juho Lee, Yoonho Lee, Jungtaek Kim, Adam Kosiorek, Seungjin Choi, and Yee Whye Teh.  Set transformer: A framework for attention-based permutation-invariant neural networks.  In International conference on machine learning, pages 3744–3753. PMLR, 2019.
  * [14] Yan Zhang, Jonathon Hare, and Adam Prugel-Bennett.  Deep set prediction networks.  Advances in Neural Information Processing Systems, 32, 2019.
  * [15] Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett.  Fspool: Learning set representations with featurewise sort pooling.  In International Conference on Learning Representations, 2020.
  * [16] Aditya Grover, Eric Wang, Aaron Zweig, and Stefano Ermon.  Stochastic optimization of sorting networks via continuous relaxations.  In International Conference on Learning Representations, 2020.
  * [17] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe.  Weisfeiler and leman go neural: Higher-order graph neural networks.  In the AAAI Conference on Artificial Intelligence, volume 33, pages 4602–4609, 2019.
  * [18] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  In International Conference on Learning Representations, 2019.
  * [19] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković.  Principal neighbourhood aggregation for graph nets.  Advances in Neural Information Processing Systems, 33:13260–13271, 2020.
  * [20] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.  The graph neural network model.  IEEE Transactions on Neural Networks, 20(1):61–80, 2008.
  * [21] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In Advances in Neural Information Processing Systems, 2017.
  * [22] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman.  On the universality of invariant networks.  In International conference on machine learning, pages 4363–4371. PMLR, 2019.
  * [23] Edward Wagstaff, Fabian Fuchs, Martin Engelcke, Ingmar Posner, and Michael A Osborne.  On the limitations of representing functions on sets.  In International Conference on Machine Learning, pages 6487–6494. PMLR, 2019.
  * [24] Edward Wagstaff, Fabian B Fuchs, Martin Engelcke, Michael A Osborne, and Ingmar Posner.  Universal approximation of functions on sets.  Journal of Machine Learning Research, 23(151):1–56, 2022.
  * [25] Nimrod Segol and Yaron Lipman.  On universal equivariant set networks.  In International Conference on Learning Representations (ICLR), 2020\.
  * [26] Aaron Zweig and Joan Bruna.  Exponential separations in symmetric neural networks.  arXiv preprint arXiv:2206.01266, 2022.
  * [27] George Cybenko.  Approximation by superpositions of a sigmoidal function.  Mathematics of control, signals and systems, 2(4):303–314, 1989\.
  * [28] Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al.  Multilayer feedforward networks are universal approximators.  Neural Networks, 2(5):359–366, 1989.
  * [29] Shupeng Gui, Xiangliang Zhang, Pan Zhong, Shuang Qiu, Mingrui Wu, Jieping Ye, Zhengdao Wang, and Ji Liu.  Pine: Universal deep embedding for graph nodes via partial permutation invariant set functions.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(2):770–782, 2021.
  * [30] Nicolas Bourbaki.  Éléments d’histoire des mathématiques, volume 4.  Springer Science & Business Media, 2007.
  * [31] David Rydh.  A minimal set of generators for the ring of multisymmetric functions.  In Annales de l’institut Fourier, volume 57, pages 1741–1769, 2007\.
  * [32] Adam Santoro, David Raposo, David G Barrett, Mateusz Malinowski, Razvan Pascanu, Peter Battaglia, and Timothy Lillicrap.  A simple neural network module for relational reasoning.  Advances in neural information processing systems, 30, 2017.
  * [33] R. L. Murphy, B. Srinivasan, V. Rao, and B. Ribeiro.  Janossy pooling: Learning deep permutation-invariant functions for variable-size inputs.  In International Conference on Learning Representations (ICLR), 2018\.
  * [34] Akiyoshi Sannai, Yuuki Takai, and Matthieu Cordonnier.  Universal approximations of permutation invariant/equivariant functions by deep neural networks.  arXiv preprint arXiv:1903.01939, 2019.
  * [35] Branko Ćurgus and Vania Mascioni.  Roots and polynomials as homeomorphic spaces.  Expositiones Mathematicae, 24(1):81–95, 2006.
  * [36] Andrew R Barron.  Universal approximation bounds for superpositions of a sigmoidal function.  IEEE Transactions on Information theory, 39(3):930–945, 1993.
  * [37] Djork-Arné Clevert, Thomas Unterthiner, and Sepp Hochreiter.  Fast and accurate deep network learning by exponential linear units (elus).  arXiv preprint arXiv:1511.07289, 2015.
  * [38] Fernando Q Gouvêa.  Was cantor surprised?  The American Mathematical Monthly, 118(3):198–209, 2011.
  * [39] Dmitry Yarotsky.  Error bounds for approximations with deep relu networks.  Neural Networks, 94:103–114, 2017.
  * [40] Shiyu Liang and R Srikant.  Why deep neural networks for function approximation?  In International Conference on Learning Representations, 2017.
  * [41] Joe Kileel, Matthew Trager, and Joan Bruna.  On the expressive power of deep polynomial neural networks.  Advances in neural information processing systems, 32, 2019.
  * [42] Nadav Cohen, Or Sharir, and Amnon Shashua.  On the expressive power of deep learning: A tensor analysis.  In Conference on learning theory, pages 698–728. PMLR, 2016.
  * [43] Maithra Raghu, Ben Poole, Jon Kleinberg, Surya Ganguli, and Jascha Sohl-Dickstein.  On the expressive power of deep neural networks.  In international conference on machine learning, pages 2847–2854. PMLR, 2017.
  * [44] Dmitry Yarotsky.  Universal approximations of invariant maps by neural networks.  Constructive Approximation, 55(1):407–474, 2022.
  * [45] Ding-Xuan Zhou.  Universality of deep convolutional neural networks.  Applied and computational harmonic analysis, 48(2):787–794, 2020\.
  * [46] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl.  Neural message passing for quantum chemistry.  In International Conference on Machine Learning (ICML), 2017.
  * [47] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In International Conference on Learning Representations (ICLR), 2017\.
  * [48] Nicolas Keriven and Gabriel Peyré.  Universal invariant and equivariant graph neural networks.  In Advances in Neural Information Processing Systems, pages 7090–7099, 2019.
  * [49] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna.  On the equivalence between graph isomorphism testing and function approximation with gnns.  In Advances in Neural Information Processing Systems, pages 15868–15876, 2019.
  * [50] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna.  Can graph neural networks count substructures?  volume 33, 2020.
  * [51] Waïss Azizian and Marc Lelarge.  Expressive power of invariant and equivariant graph neural networks.  In ICLR 2021-International Conference on Learning Representations, 2021.
  * [52] Andreas Loukas.  What graph neural networks cannot learn: depth vs width.  In International Conference on Learning Representations, 2020.
  * [53] Manolis C Tsakiris.  Low-rank matrix completion theory via plücker coordinates.  IEEE Transactions on Pattern Analysis and Machine Intelligence, 2023\.
  * [54] Yunzhen Yao, Liangzu Peng, and Manolis Tsakiris.  Unlabeled principal component analysis.  Advances in Neural Information Processing Systems, 34:30452–30464, 2021.
  * [55] Manolis Tsakiris and Liangzu Peng.  Homomorphic sensing.  In International Conference on Machine Learning, pages 6335–6344. PMLR, 2019.
  * [56] Jayakrishnan Unnikrishnan, Saeid Haghighatshoar, and Martin Vetterli.  Unlabeled sensing with random linear measurements.  IEEE Transactions on Information Theory, 64(5):3237–3253, 2018\.
  * [57] Daniel J Hsu, Kevin Shi, and Xiaorui Sun.  Linear regression without correspondence.  Advances in Neural Information Processing Systems, 30, 2017.
  * [58] Manolis C Tsakiris, Liangzu Peng, Aldo Conca, Laurent Kneip, Yuanming Shi, and Hayoung Choi.  An algebraic-geometric approach for linear regression without correspondences.  IEEE Transactions on Information Theory, 66(8):5130–5144, 2020\.
  * [59] Liangzu Peng and Manolis C Tsakiris.  Linear regression without correspondences via concave minimization.  IEEE Signal Processing Letters, 27:1580–1584, 2020.
  * [60] Mohammad Fereydounian, Hamed Hassani, and Amin Karbasi.  What functions can graph neural networks generate?  arXiv preprint arXiv:2202.08833, 2022.

##  Appendix A Some Preliminary Definitions and Statements

In this section, we begin by stating basic metric spaces, which will be used
in the proofs later.

######  Definition A.1 (Standard Metric).

Define $(\mathcal{K}^{D},d_{\infty})$ as the standard metric space, where
$d_{\infty}:\mathcal{K}^{D}\times\mathcal{K}^{D}\rightarrow{}_{\geq 0}$ is the
$\ell_{\infty}$-norm induced distance metric over $\mathcal{K}^{D}$:

$\displaystyle
d_{\infty}(\boldsymbol{z},\boldsymbol{z^{\prime}})=\max_{i\in[D]}|\boldsymbol{z}_{i}-\boldsymbol{z^{\prime}}_{i}|.$
(14)

######  Definition A.2 (Product Metric).

Consider a metric space $(\mathcal{X},d_{\mathcal{X}})$. We denote the induced
product metric over the product space $(\mathcal{X}^{K},d_{\mathcal{X}}^{K})$
as
$d_{\mathcal{X}}^{K}:\mathcal{X}^{K}\times\mathcal{X}^{K}\rightarrow{}_{\geq
0}$:

$\displaystyle
d_{\mathcal{X}}^{K}(\boldsymbol{Z},\boldsymbol{Z^{\prime}})=\max_{i\in[K]}d_{\mathcal{X}}(\boldsymbol{z}_{i},\boldsymbol{z^{\prime}}_{i}),$
(15)

where
$\boldsymbol{Z}=\begin{bmatrix}\boldsymbol{z}_{1}&\cdots&\boldsymbol{z}_{K}\end{bmatrix}\in\mathcal{X}^{K},\boldsymbol{z}_{i}\in\mathcal{X},\forall
i\in[K]$.

We provide rigorous definitions to specify the topology of the input space of
permutation-invariant functions.

######  Definition A.3 (Set Metric).

Equipped $\mathcal{K}^{N\times D}$ with the equivalence relation $\sim$ (cf.
Definition 2.1), we define metric space $(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})$, where $d_{\Pi}:(\mathcal{K}^{N\times
D}/\sim)\times(\mathcal{K}^{N\times D}/\sim)\rightarrow{}_{\geq 0}$ is the
optimal transport distance:

$\displaystyle
d_{\Pi}(\boldsymbol{X},\boldsymbol{X^{\prime}})=\min_{\boldsymbol{P}\in\Pi(N)}\left\lVert\boldsymbol{P}\boldsymbol{X}-\boldsymbol{X^{\prime}}\right\rVert_{\infty,\infty},$
(16)

and $\mathcal{K}$ can be either or $\mathbb{C}$.

######  Remark A.4.

The $\left\lVert\cdot\right\rVert_{\infty,\infty}$ norm takes the absolute
value of the maximal entry: $\max_{i\in[N],j\in[D]}|\boldsymbol{X}_{i,j}|$.
Other topologically equivalent matrix norms also apply.

######  Lemma A.5.

The function $d_{\Pi}:(\mathcal{K}^{N\times
D}/\sim)\times(\mathcal{K}^{N\times D}/\sim)\rightarrow{}_{\geq 0}$ is a
distance metric on $\mathcal{K}^{N\times D}/\sim$.

###### Proof.

Identity, positivity, and symmetry trivially hold for $d_{\Pi}$. It remains to
show the triangle inequality as below: for arbitrary
$\boldsymbol{X},\boldsymbol{X^{\prime}},\boldsymbol{X^{\prime\prime}}\in(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})$,

$\displaystyle d_{\Pi}(\boldsymbol{X},\boldsymbol{X^{\prime\prime}})$
$\displaystyle=\min_{\boldsymbol{P}\in\Pi(N)}\left\lVert\boldsymbol{P}\boldsymbol{X}-\boldsymbol{X^{\prime\prime}}\right\rVert_{\infty,\infty}\leq\min_{\boldsymbol{P}\in\Pi(N)}\left(\left\lVert\boldsymbol{P}\boldsymbol{X}-\boldsymbol{Q}^{*}\boldsymbol{X^{\prime}}\right\rVert_{\infty,\infty}+\left\lVert\boldsymbol{Q}^{*}\boldsymbol{X^{\prime}}-\boldsymbol{X^{\prime\prime}}\right\rVert_{\infty,\infty}\right)$
$\displaystyle=\min_{\boldsymbol{P}\in\Pi(N)}\left\lVert\boldsymbol{P}\boldsymbol{X}-\boldsymbol{Q}^{*}\boldsymbol{X^{\prime}}\right\rVert_{\infty,\infty}+\left\lVert\boldsymbol{Q}^{*}\boldsymbol{X^{\prime}}-\boldsymbol{X^{\prime\prime}}\right\rVert_{\infty,\infty}$
$\displaystyle=d_{\Pi}(\boldsymbol{X},\boldsymbol{X^{\prime}})+d_{\Pi}(\boldsymbol{X},\boldsymbol{X^{\prime\prime}}),$

where
$\boldsymbol{Q}^{*}\in\operatorname{argmin}_{\boldsymbol{Q}\in\Pi(N)}\left\lVert\boldsymbol{Q}\boldsymbol{X^{\prime}}-\boldsymbol{X^{\prime\prime}}\right\rVert_{\infty,\infty}$.
∎

Also we reveal a topological property for $(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})$ which is essential to show continuity later.

######  Lemma A.6.

Each bounded and closed subset of $(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$ is
compact.

###### Proof.

Without loss of generality, the proof is done by extending Theorem 2.4 in [35]
to high-dimensional set elements. Let $\varrho:(\mathcal{K}^{N\times
D},d_{\infty})\rightarrow(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$ maps a matrix
$\boldsymbol{X}$ to a set whose elements are the rows of $\boldsymbol{X}$. We
notice that $\varrho$ is a continuous mapping due to its contraction nature:
$d_{\Pi}(\varrho(\boldsymbol{X}),\varrho(\boldsymbol{X^{\prime}}))\leq\lVert\boldsymbol{X}-\boldsymbol{X^{\prime}}\rVert_{\infty,\infty}=d_{\infty}(\boldsymbol{X},\boldsymbol{X^{\prime}})$.
Let $\varrho^{-1}(\boldsymbol{Z})=\\{\boldsymbol{X}\in(\mathcal{K}^{N\times
D},d_{\infty}):\varrho(\boldsymbol{X})\sim\boldsymbol{Z}\\}$. Define
$\mathcal{T}\subset(\mathcal{K}^{N\times D},d_{\infty})$ such that
$\varrho^{-1}(\boldsymbol{Z})\cap\mathcal{T}$ has only one element for every
$\boldsymbol{Z}\in(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$. One example of
picking elements for $\mathcal{T}$ is to sort every
$\boldsymbol{Z}\in(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$ in the
lexicographical order. Now constraining the domain of $\varrho$ to be
$\mathcal{T}$ yields a bijective mapping $\varrho|_{\mathcal{T}}$, and its
inverse $\varrho|_{\mathcal{T}}^{-1}$. We notice that
$\varrho\circ\varrho|_{\mathcal{T}}^{-1}$ induces an identity mapping over
$(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$.

Now consider an arbitrary closed and bounded subset
$\mathcal{S}\subset(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$. To show
$\mathcal{S}$ is compact, we demonstrate every sequence
$\\{\boldsymbol{X}_{k}\\}$ in $\mathcal{S}$ has a convergent subsequence.
First observe that $\\{\varrho|_{\mathcal{T}}^{-1}(\boldsymbol{X}_{k})\\}$ is
also bounded in $(\mathcal{K}^{N\times D},d_{\infty})$. This is because
$\lVert\varrho|_{\mathcal{T}}^{-1}(\boldsymbol{X})\rVert_{\infty,\infty}=d_{\Pi}(\boldsymbol{X},\boldsymbol{0})$.
Hence, by Bolzano-Weierstrass Theorem, there exists a subsequence
$\\{\boldsymbol{X}_{j_{k}}\\}\subset\\{\boldsymbol{X}_{k}\\}$ such that
$\\{\varrho|_{\mathcal{T}}^{-1}(\boldsymbol{X}_{j_{k}})\\}$ converges to some
$\boldsymbol{\chi}\in(\mathcal{K}^{N\times D},d_{\infty})$. As aforementioned,
since $\varrho$ is a continuous mapping,
$\\{\varrho\circ\varrho|_{\mathcal{T}}^{-1}(\boldsymbol{X})\\}$ converges to
$\varrho(\boldsymbol{\chi})$ in $(\mathcal{K}^{N\times D}/\sim,d_{\Pi})$.
Since $\mathcal{S}$ is closed, $\varrho(\boldsymbol{\chi})\in\mathcal{S}$.
This is
$\lim_{k\rightarrow\infty}\boldsymbol{X}_{j_{k}}=\varrho(\boldsymbol{\chi})$,
which concludes the proof. ∎

Then we can rephrase the definition of a permutation-invariant function as a
proper function mapping between the two metric spaces:
$f:(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})\rightarrow(\mathcal{K}^{D^{\prime}},d_{\infty})$.

We also recall the definition of injectivity for permutation-invariant
functions:

######  Definition A.7 (Injectivity).

A permutation-invariant function $f:(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})\rightarrow(\mathcal{K}^{D^{\prime}},d_{\infty})$ is injective
if for every $\boldsymbol{X},\boldsymbol{X^{\prime}}\in\mathcal{K}^{N\times
D}$ such that $f(\boldsymbol{X})=f(\boldsymbol{X^{\prime}})$, then
$\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$.

######  Definition A.8 (Bijectivity/Invertibility).

A permutation-invariant function $f:(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})\rightarrow(\mathcal{K}^{D^{\prime}},d_{\infty})$ is bijective
or invertible if there exists a function
$g:(\mathcal{K}^{D^{\prime}},d_{\infty})\rightarrow(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})$ such that for every $\boldsymbol{X}\in\mathcal{K}^{N\times
D}$, $g\circ f(\boldsymbol{X})\sim\boldsymbol{X}$.

A well-known and useful result in set theory connects injectivity and
bijectivity:

######  Lemma A.9.

A function is bijective if and only if it is simultaneously injective and
surjective.

We give an intuitive definition of continuity for permutation-invariant
functions via the epsilon-delta statement:

######  Definition A.10 (Continuity).

A permutation-invariant function $f:(\mathcal{K}^{N\times
D}/\sim,d_{\Pi})\rightarrow(\mathcal{K},d_{\infty})$ is continuous if for
arbitrary $\boldsymbol{X}\in\mathcal{K}^{N\times D}$ and $\epsilon>0$, there
exists $\delta>0$ such that for every
$\boldsymbol{X^{\prime}}\in\mathcal{K}^{N\times D}$,
$d_{\Pi}(\boldsymbol{X},\boldsymbol{X^{\prime}})<\delta$ then
$d_{\infty}(f(\boldsymbol{X}),f(\boldsymbol{X^{\prime}}))<\epsilon$.

######  Remark A.11.

Since $d_{\Pi}$ is a distance metric, other equivalent definitions of
continuity still applies.

##  Appendix B Properties of Sum-of-Power Mapping for Real and Complex Domains

In this section, we extend the sum-of-power mapping to both real and complex
domains, and explore their desirable properties that serve as prerequisites
for our later proof. The proof techniques are borrowed from [35]. Below,
$\mathcal{K}$ can be either or $\mathbb{C}$.

######  Definition B.1.

Define power mapping: $\psi_{N}:\mathcal{K}\rightarrow\mathcal{K}^{N}$,
$\psi_{N}(z)=\begin{bmatrix}z&z^{2}&\cdots&z^{N}\end{bmatrix}^{\top}$ and
(complex) sum-of-power mapping
$\Psi_{N}:(\mathcal{K}^{N}/\sim,d_{\Pi})\rightarrow(\mathcal{K}^{N},d_{\infty})$,
$\Psi_{N}(\boldsymbol{z})=\sum_{i=1}^{N}\psi_{N}(z_{i})$.

######  Lemma B.2 (Existence of Continuous Inverse of Complex Sum-of-Power
[35]).

$\Psi_{N}$ is injective, thus the inverse
$\Psi_{N}^{-1}:(\mathcal{K}^{N},d_{\infty})\rightarrow(\mathcal{K}^{N}/\sim,d_{\Pi})$
exists. Moreover, $\Psi_{N}^{-1}$ is continuous.

######  Lemma B.3 (Corollary 3.2 [35]).

Consider a function
$\zeta:(\mathcal{K}^{N},d_{\infty})\rightarrow(\mathcal{K}^{N}/\sim,d_{\Pi})$
that maps the coefficients of a polynomial to its root multi-set. Then for any
bounded subset $\mathcal{U}\subset(\mathcal{K}^{N},d_{\infty})$, the image
$\zeta(\mathcal{U})=\\{\zeta(\boldsymbol{z}):\boldsymbol{z}\in\mathcal{U}\\}$
is also bounded.

######  Remark B.4.

The original proof of Lemma B.3 is done for the complex domain. However, it is
naturally true for real numbers because we can constrain the domain of $\zeta$
to be real coefficients such that the corresponding polynomials can fully
split over the real domain, and the image to be all the real roots. Then both
domain and image turn out to be a subset of the complex-valued version.

######  Lemma B.5.

Consider the $N$-degree sum-of-power mapping:
$\Psi_{N}:(\mathcal{K}^{N}/\sim,d_{\Pi})\rightarrow(\mathcal{K}^{N},d_{\infty})$,
where $\Psi_{N}(\boldsymbol{x})=\sum_{i=1}^{N}\psi_{N}(x_{i})$. Denote the
range of $\Psi_{N}$ as $\mathcal{Z}_{\Psi_{N}}\subseteq\mathcal{K}^{N}$ and
its inverse mapping
$\Psi_{N}^{-1}:(\mathcal{Z}_{\Psi_{N}},d_{\infty})\rightarrow(\mathcal{K}^{N}/\sim,d_{\Pi})$
(existence guaranteed by Lemma B.2). Then for every bounded set
$\mathcal{U}\subset(\mathcal{Z}_{\Psi_{N}},d_{\infty})$, the image
$\Psi_{N}^{-1}(\mathcal{U})=\\{\Psi_{N}^{-1}(\boldsymbol{z}):\boldsymbol{z}\in\mathcal{U}\\}$
is also bounded.

###### Proof.

We first show this result when $\mathcal{K}=\mathbb{C}$, and naturally extend
it to $\mathcal{K}=\real$. We borrow the proof technique from [9] to reveal a
polynomial mapping between $(\mathcal{Z}_{\Psi_{N}},d_{\infty})$ and
coefficient space of complex polynomials $(\mathbb{C}^{N},d_{\infty})$. For
every $\boldsymbol{\xi}\in(\mathbb{C}^{N}/\sim,d_{\Pi})$, let
$\boldsymbol{z}=\Psi_{N}(\boldsymbol{\xi})$ and construct a polynomial:

$\displaystyle
P_{\boldsymbol{\xi}}(x)=\prod_{i=1}^{N}(x-\xi_{i})=x^{N}-a_{1}x^{N-1}+\cdots+(-1)^{N-1}a_{N-1}x+(-1)^{N}a_{N},$
(17)

where $\boldsymbol{\xi}$ are the roots of $P_{\boldsymbol{\xi}}(x)$ and the
coefficients can be written as elementary symmetric polynomials, i.e.,

$\displaystyle a_{n}=\sum_{1\leq j_{1}\leq j_{2}\leq\cdots\leq j_{n}\leq
N}\xi_{j_{1}}\xi_{j_{2}}\cdots\xi_{j_{n}},\forall n\in[N].$ (18)

On the other hand, the elementary symmetric polynomials can be uniquely
expressed as a function of $\boldsymbol{z}$ by Newton-Girard formula:

$\displaystyle a_{n}=\frac{1}{n}\det\begin{bmatrix}z_{1}&1&0&0&\cdots&0\\\
z_{2}&z_{1}&1&0&\cdots&0\\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\\
z_{n-1}&z_{n-2}&z_{n-3}&z_{n-4}&\cdots&1\\\
z_{n}&z_{n-1}&z_{n-2}&z_{n-3}&\cdots&1\\\
\end{bmatrix}:=Q(\boldsymbol{z}),\forall n\in[N]$ (19)

where the determinant $Q(\boldsymbol{z})$ is also a polynomial in
$\boldsymbol{z}$. Now we establish the mapping between
$(\mathcal{Z}_{\Psi_{N}},d_{\infty})$ and $(\mathbb{C}^{N}/\sim,d_{\Pi})$:

$\displaystyle(\mathcal{Z}_{\Psi_{N}},d_{\infty})\xRightarrow{Q(\boldsymbol{z})}\underbrace{(\mathbb{C}^{N},d_{\infty})}_{\text{Coefficients}}\xRightarrow{\text{Lemma
\ref{lem:inv_poly_boundedness}}}\underbrace{(\mathbb{C}^{N}/\sim,d_{\Pi})}_{\text{Roots}}.$
(20)

Then the proof proceeds by observing that for any bounded subset
$\mathcal{U}\subseteq(\mathcal{Z}_{\Psi_{N}},d_{\infty})$, the resulting
$\mathcal{A}=Q(\mathcal{U})$ is also bounded in $(\mathbb{C}^{N},d_{\infty})$.
Therefore, by Lemma B.3, any bounded coefficient set $\mathcal{A}$ will
produce a bounded root multi-set in $(\mathbb{C}^{N}/\sim,d_{\Pi})$.

Now we show Lemma B.3 is also true for real numbers. By Remark B.4, we can
constrain the ambient space of $\mathcal{A}$ to be real coefficients whose
corresponding polynomials can split over real numbers, and then the same proof
proceed. ∎

######  Corollary B.6.

Consider channel-wise high-dimensional sum-of-power
$\widehat{\Psi_{N}}(\boldsymbol{X}):(\mathcal{K}^{N\times
K}/\sim,d_{\Pi})\rightarrow(\mathcal{Z}_{\Psi_{N}}^{K},d_{\infty})$ defined as
below:

$\displaystyle\widehat{\Psi_{N}}(\boldsymbol{X})=\begin{bmatrix}\Psi_{N}(\boldsymbol{x}_{1})^{\top}&\cdots&\Psi_{N}(\boldsymbol{x}_{K})^{\top}\end{bmatrix}^{\top}\in(\mathcal{Z}_{\Psi_{N}}^{K},d_{\infty}),$
(21)

where
$\mathcal{Z}_{\Psi_{N}}=\\{\Psi_{N}(\boldsymbol{x}):\boldsymbol{x}\in\mathcal{K}^{N}\\}\subseteq\mathcal{K}^{N}$
is the range of the sum-of-power mapping. Define an associated mapping
$\widehat{\Psi_{N}}^{\dagger}:(\mathcal{Z}_{\Psi_{N}}^{K},d_{\infty})\rightarrow(\mathcal{K}^{N}/\sim,d_{\Pi})^{K}$:

$\displaystyle\widehat{\Psi_{N}}^{\dagger}(\boldsymbol{Z})=\begin{bmatrix}\Psi_{N}^{-1}(\boldsymbol{z}_{1})&\cdots&\Psi_{N}^{-1}(\boldsymbol{z}_{K})\end{bmatrix},$
(22)

where
$\boldsymbol{Z}=\begin{bmatrix}\boldsymbol{z}_{1}^{\top}&\cdots&\boldsymbol{z}_{K}^{\top}\end{bmatrix}^{\top}$,
$\boldsymbol{z}_{i}\in\mathcal{Z}_{\Psi_{N}},\forall i\in[K]$. Then the
mapping $\widehat{\Psi_{N}}^{\dagger}$ maps any bounded set in
$(\mathcal{Z}_{\Psi_{N}}^{K},d_{\infty})$ to a bounded set in
$(\mathcal{K}^{N}/\sim,d_{\Pi})^{K}$.

###### Proof.

Proved by noting that if
$d_{\infty}(\boldsymbol{z}_{i},\boldsymbol{z^{\prime}}_{i})\leq C_{1}$ for
some
$\boldsymbol{z}_{i},\boldsymbol{z^{\prime}}_{i}\in(\mathcal{Z}_{\Psi_{N}},d_{\infty}),\forall
i\in[K]$ and a constant $C_{1}\geq 0$, then
$d_{\Pi}(\Psi_{N}^{-1}(\boldsymbol{z}_{i}),\Psi_{N}^{-1}(\boldsymbol{z^{\prime}}_{i}))\leq
C_{2},\forall i\in[K]$ for some constant $C_{2}\geq 0$ by Lemma B.5. Finally,
we have:

$\displaystyle
d_{\Pi}^{K}\left(\widehat{\Psi_{N}}^{\dagger}\left(\boldsymbol{Z}\right),\widehat{\Psi_{N}}^{\dagger}\left(\boldsymbol{Z^{\prime}}\right)\right)=\max_{i\in[K]}d_{\Pi}(\Psi_{N}^{-1}(\boldsymbol{z}_{i}),\Psi_{N}^{-1}(\boldsymbol{z^{\prime}}_{i}))\leq
C_{2},$

which is also bounded above. ∎

##  Appendix C Proofs for the Properties of Anchor

The main ingredient of our construction is anchor defined in Definition 4.1.
Two key properties of anchors are restated in Lemma C.1 and C.2 and proved
below:

######  Lemma C.1 (Lemma 4.2).

Consider the data matrix $\boldsymbol{X}\in{}^{N\times D}$ and
$\boldsymbol{a}\in{}^{N}$ an anchor of $\boldsymbol{X}$. Then if there exists
$\boldsymbol{P}\in\Pi(N)$ such that
$\boldsymbol{P}\boldsymbol{a}=\boldsymbol{a}$ then
$\boldsymbol{P}\boldsymbol{x}_{i}=\boldsymbol{x}_{i}$ for every $i\in[D]$.

###### Proof.

Prove by contradiction. Suppose
$\boldsymbol{P}\boldsymbol{x}_{i}\neq\boldsymbol{x}_{i}$ for some $i\in[D]$,
then there exist some $p,q\in[N]$ such that
$\boldsymbol{x}_{i}^{(p)}\neq\boldsymbol{x}_{i}^{(q)}$ while $a_{p}=a_{q}$.
However, this contradicts the definition of an anchor (cf. Definition 4.1). ∎

######  Lemma C.2 (Union Alignment, Lemma 4.3).

Consider the data matrix $\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times
D}$, $\boldsymbol{a}\in{}^{N}$ is an anchor of $\boldsymbol{X}$ and
$\boldsymbol{a^{\prime}}\in{}^{N}$ is an arbitrary vector. If
$\begin{bmatrix}\boldsymbol{a}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{a^{\prime}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix}$
for every $i\in[D]$, then $\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$.

###### Proof.

According to definition of equivalence, there exists
$\boldsymbol{Q}_{i}\in\Pi(N)$ for every $i\in[D]$ such that
$\begin{bmatrix}\boldsymbol{a}&\boldsymbol{x}_{i}\end{bmatrix}=\begin{bmatrix}\boldsymbol{Q}_{i}\boldsymbol{a^{\prime}}&\boldsymbol{Q}_{i}\boldsymbol{x^{\prime}}_{i}\end{bmatrix}$.
Moreover, since
$\begin{bmatrix}\boldsymbol{a}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{a^{\prime}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix}$,
it must hold that $\boldsymbol{a}\sim\boldsymbol{a^{\prime}}$, i.e., there
exists $\boldsymbol{P}\in\Pi(N)$ such that
$\boldsymbol{P}\boldsymbol{a}=\boldsymbol{a^{\prime}}$. Combined together, we
have that $\boldsymbol{Q}_{i}\boldsymbol{P}\boldsymbol{a}=\boldsymbol{a}$.

Next, we choose
$\boldsymbol{Q^{\prime}}_{i}=\boldsymbol{P}^{\top}\boldsymbol{Q}_{i}^{\top}$
so
$\boldsymbol{Q^{\prime}}_{i}\boldsymbol{a}=\boldsymbol{Q^{\prime}}_{i}\boldsymbol{Q}_{i}\boldsymbol{P}\boldsymbol{a}=\boldsymbol{a}$.
Due to the property of anchors (Lemma C.1), we have
$\boldsymbol{Q^{\prime}}_{i}\boldsymbol{x}_{i}=\boldsymbol{x}_{i}$. Notice
that
$\boldsymbol{x}_{i}=\boldsymbol{Q^{\prime}}_{i}\boldsymbol{x}_{i}=\boldsymbol{P}^{\top}\boldsymbol{Q}_{i}^{\top}\boldsymbol{Q}_{i}\boldsymbol{x^{\prime}}_{i}=\boldsymbol{P}\boldsymbol{x^{\prime}}_{i}$.
Therefore, we can conclude the proof as we have found a permutation matrix
$\boldsymbol{P}$ that simultaneously aligns $\boldsymbol{x}_{i}$ and
$\boldsymbol{x^{\prime}}_{i}$ for every $i\in[D]$, i.e.,
$\boldsymbol{X}=\begin{bmatrix}\boldsymbol{x}_{1}&\cdots&\boldsymbol{x}_{D}\end{bmatrix}=\begin{bmatrix}\boldsymbol{P}\boldsymbol{x}_{1}&\cdots&\boldsymbol{P}\boldsymbol{x}_{D}\end{bmatrix}=\boldsymbol{P}\boldsymbol{X^{\prime}}$.
∎

Next, we need to examine how many weights are needed to construct an anchor
via linear combining all the existing channels. We restate Lemma 4.4 in Lemma
C.4 with more specifications as well as a simple result from linear algebra
(Lemma C.3) to prove it, as below:

######  Lemma C.3.

Consider $D$ linearly independent weight vectors
$\\{\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{D}\in{}^{D}\\}$. Then for every
$p,q\in[N]$ such that $\boldsymbol{x}^{(p)}\neq\boldsymbol{x}^{(q)}$, there
exists $\boldsymbol{w}_{j},j\in[D]$, such that
$\boldsymbol{x}^{(p)\top}\boldsymbol{w}_{j}\neq\boldsymbol{x}^{(q)\top}\boldsymbol{w}_{j}$.

###### Proof.

This is the simple fact of full-rank linear systems. Prove by contradiction.
Suppose for $\forall j\in[D]$ we have
$\boldsymbol{x}^{(p)\top}\boldsymbol{w}_{j}=\boldsymbol{x}^{(q)\top}\boldsymbol{w}_{j}$.
Then we form a linear system:
$\boldsymbol{x}^{(p)\top}\begin{bmatrix}\boldsymbol{w}_{1}&\cdots&\boldsymbol{w}_{D}\end{bmatrix}=\boldsymbol{x}^{(q)\top}\begin{bmatrix}\boldsymbol{w}_{1}&\cdots&\boldsymbol{w}_{D}\end{bmatrix}$.
Since $\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{D}$ are linearly independent,
it yields $\boldsymbol{x}^{(p)}=\boldsymbol{x}^{(q)}$, which reaches the
contradiction. ∎

######  Lemma C.4 (Anchor Construction).

Consider a set of weight vectors
$\\{\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K_{1}}\in{}^{D}\\}$ with
$K_{1}=N(N-1)(D-1)/2+1$, of which every $D$-length subset, i.e.,
$\\{\boldsymbol{w}_{j}:\forall
j\in\mathcal{J}\\},\forall\mathcal{J}\subseteq[K_{1}],|\mathcal{J}|=D$, is
linearly independent, then for every data matrix $\boldsymbol{X}\in{}^{N\times
D}$, there exists $j^{*}\in[K_{1}]$, $\boldsymbol{X}\boldsymbol{w}_{j^{*}}$ is
an anchor of $\boldsymbol{X}$.

###### Proof.

Define a set of pairs which an anchor needs to distinguish:
$\mathcal{I}=\\{(p,q):\boldsymbol{x}^{(p)}\neq\boldsymbol{x}^{(q)}\\}\subseteq[N]^{2}$
Consider a $D$-length subset $\mathcal{J}\subseteq[K]$ with $|\mathcal{J}|=D$.
Since $\\{\boldsymbol{w}_{j}:\forall j\in\mathcal{J}\\}$ are linear
independent, we assert by Lemma C.3 that for every pair $(p,q)\in\mathcal{I}$,
there exists $j\in\mathcal{J}$,
$\boldsymbol{x}^{(p)\top}\boldsymbol{w}_{j}\neq\boldsymbol{x}^{(q)\top}\boldsymbol{w}_{j}$.
It is equivalent to claim: for every pair $(p,q)\in\mathcal{I}$, at most $D-1$
many $\boldsymbol{w}_{j},j\in[K_{1}]$ satisfy
$\boldsymbol{x}^{(p)\top}\boldsymbol{w}_{j}=\boldsymbol{x}^{(q)\top}\boldsymbol{w}_{j}$.
Based on pigeon-hold principle, as long as $K_{1}\geq
N(N-1)(D-1)/2+1=(D-1){N\choose 2}+1\geq(D-1)|\mathcal{I}|+1$, there must exist
$j^{*}\in[K_{1}]$ such that
$\boldsymbol{x}^{(p)\top}\boldsymbol{w}_{j^{*}}\neq\boldsymbol{x}^{(q)\top}\boldsymbol{w}_{j^{*}}$
for $\forall(p,q)\in\mathcal{I}$. By Definition 4.1,
$\boldsymbol{X}\boldsymbol{w}_{j^{*}}$ generates an anchor. ∎

######  Proposition C.5.

The linear independence condition in Lemma C.4 can be satisfied with
probability one by drawing i.i.d. Gaussian random vectors
$\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K_{1}}\overset{i.i.d.}{\sim}\mathcal{N}(\boldsymbol{0},\boldsymbol{I})$.

###### Proof.

We first note that generating a $D\times K_{1}$ Gaussian random matrix ($D\leq
K_{1}$) is equivalent to drawing a matrix with respect to a probability
measure defined over $\mathcal{M}=\\{\boldsymbol{X}\in{}^{D\times
K}:\operatorname{rank}(\boldsymbol{X})\leq D\\}$. Since rank-$D$ matrices are
dense in $\mathcal{M}$ [53, 54], we can conclude that for
$\forall\mathcal{J}\subseteq[K_{1}]$, $|\mathcal{J}|=D$,
$\mathbb{P}(\text{$\\{\boldsymbol{w}_{j}:j\in\mathcal{J}\\}$ are linearly
independent})=1$. By union bound,
$\mathbb{P}(\text{$\\{\boldsymbol{w}_{j}:j\in\mathcal{J}\\}$ for all
$\mathcal{J}\in[K]$, $|\mathcal{J}|=D$ are linearly independent})=1$. ∎

##  Appendix D Proofs for the LP Embedding Layer

In this section, we complete the proofs for the LP embedding layer (Eq. (2)).
First we constructively show an upper bound that sufficiently achieves
injectivity following our discussion in Sec. 4.1.2, and then prove Theorem 4.6
to reveal a lower bound that is necessary for injectivity. Finally, we show
prove the continuity of the inverse of our constructed LP embedding layer with
the techniques introduced in Sec. 4.2.

###  D.1 Upper Bound for Injectivity

To prove the upper bound, we construct an LP embedding layer with $L\leq
N^{5}D^{2}$ output neurons such that its induced summation is injective.

We also restate Lemma 4.5 in the following lemma to demonstrate the weight
construction for anchor matching:

######  Lemma D.1 (Linear Coupling, Lemma 4.5).

Consider a group of coefficients
$\Gamma=\\{\gamma_{1},\cdots,\gamma_{K_{2}}\in\real\\}$ with $\gamma_{i}\neq
0,\forall i\in[K_{2}]$, $\gamma_{i}\neq\gamma_{j},\forall i,j\in[K_{2}]$, and
$K_{2}=N(N-1)+1$ such that for all 4-tuples
$(\gamma_{i},\gamma_{j},\gamma_{k},\gamma_{l})\subset\Gamma$, if
$\gamma_{i}\neq\gamma_{j},\gamma_{i}\neq\gamma_{k}$ then
$\gamma_{i}/\gamma_{j}\neq\gamma_{k}/\gamma_{l}$. It must hold that: Given any
$\boldsymbol{x},\boldsymbol{x^{\prime}},\boldsymbol{y},\boldsymbol{y^{\prime}}\in{}^{N}$
such that $\boldsymbol{x}\sim\boldsymbol{x^{\prime}}$ and
$\boldsymbol{y}\sim\boldsymbol{y^{\prime}}$, if
$(\boldsymbol{x}-\gamma_{k}\boldsymbol{y})\sim(\boldsymbol{x^{\prime}}-\gamma_{k}\boldsymbol{y^{\prime}})$
for every $k\in[K_{2}]$, then
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.

###### Proof.

We note that $\boldsymbol{x}\sim\boldsymbol{x^{\prime}}$ and
$\boldsymbol{y}\sim\boldsymbol{y^{\prime}}$ imply that there exist
$\boldsymbol{P}_{x},\boldsymbol{P}_{y}\in\Pi(N)$ such that
$\boldsymbol{P}_{x}\boldsymbol{x}=\boldsymbol{x^{\prime}}$ and
$\boldsymbol{P}_{y}\boldsymbol{y}=\boldsymbol{y^{\prime}}$. Also
$(\boldsymbol{x}-\gamma_{k}\boldsymbol{y})\sim(\boldsymbol{x^{\prime}}-\gamma_{k}\boldsymbol{y^{\prime}}),\forall
k\in[K_{2}]$ implies there exists $\boldsymbol{Q}_{k}\in\Pi(N),\forall
k\in[K_{2}]$ such that
$\boldsymbol{Q}_{k}(\boldsymbol{x}-\gamma_{k}\boldsymbol{y})=\boldsymbol{x^{\prime}}-\gamma_{k}\boldsymbol{y^{\prime}}$.
Substituting the former to the latter, we can obtain:

$\displaystyle\left(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x}\right)\boldsymbol{x}=\gamma_{k}\left(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x}\right)\boldsymbol{y},\quad\forall
k\in[K_{2}],$ (23)

where for each $k\in[K_{2}]$, Eq. (23) corresponds to $N$ equalities as
follows. Here, we let $(\boldsymbol{Z})_{i}$ denote the $i$th column of the
matrix $\boldsymbol{Z}$.

$\displaystyle(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{1}^{\top}\boldsymbol{x}$
$\displaystyle=\gamma_{k}(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{1}^{\top}\boldsymbol{y}$
$\displaystyle\vdots$ (24)
$\displaystyle(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{N}^{\top}\boldsymbol{x}$
$\displaystyle=\gamma_{k}(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{N}^{\top}\boldsymbol{y}$

We compare entries in $\boldsymbol{x}=[\cdots x_{p}\cdots]^{\top}$ and for
each entry index $p\in[N]$, we define a set of non-zero pairwise differences
between $x_{p}$ and other entries in $\boldsymbol{x}$:
$\mathcal{D}_{x}^{(p)}=\\{x_{p}-x_{q}:q\in[N],x_{p}\neq x_{q}\\}$. Similarly,
for $\boldsymbol{y}$, we define
$\mathcal{D}_{y}^{(p)}=\\{y_{p}-y_{q}:q\in[N],y_{p}\neq y_{q}\\}$. We note
that for every $n\in[N]$, either option (a)
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}=0$
or option (b)
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}\in\mathcal{D}_{x}^{(p)}$
for some $p\in[N]$ as
$(\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}$ is
one of the entries of $\boldsymbol{x}$.

Then, it is sufficient to show there must exist $k\in[K_{2}]$ such that all of
equations in Eq. (24) are induced by the option (a) rather than the option
(b), i.e.,

$\displaystyle\exists k^{*}\in[K_{2}],\forall p,n\in[N]\text{ such that
}(\boldsymbol{I}-\boldsymbol{Q}_{k^{*}}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}\not\in\mathcal{D}_{x}^{(p)}.$
(25)

This is because Eq. (25) implies:

$\displaystyle(\boldsymbol{I}-\boldsymbol{Q}_{k^{*}}\boldsymbol{P}_{x})^{\top}\boldsymbol{x}=\boldsymbol{0}$
$\displaystyle\quad\Rightarrow\quad\boldsymbol{x}=\boldsymbol{Q}_{k^{*}}^{\top}\boldsymbol{P}_{x}\boldsymbol{x}=\boldsymbol{Q}_{k^{*}}^{\top}\boldsymbol{x^{\prime}},$
$\displaystyle\text{(Since $\gamma_{k}\neq 0,\forall
k\in[K_{2}]$)}\quad(\boldsymbol{I}-\boldsymbol{Q}_{k^{*}}\boldsymbol{P}_{y})^{\top}\boldsymbol{y}=\boldsymbol{0}$
$\displaystyle\quad\Rightarrow\quad\boldsymbol{y}=\boldsymbol{Q}_{k^{*}}^{\top}\boldsymbol{P}_{y}\boldsymbol{y}=\boldsymbol{Q}_{k^{*}}^{\top}\boldsymbol{y^{\prime}},$

which is
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}=\boldsymbol{Q}_{k^{*}}^{\top}\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.

To show Eq. (25), we construct $N$ bipartite graphs
$\mathcal{G}^{(p)}=(\mathcal{D}_{x}^{(p)},\mathcal{D}_{y}^{(p)},\mathcal{E}^{(p)})$
for $p\in[N]$ where each $\alpha\in\mathcal{D}_{x}^{(p)}$ or each
$\beta\in\mathcal{D}_{y}^{(p)}$ is viewed as a node and
$(\alpha,\beta)\in\mathcal{E}^{(p)}$ gives an edge if $\alpha=\gamma_{k}\beta$
for some $k\in[K_{2}]$. Then we prove the existence of $k^{*}$ via seeing a
contradiction that does counting the number of connected pairs
$(\alpha,\beta)$ from two perspectives.

##### Perspective of $\mathcal{D}_{x}^{(p)}$.

We argue that for $\forall p\in[N]$ and arbitrary
$\alpha_{1},\alpha_{2}\in\mathcal{D}_{x}^{(p)}$, $\alpha_{1}\neq\alpha_{2}$,
there exists at most one $\beta\in\mathcal{D}_{y}^{(p)}$ such that
$(\alpha_{1},\beta)\in\mathcal{E}^{(p)}$ and
$(\alpha_{2},\beta)\in\mathcal{E}^{(p)}$. Otherwise, suppose there exists
$\beta^{\prime}\in\mathcal{D}_{y}^{(p)}$, $\beta^{\prime}\neq\beta$ such that
$(\alpha_{1},\beta^{\prime})\in\mathcal{E}^{(p)}$ and
$(\alpha_{2},\beta^{\prime})\in\mathcal{E}^{(p)}$. Then we have
$\alpha_{1}=\gamma_{i}\beta$, $\alpha_{2}=\gamma_{j}\beta$,
$\alpha_{1}=\gamma_{k}\beta^{\prime}$, and
$\alpha_{2}=\gamma_{l}\beta^{\prime}$ for some
$\gamma_{i},\gamma_{j},\gamma_{k},\gamma_{l}\in\Gamma$, which is
$\gamma_{i}/\gamma_{k}=\gamma_{k}/\gamma_{l}$. As $\alpha_{1}\neq\alpha_{2}$,
it is obvious that $\gamma_{i}\neq\gamma_{j}$. Similarly, we have
$\gamma_{i}\neq\gamma_{k}$. Altogether, it contradicts our assumption on
$\Gamma$. Therefore, $|\mathcal{E}^{(p)}|\leq
2\max\\{|\mathcal{D}_{x}^{(p)}|,|\mathcal{D}_{y}^{(p)}|\\}\leq 2(N-1)$. And
the total edge number of all bipartite graphs should be less than $2N(N-1)$.

##### Perspective of $\Gamma$.

We note that if for some $k\in[K_{2}]$ that makes
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}\in\mathcal{D}_{x}^{(p)}$
for some $p,n\in[N]$, i.e.,
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}=\gamma_{k}(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{y})_{n}^{\top}\boldsymbol{y}\neq
0$, this $\gamma_{k}$ contributes at least two edges in the entire bipartite
graph, i.e., there being another $n^{\prime}\in[N]$,
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n^{\prime}}^{\top}\boldsymbol{x}=\gamma_{k}(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{y})_{n^{\prime}}^{\top}\boldsymbol{y}\neq
0$. Otherwise, there exists a unique $n^{*}\in[N]$ such that
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n^{*}}^{\top}\boldsymbol{x}\in\mathcal{D}_{x}^{(p)}(\neq
0)$ and
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}=0$
for all $n\neq n^{*}$. This cannot be true because
$\boldsymbol{1}^{\top}(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})\boldsymbol{x}=0$.
By which, if $\forall k\in[K_{2}]$, $\exists p,n\in[N]$ such that
$(\boldsymbol{I}-\boldsymbol{Q}_{k}^{\top}\boldsymbol{P}_{x})_{n}^{\top}\boldsymbol{x}\in\mathcal{D}_{x}^{(p)}$
(i.e., Eq. (25) is always false), then the total number of edges is at least
$2K_{2}=2N(N-1)+2$.

Hereby, we conclude the proof by the contradiction, in which the minimal count
of edges $2K_{2}$ by Perspective of $\Gamma$ already surpasses the maximal
number $2N(N-1)$ by Perspective of $\mathcal{D}_{x}^{(p)}$. ∎

######  Remark D.2.

A handy choice of $\Gamma$ in Lemma D.1 are prime numbers, which are provably
positive, infinitely many, and not divisible by each other.

We wrap off this section by formally stating and proving the injectivity
statement of the LP layer.

######  Theorem D.3.

Suppose $\phi:{}^{D}\rightarrow{}^{L}$ admits the form of Eq. (2),

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\psi_{N}(\boldsymbol{w}_{1}^{\top}\boldsymbol{x})^{\top}&\cdots&\psi_{N}(\boldsymbol{w}_{K}^{\top}\boldsymbol{x})^{\top}\end{bmatrix},$
(26)

where $\psi_{N}$ is the power mapping of degree $N$, $L=KN\leq N^{5}D^{2}$,
$K=D+K_{1}+DK_{1}K_{2}$ and
$\boldsymbol{W}=\begin{bmatrix}\boldsymbol{w}^{(1)}_{1}&\cdots&\boldsymbol{w}^{(1)}_{D}&\boldsymbol{w}^{(2)}_{1}&\cdots&\boldsymbol{w}^{(2)}_{K_{1}}&\cdots&\boldsymbol{w}^{(3)}_{i,j,k}&\cdots\end{bmatrix}$
is constructed as follows:

  1. 1.

Let the first group of weights
$\boldsymbol{w}^{(1)}_{1}=\boldsymbol{e}_{1},\cdots,\boldsymbol{w}^{(1)}_{D}=\boldsymbol{e}_{D}$
to buffer the original features, where $\boldsymbol{e}_{i}$ is the $i$-th
canonical basis.

  2. 2.

Choose the second group of linear weights,
$\boldsymbol{w}^{(2)}_{1},\cdots,\boldsymbol{w}^{(2)}_{K_{1}}$ for $K_{1}$ as
large as $N(N-1)(D-1)/2+1$, such that the conditions in Lemma C.4 are
satisfied.

  3. 3.

Design the third group of weights $\boldsymbol{w}^{(3)}_{i,j,k}$ for
$i\in[D],j\in[K_{1}],k\in[K_{2}]$ where
$\boldsymbol{w}^{(3)}_{i,j,k}=\boldsymbol{e}_{i}-\gamma_{k}\boldsymbol{w}^{(2)}_{j}$,
$K_{2}=N(N-1)+1$, and $\gamma_{k},k\in[K_{2}]$ are chosen such that conditions
in Lemma D.1 are satisfied.

Then $\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$ is injective (cf. Definition
A.7).

###### Proof.

Suppose
$\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})=\sum_{n=1}^{N}\phi(\boldsymbol{x^{\prime}}^{(n)})$
for some $\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$. Due to the
injectivity property of sum-of-power mapping (cf. Lemma B.2):

$\displaystyle\sum_{n=1}^{N}\phi\left(\boldsymbol{x}^{(n)}\right)=\sum_{n=1}^{N}\phi\left(\boldsymbol{x^{\prime}}^{(n)}\right)\Rightarrow$
$\displaystyle\boldsymbol{X}\boldsymbol{w}^{(1)}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(1)}_{i},\forall
i\in[D],\boldsymbol{X}\boldsymbol{w}^{(2)}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{i},\forall
i\in[K_{1}],$ (27)
$\displaystyle\boldsymbol{X}\boldsymbol{w}^{(3)}_{i,j,k}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(3)}_{i,j,k},\forall
i\in[D],j\in[K_{1}],k\in[K_{2}].$

By Lemma C.4, it is guaranteed that there exists $j^{*}\in[K_{1}]$ such that
$\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}$ is an anchor, and according to
Eq. (27), we have
$\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}}$.
By Lemma D.1, we induce:

$\displaystyle\boldsymbol{X}\boldsymbol{w}^{(1)}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(1)}_{i},\forall
i\in[D],\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}},\boldsymbol{X}\boldsymbol{w}^{(3)}_{i,j,k}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}^{(3)}_{i,j,k},\forall
i\in[D],j\in[K_{1}],k\in[K_{2}]$
$\displaystyle\Rightarrow\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix},\forall
i\in[D].$ (28)

Since $\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}$ is an anchor, by union
alignment (Lemma C.2), we have:

$\displaystyle\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}}&\boldsymbol{x^{\prime}}_{i}\end{bmatrix},\forall
i\in[D]\Rightarrow\boldsymbol{X}\sim\boldsymbol{X^{\prime}}.$ (29)

Here $K=D+K_{1}+DK_{1}K_{2}\leq N^{4}D^{2}$, thus $L=KN\leq N^{5}D^{2}$, which
concludes the proof. ∎

###  D.2 Continuity

Next, we show that under the construction of Theorem D.3, the inverse of
$\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$ is continuous. The main idea is to
check the three conditions provided in Lemma 4.9.

######  Theorem D.4.

Suppose $\phi$ admits the form of Eq. (67) and follows the construction in
Theorem D.3, then the inverse of LP-induced sum-pooling
$\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})$ is continuous.

###### Proof.

The proof is done by invoking Lemma 4.9. First of all, the inverse of
$\Phi(\boldsymbol{X})=\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$, denoted as
$\Phi^{-1}$, exists due to Theorem D.3. By Lemma A.6, any closed and bounded
subset of $({}^{N\times D}/\sim,d_{\Pi})$ is compact. Trivially,
$\Phi(\boldsymbol{X})$ is continuous. Then it remains to show the condition
(c) in Lemma 4.9. Same with Corollary B.6 while focusing on the real domain,
let
$\mathcal{Z}_{\Psi_{N}}=\\{\Psi_{N}(\boldsymbol{x}):\boldsymbol{x}\in{}^{N}\\}\subseteq{}^{N}$
be the range of sum-of-power mapping, and define
$\mathcal{Z}_{\Phi}=\\{\Phi(\boldsymbol{X}):\boldsymbol{X}\in{}^{N\times
D}\\}\subseteq\mathcal{Z}_{\Psi_{N}}^{K}$ be the range of $\Phi$, which is
also a subset of $\mathcal{Z}_{\Psi_{N}}^{K}$. We decompose
$\Phi^{-1}=\pi\circ\widehat{\Psi_{N}}^{\dagger}$ into two mappings following
the similar idea of proving its existence:

$\displaystyle\begin{array}[]{ccccc}(\mathcal{Z}_{\Phi},d_{\infty})&\xrightarrow{\widehat{\Psi_{N}}^{\dagger}}&\mathcal{R}\subseteq({}^{N}/\sim,d_{\Pi})^{K}&\xrightarrow{\pi}&({}^{N\times
D}/\sim,d_{\Pi})\end{array},$ (31)

where $\widehat{\Phi_{N}}^{\dagger}$ is defined in Eq. (22) (Corollary B.6),
$\mathcal{R}$ is the image of $\mathcal{Z}$ under
$\widehat{\Phi_{N}}^{\dagger}$, and $\pi$ exists due to union alignment (i.e.,
Eqs. (D.1) and (29) in Theorem D.3). Also according to our construction in
Theorem D.3, for any $\boldsymbol{Z}\in\mathcal{R}$, consider its first $D$
columns produced by $\\{\boldsymbol{w}^{(1)}_{i}=\boldsymbol{e}_{i},\forall
i\in{D}\\}$, we know that $\boldsymbol{z}_{i}\sim\pi(\boldsymbol{Z})_{i}$ for
every $i\in[D]$. Therefore,
$\forall\boldsymbol{Z},\boldsymbol{Z^{\prime}}\in\mathcal{R}$ such that
$d_{\Pi}^{K}(\boldsymbol{Z},\boldsymbol{Z^{\prime}})\leq C$ for some constant
$C>0$ in terms of the product metric $d_{\Pi}^{K}$ (cf. Definition A.2), the
inequality holds:

$\displaystyle
d_{\Pi}(\pi(\boldsymbol{Z}),\pi(\boldsymbol{Z^{\prime}}))\leq\max_{i\in[D]}d_{\Pi}(\boldsymbol{z}_{i},\boldsymbol{z^{\prime}}_{i})\leq
d_{\Pi}^{K}(\boldsymbol{Z},\boldsymbol{Z^{\prime}})\leq C,$ (32)

which implies $\pi$ maps every bounded set in $\mathcal{R}$ to a bounded set
in $({}^{N\times D}/\sim,d_{\Pi})$. Now we conclude the proof by the following
chain of argument:

$\displaystyle\begin{array}[]{ccccc}\text{$\mathcal{S}\subseteq(\mathcal{Z}_{\Phi},d_{\infty})$
is bounded}&\xRightarrow{\text{Corollary
\ref{cor:inv_channelwise_boundedness}}}&\text{$\widehat{\Psi_{N}}^{{\dagger}}(\mathcal{S})$
is
bounded}&\xRightarrow{\text{Eq.~{}\eqref{eqn:lp_perm_boundedness}}}&\text{$\pi\circ\widehat{\Psi_{N}}^{{\dagger}}(\mathcal{S})$
is bounded}.\end{array}$ (34)

∎

###  D.3 Lower Bound for Injectivity

In this section, we prove Theorem 4.6 which shows that $K\geq D+1$ is
necessary for injectivity of LP-induced sum-pooling when $D\geq 2$. Our
argument mainly generalizes Lemma 2 of [55] to our equivalence class. To
proceed our argument, we define the linear subspace $\mathcal{V}$ by
vectorizing
$\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}_{1}&\cdots&\boldsymbol{X}\boldsymbol{w}_{K}\end{bmatrix}$
as below:

$\displaystyle\mathcal{V}:=\left\\{\begin{bmatrix}\boldsymbol{X}\boldsymbol{w}_{1}\\\
\vdots\\\
\boldsymbol{X}\boldsymbol{w}_{K}\end{bmatrix}:\boldsymbol{X}\in{}^{N\times
D}\right\\}=\mathcal{R}\left(\begin{bmatrix}(\boldsymbol{w}_{1}\otimes\boldsymbol{I}_{N})\\\
\vdots\\\ (\boldsymbol{w}_{K}\otimes\boldsymbol{I}_{N})\end{bmatrix}\right),$
(35)

where $\mathcal{R}(\boldsymbol{Z})$ denotes the column space of
$\boldsymbol{Z}$ and $\otimes$ is the Kronecker product. $\mathcal{V}$ is a
linear subspace of NK with dimension at most ND, characterized by
$\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K}\in{}^{D}$. For the sake of
notation simplicity, we denote $\Pi(N)^{\otimes
K}=\\{\operatorname{diag}(\boldsymbol{Q}_{1},\cdots,\boldsymbol{Q}_{K}):\forall\boldsymbol{Q}_{1},\cdots,\boldsymbol{Q}_{K}\in\Pi(N)\\}$,
and
$\boldsymbol{I}_{K}\otimes\Pi(N)=\\{\boldsymbol{I}_{K}\otimes\boldsymbol{Q}:\forall\boldsymbol{Q}\in\Pi(N)\\}$.
Next, we define the notion of unique recoverability [55] as below:

######  Definition D.5 (Unique Recoverability).

The subspace $\mathcal{V}$ is called uniquely recoverable under
$\boldsymbol{Q}\in\Pi(N)^{\otimes K}$ if whenever
$\boldsymbol{x},\boldsymbol{x^{\prime}}\in\mathcal{V}$ satisfy
$\boldsymbol{Q}\boldsymbol{x}=\boldsymbol{x^{\prime}}$, there exists
$\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$,
$\boldsymbol{P}\boldsymbol{x}=\boldsymbol{x^{\prime}}$.

Subsequently, we derive a necessary condition for the unqiue recoverability:

######  Lemma D.6.

A linear subspace $\mathcal{V}\subseteq{}^{NK}$ is uniquely recoverable under
$\boldsymbol{Q}\in\Pi(N)^{\otimes K}$ only if there exists
$\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$,
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subseteq\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$,
where $\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}$ denotes the
eigenspace corresponding to the eigenvalue $\lambda$.

###### Proof.

It is sufficient to prove that
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subseteq\bigcup_{\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(K)}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$.
This is because the LHS is a subspace and the RHS is a union of subspaces.
When a subspace is a subset of a union of subspaces, such a subspace must be a
subset of one of the subspaces, i.e.,
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subseteq\bigcup_{\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(K)}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$
implies there exists $\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(K)$ such
that
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subseteq\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$.

Next, we prove
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subseteq\bigcup_{\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(K)}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$
by contradiction. Suppose there exists
$\boldsymbol{x}\in\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}$ but
$\boldsymbol{x}\notin\bigcup_{\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(K)}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$.
Or equivalently, there exists $\boldsymbol{x^{\prime}}\in\mathcal{V}$ and
$\boldsymbol{x}=\boldsymbol{Q}\boldsymbol{x^{\prime}}$, while for
$\forall\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$,
$\boldsymbol{x}\neq\boldsymbol{Q}\boldsymbol{P}^{\top}\boldsymbol{x}$. This
implies
$\boldsymbol{Q}^{\top}\boldsymbol{x}=\boldsymbol{x^{\prime}}\neq\boldsymbol{P}\boldsymbol{x}$
for $\forall\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$. However, this
contradicts the fact that $\mathcal{V}\subseteq{}^{NK}$ is uniquely
recoverable (cf. Definition D.5). ∎

We also introduce a useful Lemma D.7 that gets rid of the discussion on
$\boldsymbol{Q}$ in the inclusion:

######  Lemma D.7.

Suppose $\mathcal{V}\subseteq{}^{N}$ is a linear subspace, and
$\boldsymbol{A}$ is a linear mapping.
$\boldsymbol{A}(\mathcal{V})\cap\mathcal{V}\cap\mathcal{E}_{\boldsymbol{A},\lambda}=\boldsymbol{0}$
if and only if
$\mathcal{V}\cap\mathcal{E}_{\boldsymbol{A},\lambda}=\boldsymbol{0}$.

###### Proof.

The sufficiency is straightforward. The necessity is shown by contradiction:
Suppose
$\mathcal{V}\cap\mathcal{E}_{\boldsymbol{A},\lambda}\neq\boldsymbol{0}$, then
there exists
$\boldsymbol{x}\in\mathcal{V}\cap\mathcal{E}_{\boldsymbol{A},\lambda}$ such
that $\boldsymbol{x}\neq\boldsymbol{0}$. Then
$\boldsymbol{A}\boldsymbol{x}=\lambda\boldsymbol{x}$ implies
$\boldsymbol{x}\in\boldsymbol{A}(\mathcal{V})$. Hence,
$\boldsymbol{x}\in\boldsymbol{A}(\mathcal{V})\cap\mathcal{V}\cap\mathcal{E}_{\boldsymbol{A},\lambda}$
which reaches the contradiction. ∎

Now we are ready to present the proof of Theorem 4.6, restated below:

######  Theorem D.8 (Lower Bound, Theorem 4.6).

Consider data matrices $\boldsymbol{X}\in{}^{N\times D}$ where $D\geq 2$. If
$K\leq D$, then for every $\boldsymbol{w}_{1},\cdots,\boldsymbol{w}_{K}$,
there exists $\boldsymbol{X^{\prime}}\in{}^{N\times D}$ such that
$\boldsymbol{X}\not\sim\boldsymbol{X^{\prime}}$ but
$\boldsymbol{X}\boldsymbol{w}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}_{i}$
for every $i\in[K]$.

###### Proof.

Proved by contrapositive. First notice that,
$\forall\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times
D},\boldsymbol{X}\boldsymbol{w}_{i}\sim\boldsymbol{X^{\prime}}\boldsymbol{w}_{i},\forall
i\in[K]\Rightarrow\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$ holds if and only
if $\dim\mathcal{V}=ND$ and $\mathcal{V}$ is uniquely recoverable under all
possible $\boldsymbol{Q}\in\Pi(N)^{\otimes K}$. By Lemma D.6, for every
$\boldsymbol{Q}\in\Pi(N)^{\otimes K}$, there exists
$\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$ such that
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\subset\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda=1}$.
This is
$\boldsymbol{Q}(\mathcal{V})\cap\mathcal{V}\cap\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}=0$
for all $\lambda\neq 1$. By Lemma D.7, we have
$\mathcal{V}\cap\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}=0$
for all $\lambda\neq 1$. Then proof is concluded by discussing the dimension
of ambient space NK such that an $ND$-dimensional subspace $\mathcal{V}$ can
reside. To ensure
$\mathcal{V}\cap\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}=0$
for all $\lambda\neq 1$, it is necessary that
$\dim\mathcal{V}\leq\min_{\lambda\neq
1}\operatorname{codim}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}$
for every $\boldsymbol{Q}\in\Pi(N)^{\otimes K}$ and its associated
$\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)$. Relaxing the dependence
between $\boldsymbol{Q}$ and $\boldsymbol{P}$, we derive the inequality:

$\displaystyle ND=\dim\mathcal{V}\leq\min_{\boldsymbol{Q}\in\Pi(N)^{\otimes
K}}\max_{\boldsymbol{P}\in\boldsymbol{I}_{K}\otimes\Pi(N)}\min_{\lambda\neq
1}\operatorname{codim}\mathcal{E}_{\boldsymbol{Q}\boldsymbol{P}^{\top},\lambda}\leq
NK-1,$ (36)

where the last inequality considers the scenario where every non-one
eigenspace is one-dimensional, which is achievable when $K\geq 2$. Hence, we
can bound $K\geq D+1/K$, i.e., $K\geq D+1$. ∎

##  Appendix E Proofs for LE Embedding Layer

In this section, we present the complete proof for the LE embedding layer
following Sec. 4.1.3.

###  E.1 Upper Bound for Injectivity

To prove the upper bound, we construct an LE embedding layer with $L\leq
N^{4}D^{2}$ output neurons such that its induced sum-pooling is injective. The
main construction idea is to couple every channel and anchor with the real and
imaginary components of complex numbers and invoke the injectiviy of sum-of-
power mapping over the complex domain to show the invertibility.

With Lemma B.2, we can prove Lemma 4.8 restated and proved as below:

######  Lemma E.1.

For any pair of vectors
$\boldsymbol{x},\boldsymbol{y}\in{}^{N},\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}}\in{}^{N}$,
if
$\sum_{i\in[N]}\boldsymbol{x}_{i}^{l-k}\boldsymbol{y}_{i}^{k}=\sum_{i\in[N]}\boldsymbol{x^{\prime}}_{i}^{l-k}\boldsymbol{y^{\prime}}_{i}^{k}$
for every $l,k\in[N]$ such that $0\leq k\leq l$, then
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.

###### Proof.

If for any pair of vectors
$\boldsymbol{x},\boldsymbol{y}\in{}^{N},\boldsymbol{x^{\prime}},\boldsymbol{y^{\prime}}\in{}^{N}$
such that
$\sum_{i\in[N]}\boldsymbol{x}_{i}^{l-k}\boldsymbol{y}_{i}^{k}=\sum_{i\in[N]}\boldsymbol{x^{\prime}}_{i}^{l-k}\boldsymbol{y^{\prime}}_{i}^{k}$
for every $l,k\in[N]$, $0\leq k\leq l$, then for $\forall l\in[N]$,

$\displaystyle\sum_{i=1}^{N}\psi_{N}(\boldsymbol{x}_{i}+\boldsymbol{y}_{i}\sqrt{-1})_{l}=\sum_{i=1}^{N}(\boldsymbol{x}_{i}+\boldsymbol{y}_{i}\sqrt{-1})^{l}$
(37)
$\displaystyle=\sum_{i=1}^{N}\sum_{k=0}^{l}(\sqrt{-1})^{k}\boldsymbol{x}_{i}^{l-k}\boldsymbol{y}_{i}^{k}=\sum_{k=0}^{l}(\sqrt{-1})^{k}\left(\sum_{i=1}^{N}\boldsymbol{x}_{i}^{l-k}\boldsymbol{y}_{i}^{k}\right)$
(38)
$\displaystyle=\sum_{k=0}^{l}(\sqrt{-1})^{k}\left(\sum_{i=1}^{N}\boldsymbol{x^{\prime}}_{i}^{l-k}\boldsymbol{y^{\prime}}_{i}^{k}\right)=\sum_{i=1}^{N}\sum_{k=0}^{l}(\sqrt{-1})^{k}\boldsymbol{x^{\prime}}_{i}^{l-k}\boldsymbol{y^{\prime}}_{i}^{k}$
(39)
$\displaystyle=\sum_{i=1}^{N}(\boldsymbol{x^{\prime}}_{i}+\boldsymbol{y^{\prime}}_{i}\sqrt{-1})^{l}=\sum_{i=1}^{N}\psi_{N}(\boldsymbol{x^{\prime}}_{i}+\boldsymbol{y^{\prime}}_{i}\sqrt{-1})_{l},$
(40)

in which we reorganize terms in the summation and apply the given condition to
establish equality between Eq. (38) and (39). $\psi_{N}$ denotes the complex
power mapping of degree $N$ (cf. Definition B.1). Consider Eq. (40) for every
$l\in[N]$, we can yield:

$\displaystyle\Psi_{N}\left(\boldsymbol{x}+\boldsymbol{y}\sqrt{-1}\right)=\Psi_{N}\left(\boldsymbol{x^{\prime}}+\boldsymbol{y^{\prime}}\sqrt{-1}\right),$

where $\Psi_{N}$ is the sum-of-power mapping (cf. Definition B.1). Then by
Lemma B.2, we have
$(\boldsymbol{x}+\boldsymbol{y}\sqrt{-1})\sim(\boldsymbol{x^{\prime}}+\boldsymbol{y^{\prime}}\sqrt{-1})$,
which is equivalent to the statement
$\begin{bmatrix}\boldsymbol{x}&\boldsymbol{y}\end{bmatrix}\sim\begin{bmatrix}\boldsymbol{x^{\prime}}&\boldsymbol{y^{\prime}}\end{bmatrix}$.
∎

######  Lemma E.2.

Suppose $f:\real\rightarrow\real$ is an injective function. We denote
$f(\boldsymbol{X})$ as applying $f$ element-wisely to entries in
$\boldsymbol{X}$, i.e.,
$f(\boldsymbol{X})_{i,j}=f(\boldsymbol{X}_{i,j}),\forall i\in[N],j\in[D]$.
Then for any $\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$,
$f(\boldsymbol{X})\sim f(\boldsymbol{X^{\prime}})$ implies
$\boldsymbol{X}\sim\boldsymbol{X^{\prime}}$.

###### Proof.

Since $f(\boldsymbol{X})\sim f(\boldsymbol{X^{\prime}})$, there exists
$\boldsymbol{P}\in\Pi(N)$ such that
$f(\boldsymbol{X})=\boldsymbol{P}f(\boldsymbol{X^{\prime}})$. Notice that
element-wise functions are permutation-equivariant, then
$f(\boldsymbol{X})=f(\boldsymbol{P}\boldsymbol{X^{\prime}})$. Since $f$ is
injective, we conclude the proof by applying its inverse $f^{-1}$ to both
sides. ∎

######  Lemma E.3.

Suppose $f:\real\rightarrow\real$ is an injective function. We denote
$f(\boldsymbol{X})$ as applying $f$ element-wisely to entries in
$\boldsymbol{X}$, i.e.,
$f(\boldsymbol{X})_{i,j}=f(\boldsymbol{X}_{i,j}),\forall i\in[N],j\in[D]$. For
any $\boldsymbol{X}\in{}^{N\times D}$, if $\boldsymbol{a}$ is an anchor of
$\boldsymbol{X}$ (cf. Definition 4.1), then $f(\boldsymbol{a})$ is also an
anchor of $f(\boldsymbol{X})$.

###### Proof.

Proved by contradiction. Suppose $f(\boldsymbol{a})$ is not an anchor of
$f(\boldsymbol{X})$. Then there exists $i,j\in[N]$,
$f(\boldsymbol{x}^{(i)})\neq f(\boldsymbol{x}^{(j)})$ while
$f(\boldsymbol{a}_{i})=f(\boldsymbol{a}_{j})$. Since $f$ is injective, then
$f(\boldsymbol{x}^{(i)})\neq f(\boldsymbol{x}^{(j)})$ implies
$\boldsymbol{x}^{(i)}\neq\boldsymbol{x}^{(j)}$, whereas
$f(\boldsymbol{a}_{i})=f(\boldsymbol{a}_{j})$ induces
$\boldsymbol{a}_{i}=\boldsymbol{a}_{j}$. This leads to a contradiction. ∎

Now we are ready to prove the injectiviy of the LE layer.

######  Theorem E.4.

Suppose $\phi:{}^{D}\rightarrow{}^{L}$ admits the form of Eq. (3):

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\exp(\boldsymbol{v}_{1}^{\top}\boldsymbol{x})&\cdots&\exp(\boldsymbol{v}_{L}^{\top}\boldsymbol{x})\end{bmatrix},$
(41)

where $L=DK_{1}N(N+3)/2\leq N^{4}D^{2}$,
$\boldsymbol{V}=\begin{bmatrix}\cdots&\boldsymbol{v}_{i,j,p,q}&\cdots\end{bmatrix}\in{}^{D\times
L}$, $i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$, are constructed as follows:

  1. 1.

Let a group of weights
$\boldsymbol{w}^{(1)}_{1}=\boldsymbol{e}_{1},\cdots,\boldsymbol{w}^{(1)}_{D}=\boldsymbol{e}_{D}$,
where $\boldsymbol{e}_{i}$ is the $i$-th canonical basis.

  2. 2.

Choose another group of linear weights,
$\boldsymbol{w}^{(2)}_{1},\cdots,\boldsymbol{w}^{(2)}_{K_{1}}\in{}^{D}$ for
$K_{1}$ as large as $N(N-1)(D-1)/2+1$, such that the conditions in Lemma C.4
are satisfied.

  3. 3.

Design the weight matrix as $\boldsymbol{v}_{i,j,p,q}\in{}^{D}$ for
$i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$ such that
$\boldsymbol{v}_{i,j,p,q}=(q-1)\boldsymbol{w}^{(1)}_{i}+(p-q+1)\boldsymbol{w}^{(2)}_{j}$.

Then $\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$ is injective (cf. Definition
A.7).

###### Proof.

First of all, we count the number of weight vectors
$\\{\boldsymbol{v}_{i,j,p,q}\\}$ where
$i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$:
$L=DK_{1}\sum_{p=1}^{N}(p+1)=DK_{1}(N+3)N/2\leq N^{4}D^{2}$, as desired.

Let
$\boldsymbol{\Omega}=\begin{bmatrix}\boldsymbol{w}^{(1)}_{1}&\cdots&\boldsymbol{w}^{(1)}_{D}&\boldsymbol{w}^{(2)}_{1}&\cdots&\boldsymbol{w}^{(2)}_{K_{1}}\end{bmatrix}\in{}^{D\times(D+K_{1})}$,
and
$\boldsymbol{u}_{i,j,p,q}=(q-1)\boldsymbol{e}_{i}+(p-q+1)\boldsymbol{e}_{j+D}\in{}^{D+K_{1}}$,
then we can rewrite
$\boldsymbol{v}_{i,j,p,q}=\boldsymbol{\Omega}\boldsymbol{u}_{i,j,p,q}$ for
every $i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$. Then, for
$\boldsymbol{x}\in{}^{D}$, we can cast Eq. (41) into:

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\cdots&\exp(\boldsymbol{u}_{i,j,p,q}^{\top}\boldsymbol{\Omega}^{\top}\boldsymbol{x})&\cdots\end{bmatrix}=\begin{bmatrix}\cdots&\exp(\boldsymbol{u}_{i,j,p,q}^{\top}\log(\exp(\boldsymbol{\Omega}^{\top}\boldsymbol{x})))&\cdots\end{bmatrix},$
(42)

where $\log(\cdot)$ and $\exp(\cdot)$ operate on vectors element-wisely. By
the arithmetic rule of exponential and logarithm, we can rewrite for $\forall
i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$

$\displaystyle\phi(\boldsymbol{x})_{i,j,p,q}$
$\displaystyle=\exp(\boldsymbol{u}_{i,j,p,q}^{\top}\log(\exp(\boldsymbol{\Omega}^{\top}\boldsymbol{x})))=\prod_{k=1}^{D+K_{1}}\left[\exp\left(\boldsymbol{\Omega}^{\top}\boldsymbol{x}\right)_{k}\right]^{\left(\boldsymbol{u}_{i,j,p,q}\right)_{k}}$
(43)
$\displaystyle=\exp(\boldsymbol{w}^{(1)\top}_{i}\boldsymbol{x})^{q-1}\exp(\boldsymbol{w}^{(2)\top}_{j}\boldsymbol{x})^{p-q+1}=\exp(\boldsymbol{x}_{i})^{q-1}\exp(\boldsymbol{w}^{(2)\top}_{j}\boldsymbol{x})^{p-q+1}.$
(44)

Then for $\boldsymbol{X},\boldsymbol{X^{\prime}}\in{}^{N\times D}$, we have:

$\displaystyle\sum_{n\in[N]}\phi\left(\boldsymbol{x}^{(n)}\right)$
$\displaystyle=\sum_{n\in[N]}\phi\left(\boldsymbol{x^{\prime}}^{(n)}\right)$
(45) $\displaystyle\Updownarrow$ (46)
$\displaystyle\sum_{n\in[N]}\exp(\boldsymbol{x}_{i})_{n}^{q-1}\exp\left(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j}\right)_{n}^{p-q+1}$
$\displaystyle=\sum_{n\in[N]}\exp(\boldsymbol{x^{\prime}_{i}})_{n}^{q-1}\exp\left(\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j}\right)_{n}^{p-q+1},$
(47) $\displaystyle\forall i\in[D],j\in[K_{1}],p\in[N],q\in[p+1].$

By Lemma E.1, we obtain that
$\begin{bmatrix}\exp(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j})&\exp(\boldsymbol{x}_{i})\end{bmatrix}\sim\begin{bmatrix}\exp(\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j})&\exp(\boldsymbol{x^{\prime}}_{i})\end{bmatrix}$
for $\forall i\in[D],j\in[K_{1}]$. By Lemma C.4, there exists
$j^{*}\in[K_{1}]$ such that $\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}$ is an
anchor of $\boldsymbol{X}$. By Lemma E.3,
$\exp(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}})$ is also an anchor of
$\exp(\boldsymbol{X})$. By union alignment (Lemma C.2), we have:

$\displaystyle\begin{bmatrix}\exp\left(\boldsymbol{X}\boldsymbol{w}^{(2)}_{j^{*}}\right)&\exp(\boldsymbol{x}_{i})\end{bmatrix}\sim\begin{bmatrix}\exp\left(\boldsymbol{X^{\prime}}\boldsymbol{w}^{(2)}_{j^{*}}\right)&\exp(\boldsymbol{x^{\prime}}_{i})\end{bmatrix},\forall
i\in[D]\Rightarrow\exp(\boldsymbol{X})\sim\exp(\boldsymbol{X^{\prime}}).$ (48)

Finally, we conclude the proof by Lemma E.2:

$\displaystyle\exp(\boldsymbol{X})\sim\exp(\boldsymbol{X^{\prime}})\Rightarrow\boldsymbol{X}\sim\boldsymbol{X^{\prime}}.$
(49)

∎

###  E.2 Continuity

The proof idea of continuity for LE layer shares the similar spirit with the
LP layer, but involves additional steps. This is because we cannot directly
achieve the end-to-end boundedness for condition (c) in Lemma 4.9 if
decomposing the inverse map of the sum-pooling, following the proof idea of
injectivity (cf. Theorem E.4), since the last step (Eq. (49)) requires taking
logarithm over $\exp(\boldsymbol{X})$ while logarithm does not preserve
boundedness.

######  Theorem E.5.

Suppose $\phi$ admits the form of Eq. (41) and follows the construction in
Theorem E.4, then the inverse of LE-induced sum-pooling
$\sum_{n=1}^{N}\phi(\boldsymbol{x}^{(n)})$ is continuous.

###### Proof.

Our proof requires the following mathematical tool to help rewrite $\phi$.
First, following the construction in Theorem E.4 and by Eq. 42, we can rewrite
$\phi(\boldsymbol{x})$ as:

$\displaystyle\phi(\boldsymbol{x})=\begin{bmatrix}\cdots&\exp(\boldsymbol{u}_{i,j,p,q}^{\top}\log(\exp(\boldsymbol{\Omega}^{\top}\boldsymbol{x})))&\cdots\end{bmatrix},$
(50)

where
$\boldsymbol{\Omega}=\begin{bmatrix}\boldsymbol{W}^{(1)}&\boldsymbol{W}^{(2)}\end{bmatrix}$,
$\boldsymbol{W}^{(1)}=\boldsymbol{I}_{D}$, and
$\boldsymbol{W}^{(2)}=\begin{bmatrix}\boldsymbol{w}^{(2)}_{1}&\cdots&\boldsymbol{w}^{(2)}_{K_{1}}\end{bmatrix}$.
Define $\widehat{\phi}:{}_{>0}^{D}\rightarrow{}^{L}$ as below:

$\displaystyle\widehat{\phi}(\boldsymbol{x})=\begin{bmatrix}\cdots&\exp\left(\boldsymbol{u}_{i,j,p,q}^{\top}\log\left(\begin{bmatrix}\boldsymbol{x}\\\
\exp(\boldsymbol{W}^{(2)\top}\log(\boldsymbol{x}))\end{bmatrix}\right)\right)&\cdots\end{bmatrix}.$
(51)

Notice that $\phi(\boldsymbol{x})=\widehat{\phi}\circ\exp(\boldsymbol{x})$.
Recall $\Phi(\boldsymbol{X})=\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})$ and
define $\widehat{\Phi}:{}_{>0}^{D}\rightarrow{}^{L}$ as
$\widehat{\Phi}(\boldsymbol{X})=\sum_{i=1}^{N}\hat{\phi}(\boldsymbol{x}^{(i)})$,
and then $\Phi(\boldsymbol{X})=\widehat{\Phi}(\exp(\boldsymbol{X}))$. The
proof can be concluded by two steps: 1) notice that $\widehat{\Phi}$ has a
continuous inverse $\widehat{\Phi}^{-1}$ by Lemma E.6 and E.7, and then 2)
show that the continuous inverse of $\Phi$ exists by letting
$\Phi^{-1}(\boldsymbol{X})=\log\circ\widehat{\Phi}^{-1}(\boldsymbol{X})$. ∎

######  Lemma E.6.

Consider $\widehat{\phi}:{}_{>0}^{D}\rightarrow{}^{L}$ as defined in Eq. (51),
Theorem E.5, then
$\widehat{\Phi}(\boldsymbol{X})=\sum_{i=1}^{N}\widehat{\phi}(\boldsymbol{x}^{(i)})$
is injective.

###### Proof.

We use the fact that
$\widehat{\phi}(\boldsymbol{x})=\phi\circ\log(\boldsymbol{x})$, and borrow the
same proof from Theorem E.4:

$\displaystyle\sum_{n\in[N]}\widehat{\phi}\left(\boldsymbol{x}^{(n)}\right)$
$\displaystyle=\sum_{n\in[N]}\widehat{\phi}\left(\boldsymbol{x^{\prime}}^{(n)}\right)$
(52) $\displaystyle\Updownarrow$
$\displaystyle\sum_{n\in[N]}(\boldsymbol{x}_{i})_{n}^{q-1}\exp\left(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j}\right)_{n}^{p-q+1}$
$\displaystyle=\sum_{n\in[N]}(\boldsymbol{x^{\prime}_{i}})_{n}^{q-1}\exp\left(\log(\boldsymbol{X^{\prime}})\boldsymbol{w}^{(2)}_{j}\right)_{n}^{p-q+1},$
(53) $\displaystyle\forall i\in[D],j\in[K_{1}],p\in[N],q\in[p+1].$

By Lemma E.1, we obtain that
$\begin{bmatrix}\exp(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j})&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\exp(\log(\boldsymbol{X^{\prime}})\boldsymbol{w}^{(2)}_{j})&\boldsymbol{x^{\prime}}_{i}\end{bmatrix}$
for $\forall i\in[D],j\in[K_{1}]$. By Lemma C.4, there exists
$j^{*}\in[K_{1}]$ such that $\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j^{*}}$
is an anchor of $\log(\boldsymbol{X})$. By Lemma E.3,
$\exp(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j^{*}})$ is also an anchor of
$\boldsymbol{X}$. By union alignment (Lemma C.2):

$\displaystyle\begin{bmatrix}\exp\left(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j^{*}}\right)&\boldsymbol{x}_{i}\end{bmatrix}\sim\begin{bmatrix}\exp\left(\log(\boldsymbol{X^{\prime}})\boldsymbol{w}^{(2)}_{j^{*}}\right)&\boldsymbol{x^{\prime}}_{i}\end{bmatrix},\forall
i\in[D]\Rightarrow\boldsymbol{X}\sim\boldsymbol{X^{\prime}}.$ (54)

∎

######  Lemma E.7.

Consider $\widehat{\phi}:{}_{>0}^{D}\rightarrow{}^{L}$ and
$\widehat{\Phi}(\boldsymbol{X})=\sum_{i=1}^{N}\widehat{\phi}(\boldsymbol{x}^{(i)})$
as defined in Eq. (51), Theorem E.5. Let
$\mathcal{Z}_{\widehat{\Phi}}=\\{\widehat{\Phi}(\boldsymbol{X}):\boldsymbol{X}\in{}_{>0}^{N\times
D}\\}\subseteq{}^{L}$. Note that
$\mathcal{Z}_{\widehat{\Phi}}=\mathcal{Z}_{\Phi}(\triangleq\\{\Phi(\boldsymbol{X}):\boldsymbol{X}\in{}^{N\times
D}\\})$. Then $\widehat{\Phi}:{}_{>0}^{N\times
D}\rightarrow\mathcal{Z}_{\widehat{\Phi}}$ has inverse $\widehat{\Phi}^{-1}$,
which is continuous.

###### Proof.

Since we constrain the image of $\widehat{\Phi}$ to be the range,
$\widehat{\Phi}$ becomes surjective. Then invertibility is simply induced by
injectivity (Lemma E.6).

Now it remains to show $\widehat{\Phi}^{-1}$ is continuous, which is done by
verifying three conditions in Lemma 4.9. By Lemma A.6, any closed and bounded
subset of $({}_{>0}^{N\times D}/\sim,d_{\Pi})$ is compact. Obviously,
$\widehat{\Phi}(\boldsymbol{X})$ is continuous. And for condition (c) in Lemma
4.9, we will decompose $\widehat{\Phi}^{-1}$ into a series bounded mappings
following the clue of proving its existence, similar to Theorem D.4. Recall
each element in $\widehat{\Phi}(\boldsymbol{X})$ has the form
$\sum_{n\in[N]}(\boldsymbol{x}_{i})_{n}^{q-1}\exp\left(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j}\right)_{n}^{p-q+1}$
for some $i\in[D],j\in[K_{1}],p\in[N],q\in[p+1]$ (cf. Eq. (53) in Lemma E.6).
Hence, by Eq. 38 shown in Lemma E.1, $\widehat{\Phi}$ can be transformed into
a sum-of-power mapping (cf. Definition B.1) via a (complex-valued) linear
mapping:
$\Psi_{N}(\boldsymbol{x}_{i}+\exp(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j})\sqrt{-1})=\boldsymbol{\Upsilon}_{i,j}\widehat{\Phi}(\boldsymbol{X})$,
where $\boldsymbol{\Upsilon}_{i,j}\in\mathbb{C}^{N\times L}$ for every
$i\in[D],j\in[K_{1}]$. Let $K=DK_{1}$ and concatenate
$\boldsymbol{\Upsilon}_{i,j}$:
$\boldsymbol{\Upsilon}=\begin{bmatrix}\cdots&\boldsymbol{\Upsilon}_{i,j}&\cdots\end{bmatrix}\in\mathbb{C}^{NK\times
L}$. Recall
$\mathcal{Z}_{\Psi_{N}}=\\{\Psi_{N}(\boldsymbol{x}):\boldsymbol{x}\in\mathbb{C}^{N}\\}\subseteq\mathbb{C}^{N}$
denotes the range of the sum-of-power mapping.

Then we leverage the following decomposition to demonstrate the end-to-end
boundedness:

$\displaystyle\begin{array}[]{ccccccc}(\mathcal{Z}_{\widehat{\Phi}},d_{\infty})&\xrightarrow{\boldsymbol{\Upsilon}}&\mathcal{O}\subseteq(\mathcal{Z}_{\Psi_{N}}^{K},d_{\infty})&\xrightarrow{\widehat{\Psi_{N}}^{{\dagger}}}&\mathcal{R}\subseteq(\mathbb{C}^{N}/\sim,d_{\Pi})^{K}&\xrightarrow{\pi}&({}_{>0}^{N\times
D}/\sim,d_{\Pi})\end{array},$ (56)

where $\widehat{\Psi_{N}}^{{\dagger}}$ is defined in Eq. (22) (Corollary B.6),
$\mathcal{O}$, $\mathcal{R}$ are ranges of $\boldsymbol{\Upsilon}$ and
$\widehat{\Psi_{N}}^{{\dagger}}$, respectively, and $\pi$ exists due to union
alignment (cf. Eq. 54 and Lemma C.2). Therefore, for any
$\boldsymbol{Z}\in\mathcal{R}$ , there exists
$\boldsymbol{X}\in({}_{>0}^{N\times D}/\sim,d_{\Pi})$ such that
$\pi(\boldsymbol{Z})\sim\boldsymbol{X}$. We denote
$\boldsymbol{Z}=\begin{bmatrix}\cdots&\boldsymbol{z}_{i,j}&\cdots\end{bmatrix},\forall
i\in[D],j\in[K_{1}]$. In the meanwhile, according to our construction of
$\widehat{\Psi_{N}}^{\dagger},\boldsymbol{\Upsilon},\widehat{\Phi}$, we
demonstrate the relationship between $\boldsymbol{Z}$ and
$\pi(\boldsymbol{Z})\sim\boldsymbol{X}$:

$\displaystyle\boldsymbol{z}_{i,j}\sim\widehat{\Psi_{N}}^{\dagger}\left[\boldsymbol{\Upsilon}\widehat{\Phi}(\boldsymbol{X})\right]_{i,j}\sim\Psi_{N}^{-1}\left[\boldsymbol{\Upsilon}_{i,j}\widehat{\Phi}(\boldsymbol{X})\right]\sim\left(\boldsymbol{x}_{i}+\exp(\log(\boldsymbol{X})\boldsymbol{w}^{(2)}_{j})\sqrt{-1}\right)$
(57) $\displaystyle\forall i\in[D],j\in[K_{1}],$

With this relationship, now we consider
$\forall\boldsymbol{Z},\boldsymbol{Z^{\prime}}\in\mathcal{R}$ such that
$d_{\Pi}^{K}(\boldsymbol{Z},\boldsymbol{Z^{\prime}})\leq C$ for some constant
$C>0$ and the product metric $d_{\Pi}^{K}$ (cf. Definition A.2), we have
inequality:

$\displaystyle
d_{\Pi}(\pi(\boldsymbol{Z}),\pi(\boldsymbol{Z^{\prime}}))=d_{\Pi}(\pi(\boldsymbol{Z})_{i^{*}},\pi(\boldsymbol{Z^{\prime}})_{i^{*}})\leq\max_{j\in[K_{1}]}d_{\Pi}(\boldsymbol{z}_{i^{*},j},\boldsymbol{z^{\prime}}_{i^{*},j})\leq
d_{\Pi}^{K}(\boldsymbol{Z},\boldsymbol{Z^{\prime}})\leq C,$ (58)

where $i^{*}\in[D]$ is the column which $\ell_{\infty,\infty}$-norm takes
value at (cf. Definition A.3). Eq. (58) implies $\pi$ maps every bounded set
in $\mathcal{R}$ to a bounded set in $({}^{N\times D}/\sim,d_{\Pi})$. Now we
conclude the proof by the following chain of argument:

$\displaystyle\begin{array}[]{ccccc}&\text{$\mathcal{S}\subseteq(\mathcal{Z}_{\widehat{\Phi}},d_{\infty})$
is bounded}&\xRightarrow{(*)}&\text{$\boldsymbol{\Upsilon}(\mathcal{S})$ is
bounded}\xRightarrow{\text{Corollary
\ref{cor:inv_channelwise_boundedness}}}\\\
&\text{$\widehat{\Psi_{N}}^{\dagger}\circ\boldsymbol{\Upsilon}(\mathcal{S})$
is
bounded}&\xRightarrow{\text{Eq.~{}\eqref{eqn:lle_perm_boundedness}}}&\text{$\pi\circ\widehat{\Psi_{N}}^{\dagger}\circ\boldsymbol{\Upsilon}(\mathcal{S})$
is bounded},\end{array}$ (61)

where $(*)$ holds due to that $\boldsymbol{\Upsilon}$ is a finite-dimensional
linear mapping.

∎

##  Appendix F Extension to Permutation Equivariance

In this section, we prove Theorem 5.1, the extension of Theorem 3.1 to
equivariant functions, following the similar arguments with [7]:

######  Lemma F.1 ([7, 34]).

$f:{}^{N\times D}\rightarrow{}^{N}$ is a permutation-equivariant function if
and only if there is a function $\tau:{}^{N\times D}\rightarrow\mathbb{R}$
that is permutation invariant to the last $N-1$ entries, such that
$f(\boldsymbol{Z})_{i}=\tau(\boldsymbol{z}^{(i)},\underbrace{\boldsymbol{z}^{(i+1)},\cdots,\boldsymbol{z}^{(N)},\cdots,\boldsymbol{z}^{(i-1)}}_{N-1})$
for any $i\in[N]$.

###### Proof.

(Sufficiency) Define $\pi:[N]\rightarrow[N]$ be an index mapping associated
with the permutation matrix $\boldsymbol{P}\in\Pi(N)$ such that
$\boldsymbol{P}\boldsymbol{Z}=\begin{bmatrix}\boldsymbol{z}^{(\pi(1))},\cdots,\boldsymbol{z}^{(\pi(N))}\end{bmatrix}^{\top}$.
Then we have:

$\displaystyle
f\left(\boldsymbol{z}^{(\pi(1))},\cdots,\boldsymbol{z}^{(\pi(N))}\right)_{i}=\tau\left(\boldsymbol{z}^{(\pi(i))},\boldsymbol{z}^{(\pi(i+1))},\cdots,\boldsymbol{z}^{(\pi(N))},\cdots,\boldsymbol{z}^{(\pi(i-1))}\right).$

Since $\tau(\cdot)$ is invariant to the last $N-1$ entries, it can shown that:

$\displaystyle
f(\boldsymbol{P}\boldsymbol{Z})_{i}=\tau\left(\boldsymbol{z}^{(\pi(i))},\boldsymbol{z}^{(\pi(i+1))},\cdots,\boldsymbol{z}^{(\pi(N))},\cdots,\boldsymbol{z}^{(\pi(i-1))}\right)=f(\boldsymbol{Z})_{\pi(i)}.$

(Necessity) Given a permutation-equivariant function $f:{}^{N\times
D}\rightarrow{}^{N}$, we first expand it to the following form:
$f(\boldsymbol{Z})_{i}=\tau_{i}(\boldsymbol{z}^{(1)},\cdots,\boldsymbol{z}^{(N)})$.
Permutation-equivariance means
$\tau_{\pi(i)}(\boldsymbol{z}^{(1)},\cdots,\boldsymbol{z}^{(N)})=\tau_{i}(\boldsymbol{z}^{\pi(1)},\cdots,\boldsymbol{z}^{\pi(N)})$
for any permutation mapping $\pi$. Suppose given an index $i\in[N]$, consider
any permutation $\pi:[N]\rightarrow[N]$ such that $\pi(i)=i$. Then, we have:

$\displaystyle\tau_{i}\left(\boldsymbol{z}^{(1)},\cdots,\boldsymbol{z}^{(i)},\cdots,\boldsymbol{z}^{(N)}\right)=\tau_{\pi(i)}\left(\boldsymbol{z}^{(1)},\cdots,\boldsymbol{z}^{(i)},\cdots,\boldsymbol{z}^{(N)}\right)=\tau_{i}\left(\boldsymbol{z}^{(\pi(1))},\cdots,\boldsymbol{z}_{i},\cdots,\boldsymbol{z}^{(\pi(N))}\right),$

which implies $\tau_{i}:{}^{N\times D}\rightarrow\real$ must be invariant to
the $N-1$ elements other than the $i$-th element. Now, consider a permutation
$\pi$ where $\pi(1)=i$. Then we have:

$\displaystyle\tau_{i}\left(\boldsymbol{z}^{(1)},\boldsymbol{z}^{(2)},\cdots,\boldsymbol{z}^{(N)}\right)$
$\displaystyle=\tau_{\pi(1)}\left(\boldsymbol{z}^{(1)},\boldsymbol{z}^{(2)},\cdots,\boldsymbol{z}^{(N)}\right)=\tau_{1}\left(\boldsymbol{z}^{(\pi(1))},\boldsymbol{z}^{(\pi(2))},\cdots,\boldsymbol{z}^{(\pi(N))}\right)$
$\displaystyle=\tau_{1}\left(\boldsymbol{z}^{(i)},\boldsymbol{z}^{(i+1)},\cdots,\boldsymbol{z}^{(N)},\cdots,\boldsymbol{z}^{(i-1)}\right),$

where the last equality is due to the invariance to $N-1$ elements, stated
beforehand. This implies two results. First, for all $i$,
$\tau_{i}(\boldsymbol{z}^{(1)},\boldsymbol{z}^{(2)},\cdots,\boldsymbol{z}^{(i)},\cdots,\boldsymbol{z}^{(N)}),\forall
i\in[N]$ should be written in terms of
$\tau_{1}(\boldsymbol{z}^{(i)},\boldsymbol{z}^{(i+1)},\cdots,\boldsymbol{z}^{(N)},\cdots,\boldsymbol{z}^{(i-1)})$.
Moreover, $\tau_{1}$ is permutation invariant to its last $N-1$ entries.
Therefore, we just need to set $\tau=\tau_{1}$ and broadcast it accordingly to
all entries. We conclude the proof. ∎

The following result, restated from Theorem 5.1, can be proved with Lemma F.1
and Theorem 3.1.

######  Theorem F.2 (Extension to Equivariance, Theorem 5.1).

For any permutation-equivariant function $f:\mathcal{K}^{N\times
D}\rightarrow{}^{N}$, $\mathcal{K}\subseteq\real$, there exists continuous
functions $\phi:{}^{D}\rightarrow{}^{L}$ and
$\rho:{}^{D}\times{}^{L}\rightarrow\real$ such that
$f(\boldsymbol{X})_{j}=\rho\left(\boldsymbol{x}^{(j)},\sum_{i\in[N]}\phi(\boldsymbol{x}^{(i)})\right)$
for every $j\in[N]$, where $L\in[N(D+1),N^{5}D^{2}]$ when $\phi$ admits LP
architecture, and $L\in[ND,N^{4}D^{2}]$ when $\phi$ admits LE architecture.

###### Proof.

Sufficiency can be shown by verifying the equivariance. We conclude the proof
by showing the necessity with Lemma F.1. First we rewrite any permutation
equivariant function
$f(\boldsymbol{x}^{(1)},\cdots,\boldsymbol{x}^{(N)}):{}^{N\times
D}\rightarrow{}^{N}$ as:

$\displaystyle
f\left(\boldsymbol{x}^{(1)},\cdots,\boldsymbol{x}^{(N)}\right)_{i}=\tau\left(\boldsymbol{x}^{(i)},\boldsymbol{x}^{(i+1)},\cdots,\boldsymbol{x}^{(N)},\cdots,\boldsymbol{x}^{(i-1)}\right),$
(62)

where $\tau:{}^{N\times D}\rightarrow\real$ is invariant to the last $N-1$
elements, according to Lemma F.1. Given $\phi$ with either LP or LE
architectures,
$\Phi(\boldsymbol{X})=\sum_{i=1}^{N}\phi(\boldsymbol{x}^{(i)})\in{}^{L}$ is
injective and has continuous inverse if:

  * •

for some $L\in[N(D+1),N^{5}D^{2}]$ when $\phi$ admits LP architecture (by
Theorem D.3 and D.4).

  * •

for some $L\in[ND,N^{4}D^{2}]$ when $\phi$ admits LE architecture (by Theorem
E.4 and E.5).

Let $\rho:{}^{D}\times{}^{L}\rightarrow\real$ take the form of
$\rho(\boldsymbol{x},\boldsymbol{z})=\tau(\boldsymbol{x},\Phi^{-1}(\boldsymbol{z}-\phi(\boldsymbol{x})))$,
and we show that function $\tau$ can be written in terms of function $\rho$ by
its invariance to last $N-1$ elements, which concludes the proof: