Learning equivariant tensor functions with applications to sparse vector recovery

## Abstract

Abstract This work characterizes equivariant polynomial functions from tuples of tensor inputs to tensor outputs. Loosely motivated by physics, we focus on equivariant functions with respect to the diagonal action of the orthogonal group on tensors. We show how to extend this characterization to other linear algebraic groups, including the Lorentz and symplectic groups. Our goal behind these characterizations is to define equivariant machine learning models. In particular, we focus on the sparse vector estimation problem. This problem has been broadly studied in the theoretical computer science literature, and explicit spectral methods, derived by techniques from sum-of-squares, can be shown to recover sparse vectors under certain assumptions. Our numerical results show that the proposed equivariant machine learning models can learn spectral methods that outperform the best theoretically known spectral methods in some regimes. The experiments also suggest that learned spectral methods can solve the problem in settings that have not yet been theoretically analyzed. This is an example of a promising direction in which theory can inform machine learning models and machine learning models could inform theory.

## Section 1 Introduction

Many recent theoretical and applied efforts have focused on the implementation of symmetries and other structural constraints in the design of machine learning models.
This is the case of graph neural networks [, ], geometric deep learning [, ], and AI for science [].
The goal is to design a hypothesis class of functions with good *inductive bias* that is aligned with the theoretical framework of the physical, mathematical, or algorithmic objects it aims to represent.
This includes respecting coordinate freedoms [], conservation laws [], or internal symmetries (e.g. in the implicit neural representations framework []).
Symmetries have also been used to provide interpretability to learned data representations [, ].
Mathematically, it has been shown that imposing symmetries can improve the generalization error and sample complexity of machine learning models [, , , , , , ].

In this work, we focus on implementing equivariant functions of tensor inputs and tensor outputs.
Tensors are the subjects of study in many theoretical computer science and applied mathematics problems, including tensor factorization or decomposition [], and planted tensor models []. Many of the algorithms to address these problems have underlying symmetries like the ones we study here. Tensors also have a broad set of uses in the natural sciences, where tensor-valued data appears as polarizations [], permeabilities [], and stresses [], for instance. Finally, tensors are the preferred way to represent data for machine learning, where both models and multidimensional data with batches, channels, etc, are implemented as tensors. Sometimes, these tensor objects have underlying symmetries, like in implicit neural representations [].

In this paper, we consider classical Lie groups acting diagonally on tensors. The groups we study arise naturally in physics and other settings, including the orthogonal group $\mathop{O}(d)$ (which typically appears in coordinate transformations), the indefinite orthogonal group $\mathop{O}(s,k-s)$ (which includes as a particular case the Lorentz group, a fundamental group for special relativity), and the symplectic group $Sp(d)$ (the underlying group in much of classical and quantum mechanics).

A variety of methods can be used for implementing invariances or equivariances, including group convolutions [, , ], irreducible representations [, , , , ], constraints on optimization [], canonicalization [], and invariant theory [, , , , ].
This work is closer to the line of research that constructs explicit equivariant functions from invariant features, and it generalizes results from [] to tensors.

Closest to us is the concurrent work of Kunisky, Moore, and Wein on tensor cumulants [].
Their focus is primarily on symmetric tensors, although they show that $\mathop{O}(d)$-invariant polynomials on symmetric tensors can be turned into $\mathop{O}(d)$-invariant polynomials over general tensors by symmetrizing over $\mathop{O}(d)$.
Our results for equivariant tensor polynomials are slightly more general for inputs of tensors of different orders and parities as well as handling the indefinite orthogonal group and the symplectic group.

As an application, we consider the problem of sparse vector estimation.
Let there be a sparse vector $v_{0}$ and vectors $v_{1},\ldots,v_{d-1}$ sampled independently at random from some prior distribution.
If we are given an orthonormal basis $w_{0},\ldots,w_{d-1}$ of span($\{v_{0},\cdots,v_{d-1}\}$), can we recover the sparse vector $v_{0}$?
The problem has roots in tensor PCA, also known as the spiked tensor model [], as well as dictionary learning [].
Solutions for this problem using sum-of-squares and spectral methods were investigated in [] and further improvements were made in [, , , ].

In [], the authors propose an algorithm that constructs a $d\times d$ matrix $A$, then uses the top eigenvector of $A$ to estimate $v_{0}$. They prove that this method recovers the planted vector under certain assumptions.
A crucial observation is that the input to the problem is *any* orthonormal basis $w_{0},\ldots,w_{d-1}$ of span$\quantity(\quantity{v_{0},\ldots,v_{d-1}})$.
This implies that a function that estimates $v_{0}$ should be invariant to certain transformations of the input basis.
In this paper, we learn algorithms to recover planted sparse vectors from data. To this end, we use a machine learning model that learns an equivariant 2-tensor $\hat{A}$ from data, and the estimator for the planted sparse vector $\hat{v}_{0}$ is obtained using $\hat{A}$’s top eigenvector following the same procedure as []. We empirically show that this approach can learn spectral methods for sparse vector recovery that can work under more general assumptions than the state-of-the-art.

The approach employed here can be seen as a particular case of the more ambitious research program of algorithmic alignment or algorithmic reasoning [, ]. In algorithmic alignment contexts, researchers design machine learning models that match known algorithmic strategies that are known to succeed at solving certain problems, such as dynamic programming [, ]. Here, the machine learning approach is structurally aligned with equivariant spectral methods arising from sum-of-squares. We believe that the connection between sum-of-squares and machine learning (in particular equivariant machine learning and graph neural networks) is a promising direction to be explored.

### 1.1 Our Contributions

We give explicit parameterizations for analytic functions (with globally convergent Taylor series) from tuples of tensor inputs to tensor outputs that are equivariant with respect to the orthogonal, indefinite orthogonal (which includes Lorentz), and symplectic groups. Section 3 derives the parameterization for $\mathop{O}(d)$, and Section 4 generalizes the construction to indefinite orthogonal and symplectic groups.

In the case of polynomial functions with vector inputs and 2-tensor outputs, the characterization above has a particularly nice form (Corollary 1 and 2) that uses invariant scalar features (cf. []).

In Section 5, we use the derived parameterization to learn algorithms for the planted sparse vector problem described above.
We compare the performance of the learned methods to baseline sum-of-squares methods from [] and [] under different data generating models.

## Section 2 Definitions

To simplify the exposition, we start by focusing on the case of the
orthogonal group before extending the result to the indefinite orthogonal and symplectic groups.
We consider the orthogonal group $\mathop{O}(d)$, the isometries of Euclidean space $\mathbb{R}^{d}$ that fix the origin.
It acts on vectors and pseudovectors $v\in\mathbb{R}^{d}$ in the following way:

$$ $\displaystyle g\cdot v=\det(M(g))^{\frac{1-p}{2}}\,M(g)\,v,$ (1) $$

where $g\in\mathop{O}(d)$, $M(g)\in\mathbb{R}^{d\times d}$ is the standard matrix representation of $g$ (i.e. $M(g)^{\top}\,M(g)=\mathbb{I}_{d}$, where $\mathbb{I}_{d}$ is the identity matrix), and $p\in\{-1,+1\}$ is the parity of $v$.
If $p=+1$ we obtain the standard $\mathop{O}(d)$ action on $\mathbb{R}^{d}$ *vectors*.
If $p=-1$ we obtain the $\mathop{O}(d)$ action on what in physics are known as *pseudovectors*.

###### Definition 1 (( ${k}_{(p)}$ -tensors)) .

We define the space of *${1}_{(p)}$-tensors* to be $\mathbb{R}^{d}$ equipped with the action $\mathop{O}(d)$ defined by (1).
If $v_{i}$ is a ${1}_{(p_{i})}$-tensor for $i=1,\ldots,k$, then $a:=v_{1}\otimes\ldots\otimes v_{k}\in(\mathbb{R}^{d})^{\otimes k}$ is a *rank-1 ${k}_{(p)}$-tensor*, where $p=\prod_{i=1}^{k}p_{i}$ and the action of $\mathop{O}(d)$ is the diagonal action:

$$ $\displaystyle g\cdot(v_{1}\otimes\ldots\otimes v_{k})=(g\cdot v_{1})\otimes \ldots\otimes(g\cdot v_{k})~{}.$ (2) $$

This definition generalizes to higher rank ${k}_{(p)}$-tensors by linearity (see (5) below).
The space of ${k}_{(p)}$-tensors in $d$ dimensions is denoted $\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$.

###### Remark 1 .

Note that the definition of ${k}_{(p)}$-tensor includes the selection of the $\mathop{O}(d)$-action on the tensor. In this way, if $a$ is a ${k}_{(+)}$-tensor, we can see $a$ as a ${k}_{(-)}$-tensor by redefining the action as $g\cdot a=\det\left(M(g)\right)(g\cdot a)$, where on the left we have the action as a ${k}_{(-)}$-tensor and on the right the action as a ${k}_{(+)}$-tensor.

###### Definition 2 ((Einstein summation notation)) .

Suppose that $a$ is a ${k}_{(p)}$-tensor.
Let $[a]_{i_{1},\ldots,i_{k}}$ denote the $(i_{1},\ldots,i_{k})$-th entry of $a$, where $i_{1},\ldots,i_{k}$ range from $1$ to $d$.
The Einstein summation notation is used to represent tensor products(^1^11We will identify vectors with co-vectors in the usual way and will not distinguish lower vs upper scripts.) where repeated indices are summed over.
In each product, a given index can appear either exactly once, in which case it appears in the result, or exactly twice, in which case it is summed over and does not appear in the result.

For example, in Einstein summation notation, the product of two ${2}_{(+)}$-tensors (i.e., the matrix product $ab$ of two $d\times d$ matrices $a$ and $b$) is written as

$$ $[a\,b]_{i,j}=[a]_{i,\ell}\,[b]_{\ell,j}:=\sum_{\ell=1}^{d}[a]_{i,\ell}\,[b]_{ \ell,j}.$ (3) $$

Using Einstein summation notation,
the action of $g\in\mathop{O}(d)$ on rank-1 tensors can be extended to general tensors by linearity by expressing $b\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ as a linear combination of (rank-1) standard basis tensors $e_{i_{1},\ldots,i_{k}}=e_{i_{1}}\otimes\cdots\otimes e_{i_{k}}$, where $[e_{i}]_{i}=1$ and $[e_{i}]_{j}=0$ for $i\not=j$

$$ $[g\cdot b]_{i_{1},\ldots,i_{k}}=[b]_{j_{1},\ldots,j_{k}}[g\cdot(e_{j_{1}} \otimes\cdots\otimes e_{j_{k}})]_{i_{1},\ldots,i_{k}}=[b]_{j_{1},\ldots,j_{k}} [g\cdot e_{j_{1}}]_{i_{1}}\cdots[g\cdot e_{j_{k}}]_{i_{k}}.$ (4) $$

Note that the action (1) on a ${k}_{(p)}$-tensor $b$ can be written as

$$ $\displaystyle[g\cdot b]_{i_{1},\ldots,i_{k}}=\det(M(g))^{\frac{1-p}{2}}\,[b]_{ j_{1},\ldots,j_{k}}\,[M(g)]_{i_{1},j_{1}}\cdots[M(g)]_{i_{k},j_{k}}$ (5) $$

for all $g\in\mathop{O}(d)$.
For example, a ${2}_{(+)}$-tensor has the transformation property

$$ $[g\cdot b]_{i,j}=[b]_{k,\ell}\,[M(g)]_{i,k}\,[M(g)]_{j,\ell},$ $$

which, in normal matrix notation, is written as
$g\cdot b=M(g)\,b\,M(g)^{\top}$.

When multiple tensors are combined, and all their indices appear in the result, we refer to that as the tensor product or outer product.
When indices are summed over, we refer to that as the contraction or scalar product.
We will further focus on a specific case of multiple tensor contractions that we will refer to as a $k$-contraction.

###### Definition 3 ((Outer product of tensors)) .

Given $a\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ and $b\in\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$, the outer product, denoted $a\otimes b$, is a tensor in $\mathcal{T}_{k+k^{\prime}}\quantity(\mathbb{R}^{d},p\,p^{\prime})$ defined as $[a\otimes b]_{i_{1},\ldots,i_{k+k^{\prime}}}=[a]_{i_{1},\ldots,i_{k}}\,[b]_{i_
{k+1},\ldots,i_{k+k^{\prime}}}$. We write $a^{\otimes k}$ to denote the outer product of $a$ with itself $k$ times and use the convention for $k=0$ that $a^{\otimes 0}\otimes b=b$.

###### Definition 4 (( $k$ -contraction)) .

Given tensor $a\in\mathcal{T}_{2k+k^{\prime}}\quantity(\mathbb{R}^{d},p)$, the $k$-contraction of $a$, denoted $\iota_{k}\quantity(a)$, is the ${k^{\prime}}_{(p)}$-tensor defined as:

$$ $[\iota_{k}\quantity(a)]_{j_{1},\ldots,j_{k^{\prime}}}:=[a]_{i_{1},\ldots,i_{k} ,i_{1},\ldots,i_{k},j_{1},\ldots,j_{k^{\prime}}}.$ (6) $$

In other words, contract on indices $(1,k+1),(2,k+2),$ all the way to $(k,2k)$.

Since ${k}_{(p)}$-tensors are elements of the vector space $(\mathbb{R}^{d})^{\otimes k}$, tensor addition and scalar multiplication are defined in the usual way.
The final operation on tensors is the permutation of the indices.

###### Definition 5 ((Permutations of tensor indices)) .

Given $a\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ and permutation $\sigma\in S_{k}$, the permutation of tensor indices of $a$ by $\sigma$, denoted $a^{\sigma}$, is defined by

$$ $[a^{\sigma}]_{i_{1},\ldots,i_{k}}:=[a]_{i_{\sigma^{-1}(1)},\ldots,i_{\sigma^{- 1}(k)}}~{}.$ (7) $$

###### Definition 6 ((Invariant and equivariant functions)) .

We say that
$f:\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)\rightarrow\mathcal{T}_{k^{\prime}
}\quantity(\mathbb{R}^{d},p^{\prime})$ is $\mathop{O}(d)$-invariant if

$$ $f(g\cdot a)=f(a),\quad\text{for all}\quad g\in\mathop{O}(d).$ (8) $$

We say that
$f:\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)\rightarrow\mathcal{T}_{k^{\prime}
}\quantity(\mathbb{R}^{d},p^{\prime})$ is
$\mathop{O}(d)$-equivariant if

$$ $f(g\cdot a)=g\cdot f(a),\quad\text{for all}\quad g\in\mathop{O}(d).$ (9) $$

If $f$ were instead a function with multiple inputs, then the same group element $g$ would act on all inputs simultaneously.

###### Definition 7 ((Isotropic tensors)) .

We say that a tensor $a\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ is $\mathop{O}(d)$-isotropic if

$$ $g\cdot a=a,\quad\text{for all}\quad g\in\mathop{O}(d).$ (10) $$

There are two special tensors, the Kronecker delta, and the Levi-Civita symbol.
These tensors are $\mathop{O}(d)$-isotropic (see, for example, []) and, as we will show in Section 3, we can construct all $\mathop{O}(d)$-isotropic tensors using only Kronecker deltas and Levi-Civita symbols.

###### Definition 8 ((Kronecker delta)) .

The Kronecker delta, $\delta$, is the $\mathop{O}(d)$-isotropic ${2}_{(+)}$-tensor such that $[\delta]_{ij}=1$ if $i=j$ and 0 0 otherwise. When considered as the matrix, it is the identity matrix $\mathbb{I}_{d}$.

###### Definition 9 ((Levi-Civita symbol)) .

The Levi-Civita symbol, $\epsilon$, in dimension $d\geq 2$ is the $\mathop{O}(d)$-isotropic ${d}_{(-)}$-tensor
such that $[\epsilon]_{i_{1},\ldots,i_{d}}=0$ if any two of the $i_{1},\ldots,i_{d}$ are equal, $[\epsilon]_{i_{1},\ldots,i_{d}}=+1$ if $i_{1},\ldots,i_{d}$ is an even permutation of $1,\ldots,d$, and $[\epsilon]_{i_{1},\ldots,i_{d}}=-1$ if $i_{1},\ldots,i_{d}$ is an odd permutation of $1,\ldots,d$. For example, when $d=2$ this is simply the matrix $\left[\begin{smallmatrix}0&1\\
-1&0\end{smallmatrix}\right]$.

###### Definition 1 (( k ( p ) subscript 𝑘 𝑝 {k}_{(p)} italic_k start_POSTSUBSCRIPT ( italic_p ) end_POSTSUBSCRIPT -tensors)) .

###### Remark 1 .

###### Definition 2 ((Einstein summation notation)) .

###### Definition 3 ((Outer product of tensors)) .

###### Definition 4 (( k 𝑘 k italic_k -contraction)) .

###### Definition 5 ((Permutations of tensor indices)) .

###### Definition 6 ((Invariant and equivariant functions)) .

###### Definition 7 ((Isotropic tensors)) .

###### Definition 8 ((Kronecker delta)) .

###### Definition 9 ((Levi-Civita symbol)) .

## Section 3 𝑂 ( d ) 𝑂 𝑑 \mathop{O}(d) italic_O ( italic_d ) -equivariant polynomial functions

In this section, we characterize
$\mathop{O}(d)$-equivariant polynomial functions mapping multiple tensor inputs to tensor outputs.
This result generalizes the results of [] from ${1}_{(+)}$-tensors to general ${k}_{(p)}$-tensors in the case of polynomials for the group $\mathop{O}(d)$.

It is straightforward to show that the outer product, $k$-contraction, and permutation of tensor indices as defined above are linear and $\mathop{O}(d)$-equivariant operations (in the case of the outer product linear in each argument), see Appendix A.
The following theorem characterizes $\mathop{O}(d)$-equivariant polynomial functions.

###### Theorem 1 .

Let $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^{d},p_{i})\to\mathcal
{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ be an $\mathop{O}(d)$-equivariant polynomial function of degree at most $R$.
Then we may write $f$ as follows:

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{R}\,\sum_{1\leq\ell_{1}\leq\cdots\leq\ell_{r }\leq n}\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}}\otimes \ldots\otimes a_{\ell_{r}}\otimes c_{\ell_{1},\ldots,\ell_{r}})$ (11) $$

where
$c_{\ell_{1},\ldots,\ell_{r}}$ is an $\mathop{O}(d)$-isotropic ${(k_{\ell_{1},\ldots,\ell_{r}}+k^{\prime})}_{(p_{\ell_{1},\ldots,\ell_{r}}\,p^
{\prime})}$-tensor for
$k_{\ell_{1},\ldots,\ell_{r}}=\sum_{q=1}^{r}k_{\ell_{q}}$ and $p_{\ell_{1},\ldots,\ell_{r}}=\prod_{q=1}^{r}p_{\ell_{q}}$.

The proof of Theorem 1 is given in Appendix B.
The main idea of the proof of Theorem 1 is to write out the polynomial $f$ in a way that takes advantage of the tensor operations of Section 2, then show that each term must be $\mathop{O}(d)$-equivariant (Lemmas 2 and 3 in Appendix B).
We then use a group averaging argument to show that $c_{\ell_{1},\ldots,\ell_{r}}$ can be written as an $\mathop{O}(d)$-isotropic tensor.

The condition that $c_{\ell_{1},\ldots,\ell_{r}}$ is $\mathop{O}(d)$-isotropic is quite restrictive; the following lemma says that all such tensors can be constructed from the Kronecker delta $\delta$, see Definition 8, and the Levi-Civita symbol, see Definition 9.
This lemma, originally from Pastori, follows from [].

###### Lemma 1 ((Characterization of $\mathop{O}(d)$ -isotropic ${k}_{(p)}$ -tensors)) .

Suppose $c\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ is $\mathop{O}(d)$-isotropic. Then the following holds:

*Case $p=+1$*:
Assume $p=+1$. If $k$ is even, then $c$ can be written in the form

$$ $c=\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\delta^{\otimes\frac{k}{2}})^ {\sigma},\quad\text{for $\alpha_{\sigma}\in\mathbb{R}$},$ (12) $$

where $\alpha_{\sigma}\in\mathbb{R}$. Otherwise, if $k$ is odd, then $c=0$ is the zero tensor.

*Case $p=-1$*: Assume $p=-1$. If $k-d$ is even and $k\geq d$, then $c$ can be written in the form

$$ $c=\sum_{\sigma\in S_{k}}\beta_{\sigma}\quantity(\delta^{\otimes\frac{k-d}{2}} \otimes\epsilon)^{\sigma}$ (13) $$

where $\beta_{\sigma}\in\mathbb{R}$.
Otherwise, if $k-d$ is odd or $k<d$, then $c=0$ is the zero tensor.

###### Remark 2 .

Note that while the sums in Lemma 1 are over the full symmetric group, we can reduce the number of terms by considering the symmetries of the summands. We develop this in detail in Appendix D.

Here is a quick example of Theorem 1 and Lemma 1 in action, with a longer example in Appendix E.

###### Example 1 .

Let $f:\mathcal{T}_{1}\quantity(\mathbb{R}^{d},+)\to\mathcal{T}_{2}\quantity(
\mathbb{R}^{d},+)$ be an $\mathop{O}(d)$-equivariant polynomial of degree at most $2$. By Theorem 1,
we can write $f$ in the form

$$ $f(a)=\iota_{0}\quantity(a^{\otimes 0}\otimes c_{0})+\iota_{1}\quantity(a^{ \otimes 1}\otimes c_{1})+\iota_{2}\quantity(a^{\otimes 2}\otimes c_{2})~{},$ (14) $$

where $c_{r}$ is an $\mathop{O}(d)$-isotropic ${(r+2)}_{(+)}$-tensor for $r=0,1,2$. By Lemma 1, we have $c_{0}=\beta_{0}\delta$, $c_{1}=0$ is trivial, and $c_{2}$ is a linear combination of $(\delta^{\otimes 2})^{\sigma}$ for $\sigma\in G_{4}=\{\sigma_{1},\sigma_{2},\sigma_{3}\}$ where $\sigma_{1}:=(1,2,3,4),\sigma_{2}=(1,3,2,4),\sigma_{3}=(1,3,4,2)$, see
Appendix D. Observe that

$$ $\iota_{2}\quantity(a^{\otimes 2}\otimes\left(\beta_{1}(\delta^{\otimes 2})^{ \sigma_{1}}+\beta_{2}(\delta^{\otimes 2})^{\sigma_{2}}+\beta_{3}(\delta^{ \otimes 2})^{\sigma_{3}}\right))=\beta_{1}\langle a,a\rangle+\beta_{2}a\otimes a +\beta_{3}a\otimes a,$ (15) $$

where the terms associated with $\beta_{2}$ and $\beta_{3}$ are the same due to the symmetry of $a^{\otimes 2}$.
We conclude

$$ $f(a)=\beta_{0}\delta+\beta_{1}\langle a,a\rangle\delta+\beta_{2}a\otimes a,$ $$

for some scalars $\beta_{0},\beta_{1},$ and $\beta_{2}$.

The result of Theorem 1 is a clean theoretical characterization of $\mathop{O}(d)$-equivariant polynomial tensor functions with arbitrary order tensor inputs. However, in practice, computing large polynomials with all possible $\mathop{O}(d)$-isotropic tensors is impractical.
One option is considering low-degree polynomials as in Example 2. Alternatively, in many applications, like the ones we consider in Section 5, we can restrict ourselves to functions that have ${1}_{(+)}$-tensors (i.e. vectors) as the input and a ${k}_{(+)}$-tensor as output, and the problem takes on a form more amenable to computation.

The following corollary says that $\mathop{O}(d)$-equivariant functions whose inputs are multiple vectors can be written as a linear combination of basis elements given by the permutations of the input vectors and Kronecker deltas, and the coefficients are functions that only depend on all the pairwise inner products of the input vectors.
The proofs of this corollary and Lemma 1 are in Appendix C.

###### Corollary 1 .

Let $f:\prod_{i=1}^{n}\mathcal{T}_{1}\quantity(\mathbb{R}^{d},+)\to\mathcal{T}_{k^{
\prime}}\quantity(\mathbb{R}^{d},+)$ be an $\mathop{O}(d)$-equivariant polynomial function.
Then, we may write it as

$$ $f(v_{1},\ldots,v_{n})=\sum_{t=0}^{\lfloor\frac{k^{\prime}}{2}\rfloor}\sum_{ \sigma\in S_{k^{\prime}}}\sum_{1\leq J_{1}\leq\ldots\leq J_{k^{\prime}-2t}\leq n }q_{t,\sigma,J}\quantity(\quantity(\langle v_{i},v_{j}\rangle)_{i,j=1}^{n})\, \quantity(v_{J_{1}}\otimes\ldots\otimes v_{J_{k^{\prime}-2t}}\otimes\delta^{ \otimes t})^{\sigma},$ (16) $$

where $J=(J_{1},\ldots,J_{k^{\prime}-2t})$, and the function $q_{t,\sigma,J}$ depends on the tuple $(t,\sigma,J)$ and is a polynomial of all $n^{2}$ possible inner products between the input vectors.

The second factor is a permutation of the outer product of $t$ Kronecker deltas and $k^{\prime}-2t$ of the input vectors $v_{1},\ldots,v_{n}$, possibly with repeats.
The first sum is over the possible numbers of Kronecker deltas 0 0 to $\lfloor\frac{k^{\prime}}{2}\rfloor$, where $\lfloor\cdot\rfloor$ is the floor function.
The second sum is over the possible permutations of the $k^{\prime}$ axes, and the third sum is over choosing $k^{\prime}-2t$ vectors from $v_{1}$ to $v_{n}$, allowing repeated vectors.

###### Remark 3 .

Note that Corollary 1 characterizes polynomial functions, but if we allow the $q_{t,\sigma,J}$ to be more general (e.g. in the class of continuous or smooth functions), then we obtain a parameterization of a larger class of $\mathop{O}(d)$-equivariant functions. In the experiments in Section 5, we set the $q_{t,\sigma,J}$ to be learnable multi-layer perceptrons (MLPs). We are unsure if a characterization of this sort can be stated for all continuous $\mathop{O}(d)$-equivariant functions. However, since by Stone–Weierstrass theorem, any continuous function can be approximated by a polynomial function to arbitrary accuracy on any fixed compact set, constructing an architecture that can represent equivariant polynomial functions is sufficient to approximately represent equivariant continuous functions (see []).

###### Remark 4 .

One interesting potential extension of Corollary 1 is to parameterize the polynomials $f$ that are simultaneously $\mathop{O}(d)$-equivariant and $S_{n}$-invariant, where $S_{n}$ is the symmetric group of order $n$ acting by permuting the inputs $v_{1},\ldots,v_{n}$. Implementations of such models may be possible by adapting techniques from DeepSets [] or graph neural networks []. However, parameterizing all permutation invariant polynomial functions $q$ might be intractable. This is because the action by permutations on the inputs of $q$ is the action of permutations in pairs, which is connected with the graph isomorphism problem. Recent work gives an efficient parameterization of a class of invariant functions that is almost separating and could potentially be used to implement the $q$ functions [].

###### Theorem 1 .

###### Lemma 1 ((Characterization of 𝑂 ( d ) 𝑂 𝑑 \mathop{O}(d) italic_O ( italic_d ) -isotropic k ( p ) subscript 𝑘 𝑝 {k}_{(p)} italic_k start_POSTSUBSCRIPT ( italic_p ) end_POSTSUBSCRIPT -tensors)) .

###### Remark 2 .

###### Example 1 .

###### Corollary 1 .

###### Remark 3 .

###### Remark 4 .

## Section 4 Generalization to other groups

The results regarding $\mathop{O}(d)$-equivariant tensor maps from Section 3 are a particular case of a more general result involving algebraic groups. We work the full generalization in Appendix F where we give all the details of the proofs.

Recall that we can define $\mathop{O}(d)$ as follows:

$$ $\mathop{O}(d):=\{g\in\mathrm{GL}(\mathbb{R}^{d})\mid g^{\top}g=\mathbb{I}_{d}\},$ (17) $$

where $\mathbb{I}$ is the identity matrix. In other words, $\mathop{O}(d)$ is the subgroup of linear transformations preserving the Euclidean inner product. However, in some contexts, we might be interested in preserving more general bilinear products on $\mathbb{R}^{d}$, such as the *Minkowski inner product*

$$ $\langle u,v\rangle_{s}:=u^{\top}\mathbb{I}_{s,d-s}v,$ $$

where $\mathbb{I}_{s,d-s}:=\begin{pmatrix}\mathbb{I}_{s}&\\
&-\mathbb{I}_{d-s}\end{pmatrix}$, or, for $d$ even, the *symplectic product*

$$ $\langle u,v\rangle_{\mathrm{symp}}:=u^{\top}J_{d}v$ $$

where $J_{d}:=\begin{pmatrix}&\mathbb{I}_{d/2}\\
-\mathbb{I}_{d/2}&\end{pmatrix}$. The subgroups of linear maps preserving these bilinear products give respectively the *indefinite orthogonal group* (which is the linear part of the *Lorentz group* when $d=4$ and $s\in\{1,3\}$) given by

$$ $\mathop{O}(s,d-s):=\{g\in\mathrm{GL}(\mathbb{R}^{d})\mid g^{\top}\mathbb{I}_{s ,d-s}g=\mathbb{I}_{s,d-s}\},$ (18) $$

and, when $d$ is even, the *symplectic group* given by

$$ $Sp(d):=\{g\in\mathrm{GL}(\mathbb{R}^{d})\mid g^{\top}J_{d}g=J_{d}\}.$ (19) $$

For any of these groups $G$, we can consider the modules $\mathcal{T}_{k}(\mathbb{R}^{d},\chi):=(\mathbb{R}^{d})^{\otimes k}$, where $\chi:G\rightarrow\mathbb{R}^{*}$ is an algebraic group homomorphism, where the action is given by the linear extension of

$$ $g\cdot(v_{1}\otimes\cdots\otimes v_{k})=\chi(g)(g\cdot v_{1})\otimes\cdots \otimes(g\cdot v_{k}).$ (20) $$

When $G=\mathop{O}(s,d-s)$, with $s\neq 0,d$, we have four possible $\chi$: $\chi_{+,+}$ being always equal to $1$, $\chi_{+,-}$ being the sign of the determinant of the bottom-right $(d-s)\times(d-s)$ submatrix, $\chi_{-,+}$ being the sign of the determinant of the top-left $s\times s$ submatrix, and $\chi_{-,-}$ being the determinant of the matrix. Hence, we can represent them by $(p_{1},p_{2})$, where $p_{i}\in\{-1,+1\}$. When $G=Sp(d)$, we have that $\chi$ can only be the trivial group-homomorphism. (It follows, for instance, from the representation theory of simple Lie algebras from [, Part III] and a standard abelianization argument).

Additionally, we have $G$-equivariant contractions $\iota_{k}^{G}:\mathcal{T}_{2k+k^{\prime}}(\mathbb{R}^{d},\chi)\rightarrow
\mathcal{T}_{2k+k^{\prime}}(\mathbb{R}^{d},\chi)$ given by

$$ $\iota_{k}^{\mathop{O}(s,d-s)}(a):=[a]_{i_{1},\ldots,i_{k},j_{1},\ldots,j_{k}, \ell_{1},\ldots,\ell_{k^{\prime}}}\left[\mathbb{I}_{s,d-s}\right]_{i_{1},j_{1} }\cdots\left[\mathbb{I}_{s,d-s}\right]_{i_{k},j_{k}}$ (21) $$

and

$$ $\iota_{k}^{Sp(d)}(a):=[a]_{i_{1},\ldots,i_{k},j_{1},\ldots,j_{k},\ell_{1}, \ldots,\ell_{k^{\prime}}}\left[J_{d}\right]_{i_{1},j_{1}}\cdots\left[J_{d} \right]_{i_{k},j_{k}}.$ (22) $$

Under these notations, we can state the generalization of Theorem 1 as follows. Recall that an entire function is a function that is analytic and whose Taylor series converges globally at any point.

###### Theorem 2 .

Let $G$ be either $\mathop{O}(s,d-s)$ or $Sp(d)$ and $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^{d},\chi_{i})\to
\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},\chi^{\prime})$ be a $G$-equivariant entire function. Then we may write $f$ as follows:

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{\infty}\,\sum_{1\leq\ell_{1}\leq\cdots\leq \ell_{r}\leq n}\iota_{k_{\ell_{1},\ldots,\ell_{r}}}^{G}\left(a_{\ell_{1}} \otimes\ldots\otimes a_{\ell_{r}}\otimes c_{\ell_{1},\ldots,\ell_{r}}\right)$ (23) $$

where $c_{\ell_{1},\ldots,\ell_{r}}\in\mathcal{T}_{k_{\ell_{1},\ldots,\ell_{r}}+k^{
\prime}}(\mathbb{R}^{d},\chi_{\ell_{1},\ldots,\ell_{r}}\,\chi^{\prime})$ is a $G$-isotropic tensor, that means a tensor
invariant under the action of $G$; for $k_{\ell_{1},\ldots,\ell_{r}}:=\sum_{q=1}^{r}k_{\ell_{q}}$ and $\chi_{\ell_{1},\ldots,\ell_{r}}=\prod_{q=1}^{r}\chi_{\ell_{q}}$.

Using the above theorem and an analogous version of Lemma 1 ([, Theorem 5.3.3], see Proposition 7 in Appendix F), we can then prove the following corollary, which generalizes Corollary 1.

###### Corollary 2 .

Let $G$ be either $\mathop{O}(s,d-s)$ or $Sp(d)$ and $f:\prod_{i=1}^{n}\mathcal{T}_{1}\quantity(\mathbb{R}^{d},\chi_{0})\to\mathcal{
T}_{k}\quantity(\mathbb{R}^{d},\chi_{0})$, with $\chi_{0}$ the constant map to $1$, be a $G$-equivariant entire function.
Then we may write $f$ as follows:

$$ $f(v_{1},\ldots,v_{n})=\sum_{t=0}^{\lfloor\frac{k}{2}\rfloor}\sum_{\sigma\in S_ {k}}\sum_{1\leq J_{1}\leq\cdots\leq J_{k-2t}\leq n}q_{t,\sigma,J}\quantity( \quantity(\langle v_{i},v_{j}\rangle_{G})_{i,j=1}^{n})\,\quantity(v_{J_{1}} \otimes\ldots\otimes v_{J_{k-2t}}\otimes\theta_{G}^{\otimes t})^{\sigma}$ (24) $$

where $\langle\,\cdot\,,\,\cdot\,\rangle_{G}=\langle\,\cdot\,,\,\cdot\,\rangle_{s}$ and $\theta_{G}=\left[\mathbb{I}_{s,d-s}\right]_{i,j}$ if $G=\mathop{O}(s,d-s)$, and $\langle\,\cdot\,,\,\cdot\,\rangle_{G}=\langle\,\cdot\,,\,\cdot\,\rangle_{
\mathrm{symp}}$ and $\theta_{G}=\left[J_{d}\right]_{i,j}$ if $G=Sp(d)$.

###### Theorem 2 .

###### Corollary 2 .

## Section 5 Numerical Experiments

We define a machine learning model to learn algorithms for the sparse vector recovery problem (defined in Section 5.1). To this end, we use the $\mathop{O}(d)$-equivariant function parameterization from Corollary 1.
The code is built using the JAX library [] and is available at

[https://github.com/WilsonGregory/TensorPolynomials](https://github.com/WilsonGregory/TensorPolynomials)

### 5.1 Problem Setup

We consider the problem of finding a planted sparse vector in a linear subspace.
This problem was introduced by Spielman, Wang, and Wright in [], in the context of dictionary learning. It was further studied in [] and [].

###### Problem 1 .

Let $v_{0}\in\mathbb{R}^{n}$ be an (approximately) sparse vector of unit length.
We sample $v_{1},\ldots,v_{d-1}\overset{\text{iid}}{\sim}\mathcal{N}(\mathbf{0}_{n},\Sigma)$, where $\mathbf{0}_{n}\in\mathbb{R}^{n}$ is the zero vector and $\Sigma\in\mathbb{R}^{n\times n}$ is a given covariance matrix.
We consider $S$ to be an $n\times d$ matrix whose columns form an orthonormal basis of span$\quantity{v_{0},\ldots,v_{d-1}}$. The problem is to recover $v_{0}$ from $S$.

We consider four sampling procedures for $v_{0}$: Accept/Reject (AR), Bernoulli-Gaussian (BG), Corrected Bernoulli-Gaussian (CBG), and Bernoulli-Rademacher (BR).
All these procedures use the same sparsity parameter $\varepsilon\leq 1/3$ and aim to satisfy the approximate sparsity condition used in [] of $\norm{v_{0}}_{4}^{4}\geq\frac{1}{\varepsilon n}$ (either directly or in expectation).
Smaller values of $\varepsilon$ indicate vectors that are more sparse and consequently have larger $\norm{v_{0}}_{4}^{4}$.
Vectors sampled using AR are rejected if they do not satisfy this condition, while $\mathop{\mathbb{E}}\norm{v_{0}}_{4}^{4}=\frac{3}{\varepsilon n}$ for $v_{0}\sim$ BG and $\mathop{\mathbb{E}}\norm{v_{0}}_{4}^{4}=\frac{1}{\varepsilon n}$ for $v_{0}\sim$ CBG and for $v_{0}\sim$ BR.
See Appendix H.1 for full details and proofs.

The theoretical settings in both [] and [] specify that $v_{1},\ldots,v_{d-1}$ are sampled independently from $\mathcal{N}\quantity(\mathbf{0}_{n},\frac{1}{n}\,\mathbb{I}_{n})$.
We will also consider more general settings that have not been theoretically analyzed yet, such as sampling $v_{1},\ldots,v_{d-1}$ from a normal distribution with diagonal non-identity covariance and with random covariance from a Wishart distribution.
See Appendix H.2 for a more detailed description, as well as how we pick a random orthonormal basis for span$\quantity{v_{0},\ldots,v_{d-1}}$.

###### Problem 1 .

### 5.2 Models

We consider a matrix $S\in\mathbb{R}^{n\times d}$ whose columns are an orthonormal basis for span$\quantity{v_{0},\ldots,v_{d-1}}$ and denote its rows by $a_{1}^{\top},\ldots a_{n}^{\top}\in\mathbb{R}^{d}$.
Let $\mathcal{S}_{d}$ be the space of $d\times d$ symmetric matrices. We consider $h:(\mathbb{R}^{d})^{n}\to\mathcal{S}_{d}$ and let $\lambda_{\text{vec}}:\mathcal{S}_{d}\to\mathbb{R}^{d}$ be the function that takes a symmetric matrix as input and outputs a normalized eigenvector corresponding to the top eigenvalue.
Then, the estimate of the planted sparse vector will be given by

$$ $\hat{v}=S\,\lambda_{\text{vec}}(h(a_{1},\ldots,a_{n}))~{},$ (25) $$

for an appropriate $h$ that can be learned from data or derived by other means.

Since $S$ may be any orthogonal basis of span$\quantity{v_{0},\ldots,v_{d-1}}$, we would like (25) to be invariant to $\mathop{O}(d)$.
It is sufficient for $h$ to be $\mathop{O}(d)$-equivariant to guarantee this invariance – see Appendix G.

The models we consider differ in their choice of function $h$.
In [] (SOS-I), the function $h$ is

$$ $h(a_{1},\ldots,a_{n}):=\sum_{i=1}^{n}\quantity(\norm{a_{i}}_{2}^{2}-\frac{d}{n })a_{i}a_{i}^{\top}~{},$ (26) $$

and in [] (SOS-II) $h$ is defined as

$$ $h(a_{1},\ldots,a_{n}):=\sum_{i=1}^{n}\quantity(\norm{a_{i}}_{2}^{2}-\frac{d-1} {n})a_{i}a_{i}^{\top}-\frac{3}{n}\mathbb{I}_{n}~{}.$ (27) $$

Both models are proven to recover the planted sparse vector under different sampling assumptions described in Appendix H.1.

In comparison to these fixed methods, we propose two machine learning-based models defined using the results of Section 3.
The first model, SparseVectorHunter (SVH), will parameterize

$$ $h(a_{1},\ldots,a_{n})=\quantity[\sum_{i=1}^{n}\sum_{j=i}^{n}q_{i,j}\quantity( \quantity(\langle a_{\ell},a_{m}\rangle)_{\ell,m=1}^{n})\frac{1}{2}\quantity(a _{i}\otimes a_{j}+a_{j}\otimes a_{i})]+q_{\mathbb{I}}\quantity(\quantity( \langle a_{\ell},a_{m}\rangle)_{\ell,m=1}^{n})\mathbb{I}_{d}~{},$ (28) $$

and the second model, SparseVectorHunterDiagonal (SVH-Diag), will parameterize

$$ $h(a_{1},\ldots,a_{n})=\quantity[\sum_{i}^{n}q_{i}\quantity(\quantity(\norm{a_{ \ell}}_{2}^{2})_{\ell=1}^{n})a_{i}\otimes a_{i}]+q_{\mathbb{I}}\quantity( \quantity(\norm{a_{\ell}}_{2}^{2})_{\ell=1}^{n})\mathbb{I}_{d}~{},$ (29) $$

where $q_{i,j}$, $q_{i}$, and $q_{\mathbb{I}}$ are $\mathop{O}(d)$-invariant scalar functions.
By Corollary 1, they should be polynomials, but we will approximate them with dense neural networks.
The SparseVectorHunter model also differs from Corollary 1 by using a basis of $\frac{1}{2}(a_{i}\otimes a_{j}+a_{j}\otimes a_{i})$ rather than just $a_{i}\otimes a_{j}$ so that $h$ produces a symmetric matrix.
The inputs to the networks are $\quantity(\langle a_{\ell},a_{m}\rangle)_{\ell,m=1}^{n}$ or $\quantity(\norm{a_{\ell}}_{2}^{2})_{\ell=1}^{n}$ respectively, and the outputs are the coefficients of $\frac{1}{2}\quantity(a_{i}\otimes a_{j}+a_{j}\otimes a_{i}),a_{i}\otimes a_{i}$, or $\mathbb{I}_{d}$.
The networks themselves are multi-layer perceptrons (MLP) with 2 hidden layers, width of 128, and ReLU activation functions.

To demonstrate the benefits of equivariance, we also implement a non-equivariant baseline model (BL), which takes as input the $nd$ components of $S$ and outputs the $d+\binom{d}{2}$ components of a symmetric $d\times d$ matrix.
This is implemented as a multi-layer perceptron with 2 hidden layers, width of 128, and ReLU activation functions to match the architecture of the SVH.
For training details on all these models, see Appendix H.3.

**Table 1: Test error comparison of different methods under different sampling schemes for $v_{0}$ and different covariances for $v_{1},\ldots,v_{d-1}$. The metric is $\langle v_{0},\hat{v}\rangle^{2}$, which ranges from 0 0 to $1$ with values closer to $1$, meaning that the vectors are closer. For each row, the best value is bolded. For these experiments, $n=100,d=5,\epsilon=0.25$, and the results were averaged over $5$ trials with the standard deviation given by $\pm 0.xxx$.**
| sampling | $\Sigma$ | SOS-I [] | SOS-II [] | BL | SVH-Diag | SVH |
| --- | --- | --- | --- | --- | --- | --- |
|  | Random | 0.610$\pm$0.009 | 0.610$\pm$0.009 | 0.241$\pm$0.019 | 0.493$\pm$0.005 | 0.938$\pm$0.002 |
| A/R | Diagonal | 0.448$\pm$0.012 | 0.448$\pm$0.012 | 0.196$\pm$0.011 | 0.589$\pm$0.026 | 0.465$\pm$0.027 |
|  | Identity | 0.606$\pm$0.014 | 0.606$\pm$0.014 | 0.196$\pm$0.008 | 0.351$\pm$0.065 | 0.190$\pm$0.008 |
|  | Random | 0.962$\pm$0.002 | 0.962$\pm$0.002 | 0.242$\pm$0.006 | 0.917$\pm$0.004 | 0.937$\pm$0.002 |
| BG | Diagonal | 0.949$\pm$0.005 | 0.949$\pm$0.005 | 0.205$\pm$0.013 | 0.914$\pm$0.006 | 0.463$\pm$0.018 |
|  | Identity | 0.962$\pm$0.002 | 0.962$\pm$0.002 | 0.196$\pm$0.009 | 0.908$\pm$0.006 | 0.342$\pm$0.043 |
|  | Random | 0.412$\pm$0.017 | 0.412$\pm$0.017 | 0.239$\pm$0.012 | 0.372$\pm$0.011 | 0.935$\pm$0.002 |
| CBG | Diagonal | 0.288$\pm$0.018 | 0.288$\pm$0.018 | 0.206$\pm$0.003 | 0.550$\pm$0.026 | 0.460$\pm$0.022 |
|  | Identity | 0.412$\pm$0.011 | 0.412$\pm$0.011 | 0.198$\pm$0.005 | 0.239$\pm$0.025 | 0.197$\pm$0.011 |
|  | Random | 0.526$\pm$0.020 | 0.526$\pm$0.020 | 0.923$\pm$0.004 | 0.437$\pm$0.034 | 0.957$\pm$0.001 |
| BR | Diagonal | 0.334$\pm$0.024 | 0.334$\pm$0.024 | 0.864$\pm$0.005 | 0.588$\pm$0.011 | 0.903$\pm$0.004 |
|  | Identity | 0.524$\pm$0.010 | 0.524$\pm$0.010 | 0.845$\pm$0.006 | 0.317$\pm$0.046 | 0.889$\pm$0.003 |

### 5.3 Results

The training errors are reported in the Appendix in Table 3, while the test errors are displayed in Table 1.
The training results show that the machine learning models can be expressive enough to fit the training data, but the testing results show that they do not always generalize well.
In particular, the baseline model performs best for some of the training data sets but generalizes poorly compared to all other models. This is consistent with the claim that enforcing symmetries improves generalization performance [, , ].
Typically, SVH does best when the covariance matrix is random, SVH-Diag does best when the covariance matrix is diagonal non-identity, and the sum-of-squares methods do best when the covariance matrix is the identity.
One exception is the Bernoulli-Rademacher sparse vectors, where the SVH model does best for all tested covariance matrices.

Another exception is that when we have Bernoulli-Gaussian sparse vectors, SOS-I and SOS-II do better than the SVH methods.
This is likely because $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\frac{3}{\varepsilon n}$ (Appendix H.1).
When this value gets larger, the sparse vectors are more sparse, which makes the problem easier.
By contrast, the Corrected Bernoulli-Gaussian and Bernoulli-Rademacher have $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\frac{1}{\varepsilon n}$, which is a harder setting for all algorithms.
Since this is in expectation, individual sparse vectors may have $\norm{v_{0}}_{4}^{4}<\frac{1}{\varepsilon n}$, which is outside the theoretical guarantees for the sum-of-squares method in [].

The learned SVH methods are an interesting development for settings where we do not have theoretical guarantees (e.g., non-identity covariance). They may even be useful for generating conjectures for spectral algorithms that may work under more general assumptions.

We also note that SOS-I and SOS-II perform identically for these experiments.
We observed some small differences between the two methods for $n$ very large.

## Section 6 Discussion

This paper provides a characterization of polynomial functions from multiple tensor inputs to tensor outputs that are equivariant with respect to the diagonal action by classical Lie groups, including the orthogonal group, the symplectic group, and the Lorentz group.

Our main goal behind this characterization is to define equivariant machine learning models. We applied the resulting models to learning algorithms for the sparse vector recovery problem. In the spirit of the neural algorithmic reasoning framework [], the proposed machine learning methods are “aligned” to known algorithms with provable performance guarantees. The learned algorithms outperform state-of-the-art algorithms for this problem in several regimes. And they also seem to work under assumptions where there are no known algorithms with theoretical guarantees.

The application of our characterization is especially useful when the input consists of ${1}_{(+)}$-tensors, and the output is a ${k}_{(+)}$-tensor.
For these problems, a parameterization based on invariant scalars, similar to [], is available and easy to implement.
For problems where the input tensors have higher order or there is a mixture of parities between the input and output, the implementation would be less efficient.
We also assume no additional structure on the relationship between the input tensors; in those situations, other techniques may be required. For instance, to extend the models to be permutation invariant as well as $\mathop{O}(d)$-equivariant (see Remark 4).

#### Acknowledgements

This project started as part of the 2022 AMS-MRC (Math Research Communities) on “Data Science at the Crossroads of Analysis, Geometry, and Topology”. JTC, NFM, ASL
and SV acknowledge support from NSF through grant DMS-1916439.
The authors would like to thank Ben Blum-Smith and Daniel Packer for helpful discussions. WGG and SV are partially supported by NSF CCF 2212457 and the NSF–Simons Research Collaboration
on the Mathematical and Scientific Foundations of Deep Learning (MoDL) (NSF DMS 2031985). SV is also funded by NSF CAREER 2339682 and ONR N00014-22-1-2126.

## Appendix A Basic properties of 𝑂 ( d ) 𝑂 𝑑 \mathop{O}(d) italic_O ( italic_d ) actions on tensors

In this section, we will show that the basic operations are $\mathop{O}(d)$-equivariant and linear by direct computation. We do so explicitly by performing routine computations. However, the universal property of tensor products, which we use in Appendix F, would give immediate proofs of these statements.

###### Proposition 1 .

The outer product is a $\mathop{O}(d)$-equivariant bilinear map. In other words, for $g\in\mathop{O}(d)$, $a,a^{\prime}\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$, $b,b^{\prime}\in\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ and $\alpha,\beta\in\mathbb{R}$, we have
$g\cdot(a\otimes b)=(g\cdot a)\otimes(g\cdot b)$,
$(\alpha a+\beta a^{\prime})\otimes b=\alpha(a\otimes b)+\beta(a^{\prime}
\otimes b)$,
and
$a\otimes(\alpha b+\beta b^{\prime})=\alpha(a\otimes b)+\beta(a\otimes b^{
\prime})$. In particular, if $c\in\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ is an $\mathop{O}(d)$-isotropic tensor, then the function mapping

$$ $\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)\to\mathcal{T}_{k+k^{\prime}} \quantity(\mathbb{R}^{d},pp^{\prime})\quad\text{by}\quad a\mapsto a\otimes c$ (30) $$

is an $\mathop{O}(d)$-equivariant linear map.

###### Proposition 2 .

The $k$-contraction $\iota_{k}:\mathcal{T}_{2k+k^{\prime}}\quantity(\mathbb{R}^{d},p)\rightarrow
\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p)$, see Definition 4, is an $\mathop{O}(d)$-equivariant linear map.

###### Proposition 3 .

For fixed $\sigma\in S_{k}$, the tensor index permutation
mapping $\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)\to\mathcal{T}_{k}\quantity(\mathbb{
R}^{d},p)$ by $a\mapsto a^{\sigma}$ is an $\mathop{O}(d)$-equivariant linear map.

###### Proof of Proposition 1 .

First, we establish equivariance. Let $a\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$, $b\in\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$, and $g\in\mathop{O}(d)$.
We have

$$ $\displaystyle\quad[g\cdot(a\otimes b)]$ ${}_{j_{1},\ldots,j_{k+k^{\prime}}}$ $\displaystyle=\det(M(g))^{\frac{1-p\,p^{\prime}}{2}}\,[(a\otimes b)]_{i_{1}, \ldots,i_{k+k^{\prime}}}[M(g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k+k^{\prime}},i_{ k+k^{\prime}}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,\det(M(g))^{\frac{1-p^{\prime}}{2}} \,[a]_{i_{1},\ldots,i_{k}}[b]_{i_{k+1},\ldots,i_{k+k^{\prime}}}[M(g)]_{j_{1},i _{1}}\cdots$ $\displaystyle\quad\quad\quad\cdots[M(g)]_{j_{k},i_{k}}[M(g)]_{j_{k+1},i_{k+1}} \cdots[M(g)]_{j_{k+k^{\prime}},i_{k+k^{\prime}}}$ $\displaystyle=\quantity(\det(M(g))^{\frac{1-p}{2}}\,[a]_{i_{1},\ldots,i_{k}}[M (g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k},i_{k}})$ $\displaystyle\quad\quad\quad\quad\quantity(\det(M(g))^{\frac{1-p^{\prime}}{2}} \,[b]_{i_{k+1},\ldots,i_{k+k^{\prime}}}[M(g)]_{j_{k+1},i_{k+1}}\cdots[M(g)]_{j _{k+k^{\prime}},i_{k+k^{\prime}}})$ $\displaystyle=[g\cdot a]_{j_{1},\ldots,j_{k}}[g\cdot b]_{j_{k+1},\ldots,j_{k+k ^{\prime}}}$ $\displaystyle=[g\cdot a\otimes g\cdot b]_{j_{1},\ldots,j_{k+k^{\prime}}}~{},$ $$

where the second equality uses the fact that

$$ $\det(M(g))^{\frac{1-p\,p^{\prime}}{2}}=\det(M(g))^{\frac{1-p}{2}}\,\det(M(g))^ {\frac{1-p^{\prime}}{2}},$ $$

which is straightforward to verify via a case analysis over possible parameter values (i.e., $p,p^{\prime}\in\{+1,-1\}$ and $\det(M(g))\in\{+1,-1\}$).

Next, we verify linearity. Let $a,a^{\prime}\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$, $b\in\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$, and $\alpha,\beta\in\mathbb{R}$.
Then,

$$ $\displaystyle[(\alpha a+\beta a^{\prime})\otimes b]_{i_{1},\ldots,i_{k+k^{ \prime}}}$ $\displaystyle=[(\alpha a+\beta a^{\prime})]_{i_{1},\ldots,i_{k}}[b]_{i_{k+1}, \ldots,i_{k+k^{\prime}}}$ $\displaystyle=\alpha[a]_{i_{1},\ldots,i_{k}}[b]_{i_{k+1},\ldots,i_{k+k^{\prime }}}+\beta[a^{\prime}]_{i_{1},\ldots,i_{k}}[b]_{i_{k+1},\ldots,i_{k+k^{\prime}}}$ $\displaystyle=\alpha[a\otimes b]_{i_{1},\ldots,i_{k+k^{\prime}}}+\beta[a^{ \prime}\otimes b]_{i_{1},\ldots,i_{k+k^{\prime}}}.$ $$

The linearity in the second argument follows in the same manner.

Finally, (30) follows immediately from the fact that the bilinear $\mathop{O}(d)$-equivariance.
∎

###### Proof of Proposition 2 .

To establish equivariance, let $a\in\mathcal{T}_{2k+k^{\prime}}\quantity(\mathbb{R}^{d},p)$ and let $g\in\mathop{O}(d)$.
Then,

$$ $\displaystyle[g\cdot\iota_{k}\quantity(a)]_{j_{1},\ldots,j_{k^{\prime}}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a]_{\ell_{1},\ldots,\ell_{k},\ell_{ 1},\ldots,\ell_{k},i_{1},\ldots,i_{k^{\prime}}}[M(g)]_{j_{1},i_{1}}\cdots[M(g) ]_{j_{k^{\prime}},i_{k^{\prime}}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a]_{\ell_{1},\ldots,\ell_{2k},i_{1} ,\ldots,i_{k^{\prime}}}[\delta]_{\ell_{1},\ell_{k+1}}\cdots[\delta]_{\ell_{k}, \ell_{2k}}[M(g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k^{\prime}},i_{k^{\prime}}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a]_{\ell_{1},\ldots,\ell_{2k},i_{1} ,\ldots,i_{k^{\prime}}}[M(g)]_{\ell_{1},m_{1}}[M(g)]_{\ell_{k+1},m_{1}}\cdots$ $\displaystyle\quad\quad\quad\cdots[M(g)]_{\ell_{k},m_{k}}[M(g)]_{\ell_{2k},m_{ k}}[M(g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k^{\prime}},i_{k^{\prime}}}$ $\displaystyle=[g\cdot a]_{m_{1},\ldots,m_{k},m_{1},\ldots,m_{k},j_{1},\ldots,j _{k^{\prime}}}$ $\displaystyle=[\iota_{k}\quantity(g\cdot a)]_{j_{1},\ldots,j_{k^{\prime}}},$ $$

where the third equality uses the fact that $\delta=M(g)\,M(g)^{\top}$.

Next, to establish linearity, let $a,b\in\mathcal{T}_{2k+k^{\prime}}\quantity(\mathbb{R}^{d},p)$ and let $\alpha,\beta\in\mathbb{R}$. Then,

$$ $\displaystyle\quantity[\iota_{k}\quantity(\alpha a+\beta b)]_{j_{1},\ldots,j_{ k^{\prime}}}$ $\displaystyle=[\alpha a+\beta b]_{i_{1},\ldots,i_{k},i_{1},\ldots,i_{k},j_{1}, \ldots,j_{k^{\prime}}}$ $\displaystyle=\alpha[a]_{i_{1},\ldots,i_{k},i_{1},\ldots,i_{k},j_{1},\ldots,j_ {k^{\prime}}}+\beta[b]_{i_{1},\ldots,i_{k},i_{1},\ldots,i_{k},j_{1},\ldots,j_{ k^{\prime}}}$ $\displaystyle=\alpha[\iota_{k}\quantity(a)]_{j_{1},\ldots,j_{k^{\prime}}}+ \beta[\iota_{k}\quantity(b)]_{j_{1},\ldots,j_{k^{\prime}}}.$ $$

This completes the proof.
∎

###### Proof of Proposition 3 .

Fix $\sigma\in S_{k}$. To establish equivariance, let $a\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ and $g\in\mathop{O}(d)$. Then,

$$ $\displaystyle[g\cdot(a^{\sigma})]_{j_{1},\ldots,j_{k}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a^{\sigma}]_{i_{1},\ldots,i_{k}}[M( g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k},i_{k}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a]_{i_{\sigma^{-1}(1)},\ldots,i_{ \sigma^{-1}(k)}}[M(g)]_{j_{1},i_{1}}\cdots[M(g)]_{j_{k},i_{k}}$ $\displaystyle=\det(M(g))^{\frac{1-p}{2}}\,[a]_{i_{\sigma^{-1}(1)},\ldots,i_{ \sigma^{-1}(k)}}[M(g)]_{j_{\sigma^{-1}(1)},i_{\sigma^{-1}(1)}}\cdots[M(g)]_{j_ {\sigma^{-1}(k)},i_{\sigma^{-1}(k)}}$ $\displaystyle=[g\cdot a]_{j_{\sigma^{-1}(1)},\ldots,j_{\sigma^{-1}(k)}}$ $\displaystyle=[(g\cdot a)^{\sigma}]_{j_{1},\ldots,j_{k}},$ $$

where the third equality holds since we are merely reordering the $M(g)$ components—which is allowed because they are scalars.

To show linearity, let $a,b\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},p)$ and $\alpha,\beta\in\mathbb{R}$. We have

$$ $\displaystyle[\quantity(\alpha a+\beta b)^{\sigma}]_{i_{1},\ldots,i_{k}}$ $\displaystyle=[\alpha a+\beta b]_{i_{\sigma^{-1}(1)},\ldots,i_{\sigma^{-1}(k)}}$ $\displaystyle=\alpha[a]_{i_{\sigma^{-1}(1)},\ldots,i_{\sigma^{-1}(k)}}+\beta[b ]_{i_{\sigma^{-1}(1)},\ldots,i_{\sigma^{-1}(k)}}$ $\displaystyle=\alpha[a^{\sigma}]_{i_{1},\ldots,i_{k}}+\beta[b^{\sigma}]_{i_{1} ,\ldots,i_{k}}.$ $$

∎

###### Proposition 1 .

###### Proposition 2 .

###### Proposition 3 .

###### Proof of Proposition 1 .

###### Proof of Proposition 2 .

###### Proof of Proposition 3 .

## Appendix B Proof of Theorem 1

In this section, we prove Theorem 1. To prove this theorem, we require two lemmas, allowing us to decompose our equivariant function into simpler equivariant functions. We state the lemmas, prove the theorem, and then prove the lemmas.

###### Lemma 2 .

Let $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^{d},p_{i})\to\mathcal
{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ be a polynomial map of degree $R$, and write

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{R}f_{r}(a_{1},\ldots,a_{n}),$ $$

where $f_{r}:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^{d},p_{i})\to
\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ is homogeneous degree $r$ polynomial.
If $f$ is $\mathop{O}(d)$-equivariant, then each $f_{r}$ is $\mathop{O}(d)$-equivariant.

###### Lemma 3 .

Let $f_{r}:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^{d},p_{i})\to
\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$ be a homogeneous polynomial of degree $r$. Then, we can write $f_{r}$ as

$$ $f_{r}(a_{1},\ldots,a_{n})=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}f_{ \ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_{r}}),$ (31) $$

where $f_{\ell_{1},\ldots,\ell_{r}}:\prod_{i=1}^{r}\mathcal{T}_{k_{\ell_{i}}}
\quantity(\mathbb{R}^{d},p_{\ell_{i}})\to\mathcal{T}_{k^{\prime}}\quantity(
\mathbb{R}^{d},p^{\prime})$ is the composition of the map

$$ $\displaystyle\prod_{i=1}^{r}\mathcal{T}_{k_{\ell_{i}}}\quantity(\mathbb{R}^{d} ,p_{\ell_{i}})$ $\displaystyle\rightarrow\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity( \mathbb{R}^{d},\prod_{i=1}^{r}p_{\ell_{i}})$ $\displaystyle(a_{\ell_{1}},\ldots,a_{\ell_{r}})$ $\displaystyle\mapsto a_{\ell_{1}}\otimes\ldots\otimes a_{\ell_{r}}$ $$

with a linear map $\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(\mathbb{R}^{d},\prod_{i=1}^{
r}p_{\ell_{i}})\to\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{\prime})$.

Moreover, if $f_{r}$ is $\mathop{O}(d)$-equivariant, then so are the $f_{\ell_{1},\ldots,\ell_{r}}$.

###### Remark 5 .

Note that Lemma 3 is nothing more than the decomposition of $f_{r}$ as a sum of multihomogeneous maps in the inputs $a_{1},\ldots,a_{n}$.

###### Proof of Theorem 1 .

Combining Lemmas 2 and 3, we can write $f$ as follows:

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{R}\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r} \leq n}f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_{r}}),$ (32) $$

where the $f_{\ell_{1},\ldots,\ell_{r}}$ is the composition of a linear map $\mathcal{T}_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(\mathbb{R}^{d},p_{\ell_{1}
,\ldots,\ell_{r}})\to\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{
\prime})$ with the map $(a_{1},\ldots,a_{\ell})\mapsto a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}$. Recall that $k_{\ell_{1},\ldots,\ell_{r}}=\sum_{q=1}^{r}k_{\ell_{q}}$ and $p_{\ell_{1},\ldots,\ell_{r}}=\prod_{q=1}^{r}p_{\ell_{q}}$. Moreover, by the lemmas, each $f_{\ell_{1},\ldots,\ell_{r}}$ is $\mathop{O}(d)$-equivariant. Hence, without loss of generality, it is enough to prove the theorem in the special case

$$ $f(a_{1},\ldots,a_{n})=\lambda(a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}),$ (33) $$

where $\lambda:\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(\mathbb{R}^{d},\prod
_{i=1}^{r}p_{\ell_{i}})\to\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},p^{
\prime})$ is linear.

Now, in coordinates, we can write this map as

$$ $[f(a_{1},\ldots,a_{n})]_{j_{1},\ldots,j_{k^{\prime}}}=\lambda_{i_{1},\ldots,i_ {k_{\ell_{1},\ldots,\ell_{r}}},j_{1},\ldots,j_{k^{\prime}}}[a_{\ell_{1}} \otimes\cdots\otimes a_{\ell_{r}}]_{i_{1},\ldots,i_{k_{\ell_{1},\ldots,\ell_{r }}}}.$ (34) $$

Consider now the tensor $c\in\mathcal{T}_{k_{\ell_{1},\ldots,\ell_{r}}+k^{\prime}}\quantity(\mathbb{R}^
{d},p_{\ell_{1},\ldots,\ell_{r}}p^{\prime})$ given by

$$ $[c]_{i_{1},\ldots,i_{k_{\ell_{1},\ldots,\ell_{r}}+k^{\prime}}}=\lambda_{i_{1}, \ldots,i_{k_{\ell_{1},\ldots,\ell_{r}}},i_{k_{\ell_{1},\ldots,\ell_{r}}+1}, \ldots,i_{k_{\ell_{1},\ldots,\ell_{r}}+k^{\prime}}}$ (35) $$

Then we have that

$$ $\displaystyle[f(a_{1},\ldots,a_{n})]_{j_{1},\ldots,j_{k^{\prime}}}$ $\displaystyle=[c]_{i_{1},\ldots,i_{k_{\ell_{1},\ldots,\ell_{r}}},j_{1},\ldots, j_{k^{\prime}}}[a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}]_{i_{1},\ldots,i _{k_{\ell_{1},\ldots,\ell_{r}}}}$ (36) $\displaystyle=[a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}\otimes c]_{i_{1}, \ldots,i_{k_{\ell_{1},\ldots,\ell_{r}}},i_{1},\ldots,i_{k_{\ell_{1},\ldots, \ell_{r}}},j_{1},\ldots,j_{k^{\prime}}}$ (37) $\displaystyle=[\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}} \otimes\cdots\otimes a_{\ell_{r}}\otimes c)]_{j_{1},\ldots,j_{k^{\prime}}},$ (38) $$

after using the definition of $k$-contraction. Hence

$$ $f(a_{1},\ldots,a_{n})=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1 }}\otimes\cdots\otimes a_{\ell_{r}}\otimes c).$ (39) $$

Since $f$ is $\mathop{O}(d)$-equivariant, we have that for all $g\in\mathop{O}(d)$,

$$ $f(a_{1},\ldots,a_{n})=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1 }}\otimes\cdots\otimes a_{\ell_{r}}\otimes g\cdot c).$ (40) $$

To see this, we argue as follows:

$$ $\displaystyle f$ $\displaystyle(a_{1},\ldots,a_{n})$ $\displaystyle=f(g\cdot(g^{-1}\cdot a_{1}),\ldots,g\cdot(g^{-1}\cdot a_{n}))$ $\displaystyle=g\cdot f((g^{-1}\cdot a_{1}),\ldots,(g^{-1}\cdot a_{n}))$ $\displaystyle\text{(}f\text{ }\mathop{O}(d)\text{-equivariant)}$ $\displaystyle=g\cdot\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity((g^{-1}\cdot a _{\ell_{1}})\otimes\cdots\otimes(g^{-1}\cdot a_{\ell_{r}})\otimes c)$ $\displaystyle=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(g\cdot(g^{-1}\cdot a _{\ell_{1}})\otimes\cdots\otimes g\cdot(g^{-1}\cdot a_{\ell_{r}})\otimes(g \cdot c))$ $\displaystyle\text{(}\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\text{ }\mathop{O}(d) \text{-equivariant)}$ $\displaystyle=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}} \otimes\cdots\otimes a_{\ell_{r}}\otimes(g\cdot c)).$ $$

Hence, by taking the expectation with respect to the Haar probability measure of $\mathop{O}(d)$ and linearity of contractions, we have that

$$ $f(a_{1},\ldots,a_{n})=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1 }}\otimes\cdots\otimes a_{\ell_{r}}\otimes\left(\mathop{\mathbb{E}}_{\mathfrak {g}\in\mathop{O}(d)}\mathfrak{g}\cdot c\right)),$ (41) $$

where $\mathop{\mathbb{E}}_{\mathfrak{g}\in\mathop{O}(d)}$ is the expectation with respect the Haar probability measure of $\mathop{O}(d)$. This holds because

$$ $\displaystyle f(a_{1},\ldots,a_{n})$ $\displaystyle=\mathop{\mathbb{E}}_{\mathfrak{g}\in\mathop{O}(d)}f(a_{1},\ldots ,a_{n})$ $\displaystyle=\mathop{\mathbb{E}}_{\mathfrak{g}\in\mathop{O}(d)}\iota_{k_{\ell _{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}} \otimes(\mathfrak{g}\cdot c))$ $\displaystyle=\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}} \otimes\cdots\otimes a_{\ell_{r}}\otimes\left(\mathop{\mathbb{E}}_{\mathfrak{g }\in\mathop{O}(d)}\mathfrak{g}\cdot c\right)).$ $$

Now, $\mathop{\mathbb{E}}_{\mathfrak{g}\in\mathop{O}(d)}\mathfrak{g}\cdot c$ is an $\mathop{O}(d)$-isotropic tensor. Hence, we have shown that we can write $f$ in the desired form.
∎

###### Proof of Lemma 2 .

Let $t\in\mathbb{R}$, since each $f_{r}$ is homogeneous of degree $r$, we have

$$ $f(t\,a_{1},\ldots,t\,a_{n})=\sum_{r=0}^{R}f_{r}(t\,a_{1},\ldots,t\,a_{n})=\sum _{r=1}^{R}t^{r}f_{r}(a_{1},\ldots,a_{n}).$ $$

Let now $g\in\mathop{O}(d)$, then, by equivariance of $f$, we have

$$ $\sum_{r=0}^{R}t^{r}\,f_{r}(g\cdot a_{1},\ldots,g\cdot a_{n})=\sum_{r=0}^{R}t^{ r}\,g\cdot f_{r}(a_{1},\ldots,a_{n}),$ (42) $$

since

$$ $\displaystyle\sum_{r=0}^{R}t^{r}\,f_{r}(g\cdot a_{1},\ldots,g\cdot a_{n})$ $\displaystyle=f\quantity(t\,(g\cdot a_{1}),\ldots,t\,(g\cdot a_{n}))$ $\displaystyle=f\quantity(g\cdot t\,a_{1},\ldots,g\cdot t\,a_{n})$ $\displaystyle=g\cdot f\quantity(t\,a_{1},\ldots,t\,a_{n})$ $\displaystyle=g\cdot\sum_{r=0}^{R}t^{r}f_{r}(a_{1},\ldots,a_{n})$ $\displaystyle=\sum_{r=0}^{R}t^{r}\,g\cdot f_{r}(a_{1},\ldots,a_{n}).$ $$

Hence, for all $g\in\mathop{O}(d)$, $t\in\mathbb{R}$ and $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^
{d},p_{i})$, we have that

$$ $0=\sum_{r=0}^{R}t^{r}\,\quantity(g\cdot f_{r}(a_{1},\ldots,a_{n})-f_{r}(g\cdot a _{1},\ldots,g\cdot a_{n})).$ (43) $$

Now, the only way in which the univariate polynomial in $t$ of degree $R$ is identically zero is if it is the zero polynomial (cf. [, Chapter 1 §1 Proposition 5]). Therefore for all $r\in\mathbb{N}$, $g\in\mathop{O}(d)$ and $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^
{d},p_{i})$,

$$ $f_{r}(g\cdot a_{1},\ldots,g\cdot a_{n})=g\cdot f_{r}(a_{1},\ldots,a_{n}),$ (44) $$

i.e., for each $r$, $f_{r}$ is $\mathop{O}(d)$-equivariant, as we wanted to show.
∎

###### Proof of Lemma 3 .

First, we will show that if the decomposition exists, each summand is equivariant. Then, we will show that the decomposition exists.

Let $t_{1},\ldots,t_{n}\in\mathbb{R}$. Then, by the linearity, we have that

$$ $f_{r}(t_{1}\,a_{1},\ldots,t_{n}\,a_{n})=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_ {r}\leq n}t_{\ell_{1}}\cdots t_{\ell_{r}}\,f_{\ell_{1},\ldots,\ell_{r}}(a_{ \ell_{1}},\ldots,a_{\ell_{r}}),$ (45) $$

since

$$ $\displaystyle f_{r}(t_{1}\,a_{1},\ldots,t_{n}\,a_{n})$ $\displaystyle=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}f_{\ell_{1}, \ldots,\ell_{r}}(t_{\ell_{1}}\,a_{\ell_{1}},\ldots,t_{\ell_{r}}\,a_{\ell_{r}})$ $\displaystyle=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}} \cdots t_{\ell_{r}}\,f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_ {r}})~{}.$ $$

Now, let $g\in\mathop{O}(d)$. Then, by the equivariance of $f_{r}$, we have

$$ $\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}}\cdots t_{\ell_{r} }\,f_{\ell_{1},\ldots,\ell_{r}}(g\cdot a_{\ell_{1}},\ldots,g\cdot a_{\ell_{r}} )=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}}\cdots t_{\ell_{ r}}\,g\cdot f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_{r}}),$ (46) $$

since

$$ $\displaystyle\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}} \cdots t_{\ell_{r}}\,$ $\displaystyle f_{\ell_{1},\ldots,\ell_{r}}(g\cdot a_{\ell_{1}},\ldots,g\cdot a _{\ell_{r}})$ $\displaystyle=f_{r}\quantity(t_{1}\,(g\cdot a_{1}),\ldots,t_{n}\,(g\cdot a_{n}))$ $\displaystyle=f_{r}\quantity(g\cdot t_{1}\,a_{1},\ldots,g\cdot t_{n}\,a_{n})$ $\displaystyle=g\cdot f_{r}\quantity(t_{1}\,a_{1},\ldots,t_{n}\,a_{n})$ $\displaystyle=g\cdot\left(\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{ \ell_{1}}\cdots t_{\ell_{r}}\,f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots ,a_{\ell_{r}})\right)$ $\displaystyle=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}} \cdots t_{\ell_{r}}\,g\cdot f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a _{\ell_{r}}).$ $$

Hence, for all $g\in\mathop{O}(d)$, $t\in\mathbb{R}$ and $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^
{d},p_{i})$, we have that

$$ $0=\sum_{1\leq\ell_{1}\leq\ldots\leq\ell_{r}\leq n}t_{\ell_{1}}\cdots t_{\ell_{ r}}\,\quantity[g\cdot f_{\ell_{1},\ldots,\ell_{r}}\quantity(a_{\ell_{1}}, \ldots,a_{\ell_{r}})-f_{\ell_{1},\ldots,\ell_{r}}\quantity(g\cdot a_{\ell_{1}} ,\ldots,g\cdot a_{\ell_{r}})]_{i_{1},\ldots,i_{k^{\prime}}}.$ (47) $$

Now, each of these is a polynomial in $t_{1},\ldots,t_{n}$ that vanishes on $\mathbb{R}^{n}$. Moreover, note that no two $t_{\ell_{1}}\cdots t_{\ell_{r}}$ give the same monomial. Hence, by [, Chapter 1 §1 Proposition 5], all these polynomials are the zero polynomial, i.e., their coefficients are zero. In this way, we conclude that for each $f_{\ell_{1},\ldots,\ell_{r}}$, and all $g\in\mathop{O}(d)$, $t\in\mathbb{R}$ and $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(\mathbb{R}^
{d},p_{i})$,

$$ $f_{\ell_{1},\ldots,\ell_{r}}\quantity(g\cdot a_{\ell_{1}},\ldots,g\cdot a_{ \ell_{r}})=g\cdot f_{\ell_{1},\ldots,\ell_{r}}\quantity(a_{\ell_{1}},\ldots,a_ {\ell_{r}}),$ (48) $$

i.e., each $f_{\ell_{1},\ldots,\ell_{r}}$ is $\mathop{O}(d)$-equivariant.

Now, we show how to obtain the decomposition. Recall that $f_{r}$ is homogeneous of degree $r$. Therefore each entry of $f_{r}(a_{1},\ldots,a_{n})$ is an homogeneous polynomial of degree $r$ in the $[a_{i}]_{j_{1},\ldots,j_{k_{i}}}$, i.e., a linear combination of products of the form

$$ $\prod_{q=1}^{r}[a_{\ell_{q}}]_{j_{q,1},\ldots,j_{q,k_{\ell_{q}}}},$ $$

where, without loss of generality, we can assume that $\ell_{1}\leq\cdots\leq\ell_{q}$. Hence, in coordinates, we have

$$ $[f_{r}(a_{1},\ldots,a_{n})]_{i_{1},\ldots,i_{k^{\prime}}}\\ =\sum_{1\leq\ell_{1}\leq\cdots\leq\ell_{r}\leq n}\lambda_{\ell_{1},\ldots,\ell _{r};i_{1},\ldots,i_{k^{\prime}};j_{1,1},\ldots,j_{1,k_{\ell_{1}}},\ldots,j_{r ,1},\ldots,j_{r,k_{\ell_{r}}}}\prod_{q=1}^{r}[a_{\ell_{q}}]_{j_{q,1},\ldots,j_ {q,k_{\ell_{q}}}}$ (49) $$

And so, we can consider the map $f_{\ell_{1},\ldots,\ell_{r}}$ given in coordinates by

$$ $[f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_{r}})]_{i_{1},\ldots ,i_{k^{\prime}}}:=\lambda_{\ell_{1},\ldots,\ell_{r};i_{1},\ldots,i_{k^{\prime} };j_{1,1},\ldots,j_{1,k_{\ell_{1}}},\ldots,j_{r,1},\ldots,j_{r,k_{\ell_{r}}}} \prod_{q=1}^{r}[a_{\ell_{q}}]_{j_{q,1},\ldots,j_{q,k_{\ell_{q}}}},$ (50) $$

which, by construction, is the composition of the linear map given by

$$ $b\mapsto\lambda_{\ell_{1},\ldots,\ell_{r};i_{1},\ldots,i_{k^{\prime}};j_{1}, \ldots,j_{\sum_{q=1}^{r}k_{\ell_{q}}}}[b]_{j_{1},\ldots,j_{\sum_{q=1}^{r}k_{ \ell_{q}}}},$ $$

in coordinates, and $(a_{\ell_{1}},\ldots,a_{\ell_{r}})\mapsto a_{\ell_{1}}\otimes\cdots\otimes a_{
\ell_{r}}$. Hence the desired decomposition of $f_{r}$ has been obtained.
∎

###### Lemma 2 .

###### Lemma 3 .

###### Remark 5 .

###### Proof of Theorem 1 .

###### Proof of Lemma 2 .

###### Proof of Lemma 3 .

## Appendix C Proof of Corollary 1

In this section, we will prove Corollary 1 using Lemma 1, which we prove afterward.

###### Proof of Corollary 1 .

By Theorem 1 and Lemma 1, we can assume, without loss of generality, it suffices to consider the special case where $f$ consists of a single term

$$ $f(v_{1},\ldots,v_{n})=\iota_{r}\quantity(v_{\ell_{1}}\otimes\cdots\otimes v_{ \ell_{r}}\otimes\left(\delta^{\otimes\frac{r+k^{\prime}}{2}}\right)^{\sigma}),$ (51) $$

for some $\sigma\in S_{r+k^{\prime}}$ and $r+k^{\prime}$ even. To simplify notation, set $t:=\frac{r+k^{\prime}}{2}$.

Now, note that

$$ $\delta=e_{i}\otimes e_{i},$ $$

where $\{e_{1},\ldots,e_{d}\}$ is the canonical basis of $\mathbb{R}^{d}$. Hence we get

$$ $f(v_{1},\ldots,v_{n})=\iota_{r}\quantity(v_{\ell_{1}}\otimes\cdots\otimes v_{ \ell_{r}}\otimes\left(e_{i_{1}}\otimes e_{i_{1}}\otimes\cdots\otimes e_{i_{t}} \otimes e_{i_{t}}\right)^{\sigma})$ (52) $$

Let’s write

$$ $\left(e_{i_{1}}\otimes e_{i_{1}}\otimes\cdots\otimes e_{i_{t}}\otimes e_{i_{t} }\right)^{\sigma}=e_{j_{1}}\otimes\cdots\otimes e_{j_{2t}}$ $$

where each $(j_{1},\ldots,j_{2t})$ is some permutation of $(i_{1},i_{1},\ldots,i_{t},i_{t})$ and so, by Einstein notation, we are still adding over repeated indexes. Then we have that

$$ $f(v_{1},\ldots,v_{n})=\langle v_{\ell_{1}},e_{j_{1}}\rangle\cdots\langle v_{ \ell_{r}},e_{j_{r}}\rangle e_{j_{r+1}}\otimes\cdots\otimes e_{j_{2t}}.$ (53) $$

Now, we can freely rearrange the $\langle v_{\ell},e_{j}\rangle$ as they are scalars. There are three cases for each of the original indices $i_{q}$: (a) $e_{i_{q}}$ appears in an inner product twice, (b) $e_{i_{q}}$ appears in an inner product once, or (c) $e_{i_{q}}$ does not appear in an inner product.

In the case (a), we will get

$$ $\langle v_{\ell},e_{i}\rangle\langle v_{\ell^{\prime}},e_{i}\rangle=\langle v_ {\ell},v_{\ell^{\prime}}\rangle.$ $$

In the case (b), we will get

$$ $\langle v_{\ell},e_{i}\rangle e_{i}=v_{\ell}.$ $$

And, in the case (c), we will get

$$ $e_{i}\otimes e_{i}=\delta.$ $$

Now, assume that we have $\alpha$ of the case (a), $\beta$ of the case (b) and $\gamma$ of the case (c).
By permuting the $i_{q}$, which does not change the result, we can write for some permutation $\tilde{\sigma}\in S_{\beta+\gamma}$ and some permutation $J_{1},\ldots,J_{r}$ some permutation of $\ell_{1},\ldots,\ell_{r}$ that

$$ $f(v_{1},\ldots,v_{n})=\langle v_{J_{1}},e_{i_{1}}\rangle\langle v_{J_{2}},e_{i _{1}}\rangle\cdots\langle v_{J_{2\alpha-1}},e_{i_{\alpha}}\rangle\langle v_{J_ {2\alpha}},e_{i_{\alpha}}\rangle\\ \left(\langle v_{J_{2\alpha+1}},e_{i_{\alpha+1}}\rangle e_{i_{\alpha+1}} \otimes\cdots\otimes\langle v_{J_{2\alpha+\beta}},e_{i_{\alpha+\beta}}\rangle e _{i_{\alpha+\beta}}\right.\\ \left.\otimes e_{i_{\alpha+\beta+1}}\otimes e_{i_{\alpha+\beta+1}}\otimes \cdots\otimes e_{i_{\alpha+\beta+\gamma}}\otimes e_{i_{\alpha+\beta+\gamma}} \right)^{\tilde{\sigma}}\\ =\langle v_{J_{1}},v_{J_{2}}\rangle\cdots\langle v_{J_{2\alpha-1}},v_{J_{2 \alpha}}\rangle\quantity(v_{J_{2}\alpha+1}\otimes\cdots\otimes v_{2\alpha+ \beta}\otimes\delta^{\otimes\gamma})^{\tilde{\sigma}}.$ $$

Hence, the desired claim follows, and we finish the proof.
∎

###### Proof of Lemma 1 .

We will prove each case separately. However, note that no matter the value of $p$, an $\mathop{O}(d)$-isotropic tensor is always an $\mathop{SO}(d)$-isotropic tensor since $\det(M(g))=1$ for all $g\in\mathop{SO}(d)$. Now, by [, Theorem §2] (cf. [, Eq. (4.10)]), any $\mathop{SO}(d)$-isotropic tensor $z$ can be written as a linear combination of the form

$$ $z=\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\delta^{\otimes\frac{k}{2}})^ {\sigma}+\beta_{\sigma}\quantity(\delta^{\otimes\frac{k-d}{2}}\otimes\epsilon) ^{\sigma},$ (54) $$

where $\delta$ is the Kronecker delta (Definition 8), and $\epsilon$ is
the Levi-Civita symbol (Definition 9),
with the convention that the coefficients $\alpha_{\sigma}$ and $\beta_{\sigma}$ are zero when the expressions $\delta^{\otimes\frac{k}{2}}$ and $\delta^{\otimes\frac{k-d}{2}}$ do not make sense.
More precisely, the $\alpha_{\sigma}=0$ if $k$ is odd, and the $\beta_{\sigma}=0$ if $k-d$ is odd.

Note that under the $\mathop{SO}(d)$-action, we don’t need to worry about the parity, and so both $\delta$ and $\epsilon$ are $\mathop{SO}(d)$-invariant.
However, for the $\mathop{O}(d)$-action, the parity matters.
Suppose $\gamma\in\mathop{O}(d)$ is a hyperplane reflection, and let $T$ be an $\mathop{O}(d)$-isotropic ${k}_{(-)}$-tensor.
If $\hat{T}$ is a ${k}_{(+)}$-tensor whose components equal $T$, then

$$ $\gamma\cdot\hat{T}=-\hat{T}~{}.$ $$

Likewise, if $T$ is an $\mathop{O}(d)$-isotropic ${k}_{(+)}$-tensor and $\hat{T}$ is a ${k}_{(-)}$-tensor whose components equal $T$, then

$$ $\gamma\cdot\hat{T}=-\hat{T}~{}.$ $$

Note that being isotropic depends on the parity because it affects the considered action.

*Case $p=-1$*:
Let $z\in\mathcal{T}_{k}\quantity(\mathbb{R}^{d},+)$ be $\mathop{O}(d)$-isotropic. In particular, $z$ is also $\mathop{SO}(d)$-isotropic, and so we can write it using (54).

Recall that $\mathop{O}(d)$ is generated by all the (hyperplane) reflections. Hence, to show that $z$ is an $\mathop{O}(d)$-isotropic, we need only to show that for every (hyperplane) reflection $\gamma\in\mathop{O}(d)$,

$$ $\gamma\cdot z=z.$ $$

Now, by our observation above, inside $\mathcal{T}_{k}\quantity(\mathbb{R}^{d},+)$, we have that

$$ $\gamma\cdot\delta^{\otimes\frac{k-d}{2}}\otimes\epsilon=-\delta^{\otimes\frac{ k-d}{2}}\otimes\epsilon,$ (55) $$

since $\delta^{\otimes\frac{k-d}{2}}\otimes\epsilon$ is an $\mathop{O}(d)$-isotropic ${k}_{(-)}$-tensor.
Hence

$$ $\displaystyle\gamma\cdot z$ $\displaystyle=\gamma\cdot\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\delta ^{\otimes\frac{k}{2}})^{\sigma}+\beta_{\sigma}\quantity(\delta^{\otimes\frac{k -d}{2}}\otimes\epsilon)^{\sigma}$ $\displaystyle=\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\quantity(\gamma \cdot\delta)^{\otimes\frac{k}{2}})^{\sigma}+\beta_{\sigma}\quantity(\quantity( \gamma\cdot\delta)^{\otimes\frac{k-d}{2}}\otimes\gamma\cdot\epsilon)^{\sigma}$ $\displaystyle=\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\delta^{\otimes \frac{k}{2}})^{\sigma}-\beta_{\sigma}\quantity(\delta^{\otimes\frac{k-d}{2}} \otimes\epsilon)^{\sigma}$ $\displaystyle=z-2\sum_{\sigma\in S_{k}}\beta_{\sigma}\quantity(\delta^{\otimes \frac{k-d}{2}}\otimes\epsilon)^{\sigma}~{}.$ $$

Now, by assumption, $z$ is $\mathop{O}(d)$-isotropic, so we can conclude $\sum_{\sigma\in S_{k}}\beta_{\sigma}\quantity(\delta^{\otimes\frac{k-d}{2}}
\otimes\epsilon)^{\sigma}=0$, and so $z$ has the desired form.

*Case $p=-1$*: We argue as above, but using that for a (hyperplane) reflection $\gamma\in\mathop{O}(d)$, we have, inside $\mathcal{T}_{k}\quantity(\mathbb{R}^{d},-)$,

$$ $\gamma\cdot\delta^{\otimes\frac{k}{2}}=-\delta^{\otimes\frac{k}{2}},$ (56) $$

since $\delta^{\otimes\frac{k}{2}}$ is an $\mathop{O}(d)$-isotropic ${k}_{(+)}$-tensor. Hence, arguing similarly as in the previous case, we conclude that $\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\delta^{\otimes\frac{k}{2}})^{
\sigma}=0$, and so that $z$ has the desired form.
∎

###### Proof of Corollary 1 .

###### Proof of Lemma 1 .

## Appendix D Smaller parameterization of 𝑂 ( d ) 𝑂 𝑑 \mathop{O}(d) italic_O ( italic_d ) -isotropic tensors

In Lemma 1, the sum does not have to be over all permutations. The reason for this is that the tensors

$$ $\delta^{\otimes\frac{k}{2}}~{}\text{ and }~{}\delta^{\otimes\frac{k-d}{2}}\otimes\epsilon$ $$

do not have a trivial stabilizer under the action of $S_{k}$. One can easily see the following proposition. Recall that the *stabilizer of a $k$-tensor $\pm T$ in $S_{k}$* is the following subgroup:

$$ $\mathrm{Stab}_{S_{k}}(\pm T):=\{\sigma\in S_{k}\mid T^{\sigma}=\pm T\},$ (57) $$

where $T^{\sigma}=\pm T$ means that either $T^{\sigma}=T$ or $T^{\sigma}=-T$. Note that the laxity in the signs comes from the fact that positive summands and their negative counterparts can be combined.

###### Proposition 4 .

(a) If $k$ is even, $\mathrm{Stab}_{S_{k}}\quantity(\pm\delta^{\otimes\frac{k}{2}})$ is generated by the transpositions

$$ $(1,2),(3,4),\ldots,(k-1,k)$ $$

and all permutations of the form

$$ $(i,j)(i+1,j+1)$ $$

with $i,j<k$ odd. In particular, $\#\,\mathrm{Stab}_{S_{k}}\quantity(\pm\delta^{\otimes\frac{k}{2}})=(k/2)!\,2^{
k/2}$.

(b) If $k-d$ is even, $\mathrm{Stab}_{S_{k}}\quantity(\pm\delta^{\otimes\frac{k-d}{2}}\otimes\epsilon)$ is generated by the transpositions

$$ $(1,2),(3,4),\ldots,(k-d-1,k-d),$ $$

all permutations of the form

$$ $(i,j)(i+1,j+1)$ $$

with $i,j<k-d$ odd, and all transpositions of the form

$$ $(i,j)$ $$

with $k-d<i,j$. In particular, $\#\,\mathrm{Stab}_{S_{k}}\quantity(\pm\delta^{\otimes\frac{k-d}{2}}\otimes
\epsilon)=((k-d)/2)!\,2^{(k-d)/2}d!$.

###### Proof.

This follows from [, Theorem 5.3.4].
∎

Using these proposition, we can write any $\mathop{O}(d)$-isotropic ${k}_{(+)}$-tensor as

$$ $\sum_{\sigma\in G_{k}}\alpha_{\sigma}\quantity(\delta^{\otimes\frac{k}{2}})^{\sigma}$ $$

with the $\alpha_{\sigma}$ real and

$$ $G_{k}=\big{\{}\sigma\in S_{k}:\sigma(1)<\sigma(3)<\cdots<\sigma(k-1)\text{ and for all }i\leq\frac{k}{2},\,\sigma(2i-1)<\sigma(2i)\big{\}}$ $$

of size $\frac{k!}{(k/2)!2^{k/2}}$; and any $\mathop{O}(d)$-isotropic ${k}_{(-)}$-tensor as

$$ $\sum_{\sigma\in H_{k}}\beta_{\sigma}\quantity(\delta^{\otimes\frac{k-d}{2}} \otimes\epsilon)^{\sigma}$ (58) $$

with the $\beta_{\sigma}$ real and

$$ $H_{k}=\big{\{}\sigma\in S_{k}:\sigma(1)<\sigma(3)<\cdots<\sigma(k-d-1)\text{, for all }i\leq\frac{k-d}{2},\,\sigma(2i-1)<\sigma(2i)\\ \text{ and for all }j>k-d,\sigma(j)<\sigma(j+1)\big{\}}.$ $$

of size $\frac{k!}{\left(\frac{k-d}{2}\right)!2^{\frac{k-d}{2}}d!}$.

###### Proposition 4 .

###### Proof.

## Appendix E Example of Theorem 1

In this section, we give a second example of Theorem 1.

###### Example 2 .

Let $f:\mathcal{T}_{1}\quantity(\mathbb{R}^{d},+)\times\mathcal{T}_{2}\quantity(
\mathbb{R}^{d},+)\to\mathcal{T}_{2}\quantity(\mathbb{R}^{d},+)$ be $\mathop{O}(d)$-equivariant polynomial of degree at most $2$. By Theorem
1 we can write $f$ in the form

$$ $f(a_{1},a_{2})=\sum_{r=0}^{2}\,\sum_{1\leq\ell_{1}\leq\cdots\leq\ell_{r}\leq 2 }\iota_{k_{\ell_{1},\ldots,\ell_{r}}}\quantity(a_{\ell_{1}}\otimes\ldots \otimes a_{\ell_{r}}\otimes c_{\ell_{1},\ldots,\ell_{r}})~{},$ (59) $$

where
$c_{\ell_{1},\ldots,\ell_{r}}$ is an $\mathop{O}(d)$-isotropic ${(k_{\ell_{1},\ldots,\ell_{r}}+2)}_{(+)}$-tensor.
By Lemma 1, $c_{\ell_{1},\ldots,\ell_{r}}$ is nontrivial only when $k_{\ell_{1},\ldots,\ell_{r}}+2$ is even.
Recall that $k_{\ell_{1},\ldots,\ell_{r}}=\sum_{q=1}^{r}k_{\ell_{q}}$. The inputs are a ${1}_{(+)}$-tensor and ${2}_{(+)}$-tensor. The even combinations of $1$ and $2$ with at most $2$ terms are $\emptyset,2,1+1,2+2$ so we have

$$ $f(a_{1},a_{2})=\beta_{0}\delta+\iota_{2}\quantity(a_{2}\otimes c_{2})+\iota_{2 }\quantity(a_{1}\otimes a_{1}\otimes c_{2}^{\prime})+\iota_{4}\quantity(a_{2} \otimes a_{2}\otimes c_{3})~{},$ (60) $$

where $c_{2},c_{2}^{\prime}$ are $\mathop{O}(d)$-isotropic ${4}_{(+)}$-tensors and $c_{3}$ is an $\mathop{O}(d)$-isotropic ${6}_{(+)}$-tensor. By similar reasoning to Example 1, we can write

$$ $\iota_{2}\quantity(a_{2}\otimes c_{2})=\beta_{1}\tr(a_{2})\delta+\beta_{2}a_{2 }+\beta_{3}a_{2}^{\top}$ (61) $$

for constants $\beta_{1},\beta_{2},\beta_{3}$ and

$$ $\iota_{2}\quantity(a_{1}\otimes a_{1}\otimes c_{2}^{\prime})=\beta_{4}\langle a _{1},a_{1}\rangle\delta+\beta_{5}a_{1}\otimes a_{1}~{},$ (62) $$

for constants $\beta_{4},\beta_{5}$ (there are only two terms due to the symmetry of $a_{1}\otimes a_{1}$).
It remains to consider $\iota_{4}\quantity(a_{2}\otimes a_{2}\otimes c_{3})$. By Lemma 1, we can write

$$ $c_{3}=\sum_{\sigma\in G_{6}}\beta_{\sigma}(\delta^{\otimes 3})^{\sigma}~{},$ (63) $$

where $|G_{6}|=6!/(3!2^{3})=15$. In particular, we have

$$ $\begin{split}G_{6}=\big{\{}&(1,2,3,4,5,6),(1,2,3,5,4,6),(1,2,3,5,6,4),(1,3,2,4 ,5,6),(1,3,2,5,4,6),\\ &(1,3,2,5,6,4),(1,3,4,2,5,6),(1,3,4,5,2,6),(1,3,4,5,6,2),(1,3,5,2,4,6),\\ &(1,3,5,2,6,4),(1,3,5,4,2,6),(1,3,5,4,6,2),(1,3,5,6,2,4),(1,3,5,6,4,2)\big{\}} ~{}.\end{split}$ $$

However, due to the symmetry of $a_{2}\otimes a_{2}$, when we compute $\iota_{4}\quantity(a_{2}\otimes a_{2}(\delta^{\otimes 3})^{\sigma})$ for $\sigma\in G_{6}$, there are only $7$ distinct terms

$$ $\iota_{4}\quantity(a_{2}\otimes a_{2}\otimes c_{3})=\\ \beta_{6}\tr(a_{2})^{2}\delta+\beta_{7}\tr(a_{2})a_{2}+\beta_{8}\tr(a_{2})a_{2 }^{\top}+\beta_{9}a_{2}^{\top}a_{2}+\beta_{10}a_{2}a_{2}^{\top}+\beta_{11}a_{2 }a_{2}+\beta_{12}a_{2}^{\top}a_{2}^{\top}~{}.$ (64) $$

In summary,

$$ $f(a_{1},a_{2})=\beta_{0}\delta+\beta_{1}\tr(a_{2})\delta+\beta_{2}a_{2}+\beta_ {3}a_{2}^{\top}+\beta_{3}\langle a_{1},a_{1}\rangle\delta+\beta_{4}a_{1} \otimes a_{1}+\beta_{5}\tr(a_{2})^{2}\delta\\ +\beta_{6}\tr(a_{2})a_{2}+\beta_{7}\tr(a_{2})a_{2}^{\top}+\beta_{8}a_{2}^{\top }a_{2}+\beta_{9}a_{2}a_{2}^{\top}+\beta_{10}a_{2}a_{2}+\beta_{11}a_{2}^{\top}a _{2}^{\top}~{},$ $$

for some coefficients $\beta_{0},\beta_{1},\ldots,\beta_{11}$.

###### Example 2 .

## Appendix F Generalization to other linear algebraic groups

In this section, we will show how Theorem 1 and Corollary 1 can be extended to the indefinite orthogonal and the symplectic group as Theorem 2 and Corollary 2.

The main idea to extend Theorem 1 to other groups is to use some form of averaging. On $\mathop{O}(d)$, the compactness guarantees the existence of a Haar probability measure. However, to apply the same trick over non-compact groups such as $\mathop{O}(s,d-s)$ and $\mathop{Sp}(d)$, we need to use technical machinery to imitate the averaging strategy.

First, we introduce some definitions and examples regarding
complex and real linear algebraic groups. The main point will be to establish how to get a compact subgroup over which to average. Basically the results will generalize to real linear algebraic groups such that their complexifications have a Zariski-dense compact subgroup. For instance reductive connected complex algebraic groups satisfy this assumption. Second, we prove a generalization of Theorem 1 for complex linear algebraic groups with a Zariski-dense compact subgroup acting on complex tensors. Third, we prove a generalization of Theorem 1 for real linear algebraic groups that are compact or such that their complexification has a Zariski-dense compact subgroup. Finally, we prove Corollary 2.

### F.1 Reductive complex and real linear algebraic groups

Recall that a *complex linear algebraic group* is a subgroup $G$ of $\mathrm{GL}(V)$, where $V$ is a finite-dimensional complex vector space, such that $G$ is the zero set of some set of complex polynomial functions over $\mathop{End}(V)$, the set of (complex) linear maps $V\rightarrow V$. Recall also that a *rational $G$-module* of $G$ is a vector space $U$ together with a linear action of $G$ on $U$ such that the map $G\times U\ni(g,x)\mapsto g\cdot x\in U$ is polynomial(^2^22To be precise, we mean that the map $G\times U\rightarrow U$ is a morphism of algebraic varieties. Choose basis for $U$ and $V$, so that we can identify $V$ with $\mathbb{C}^{d}$ and $U$ with $\mathbb{C}^{n}$. Then, being a morphism between algebraic varieties, just means that the map $G\times\mathbb{C}^{n}\rightarrow\mathbb{C}^{n}$ is the restriction of a map $\mathbb{C}^{d\times d}\times\mathbb{C}^{n}\rightarrow\mathbb{C}^{n}$ that can be written componentwise as $\left(p_{l}((g_{i,j})_{i,j},(u_{k})_{k})/(\det\,g)^{a_{l}}\right)_{l}$ where each $p_{l}$ is a polynomial in the $g_{i,j}$ and $u_{k}$ and each $a_{l}$ an integer.), and that a $G$-submodule $U_{0}$ of $U$ is a vector subspace $U_{0}\subseteq U$ such that for all $g\in G$, $g\cdot U_{0}\subseteq U_{0}$.

###### Definition 10 .

[, Def. 3.3.1]
A *reductive complex linear algebraic group* is a complex linear algebraic group $G\subset\mathop{GL}(V)$ such that every rational $G$-module $U$ is *completely reducible*, i.e., for every $G$-submodule $U_{0}$ of $U$, there is a $G$-submodule $U_{1}$ such that $U=U_{0}+U_{1}$ and $U_{0}\cap U_{1}=0$.

###### Example 3 .

Given any finite-dimensional vector space, the classical complex groups $\mathop{GL}(V)$ and $\mathop{SL}(V)$ are reductive complex linear algebraic groups.

###### Example 4 .

Given any finite-dimensional vector space $V$ together with a symmetric non-degenerate bilinear form(^3^33Recall that this means that for all $u,v,w\in V$ and $t,s\in\mathbb{C}$: (a) $\langle u,v\rangle=\langle v,u\rangle$, (b) for all $x\in V$, $\langle u,x\rangle=0$ if and only if $u=0$, and (c) $\langle tu+sv,w\rangle=t\langle u,w\rangle+s\langle v,w\rangle$.) $\langle\,\cdot\,,\,\cdot\,\rangle:V\times V\to\mathbb{C}$, the (complex) orthogonal group

$$ $\mathop{O}(V,\langle\,\cdot\,,\,\cdot\,\rangle):=\{g\in\mathop{GL}(V)\mid\text {for all }v,w\in V,\,\langle g\cdot v,g\cdot w\rangle=\langle v,w\rangle\}$ (65) $$

is a reductive complex linear algebraic group.
We will pay special attention to the following family of complex orthogonal groups:

$$ $\mathop{O^{\mathbb{C}}}(s,d-s):=\{g\in\mathop{GL}(\mathbb{C}^{d})\mid g^{\top} \mathbb{I}_{s,d-s}g=\mathbb{I}_{s,d-s}\}=\mathop{O}(\mathbb{C}^{d},\langle\, \cdot\,,\,\cdot\,\rangle_{s})$ (66) $$

where $\langle u,v\rangle_{s}:=u^{\top}\mathbb{I}_{s,d-s}v$. Note that all these groups are isomorphic, satisfying that

$$ $\mathop{O^{\mathbb{C}}}(s,d-s)=\begin{pmatrix}\mathbb{I}_{s}&\\ &i\mathbb{I}_{d-s}\end{pmatrix}\mathop{O^{\mathbb{C}}}(d,0)\begin{pmatrix} \mathbb{I}_{s}&\\ &i\mathbb{I}_{d-s}\end{pmatrix}^{-1}.$ $$

Moreover, this is true in general: any two complex orthogonal groups are isomorphic if they are of the same order—this follows from the fact that all symmetric non-degenerate bilinear forms are equivalent over the complex numbers.

###### Example 5 .

Given any finite-dimensional vector space $V$ together with an anti-symmetric non-degenerate bilinear form $\langle\,\cdot\,,\,\cdot\,\rangle:V\times V\to\mathbb{C}$, the (complex) symplectic group

$$ $\mathop{Sym}(V,\langle\,\cdot\,,\,\cdot\,\rangle):=\{g\in\mathop{GL}(V)\mid \text{for all }v,w\in V,\,\langle g\cdot v,g\cdot w\rangle=\langle v,w\rangle\}$ (67) $$

is a reductive complex linear algebraic group. We will pay special attention to the following special case:

$$ $\mathop{Sp^{\mathbb{C}}}(d):=\{g\in\mathop{GL}(\mathbb{C}^{d})\mid g^{\top}J_{ d}g=J_{d}\}=\mathop{Sp}(\mathbb{C}^{d},\langle\,\cdot\,,\,\cdot\,\rangle_{ \mathrm{symp}})$ (68) $$

where $\langle u,v\rangle_{\mathrm{symp}}:=u^{\top}J_{d}v$. Note that any symplectic group of order $d$ is isomorphic to $\mathop{Sp}^{\mathbb{C}}(d)$ because any two antisymmetric non-degenerate bilinear forms are equivalent over the complex numbers.

###### Example 6 .

The complex linear algebraic group

$$ $H=\left\{\begin{pmatrix}1&t\\ &1\end{pmatrix}\mid t\in\mathbb{C}\right\}$ $$

is not reductive, since $\mathbb{C}^{2}$ is an $H$-module that is not completely reducible. Note that $\mathbb{C}\times 0$ is the only $H$-submodule of $\mathbb{C}^{2}$, so we cannot find a complementary $H$-submodule.

Recall that a subset $X$ of a set $\tilde{X}$ is *Zariski-dense* in $\tilde{X}$ if every polynomial function that vanishes in $X$ vanishes in $\tilde{X}$, i.e. if every polynomial function that does not vanish on $\tilde{X}$ does not vanish in $X$. The following theorem allows us to use the power of averaging for reductive connected complex linear algebraic groups.

###### Theorem 3 .

[, Theorem 11.5.1]
Let $G$ be a reductive connected complex algebraic group. Then there exists a Zariski-dense compact subgroup $K$. More precisely, there is a subgroup $\mathop{U}(G)$ of $G$ that is Zariski-dense in $G$ and that, with respect to the usual topology(^4^44The topology inherited from the Euclidean topology of $\mathrm{GL}(\mathbb{C}^{d})$.), is compact.

###### Remark 6 .

Note that using this compact subgroup $K$, we can consider expressions of the form

$$ $\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}\cdot T$ $$

by taking the expectation with respect to the unique Haar probability measure of $K$. Now, since $\mathop{U}(G)$ is Zariski-dense in $G$, we have that the fact that for all $u\in\mathop{U}(G)$, $u\cdot\quantity(\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}
\cdot T)=\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}\cdot T$ implies that for all $g\in G$,

$$ $g\cdot\quantity(\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u} \cdot T)=\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}\cdot T.$ $$

Note that $\mathop{U}(G)$ is not necessarily unique.

###### Example 7 .

In $\mathop{GL}(\mathbb{C}^{d})$, the Zariski-dense compact subgroup is the group of unitary matrices:

$$ $\mathop{U}(\mathbb{C}^{d}):=\{g\in\mathop{GL}(\mathbb{C}^{d})\mid g^{*}g= \mathbb{I}_{d}\}$ $$

where ^∗ denotes the conjugate transpose. In $\mathop{SL}(\mathbb{C}^{d})$, it is the group of special unitary transformations:

$$ $\mathop{SU}(\mathbb{C}^{d}):=\{g\in\mathop{U}(\mathbb{C}^{d})\mid\det g=1\}.$ $$

###### Example 8 .

In $\mathop{O^{\mathbb{C}}}(s,d-s)$, the Zariski-dense compact subgroup is

$$ $\begin{pmatrix}\mathbb{I}_{s}&\\ &i\mathbb{I}_{d-s}\end{pmatrix}\mathop{O}(d)\begin{pmatrix}\mathbb{I}_{s}&\\ &i\mathbb{I}_{d-s}\end{pmatrix}^{-1}.$ $$

Note that when $s=0$ or $s=d$, this is the orthogonal group over the reals. Moreover, this does not follow from Theorem 3 as $O^{\mathbb{C}}(s,d-s)$ is not connected.

###### Example 9 .

In $\mathop{Sp^{\mathbb{C}}}(d)$, the Zariski-dense compact subgroup is the so-called compact symplectic group:

$$ $\mathop{USp}(d):=\mathop{Sp^{\mathbb{C}}}(d)\cap\mathop{U}(\mathbb{C}^{d}).$ $$

Recall that a *real linear algebraic group* is a subgroup $G$ of $\mathrm{GL}(V)$, where $V$ is a finite-dimensional real vector space, such that $G$ is the zero set of some set of real polynomial functions over $\mathbb{R}^{d\times d}$. Similarly, as we did with complex linear algebraic groups, we can talk about *rational modules* and about *reductive real linear algebraic groups*.

However, given a reductive real linear algebraic group we cannot necessarily guarantee the existence of a Zariski-dense compact subgroup. This means that we cannot apply the averaging trick directly, but we can do so by passing to the Zariski-dense compact subgroup of the complexification of the real linear algebraic group.

###### Definition 11 .

Let $G\subset\mathop{GL}(V)$ be a real linear algebraic group. The *complexification* $G^{\mathbb{C}}$ of $G$ is the complex linear algebraic group given by

$$ $G^{\mathbb{C}}:=\{g\in\mathop{GL}(V^{\mathbb{C}})\mid\text{for every polynomial }f\text{ such that }f(G)=0,\,f(g)=0\}$ (69) $$

where $V^{\mathbb{C}}:=V\otimes_{\mathbb{R}}\mathbb{C}$ is the complexification of $V$, i.e., the complex vector space obtained from $V$ by extending scalars.

###### Remark 7 .

In essence, we complexify the underlying real algebraic variety. Group multiplication preserves its structure as a complex variety as it is given by polynomial functions of the matrix entries.

###### Definition 12 .

A real linear algebraic group $G$ is *complexly averageable* if it’s Zariski-dense in its complexification and its complexification admits a Zariski-dense compact subgroup closed under complex conjugation.

###### Remark 8 .

Recall that the complexification of $\mathbb{R}^{d}$ is naturally isomorphic to $\mathbb{C}^{d}$.

###### Example 10 .

The complexification of $\mathop{GL}(\mathbb{R}^{d})$ is $\mathop{GL}(\mathbb{C}^{d})$, and the complexification of $\mathop{SL}(\mathbb{R}^{d})$ is $\mathop{SL}(\mathbb{R}^{d})$.

###### Example 11 .

We have that

$$ $\mathop{O}(s,d-s)^{\mathbb{C}}=\mathop{O^{\mathbb{C}}}(s,d-s)$ $$

and that

$$ $\mathop{Sp}(d)^{\mathbb{C}}=\mathop{Sp^{\mathbb{C}}}(d).$ $$

Hence, both the indefinite orthogonal group and symplectic group are complexly averageable. The symplectic group is connected but the indefinite orthogonal group is not connected. However, it does have a Zariski-dense compact subgroup (see Example 8).

The following proposition shows that complexly averageable real linear algebraic groups are common.

###### Proposition 5 .

Let $G\subset\mathop{GL}(V)$ be a real linear algebraic group. (1) $G$ is Zariski-dense in $G^{\mathbb{C}}$. (2) If the complexification $G^{\mathbb{C}}$ of $G$ is connected and reductive, then $G$ is complexly averageable.

###### Proof.

(1) Let $f$ be a complex polynomial vanishing on $G$. Then, we can write this polynomial as $f=f_{r}+if_{i}$ for some polynomials $f_{r}$ and $f_{i}$ with real coefficients. Now, since $f$ vanishes on $G$, then $f_{r}$ and $f_{i}$ vanish also on $G$—as otherwise there would be $g\in G$ such that either $f_{r}(g)\neq 0$ or $f_{i}(g)\neq 0$, contradicting $f(g)=0$. But then, by definition of $G^{\mathbb{C}}$, $f_{r}$ and $f_{i}$ vanish on $G$ and so $f=f_{r}+if_{i}$ vanishes on $G^{\mathbb{C}}$. Hence we have just proven that a complex polynomial vanishes on $G$ if and only if vanishes on $G^{\mathbb{C}}$, i.e., we have proven that $G$ is Zariski-dense in $G^{\mathbb{C}}$.

(2) This follows from Theorem 3.
∎

###### Example 12 .

Observe that the Zariski-dense compact subgroups of $\mathop{O^{\mathbb{C}}}(s,d-s)$ and $\mathop{Sp}^{\mathbb{C}}(d)$ that have been given satisfy that they are closed under the complex conjugation.

###### Definition 10 .

###### Example 3 .

###### Example 4 .

###### Example 5 .

###### Example 6 .

###### Theorem 3 .

###### Remark 6 .

###### Example 7 .

###### Example 8 .

###### Example 9 .

###### Definition 11 .

###### Remark 7 .

###### Definition 12 .

###### Remark 8 .

###### Example 10 .

###### Example 11 .

###### Proposition 5 .

###### Proof.

###### Example 12 .

### F.2 Complex equivariant tensor maps

We will consider vector spaces on which a non-degenerate bilinear form has been chosen.

###### Definition 13 .

A *self-paired vector space* $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$ is a finite-dimensional vector space $V$ together with a non-degenerate bilinear form $\langle\,\cdot\,,\,\cdot\,\rangle:V\times V\rightarrow\mathbb{C}$.

Recall the *universal property* of tensor products of vector spaces, by which multilinear maps $V_{1}\times\cdots\times V_{k}\rightarrow W$ can be lifted to linear maps $V_{1}\otimes\cdots\otimes V_{k}\rightarrow W$. Using the universal property, we can see that from a self-paired vector space $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$, we get the family

$$ $(V^{\otimes k},\langle\,\cdot\,,\,\cdot\,\rangle)$ $$

of self-paired spaces of tensors, by extending by linearity the expression

$$ $\langle v_{1}\otimes\cdots\otimes v_{k},\tilde{v}_{1}\otimes\cdots\otimes \tilde{v}_{k}\rangle=\langle v_{1},\tilde{v}_{1}\rangle\cdots\langle v_{k}, \tilde{v}_{k}\rangle.$ (70) $$

And again, by the universal property, we get a *$k$-contraction*

$$ $\iota_{k}:V^{\otimes(2k+k^{\prime})}\cong V^{\otimes k}\otimes V^{\otimes k} \otimes V^{k^{\prime}}\rightarrow V^{k^{\prime}}$ (71) $$

by extending by linearity, the expression

$$ $a\otimes b\otimes c\mapsto\langle a,b\rangle c.$ (72) $$

Now, in the above setting, let $G$ be a group acting in a structure-preserving way on $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$, meaning that the action is linear and preserves $\langle\,\cdot\,,\,\cdot\,\rangle$, i.e., for all $g\in G$,
$v,\tilde{v}\in V$,
$\langle v,\tilde{v}\rangle=\langle g\cdot v,g\cdot\tilde{v}\rangle$. Then, by the universal property, we get that $G$ acts also on $(V^{\otimes k},\langle\,\cdot\,,\,\cdot\,\rangle)$ by extending linearly the expression

$$ $g(v_{1}\otimes\cdots\otimes v_{k})=\chi(g)(gv_{1})\otimes\cdots\otimes(gv_{k}).$ (73) $$

Moreover, by considering all (rational)(^5^55Recall that rational means that the homomorphism is given by polynomials.) unidimensional representations $\chi:G\rightarrow\mathbb{C}^{*}$ of $G$, we get the following family of self-paired (rational) $G$-modules:

$$ $\mathcal{T}_{k}(V,\chi):=(V^{\otimes k},\langle\,\cdot\,,\,\cdot\,\rangle)$ (74) $$

where the action by $G$ is given by

$$ $g\cdot T:=\chi(g)M(g)\cdot T$ (75) $$

in a structure-preserving way.
For the sake of distinction, we will denote the $k$-contraction as

$$ $\iota_{k}^{G}:\mathcal{T}_{2k+k^{\prime}}(V,\chi)\rightarrow\mathcal{T}_{k^{ \prime}}(V,\chi)$ (76) $$

in this setting to emphasize the dependence on the group $G$, as we will be choosing the original $\langle\,\cdot\,,\,\cdot\,\rangle$ in terms of the group.
Using the universal property, we can easily see the following:

###### Proposition 6 .

The following statements hold:

- (a)
The outer product map
$\mathcal{T}_{k}(V,\chi)\times\mathcal{T}_{k^{\prime}}(V,\chi^{\prime})
\rightarrow\mathcal{T}_{k+k^{\prime}}(V,\chi\chi^{\prime})$
is a $G$-equivariant bilinear map.
- (b)
The $k$-contraction $\iota_{k}^{G}:\mathcal{T}_{2k+k^{\prime}}(V,\chi)\rightarrow\mathcal{T}_{k^{
\prime}}(V,\chi)$ is a $G$-equivariant linear map.
- (c)
For any $\sigma\in S_{k}$, the tensor index permutation by $\sigma$, $\mathcal{T}_{k}(V,\chi)\rightarrow\mathcal{T}_{k}(V,\chi)$ given by $v_{1}\otimes\cdots\otimes v_{k}\mapsto v_{\sigma^{-1}(1)}\otimes\cdots\otimes v
_{\sigma^{-1}(k)}$, is a $G$-equivariant linear map.

Finally, recall that a $G$-isotropic tensor of $\mathcal{T}_{\ell}(V,\chi)$ is a $G$-invariant tensor in $\mathcal{T}_{\ell}(V,\chi)$. Further, recall that an *entire* function is an analytic function whose Taylor series at any point has an infinite radius of convergence. We can now state the theorem.

###### Theorem 4 .

Let $G\subset\mathop{GL}(V)$ be a reductive connected complex linear algebraic group (or more generally, a complex linear algebraic group with a Zariski-dense compact subgroup) acting rationally on an structure-preserving way on a self-paired complex vector space $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$ and $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})\to\mathcal{T}_{k^{
\prime}}\quantity(V,\chi^{\prime})$ a $G$-equivariant entire function. Then we may write $f$ as follows:

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{\infty}\,\sum_{1\leq\ell_{1}\leq\cdots\leq \ell_{r}\leq n}\iota_{k_{\ell_{1},\ldots,\ell_{r}}}^{G}\left(a_{\ell_{1}} \otimes\ldots\otimes a_{\ell_{r}}\otimes c_{\ell_{1},\ldots,\ell_{r}}\right)$ (77) $$

where $c_{\ell_{1},\ldots,\ell_{r}}\in\mathcal{T}_{k_{\ell_{1},\ldots,\ell_{r}}+k^{
\prime}}(\mathbb{R}^{d},\chi_{\ell_{1},\ldots,\ell_{r}}\,\chi^{\prime})$ is a $G$-isotropic tensor for $k_{\ell_{1},\ldots,\ell_{r}}:=\sum_{q=1}^{r}k_{\ell_{q}}$ and $\chi_{\ell_{1},\ldots,\ell_{r}}=\prod_{q=1}^{r}\chi_{\ell_{q}}$.

To prove this, we proceed as in the orthogonal case: we reduce to the multihomogeneous case and then prove the result using averaging over the Zariski-dense compact subgroup.

###### Lemma 4 .

Let $G\in\mathop{GL}(V)$ be any subgroup acting linearly on a self-paired complex vector space $(V,\langle,\,\cdot\,,\,\cdot\,\rangle)$ and $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})\to\mathcal{T}_{k^{
\prime}}\quantity(V,\chi^{\prime})$ an entire function. Then, we can write $f$ as

$$ $f_{r}(a_{1},\ldots,a_{n})=\sum_{r=0}^{\infty}\sum_{1\leq\ell_{1}\leq\ldots\leq \ell_{r}\leq n}f_{\ell_{1},\ldots,\ell_{r}}(a_{\ell_{1}},\ldots,a_{\ell_{r}}),$ (78) $$

where $f_{\ell_{1},\ldots,\ell_{r}}:\prod_{i=1}^{r}\mathcal{T}_{k_{\ell_{i}}}
\quantity(V,\chi_{i})\to\mathcal{T}_{k^{\prime}}\quantity(V,\chi^{\prime})$ is the composition of the map

$$ $\displaystyle\prod_{i=1}^{r}\mathcal{T}_{k_{\ell_{i}}}\quantity(V,\chi_{\ell_{ i}})$ $\displaystyle\rightarrow\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(V, \prod_{i=1}^{r}\chi_{\ell_{i}})$ $\displaystyle(a_{\ell_{1}},\ldots,a_{\ell_{r}})$ $\displaystyle\mapsto a_{\ell_{1}}\otimes\ldots\otimes a_{\ell_{r}}$ $$

with a linear map $\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(V,\prod_{i=1}^{r}\chi_{\ell_
{i}})\to\mathcal{T}_{k^{\prime}}\quantity(\mathbb{R}^{d},\chi^{\prime})$.

Moreover, for the above decomposition, if $f$ is $G$-equivariant, then so are the $f_{\ell_{1},\ldots,\ell_{r}}$.

###### Remark 9 .

Note that we don’t need to assume anything about $G$ in the above lemma.

###### Proof of Theorem 4 .

By Lemma 4, we can assume without loss of generality that $f$ is of the form

$$ $f(a_{1},\ldots,a_{n})=\lambda(a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}})$ $$

for some non-negative integer $r$, $1\leq\ell_{1}\leq\cdot\leq\ell_{r}\leq r$ and $\lambda:\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(V,\prod_{i=1}^{r}
\chi_{\ell_{i}})\to\mathcal{T}_{k^{\prime}}\quantity(V,\chi^{\prime})$ is linear.

The above map can be written as a linear combination of maps of the form

$$ $(a_{1},\ldots,a_{n})\mapsto\quantity(\prod_{i=1}^{r}\lambda_{i}(a_{\ell_{i}})) \,v_{j_{1}}\otimes\cdots\otimes v_{j_{k^{\prime}}}$ $$

where the $\lambda_{i,j}$ are linear and $v_{j}\in V$, due to the universal property—the factor $\left(\prod_{i=1}^{r}\lambda_{i,j}(a_{\ell_{i}})\right)$ just corresponds to a linear map $\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}}\quantity(V,\prod_{i=1}^{r}\chi_{\ell_
{i}})\to\mathbb{C}$. Moreover,

$$ $\quantity(\prod_{i=1}^{r}\lambda_{i}(a_{\ell_{i}}))\,v_{j_{1}}\otimes\cdots \otimes v_{j_{k^{\prime}}}=\iota_{\sum_{i=1}^{r}k_{\ell_{i}}+k^{\prime}}^{G} \quantity(a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}\otimes c_{1}\otimes \cdots\otimes c_{r}\otimes v_{j_{1}}\otimes\cdots\otimes v_{j_{k^{\prime}}})$ $$

where the $c_{i}\in\mathcal{T}_{k_{i}}(V,\chi_{i})$ are the unique tensors so that for all $a_{\ell_{i}}\in\mathcal{T}_{k_{i}}(V,\chi_{i})$,

$$ $\lambda_{i}(a_{\ell_{i}})=\langle a_{\ell_{i}},c_{i}\rangle.$ $$

These $c_{i}$ exist, because $\langle\,\cdot\,,\,\cdot\,\rangle$ is non-degenerate.
Hence for some $c\in\mathcal{T}_{\sum_{i=1}^{r}k_{\ell_{i}}+k^{\prime}}\quantity(V,\prod_{i=1}
^{r}\chi_{i}\chi^{\prime})$, we have

$$ $f(a_{1},\ldots,a_{n})=\iota_{\sum_{i=1}^{r}k_{\ell_{i}}+k^{\prime}}^{G} \quantity(a_{\ell_{1}}\otimes\cdots\otimes a_{\ell_{r}}\otimes c).$ (79) $$

Since $f$ and $\iota_{k_{\ell}+k^{\prime}}\quantity(\cdot)$ are $G$-equivariant, we have that for all $g\in G$ and $a\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V,\chi_{i})$,

$$ $\displaystyle\iota_{k_{\ell}+k^{\prime}}\quantity(a_{\ell_{1}}\otimes\cdots \otimes a_{\ell_{r}}\otimes c_{\ell})$ $\displaystyle=f(a_{1},\ldots,a_{n})$ $\displaystyle=f(g\cdot(g^{-1}\cdot a_{1}),\ldots,g\cdot(g^{-1}\cdot a_{n}))$ $\displaystyle=g\cdot f((g^{-1}\cdot a_{1}),\ldots,(g^{-1}\cdot a_{n}))$ $\displaystyle=g\cdot\iota_{k_{\ell}+k^{\prime}}\quantity(\quantity(g^{-1}\cdot a _{\ell_{1}})\otimes\cdots\otimes(g^{-1}\cdot a_{\ell_{r}})\otimes c_{\ell})$ $\displaystyle=\iota_{k_{\ell}+k^{\prime}}\quantity(a_{\ell_{1}}\otimes\cdots \otimes a_{\ell_{r}}\otimes(g\cdot c_{\ell}))~{}.$ $$

Finally, $G$ has a Zariski-dense compact subgroup $\mathop{U}(G)$. Hence, averaging over $\mathop{U}(G)$, we can substitute $c$ by the $\mathop{U}(G)$-isotropic tensor

$$ $\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}\cdot c$ $$

where the expectation is taken with respect the unique Haar probability measure of $\mathop{U}(G)$. But, since $\mathop{U}(G)$ is Zariski-dense in $G$ and the action rational, $\mathop{\mathbb{E}}_{\mathfrak{u}\in\mathop{U}(G)}\mathfrak{u}\cdot c$ is also $G$-isotropic, as we wanted to show.
∎

###### Proof of Lemma 4 .

Recall that, since $f$ in entire, we have, by Taylor’s theorem, that

$$ $f(a)=\sum_{r=0}^{\infty}\frac{1}{r!}\mathrm{D}_{0}^{r}f(a,\ldots,a)$ (80) $$

where $a=(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V,\chi_{i})$ and $\mathrm{D}_{0}^{k}f:\quantity(\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V,\chi_{i}))^
{k}\rightarrow\mathcal{T}_{k^{\prime}}(V,\chi^{\prime})$ is the $k$-multilinear map given by $k$th order partial derivatives of $f$ at 0 0. Now, write $a=a_{1}+\cdots+a_{n}$ as an abuse of notation for

$$ $a=(a_{1},0,\ldots,0)+\cdots+(0,\ldots,0,a_{n}).$ $$

We will further use this abuse of notation to write $a_{i}$ instead of $(0,\ldots,0,a_{i},0,\ldots,0)$. Now, since $\mathrm{D}_{0}^{k}f$ is $k$-multilinear and symmetric, we have that

$$ $\frac{1}{r!}\mathrm{D}_{0}^{r}f(a,\ldots,a)=\sum_{1\leq\ell_{1}\leq\cdots\leq \ell_{r}\leq n}\frac{1}{\alpha_{\ell_{1},\ldots,\ell_{r}}!}\mathrm{D}_{0}^{r}f (a_{\ell_{1}},\ldots,a_{\ell_{r}})$ (81) $$

where $\alpha_{\ell_{1},\ldots,\ell_{r}}\in\mathbb{N}^{r}$ is the vector given by $\quantity(\alpha_{\ell_{1},\ldots,\ell_{r}})_{i}:=\#\{j\mid\ell_{j}=i\}$ and $\alpha!:=\alpha_{1}!\cdots\alpha_{r}!$. Note that this terms appears when we reorder $(a_{\ell_{1}},\ldots,a_{\ell_{r}})$ so that the subindices are in order.

Summing up, we can write $f$ as (78), with

$$ $f_{\ell_{1},\ldots,\ell_{r}}(a_{1},\ldots,a_{n})=\frac{1}{\alpha_{\ell_{1}, \ldots,\ell_{r}}!}\mathrm{D}_{0}^{r}f(a_{\ell_{1}},\ldots,a_{\ell_{r}}),$ (82) $$

where this has the desired form by the universal property of tensor products. Now, observe that for $t_{1},\ldots,t_{n}\in\mathbb{C}$ and $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})$,

$$ $f_{\ell_{1},\ldots,\ell_{r}}(t_{1}a_{1},\ldots,t_{n}a_{n})=t^{\alpha_{\ell_{1} ,\ldots,\ell_{r}}}f_{\ell_{1},\ldots,\ell_{r}}(a_{1},\ldots,a_{n})$ (83) $$

where $t^{\alpha_{\ell_{1},\ldots,\ell_{r}}}:=t_{1}^{\alpha_{1}}\cdots t_{n}^{\alpha_
{n}}$. Hence, arguing as in Lemma 3, we have that for any $g\in G$ and all $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})$,

$$ $\sum_{r=0}^{\infty}\sum_{1\leq\ell_{1}\leq\cdots\leq\ell_{r}\leq n}t^{\alpha_{ \ell_{1},\ldots,\ell_{r}}}g\cdot f_{\ell_{1},\ldots,\ell_{r}}(a_{1},\ldots,a_{ n})\\ =\sum_{r=0}^{\infty}\sum_{1\leq\ell_{1}\leq\cdots\leq\ell_{r}\leq n}t^{\alpha_ {\ell_{1},\ldots,\ell_{r}}}f_{\ell_{1},\ldots,\ell_{r}}(g\cdot a_{1},\ldots,g \cdot a_{n}).$ (84) $$

Hence, by the uniqueness of coefficients for entire functions functions that are equal(^6^66The statement is qualitatively different from [, Chapter 1 §1 Proposition 5], but its proof is similar. We only need to use that a univariate entire function which vanishes in an infinite set with an accumulation point has to vanish everywhere.), we conclude that for any $g\in G$ and all $(a_{1},\ldots,a_{n})\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})$,

$$ $g\cdot f_{\ell_{1},\ldots,\ell_{r}}(a_{1},\ldots,a_{n})=f_{\ell_{1},\ldots, \ell_{r}}(g\cdot a_{1},\ldots,g\cdot a_{n}),$ (85) $$

and so that the $f_{\ell_{1},\ldots,\ell_{r}}$ are $G$-equivariant.
∎

###### Definition 13 .

###### Proposition 6 .

###### Theorem 4 .

###### Lemma 4 .

###### Remark 9 .

###### Proof of Theorem 4 .

###### Proof of Lemma 4 .

### F.3 Real equivariant tensor maps (and proof of Theorem 2 )

All the definitions in the previous subsection can be specialized to the real case. Hence we will have a self-paired real vector space $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$ on which a group $G$ acts (rationally) in a structure-preserving way. Then we get the family of (rational) $G$-modules:

$$ $\mathcal{T}_{k}(V,\chi):=(V^{\otimes k},\langle\,\cdot\,,\,\cdot\,\rangle)$ $$

where $\chi:G\to\mathbb{R}^{*}$ is a one-dimensional (rational) group-homomorphism of $G$. Together with this family, we have the $k$-contractions given by

$$ $\iota_{k}^{G}:\mathcal{T}_{2k+k^{\prime}}(V,\chi)\rightarrow\mathcal{T}_{k^{ \prime}}(V,\chi),$ (86) $$

which are $G$-equivariant linear maps. Then we get a very similar theorem to Theorem 4 from which Theorem 2 follows.

###### Theorem 5 .

Let $G\subset\mathop{GL}(V)$ be be either a compact or a complexly averagable real linear algebraic group acting rationally in a structure-preserving way on a self-paired vector space $(V,\langle\,\cdot\,,\,\cdot\,\rangle)$ and $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}\quantity(V,\chi_{i})\to\mathcal{T}_{k^{
\prime}}\quantity(V,\chi^{\prime})$ a $G$-equivariant entire function. Then we may write $f$ as follows:

$$ $f(a_{1},\ldots,a_{n})=\sum_{r=0}^{\infty}\,\sum_{1\leq\ell_{1}\leq\cdots\leq \ell_{r}\leq n}\iota_{k_{\ell_{1},\ldots,\ell_{r}}}^{G}\left(a_{\ell_{1}} \otimes\ldots\otimes a_{\ell_{r}}\otimes c_{\ell_{1},\ldots,\ell_{r}}\right)$ (87) $$

where $c_{\ell_{1},\ldots,\ell_{r}}\in\mathcal{T}_{k_{\ell_{1},\ldots,\ell_{r}}+k^{
\prime}}(\mathbb{R}^{d},\chi_{\ell_{1},\ldots,\ell_{r}}\,\chi^{\prime})$ is a $G$-isotropic tensor for $k_{\ell_{1},\ldots,\ell_{r}}:=\sum_{q=1}^{r}k_{\ell_{q}}$ and $\chi_{\ell_{1},\ldots,\ell_{r}}=\prod_{q=1}^{r}\chi_{\ell_{q}}$.

###### Proof of Theorem 2 .

This is just a particular case of Theorem 5 as both $\mathop{O}(s,d-s)$ and $\mathop{Sp}(d)$ are both real linear algebraic groups and their complexifications have a Zariski-dense compact subgroup.
∎

###### Proof of Theorem 5 .

When $G$ is compact, we can just repeat the proof for the orthogonal group. When $G$ is a linear algebraic group such that its complexification has a Zariski-dense compact subgroup, we can extend, using the same analytic expression evaluated in the complex tensors, the $G$-equivariant map $f:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V,\chi_{i})\rightarrow\mathcal{T}_{k^{
\prime}}(V,\chi^{\prime})$ to a complex $G^{\mathbb{C}}$-equivariant map $f_{\mathbb{C}}:\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V^{\mathbb{C}},\chi_{i})
\rightarrow\mathcal{T}_{k^{\prime}}(V^{\mathbb{C}},\chi^{\prime})$. The map becomes $G^{\mathbb{C}}$-equivariant, because $G$ is Zariski-dense inside $G_{\mathbb{C}}$ by Proposition 5.

But for $a\in\prod_{i=1}^{n}\mathcal{T}_{k_{i}}(V,\chi_{i})$, we have that

$$ $f(a)=\frac{1}{2}f^{\mathbb{C}}(a)+\frac{1}{2}\overline{f^{\mathbb{C}}(a)},$ (88) $$

by reality of the input and output. Hence, by linearity, we can change the non-necessarily real $c_{\ell_{1},\ldots,\ell_{r}}$ by the still $G$-isotropic and real $\frac{1}{2}c_{\ell_{1},\ldots,\ell_{r}}+\frac{1}{2}c_{\ell_{1},\ldots,\ell_{r}}$. The latter is $G$-isotropic, finishing the proof.
∎

###### Theorem 5 .

###### Proof of Theorem 2 .

###### Proof of Theorem 5 .

### F.4 Proof of Corollary 2

The following proposition is needed to prove the above corollary.

###### Proposition 7 .

[, Theorem 5.3.3]
Let $G$ be either $\mathop{O}(s,k-s)$ or $\mathop{Sp}(d)$ and $\langle\,\cdot\,,\,\cdot\,\rangle$ be the corresponding non-degenerate bilinear form fixed by the usual action of $G$ on $\mathbb{R}^{d}$, i.e., $\langle\,\cdot\,,\,\cdot\,\rangle_{s}$ for $\mathop{O}(s,k-s)$ and $\langle\,\cdot\,,\,\cdot\,\rangle_{\mathrm{symp}}$ for $Sp(d)$. The subspace of $G$-isotropic tensors in $\mathcal{T}_{k}(\mathbb{R}^{d},\chi_{0})$, where $\chi_{0}$ the constant map to $1$, consist only of the zero tensor if $k$ is odd, and it is of the form

$$ $\sum_{\sigma\in S_{k}}\alpha_{\sigma}\quantity(\theta_{G}^{\otimes k/2})^{\sigma}$ (89) $$

with the $\alpha_{\sigma}\in\mathbb{R}$ and $\theta_{G}\in(\mathbb{R}^{d})^{\otimes 2}$ the only tensor such that for all $v\in\mathbb{R}^{d}$, $\iota_{1}^{G}\quantity(v\otimes\theta_{G})=v$, if $k$ is even.

###### Remark 10 .

Recall that $\theta_{G}=\left[\mathbb{I}_{s,d-s}\right]_{i,j}$ if $G=\mathop{O}(s,d-s)$ and $\theta_{G}=\left[J_{d}\right]_{i,j}$ if $G=Sp(d)$.

###### Remark 11 .

Note that the above sum can be written with less summands using the methods of Appendix D.

###### Proof of Corollary 2 .

By Theorem 2, Proposition 7 and linearity, we can assume, without loss of generality, that

$$ $f(v_{1},\ldots,v_{n})=\iota_{r+k}\quantity(v_{\ell_{1}}\otimes\cdots\otimes v_ {\ell_{r}}\otimes\theta_{G}^{\frac{r+k^{\prime}}{2}})$ $$

with $1\leq\ell_{1}\leq\cdots\leq\ell_{r}\leq n$ and $r+k^{\prime}$ even.

Now, the proof is very similar to that of Corollary 1. However, note that now, we write

$$ $\theta=e_{i}\otimes\tilde{e}_{i},$ $$

where $\{e_{i}\mid i\in[d]\}$ and $\{\tilde{e}_{i}\mid i\in[d]\}$ are dual basis to each other, i.e., for all $i,j$, $\langle e_{i},\tilde{e}_{j}\rangle=\delta_{i,j}$. The reason we have to pick a couple of bases is that the bilinear form is not necessarily an inner product.

Now, the proof becomes the same as that of Corollary 1, but we have to be careful regarding the $e_{i}$ and the $\tilde{e}_{i}$. However, after making the pairings for contraction, we get four cases:

- 1.
$\langle v,e_{j}\rangle\langle w,\tilde{e}_{j}\rangle=\pm\langle v,w\rangle$, where the sign depends on whether $\langle\,\cdot\,,\,\cdot\,\rangle$ is symmetric or antisymmetric.
- 2.
$\langle v,\tilde{e}_{j}\rangle e_{j}=v$.
- 3.
$\langle v,e_{j}\rangle\tilde{e}_{j}=\pm v$, where the sign depends on whether $\langle\,\cdot\,,\,\cdot\,\rangle$ is symmetric or antisymmetric.
- 4.
$e_{j}\otimes\tilde{e}_{j}=\pm\theta$, where the sign depends on whether $\langle\,\cdot\,,\,\cdot\,\rangle$ is symmetric or antisymmetric, or $\sum_{j}\tilde{e}_{j}\otimes e_{j}=\theta_{G}$.

Now, putting these back together as we did in the proof of Corollary 1 gives the desired statement.
∎

###### Proposition 7 .

###### Remark 10 .

###### Remark 11 .

###### Proof of Corollary 2 .

## Appendix G Equivariance in sparse vector recovery

In this section, we show a sufficient condition for the $\mathop{O}(d)$-invariance of sparse vector estimation.
We start with a lemma on the equivariance of finding an eigenvector.

###### Lemma 5 .

Let $b$ be a ${2}_{(+)}$-tensor and let $g\in\mathop{O}(d)$.
If $u$ is an eigenvector for eigenvalue $\lambda$ of $M(g)\,b\,M(g)^{\top}$, then $M(g)^{\top}\,u$ is an eigenvector for eigenvalue $\lambda$ of $b$.

###### Proof.

Let $b$ be a ${2}_{(+)}$-tensor, let $g\in\mathop{O}(d)$, and let $\lambda,u$ be an eigenvalue, eigenvector pair of $M(g)\,b\,M(g)^{\top}$.

$$ $(M(g)\,b\,M(g)^{\top})\,u=\lambda u\Rightarrow b(M(g)^{\top}\,u)=\lambda(M(g)^ {\top}\,u)~{}.$ $$

Thus $M(g)^{\top}\,u$ is an eigenvector for eigenvalue $\lambda$ of $b$.
∎

###### Proposition 8 .

Let $S\in\mathbb{R}^{n\times d}$ with rows $a_{i}^{\top}\in\mathbb{R}^{d}$ so that $a_{i}$ are column vectors.
We define the action of $\mathop{O}(d)$ on $S$ for all $g\in\mathop{O}(d)$ as $S\,M(g)$, and therefore $M(g)^{\top}\,a_{i}$ for the rows.
Let $f:\mathbb{R}^{n\times d}\to\mathbb{R}^{n},h:\quantity(\mathbb{R}^{d})^{n}\to
\mathbb{R}^{d\times d}$ symmetric such that $f(S)=S\,\lambda_{\text{vec}}\quantity(h\quantity(a_{1},\ldots,a_{n}))$ where $\lambda_{\text{vec}}(\cdot)$ returns a normalized eigenvector for the top eigenvalue of the input symmetric matrix.
If $h$ is $\mathop{O}(d)$-equivariant, then $f$ is $\mathop{O}(d)$-invariant.

###### Proof.

Let $S,h,$ and $f$ be defined as above.
Suppose that $h$ is $\mathop{O}(d)$-equivariant.
Suppose

$$ $\lambda_{\text{vec}}\quantity(M(g)^{\top}\,h(a_{1},\ldots,a_{n})\,M(g))=u,$ $$

then by lemma 5, up to a sign flip, we have:

$$ $\lambda_{\text{vec}}\quantity(M(g)^{\top}\,h(a_{1},\ldots,a_{n})\,M(g))=u=M(g) ^{\top}\,M(g)\,u=M(g)^{\top}\,\lambda_{\text{vec}}\quantity(h\quantity(a_{1}, \ldots,a_{n}))$ (90) $$

Thus,

$$ $\displaystyle f(g\cdot S)$ $\displaystyle=(g\cdot S)\,\lambda_{\text{vec}}\quantity(h\quantity(g^{-1}\cdot a _{1},\ldots,g^{-1}\cdot a_{n}))$ $\displaystyle=(g\cdot S)\,\lambda_{\text{vec}}\quantity(g^{-1}\cdot h\quantity (a_{1},\ldots,a_{n}))$ $\displaystyle=S\,M(g)\,\lambda_{\text{vec}}\quantity(M(g)^{\top}\,h\quantity(a _{1},\ldots,a_{n})\,M(g))$ $\displaystyle=S\,M(g)\,M(g)^{\top}\,\lambda_{\text{vec}}\quantity(h\quantity(a _{1},\ldots,a_{n}))$ $\displaystyle=S\,\lambda_{\text{vec}}\quantity(h\quantity(a_{1},\ldots,a_{n}))$ $\displaystyle=f(S)~{}.$ $$

This completes the proof.
∎

###### Lemma 5 .

###### Proof.

###### Proposition 8 .

###### Proof.

## Appendix H Experimental Details

### H.1 Sparse Vector Samplings

We consider the following sampling procedures for $v_{0}$. All these procedures use the same sparsity parameter $\varepsilon\leq 1/3$.

#### Accept/Reject (A/R).

A random vector $v_{0}\sim\mathcal{N}(\mathbf{0}_{n},\mathbb{I}_{n})$ is sampled and normalized to unit $\ell_{2}$ length. We accept it if $\norm{v_{0}}_{4}^{4}\geq\frac{1}{\varepsilon n}$ and otherwise reject it. Note that the sparsity of $v_{0}$ is not explicitly imposed, but the 4-norm condition suggests that $v_{0}$ is approximately sparse.
The 4-norm condition of sparsity is used in [].

#### Bernoulli-Gaussian (BG)

This sampling procedure, considered in [], defines $v_{0}$ as

$$ $\begin{cases}[v_{0}]_{i}=0&\text{with probability }1-\varepsilon\\ [v_{0}]_{i}\sim\mathcal{N}\quantity(0,\frac{1}{\varepsilon n})&\text{with probability }\varepsilon.\end{cases}$ (91) $$

Note that under this sampling procedure $\mathbb{E}\norm{v_{0}}_{4}^{4}=\frac{3}{\varepsilon n}$.

#### Corrected Bernoulli-Gaussian (CBG)

We consider a modified version of the Bernoulli-Gaussian that replaces the values set to exactly 0 in the Bernoulli-Gaussian distribution with values sampled from a Gaussian with small variance. Under this distribution we have $\mathbb{E}\norm{v_{0}}_{2}=1$ and $\mathbb{E}\norm{v_{0}}_{4}^{4}=\frac{1}{\varepsilon n}$.

$$ $\begin{cases}[v_{0}]_{i}\sim\mathcal{N}\quantity(0,\frac{1-\varepsilon-\sqrt{ \frac{1}{3}(1-\varepsilon)(1-3\varepsilon)}}{(1-\varepsilon)n})&\text{with probability }1-\varepsilon\\ [v_{0}]_{i}\sim\mathcal{N}\quantity(0,\frac{\varepsilon+\sqrt{\frac{1}{3}(1- \varepsilon)(1-3\varepsilon)}}{\varepsilon n})&\text{with probability } \varepsilon.\end{cases}~{},$ (92) $$

#### Bernoulli-Rademacher (BR)

This sampling procedure, studied in [], defines $v_{0}$ as

$$ $[v_{0}]_{i}=\begin{cases}0&\text{with probability }1-\varepsilon\\ \frac{1}{\sqrt{\varepsilon n}}&\text{with probability }\frac{\varepsilon}{2}\\ \frac{-1}{\sqrt{\varepsilon n}}&\text{with probability }\frac{\varepsilon}{2}. \\ \end{cases}$ (93) $$

Under this distribution we have $\mathbb{E}\norm{v_{0}}_{2}=1$ and $\mathop{\mathbb{E}}\norm{v_{0}}_{4}^{4}\geq\frac{1}{\varepsilon n}$.

Since the BG, CBG, and BR distributions have $\mathop{\mathbb{E}}\norm{v_{0}}_{2}=1$, we also normalize these vectors to unit $\ell_{2}$ length after generating them.

###### Proposition 9 .

Let $v_{0}$ be a Bernoulli-Gaussian vector.
Then $\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]=1$ and $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\frac{3}{\varepsilon n}$.

###### Proof.

Let $\varepsilon\in(0,1]$ and let $v_{0}$ be a Bernoulli-Gaussian sparse vector.
Thus

$$ $\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]=\mathbb{E}\quantity[\sum_{i=1}^{n} \quantity[v_{0}]_{i}^{2}]=\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{ i}^{2}]~{}.$ (94) $$

Thus, we need to find the 2nd moment of an entry of $[v_{0}]_{i}$, which we will do by first calculating its moment generating function.
If $Z$ is a Bernoulli-Gaussian random variable, then $Z=XY$ where $X$ and $Y$ are random variables with $X\sim$ Bern$(\varepsilon)$ and $Y\sim\mathcal{N}\quantity(0,\frac{1}{\varepsilon n})$.
Then

$$ $\displaystyle\mathbb{E}\quantity[\exp{tXY}]$ $\displaystyle=\mathbb{E}\quantity[\mathbb{E}\quantity[\exp{tXY}|X]]$ $\displaystyle=\mathbb{E}\quantity[\exp{tXY}|X=0]P(X=0)+\mathbb{E}\quantity[ \exp{tXY}|X=1]P(X=1)$ $\displaystyle=\mathbb{E}\quantity[\exp{0}](1-\varepsilon)+\varepsilon\mathbb{E }\quantity[\exp{tY}]$ $\displaystyle=(1-\varepsilon)+\varepsilon\mathbb{E}\quantity[\exp{tY}]~{}.$ $$

Since $\mathbb{E}\quantity[\exp{tY}]$ is the moment generating function of $Y$, a Gaussian random variable, we can see that the 2nd moment of $Z$ is the 2nd moment of $Y$ multiplied by $\varepsilon$.
Then

$$ $\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{i}^{2}]=\sum_{i=1}^{n} \varepsilon\quantity(\frac{1}{\varepsilon n})=\sum_{i=1}^{n}\frac{1}{n}=1~{}.$ (95) $$

Now, for the sparsity condition, we have

$$ $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\sum_{i=1}^{n}\mathbb{E}\quantity[ \quantity[v_{0}]_{i}^{4}]=\sum_{i=1}^{n}\varepsilon\quantity(3\quantity(\frac{ 1}{\varepsilon n})^{2})=\sum_{i=1}^{n}\frac{3}{\varepsilon n^{2}}=\frac{3}{ \varepsilon n}~{}.$ (96) $$

This follows because our previous analysis shows that the 4th moment of an entry of $[v_{0}]_{i}$ is $3\sigma^{4}=3\quantity(\frac{1}{\varepsilon n})^{2}$.
This completes the proof.
∎

###### Proposition 10 .

Let $v_{0}$ be a Corrected Bernoulli-Gaussian vector.
Then $\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]=1$ and $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\frac{1}{\varepsilon n}$.

###### Proof.

Let $\varepsilon\in\left(0,\frac{1}{3}\right]$ and let $v_{0}\in\mathbb{R}^{n}$ be a Corrected Bernoulli-Gaussian sparse vector.
Thus

$$ $\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]=\mathbb{E}\quantity[\sum_{i=1}^{n} \quantity[v_{0}]_{i}^{2}]=\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{ i}^{2}]~{}.$ (97) $$

Thus, we need to find the 2nd moment of an entry of $[v_{0}]_{i}$, which we will do by first calculating its moment-generating function.
If $Z$ is a Corrected Bernoulli-Gaussian random variable, then $Z=XY+(1-X)W$ where $X,Y,$ and $W$ are random variables with $X\sim$ Bern$(\varepsilon),Y\sim\mathcal{N}\quantity(0,\frac{\varepsilon+q}{\varepsilon n})$, and $W\sim\mathcal{N}\quantity(0,\frac{1-\varepsilon-q}{n(1-\varepsilon)})$ where $q=\sqrt{\frac{1}{3}(1-\varepsilon)(1-3\varepsilon)}$.
Then

$$ $\displaystyle\mathbb{E}\quantity[\exp{t(XY+(1-X)W)}]$ $\displaystyle=\mathbb{E}\quantity[\mathbb{E}\quantity[\exp{t(XY+(1-X)W)}|X]]$ $\displaystyle=\mathbb{E}\quantity[\exp{tW}|X=0]P(X=0)+\mathbb{E}\quantity[\exp {tY}|X=1]P(X=1)$ $\displaystyle=(1-\varepsilon)\mathbb{E}\quantity[\exp{tW}]+\varepsilon\mathbb{ E}\quantity[\exp{tY}]$ $$

Since $\mathbb{E}\quantity[\exp{tW}]$ is the moment generating function of $W$ and $\mathbb{E}\quantity[\exp{tY}]$ is the moment generating function of $Y$, we can immediately get the moments of $Z$.
Then

$$ $\displaystyle\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{i}^{2}]$ $\displaystyle=\sum_{i=1}^{n}\varepsilon\quantity(\frac{\varepsilon+q}{n \varepsilon})+(1-\varepsilon)\quantity(\frac{1-\varepsilon-q}{n(1-\varepsilon)})$ $\displaystyle=\sum_{i=1}^{n}\frac{\varepsilon+q+1-\varepsilon-q}{n}$ $\displaystyle=1~{}.$ $$

For the sparsity condition, we use the same result above but now for the 4th moment

$$ $\displaystyle\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]$ $\displaystyle=\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{i}^{4}]$ $\displaystyle=\sum_{i=1}^{n}\varepsilon\quantity(3\quantity(\frac{\varepsilon+ q}{n\varepsilon})^{2})+(1-\varepsilon)\quantity(3\quantity(\frac{1-\varepsilon -q}{n(1-\varepsilon)})^{2})$ $\displaystyle=\sum_{i=1}^{n}3\varepsilon\quantity(\frac{\varepsilon^{2}+2 \varepsilon q+q^{2}}{n^{2}\varepsilon^{2}})+3(1-\varepsilon)\quantity(\frac{(1 -\varepsilon)^{2}-2(1-\varepsilon)q+q^{2}}{n^{2}(1-\varepsilon)^{2}})$ $\displaystyle=\sum_{i=1}^{n}\quantity(\frac{3\varepsilon^{2}(1-\varepsilon)+6 \varepsilon(1-\varepsilon)q+3(1-\varepsilon)q^{2}+3\varepsilon(1-\varepsilon)^ {2}-6\varepsilon(1-\varepsilon)q+3\varepsilon q^{2}}{n^{2}\varepsilon(1- \varepsilon)})$ $\displaystyle=\sum_{i=1}^{n}\quantity(\frac{3\varepsilon(1-\varepsilon)+3q^{2} }{n^{2}\varepsilon(1-\varepsilon)})$ $\displaystyle=\sum_{i=1}^{n}\quantity(\frac{3\varepsilon(1-\varepsilon)+3 \quantity(\frac{1}{3}(1-\varepsilon)(1-3\varepsilon))}{n^{2}\varepsilon(1- \varepsilon)})$ $\displaystyle=\sum_{i=1}^{n}\quantity(\frac{3\varepsilon+(1-3\varepsilon)}{n^{ 2}\varepsilon})$ $\displaystyle=\frac{1}{n\varepsilon}~{}.$ $$

This completes the proof.
∎

###### Proposition 11 .

Let $v_{0}$ be a Bernoulli-Rademacher vector.
Then $\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]=1$ and $\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]=\frac{1}{\varepsilon n}$.

###### Proof.

Let $\epsilon\in(0,1]$ and let $v_{0}$ be a Bernoulli-Rademacher sparse vector.
Thus

$$ $\displaystyle\mathbb{E}\quantity[\norm{v_{0}}_{2}^{2}]$ $\displaystyle=\mathbb{E}\quantity[\sum_{i=1}^{n}\quantity[v_{0}]_{i}^{2}]$ $\displaystyle=\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{i}^{2}]$ $\displaystyle=\sum_{i=1}^{n}(1-\epsilon)(0)^{2}+\frac{\epsilon}{2}\quantity( \frac{1}{\sqrt{\epsilon n}})^{2}+\frac{\epsilon}{2}\quantity(\frac{-1}{\sqrt{ \epsilon n}})^{2}$ $\displaystyle=\sum_{i=1}^{n}\frac{\epsilon}{\epsilon n}$ $\displaystyle=1~{}.$ $$

We also have

$$ $\displaystyle\mathbb{E}\quantity[\norm{v_{0}}_{4}^{4}]$ $\displaystyle=\mathbb{E}\quantity[\sum_{i=1}^{n}\quantity[v_{0}]_{i}^{4}]$ $\displaystyle=\sum_{i=1}^{n}\mathbb{E}\quantity[\quantity[v_{0}]_{i}^{4}]$ $\displaystyle=\sum_{i=1}^{n}(1-\epsilon)(0)^{4}+\frac{\epsilon}{2}\quantity( \frac{1}{\sqrt{\epsilon n}})^{4}+\frac{\epsilon}{2}\quantity(\frac{-1}{\sqrt{ \epsilon n}})^{4}$ $\displaystyle=\sum_{i=1}^{n}\frac{\epsilon}{\epsilon^{2}n^{2}}$ $\displaystyle=\frac{1}{\epsilon n}~{}.$ $$

This completes the proof.
∎

###### Proposition 9 .

###### Proof.

###### Proposition 10 .

###### Proof.

###### Proposition 11 .

###### Proof.

### H.2 Covariance and Noise Vectors

Suppose we want an $n\times n$ covariance matrix $\Sigma$ that is diagonal but not necessarily the identity matrix.
We generate $\Sigma$ by sampling the diagonal entries $[\Sigma]_{i,j}\sim\text{Unif}\quantity(\frac{1}{2},\frac{3}{2})$ and setting the off-diagonal entries to 0.
Instead, suppose $\Sigma$ is a random covariance matrix.
First, we sample an $n\times n$ matrix $M$ with entries $[M]_{i,j}\sim\mathcal{N}(0,1)$.
Then we set $\Sigma=M\,M^{\top}+0.00001\,\mathbb{I}_{n}$ which ensures that $\Sigma$ is symmetric and positive definite.
In all cases, we don’t worry about the scaling because the sampled vectors $v_{1},\ldots,v_{d-1}$ will be normalized to unit length.

Now suppose we have a set of vectors $v_{0},\ldots,v_{d-1}\in\mathbb{R}^{n}$, and we would like to get a random orthonormal basis of span$\quantity{v_{0},\ldots,v_{d-1}}$.
To do this, we form the matrix $B$ whose columns are the vectors $v_{0},\ldots,v_{d-1}$.
If we right multiply $B$ by a random orthogonal matrix and take the Q-R factorization, then $Q$ is a random orthonormal basis of $v_{0},\ldots,v_{d-1}$ as we show below.
We will add an assumption that the $v_{0},\ldots,v_{d-1}$ are linearly independent, which is reasonable given that $d\ll n$ and we are generating these vectors randomly.

###### Proposition 12 .

Let $n\geq d$, and let $B$ be the $n\times d$ matrix with $v_{0},\ldots,v_{d-1}$ as the columns.
Assume that $v_{0},\ldots,v_{d-1}$ are linearly independent, so rank $B=d$.
Let $O$ be a $d\times d$ orthogonal matrix and $Q\,R=B\,O$ be a Q-R factorization of $B\,O$.
Then the columns of $Q$ form an orthonormal basis of span$\quantity{v_{0},\ldots,v_{d-1}}$.

###### Proof.

The Q-R factorization gives us that the columns of $Q$ are orthonormal.
Thus we just have to show that $\text{span}\quantity{v_{0},\ldots,v_{d-1}}=\text{span}\quantity{Q_{0},\ldots,Q
_{d-1}}$

Let $a\in\text{span}\quantity{v_{0},\ldots,v_{d-1}}$, so for some $\alpha_{0},\ldots,\alpha_{d-1}$ we have $a=\alpha_{0}v_{0}+\ldots+\alpha_{d-1}v_{d-1}$.
Let $\alpha\in\mathbb{R}^{d}$ be the vector of these coefficients, and then we have,

$$ $a=B\,\alpha=B\,O\,O^{\top}\alpha=Q\,R\,O^{\top}\alpha=Q\hat{\alpha}~{}.$ (98) $$

Thus $\hat{\alpha}\in\mathbb{R}^{d}$ is a vector of coefficients, so $a\in\text{span}\quantity{Q_{0},\ldots,Q_{d-1}}$.
Therefore, $\text{span}\quantity{v_{0},\ldots,v_{d-1}}\subseteq\text{span}\quantity{Q_{0},
\ldots,Q_{d-1}}$.

Now let $b\in\text{span}\quantity{Q_{0},\ldots,Q_{d-1}}$, so for some $\beta_{0},\ldots,\beta_{d-1}$ we have $b=\beta_{0}Q_{0}+\ldots+\beta_{d-1}Q_{d-1}$.
Let $\beta\in\mathbb{R}^{d}$ be a vector of the coefficients $\beta_{0},\ldots,\beta_{d-1}$.
Now, since rank $B=d$, rank $B\,O=d$, so in the Q-R factorization, the upper triangular $R$ has positive diagonal entries, so it is invertible [[], Theorem 2.1.14].
Then we have,

$$ $b=Q\,\beta=Q\,R\,R^{-1}\,\beta=B\,O\,R^{-1}\,\beta=B\hat{\beta}~{}.$ (99) $$

Thus $\hat{\beta}\in\mathbb{R}^{d}$ is a vector of coefficients, so $b\in\text{span}\quantity{v_{0},\ldots,v_{d-1}}$.
Therefore, $\text{span}\quantity{Q_{0},\ldots,Q_{d-1}}\subseteq\text{span}\quantity{v_{0},
\ldots,v_{d-1}}$ which completes the proof.

∎

###### Proposition 12 .

###### Proof.

### H.3 Training Details

For training our models, we used $1-\langle\hat{v},v_{0}\rangle^{2}$ as the loss function.
The train dataset size was $5\,000$, and the validation and testing dataset sizes were both $500$.
We used the Adam optimizer [] with exponential decay of $0.999$ per epoch, batch size $100$, and we trained until the validation error had not improved for 20 epochs.
See Table 2 for the learning rate and number of parameters for each model.
We did a small exploration to find these hyper-parameters.
These hyper-parameters seemed to work well, but it is always possible that better ones could be found with more exploration.

**Table 2: Parameter count and learning rate for each model. Since all models have the same number of hidden layers of the same width, the difference in the number of parameters is driven by the different inputs to each model.**
|  | Baseline | SparseVectorHunter-Diagonal | SparseVectorHunter |
| --- | --- | --- | --- |
| parameter count | 99 087 | 58 981 | 1 331 131 |
| learning rate | 1e-3 | 5e-4 | 3e-4 |

The experiments were run on a single RTX 6000 Ada GPU and took 18 hours.

### H.4 Further Results

**Table 3: Train error comparison of different methods under different sampling schemes for $v_{0}$ and different covariances for $v_{1},\ldots,v_{d-1}$. The metric is $\langle v_{0},\hat{v}\rangle^{2}$, which ranges from 0 0 to $1$ with values closer to $1$, meaning that the vectors are closer. For each row, the best value is bolded. For these experiments, $n=100,d=5,\epsilon=0.25$, and the results were averaged over $5$ trials with the standard deviation given by $\pm 0.xxx$.**
| sampling | $\Sigma$ | SOS-I [] | SOS-II [] | BL | SVH-Diag | SVH |
| --- | --- | --- | --- | --- | --- | --- |
|  | Random | 0.610$\pm$0.011 | 0.610$\pm$0.011 | 0.647$\pm$0.177 | 0.768$\pm$0.045 | 0.966$\pm$0.001 |
| A/R | Diagonal | 0.444$\pm$0.012 | 0.444$\pm$0.012 | 0.561$\pm$0.262 | 0.698$\pm$0.034 | 0.755$\pm$0.057 |
|  | Identity | 0.611$\pm$0.002 | 0.611$\pm$0.002 | 0.494$\pm$0.285 | 0.622$\pm$0.201 | 0.647$\pm$0.289 |
|  | Random | 0.963$\pm$0.001 | 0.963$\pm$0.001 | 0.783$\pm$0.090 | 0.970$\pm$0.003 | 0.965$\pm$0.002 |
| BG | Diagonal | 0.949$\pm$0.002 | 0.949$\pm$0.002 | 0.672$\pm$0.260 | 0.974$\pm$0.004 | 0.775$\pm$0.078 |
|  | Identity | 0.963$\pm$0.000 | 0.963$\pm$0.000 | 0.681$\pm$0.241 | 0.966$\pm$0.004 | 0.999$\pm$0.001 |
|  | Random | 0.409$\pm$0.005 | 0.409$\pm$0.005 | 0.836$\pm$0.149 | 0.490$\pm$0.089 | 0.965$\pm$0.002 |
| CBG | Diagonal | 0.292$\pm$0.005 | 0.292$\pm$0.005 | 0.835$\pm$0.150 | 0.597$\pm$0.027 | 0.722$\pm$0.013 |
|  | Identity | 0.418$\pm$0.006 | 0.418$\pm$0.006 | 0.558$\pm$0.216 | 0.368$\pm$0.119 | 0.750$\pm$0.288 |
|  | Random | 0.523$\pm$0.006 | 0.523$\pm$0.006 | 0.975$\pm$0.005 | 0.669$\pm$0.150 | 0.970$\pm$0.002 |
| BR | Diagonal | 0.340$\pm$0.010 | 0.340$\pm$0.010 | 0.943$\pm$0.008 | 0.701$\pm$0.041 | 0.913$\pm$0.002 |
|  | Identity | 0.526$\pm$0.005 | 0.526$\pm$0.005 | 0.949$\pm$0.006 | 0.570$\pm$0.199 | 0.898$\pm$0.001 |

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 5
presentation: 2
questions: See weakness.
soundness: 2
strengths: They construct a equivariant function $h$.
summary: This work characterizes equivariant polynomial functions from tuples of tensor inputs to tensor outputs. The goal behind these characterizations is to define equivariant machine learning models. In particular, they focus on the sparse vector estimation problem. They try to recover a sparse vector from the given an orthonormal basis of subspace spanned by $d$ vectors, where one is the sparse vector to be recovered and the other $d-1$ are just vectors. The recovered sparse vector is stated in (25) and the contributed is how to construct $h$.
weaknesses: There are some question you need to solve:

1 Are there some applications about your proposed problem to recover a sparse vector?

2. The representation of $h$ is only related to matrices, but not a complex tensor. Your definitions and analysis are all based on tensors. 

3. Can you give a details how to get (28) from Corollary 1?

4. Why you set $h$ to be a equivariant function? What is the advantages?

5. In the numerical experiments about mnist, do you get the similar results if you choose $v_1,\cdots, v_{d-1}$ to be some other vectors which is not so related to the sparse vector?

6. How to get the orthonormal basis for the spanned subspace? Do you get the similar results if you choose different orthonormal basis?

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 4
questions: 1. Can you provide a bit more insight into what are the requirements for the training set for your method to be able to train the neural networks defining coefficients in the parametrization of h in Eq 28? Do you need to assume that all training samples have the same planted sparse vector $v_1$? Or is it sufficient to assume that all such vectors $v_1$ are coming from some distribution with nice properties?
2. How many training samples do you anticipate needing to recover $n$-dimensional planted sparse vector? 
3. Are you aware of any immediate applications of the provided characterizations for the indefinite orthogonal group O(s, k-s) or the symplectic group Sp(d)?
soundness: 3
strengths: The characterization of equivariant polynomial functions studied in this paper is demonstrated to have applications to a planted sparse vector recovery problem which has several practical applications and received a lot of attention over the past decade. In this problem, one is given a linear space $L$ defined by a sparse planted vector $v_1$ and randomly selected complement basis $v_2, ... v_n$. The goal is to recover vector $v_1$ from $L$. The Authors observe that the function $h: L \rightarrow v_1$ is equivariant so can be parametrized using the main characterization proven in this paper and they learn parameters of h by training NN over the training dataset.
I think that this is a new interesting approach to the sparse vector recovery problem.

The proposed characterizations of equivariant polynomial functions may find applications in other areas and may be of its own interest.
summary: This paper studies polynomial functions from tensor spaces to tensor spaces that are preserved by the action of the Orthogonal group O(d), the indefinite orthogonal group O(s, k-s) or the symplectic group Sp(d). The authors provide a characterization of such polynomial functions in the form of a linear combination of "elementary functions".

As a main application of such result authors propose an algorithm for planted vector recovery, dictionary learning, and experimentally demonstrated that the proposed algorithm outperforms earlier proposed Sum-of-Squares based methods.

Study of such polynomial function is also tangentially motivated by physics applications.
weaknesses: If I understand the proposed approach to the sparse vector recovery problem, for the approach to work one actually need to observe many data samples to be able to train neural networks that define coefficients for the unknown polynomial $h: L \rightarrow v_1$. This may be a strong assumption in many applications and is different from SOS-based methods that can recover $v_1$ from observing only one subspace L and does not require to go through the learning process. 

The proof of the main theorem follows standard steps for this sort of problems: problem is easily reduced to homogenous degree r monomials and for homogeneous degree monomials the characterization is obtained by using a somewhat standard group averaging technique. In this sense, the proof of the main result is somewhat "standard" for the literature.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 2
questions: • The statement of Theorem 1 introduces a complex expression involving
linear combinations over isotropic tensors. Could the authors provide more
intuitive explanations or mathematical nature of this theorem?

• The authors state that parameterizing all permutation-invariant polyno-
mial functions may be as challenging as solving the graph isomorphism
problem. Could the authors provide an estimate of the computational
complexity or approximate methods for tackling this problem? can we
push this into high-dimensional settings?

• While MLPs are popular in approximating the polynomial functions, is
there a risk that they might not fully capture the necessary polynomial
structures or equivariance properties?

• The learned SVH models perform better when stringent data assumptions
are not met. Could the authors elaborate on why their models are more
robust in these scenarios? Please provide valuable insights.

• The paper focuses on equivariance. Could you derive some examples for
other groups, such as unitary groups or affine transformations?
soundness: 4
strengths: ## Originality
The paper presents a novel and significant advancement in the field of equiv-
ariant machine learning. Additionally, it uniquely incorporates the indefinite
orthogonal group O(s,k− s) and the symplectic group Sp(d), which are funda-
mental in physics and other scientific domains but have been less explored in the
context of physics informed machine learning. The application of these theo-
retical developments to the sparse vector estimation problem further showcases
originality by demonstrating how algorithms can outperform state-of-the-art
methods in regimes not previously addressed.

## Quality
The paper is of high quality, offering rigorous mathematical formulations and
proofs that underpin the proposed methods. The experiments are well-designed,
and the empirical results convincingly demonstrate the effectiveness.

## Significance
The significance of the work is substantial. By providing explicit parameteriza-
tions for equivariant functions of tensor inputs and outputs, the paper equips
researchers and practitioners with powerful tools. The successful application to
sparse vector es
summary: This paper develop a generic framework for defining functions that are equiv-
ariant under the action of classical Lie groups acting diagonally on tensors.
The groups considered include the orthogonal group O(d), the indefinite orthogonal group O(s,k− s), and the symplectic group Sp(d) and other general group actions. The main theoretical contribution is a characterization of
O(d)-equivariant polynomial functions mapping multiple tensor inputs to tensor outputs. The authors prove that any such functions can be expressed as linear
combination of tensor products of the inputs with O(d) isotropic tensors. An
important result is Theorem 1, which provides an explicit parameterization
of O(d)-equivariant polynomial functions. The authors also present a practical
corollary (Corollary 1) for the case where the inputs are vectors and the out-
puts are vector spaces, showing that the equivariant functions can be written
as linear combinations of basis elements formed by permutations of the input
vectors. Furthermore, the author also present a generalization form of general
tensors in Theorem 2 and Corollary 2.

As a proof of concept, They consider the challenge of recovering a planted
sparse vector from a set of vectors forming an orthonormal basis of a sub-
space. By designing a machine learning model that learns an equivariant 2-
tensor (which is the covariance matrix) from data, they use the top eigenvector
of this tensor as an estimator for the sparse vector. The numerical experiments
demonstrate that the learned algorithms outperform state-of-the-art methods.
The models adapt effectively to various noise structures and data sampling
methods.

In physics, Lorentz group O(1,3) is a special case of the equivariant group.
Particularly in general relativity, tensors are used to describe physical quantities such as the curvature of spacetime, energy-momentum distributions. The
authors’ work generally present one of the proof for how to comprehend this
structure in the regime of mathematical tensor products. they also provide a
framework for building physics informed machine learning models that inherently respect Lorentz symmetry and applying for advanced physics studies.
weaknesses: ## Limited Scope of Experiments
One of the main weaknesses of the paper is the limited scope of the experimental
evaluation. The experiments are primarily focused on the sparse vector estima-
tion problem, which, while important, represents a rather narrow application
domain. The method should have broader applications, such as in physics and
general relativity, but these areas are not sufficiently discussed or explored.

## Clarity
The paper is difficult to follow due to disorganized notation and unclear variable
definitions. The use of coordinates is somewhat messy, which makes the math-
ematical developments hard to track. Variables are often introduced without
proper explanation or context, causing confusion. For example:

• In Definition 4, the indices need more explanation.

• In Theorem 1, how each tensor alk contracts with certain indices (dimen-
sions) of cl1 ,l2 ,...,lr should be explained more clearly.

• In Example 1, there should be more explanation of why only the generic
elements of the G4 group are used while others are contracted.

• In Lemma 1, the meaning and constraints of ασ need clarification.
Moreover, the progression from theoretical concepts to experimental appli-
cations lacks smoothness. The presentation could be improved by organizing
notation more systematically and clearly defining all variables.

## Comparative Analysis
There are other contemporary techniques for sparse vector recovery and tensor
analysis that are not considered. The lack of comparison with a wider array
of methods makes it difficult to fully assess the advantages of the proposed
approach.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 1
questions: Please refer to each weakness and suggestion section to help improve the readability and applicability of the work.
soundness: 3
strengths: - To the best of my knowledge, this paper introduces a new approach to equivariant tensor functions, expanding to cases with mixed symmetry properties through the $k(p)$-tensor space concept.

- The paper provides a well-grounded method with precise definitions, such as outer product and $k$-contraction, supported by theoretical proofs.

- Extending Haar averaging to non-compact groups (such as the indefinite orthogonal group $O(s, d-s)$ and symplectic group $Sp(d)$) broadens the versatility.
summary: This paper introduces a framework for constructing equivariant tensor functions to facilitate sparse vector recovery in distributions with specific symmetry properties, such as those invariant under orthogonal transformations. The key concepts introduced include the $ k(p)$-tensor space, which captures parity characteristics in tensor components, and the construction of equivariant polynomial functions that remain consistent under orthogonal group actions. The framework also incorporates tensor operations such as outer product and $ k $-contraction to enable flexible tensor combinations while preserving equivariance. Furthermore, the paper extends Haar averaging to non-compact groups, allowing the model to maintain equivariance in settings with broader symmetry requirements, like the indefinite orthogonal group.
weaknesses: 1. **Lack of Clear Theoretical Motivation and Practical Relevance**

   - **W1.1:** The paper focuses heavily on mathematical formulas and definitions but lacks intuitive explanations to clarify the need for equivariant tensor functions and their practical motivations.
   - **Suggestion**: Consider adding a high-level overview section that explains why equivariance is essential in certain applications and provides examples that demonstrate the demand for equivariant tensor functions in real-world scenarios.

   - **W1.2:** Key theoretical challenges and the novel aspects of the proposed method are not thoroughly discussed, leaving readers uncertain about the primary obstacles and contributions within the framework.
   - **Suggestion**: Consider adding a dedicated “Contributions” section that explicitly outlines how this method differs from existing approaches, helping readers understand the unique contributions of the framework.

   - **W1.3:** The paper does not clearly explain the necessity of "learning equivariant tensor functions," lacking specific application scenarios that showcase the unique benefits and suitability of these functions. It remains unclear why certain types of tensors in applications require equivariance.
   - **Suggestion**: Include examples of practical applications where specific types of tensors need to be equivariant and clarify how these scenarios validate the advantages of using equivariant tensor functions.

2. **Limitations in Sparse Vector Recovery Application**

   - **W2.1:** The paper centers its applications on sparse vector recovery, a problem that is primarily theoretical and rooted in computer science, with limited overlap with current mainstream machine learning applications, such as computer vision or natural language processing.
   - **Suggestion**: Discuss the potential connections between sparse vector recovery and mainstream machine learning applications, such as compressed sensing, feature selection, or dimensionality reduction in deep learning, to enhance the method’s appeal.

   - **W2.2:** The paper does not demonstrate if or how sparse vector recovery can extend to practical uses in deep learning or other prominent areas within machine learning, lacking case studies or examples of its effectiveness in real-world tasks.
   - **Suggestion**: Consider adding relevant cases or discussions on how the method could be integrated into neural network architectures or applied to tasks such as network pruning, compression, or efficient inference, to illustrate its practicality.

   - **W2.3:** The real-world significance of the proposed method is unclear, potentially making it seem disconnected from practical contributions to machine learning, which could limit its appeal to a broader audience.
   - **Suggestion**: To increase its appeal, the authors could discuss the broader implications of their work, such as how advances in equivariant functions might contribute to more efficient or interpretable machine learning models over the long term.

3. **Limited Relevance to Machine Learning**

   - **W3.1:** While the method shows mathematical novelty, its applications in machine learning are not well-established, which may restrict its potential readership. Machine learning researchers tend to focus on methods with clear, practical applicability and accessibility.
   - **Suggestion**: Strengthen the connection to machine learning demands by discussing how equivariant tensor functions could enhance model interpretability or efficiency, demonstrating its contributions to machine learning research.

   - **W3.2:** The paper extensively uses group theory terms and concepts, such as orthogonal groups and indefinite orthogonal groups, which may be unfamiliar and challenging for machine learning readers without a strong mathematics background.
   - **Suggestion**: Consider including a brief primer on the relevant group theory concepts or offering more intuitive explanations for these mathematical objects. Providing references to introductory resources may also help readers better understand these terms.


**Additional Suggestions:**

- **Add Visual Aids and Case Studies**: Introduce diagrams in appropriate sections to help readers visually understand the basic principles of the method, or add case studies to illustrate its practical applications. This could help engage a wider range of machine learning researchers.