Memory capacity of two layer neural networks with smooth activations
Determining the memory capacity of two layer neural networks with $m$ hidden
neurons and input dimension $d$ (i.e., $md+2m$ total trainable parameters),
which refers to the largest size of general data the network can memorize, is a
fundamental machine learning question. For activations that are real analytic
at a point and, if restricting to a polynomial there, have sufficiently high
degree, we establish a lower bound of $\lfloor md/2\rfloor$ and optimality up
to a factor of approximately $2$. All practical activations, such as sigmoids,
Heaviside, and the rectified linear unit (ReLU), are real analytic at a point.
Furthermore, the degree condition is mild, requiring, for example, that
$\binom{k+d-1}{d-1}\ge n$ if the activation is $x^k$. Analogous prior results
were limited to Heaviside and ReLU activations -- our result covers almost
everything else. In order to analyze general activations, we derive the precise
generic rank of the network's Jacobian, which can be written in terms of
Hadamard powers and the Khatri-Rao product. Our analysis extends classical
linear algebraic facts about the rank of Hadamard powers. Overall, our approach
differs from prior works on memory capacity and holds promise for extending to
deeper models and other architectures.
Liam Madden, Christos Thrampoulidis
# Memory capacity of two layer neural networks

###### Abstract

Determining the memory capacity of two layer neural networks with \(m\) hidden neurons and input dimension \(d\) (i.e., \(md+m\) total trainable parameters), which refers to the largest size of general data the network can memorize, is a fundamental machine learning question. For polynomial activations of sufficiently high degree, such as \(x^{k}\) with \(\binom{d+k}{d-1}\geq n\), and real analytic activations, such as sigmoids and smoothed rectified linear units (smoothed ReLUs), we establish a lower bound of \(\lfloor md/2\rfloor\) and optimality up to a factor of approximately \(2\). Analogous prior results were limited to Heaviside and ReLU activations. In order to analyze general real analytic activations, we derive the precise generic rank of the network's Jacobian, which can be written in terms of Hadamard powers and the Khatri-Rao product. Our analysis extends classical linear algebraic facts about the rank of Hadamard powers. Overall, our approach differs from prior works on memory capacity and holds promise for extending to deeper models and other architectures.

**Keywords: Neural networks, Memory capacity, Hadamard powers, Khatri-Rao products, Kruskal rank**

**MSC Classification: 15A03, 26B10**

## 1 Introduction

Machine learning models, such as neural networks, have become increasingly adept at performing tasks, such as image classification and natural language processing, but
also increasingly opaque in terms of their underlying mechanisms. And the intuition that experts employ to construct such models, while useful now, may be based on an erroneous understanding of those underlying mechanisms, much as a field specialist in an engineering firm may come up with explanations that are useful in the field but contradict the underlying physics. It is important that we understand the underlying mechanisms in machine learning so that we can mitigate inherent biases and avoid potential failures.

Neural networks, despite their simplicity, are still not fully understood. From the perspective of traditional optimization, they should be extremely hard to train due to the nonconvexity of their associated training objectives. However, even simple algorithms like stochastic gradient descent are able to find global minima to these training objectives. At the heart of this phenomena is the fact that neural networks are expressive enough to interpolate data sets. But, from the perspective of traditional statistical learning theory then, they should not generalize well to unseen data. Nevertheless, they do generalize well to unseen data, interpolating without merely memorizing the seen data. Thus, the expressive power of neural networks is integral to both the convergence and generalization properties of neural networks, and so we take it as the theme of the present paper.

The output of the two layer neural network model with data matrix \(X\in\mathbb{R}^{d\times n}\), first layer weight matrix \(W\in\mathbb{R}^{d\times m}\), second layer weight vector \(v\in\mathbb{R}^{m}\), and activation function \(\psi\) is

\[h(W,v,X)=\psi\left(X^{T}W\right)v\in\mathbb{R}^{n},\]

where \(\psi\) is applied coordinate-wise. The columns of \(W\) correspond to \(m\) hidden neurons, \(\psi(W^{T}X)\) embeds the data into \(\mathbb{R}^{m}\), \(m\) is the embedding dimension, and \(v\) corresponds to a linear model applied to the embedded data. For fixed \(m\), the memory capacity of \(h\) is the largest \(n\) such that \(h(\cdot,\cdot,X)\) is surjective for generic \(X\)[7]. By "generic" we mean that \(X\) comes from a set whose complement is contained in the zero set of a non-identically zero real analytic function; in particular, this implies that the complement is measure zero and closed. Given \(n\), we are interested in how large \(m\) has to be in order for the memory capacity of \(h\) to be at least \(n\). We consider general real analytic activation functions, which includes polynomials; sigmoids, such as the logistic function, \(\tanh\), and \(\arctan\); and smoothed rectified linear units, such as GELU.

In Theorem 11, we show that for any data matrix and any machine learning model that consists of a linear model/layer applied to a smooth embedding, if the rank of the Jacobian is \(n\) at any point, then the "doubled model" with twice the number of parameters is surjective. The doubled model may or may not be in the model class, but for neural networks, including deep networks, we show that it is.

Thus, the question of memory capacity reduces to a question of Jacobian rank. In the case of a two layer neural network, the transpose of the Jacobian of \(h(\mathrm{vec}^{-1}(\cdot),v,X):\mathbb{R}^{md}\rightarrow\mathbb{R}^{n}\), where \(\mathrm{vec}^{-1}\) denotes column-wise reshaping, can be written \(\Phi=\mathrm{diag}(v)\psi^{\prime}\left(W^{T}X\right)\odot X\in\mathbb{R}^{md \times n}\), where \(\odot\) is the Khatri-Rao product [16, Sec. VI.A]. Given \(X\), we just need a single \((W,v)\) such that \(\mathrm{rank}(\Phi)=n\) in order to get surjectivity for \(h(\cdot,\cdot,X)\) with embedding dimension \(2m\) instead of \(m\). The main contribution of the present paper is proving that \(\mathrm{rank}(\Phi)\) actually equals \(\min\{md,n\}\)
for generic \((W,v,X)\). We then combine this with Theorem 11 to prove the following memory capacity result, and show that the result is tight up to a factor of \(\approx 2\):

* Theorem 12: If \(md\geq 2n\) and \(m\) is even, then \(h(\cdot,\cdot,X)\) is surjective for generic \(X\).
* Theorem 13: If \(m(d+1)<n\), then, for all \(X\), \(h(\cdot,\cdot,X)\) is not surjective.

As mentioned, the main work of the present paper is in showing that \(\Phi\) is generically full rank. We abstract this to the problem of showing that the matrix \(B^{T}\odot\phi(AB^{T})\) is generically full Kruskal rank. Specifically, consider \(A\in\mathbb{R}^{m\times d}\) and \(B\in\mathbb{R}^{n\times d}\) and let \((c_{k})\subset\mathbb{R}\) and \(\phi:\mathbb{R}\rightarrow\mathbb{R}\) be non-polynomial real analytic. Then we prove the following results, where the exponent \((k)\) denotes the \(k\)th Hadamard power:

* Theorem 3: All order \(\min\{m,n,\binom{k+d-1}{k}\}\) or less minors of \((AB^{T})^{(k)}\) are nonzero for generic \((A,B)\).
* Theorem 4: All order \[\min\left\{m,n,\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\binom{k+d-1}{k }\right\}\text{ or less minors of }\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\] are nonzero for generic \((A,B)\).
* Theorem 6: \(B^{T}\odot(AB^{T})^{(k)}\) has Kruskal rank \(\min\{md,n,\binom{k+d}{k+1}\}\) for generic \((A,B)\).
* Theorem 7: \[B^{T}\odot\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\text{ has Kruskal rank }\min\left\{md,n,\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\binom{k+d }{k+1}\right\}\] for generic \((A,B)\).
* Theorem 8: All order \(\min\{m,n\}\) or less minors of \(\phi(AB^{T})\) are nonzero for generic \((A,B)\).
* Theorem 9: \(B^{T}\odot\phi(AB^{T})\) has Kruskal rank \(\min\{md,n\}\) for generic \((A,B)\).
It may be helpful to see the relevant objects in the above diagram, which has arrows indicating particular proof extensions.

Theorems 6, 7, and 9 are our main contributions (in addition to Theorems 11-13). Theorem 3 was proved in [8] but we give a novel proof that allows us to extend to the other results. The second proof extension, shown in the diagram by the arrows labeled "2," follows almost immediately thanks to the structure of our proof. The first proof extension, shown in the diagram by the arrows labeled "1," is the most involved and requires a novel decomposition of \(B^{T}\odot(AB^{T})^{(k)}\). The third proof extension, shown in the diagram by the arrows labeled "3," is not difficult but subtle and involves reducing to the polynomial setting using Taylor's theorem.

### Related work

Recall that the transpose of the Jacobian of the two layer neural network model, with respect to the hidden layer, is \(\Phi=\operatorname{diag}(v)\psi^{\prime}\left(W^{T}X\right)\odot X\). If \(\operatorname{rank}(\Phi)=n\) at \((W_{0},v_{0},X)\), then, given a label vector \(y\in\mathbb{R}^{n}\), we can solve for \(U_{0}\in\mathbb{R}^{d\times m}\) in the linear equation

\[\begin{split} y&=\left(\operatorname{diag}(v_{0}) \psi^{\prime}\left(W_{0}^{T}X\right)\odot X\right)^{T}\operatorname{vec}(U_{0 })\\ \text{and use }&=\lim_{\epsilon\to 0}\;\psi\left(X^{T}[W_{0}+ \epsilon U_{0}\;W_{0}]\right)[v_{0}/\epsilon;-v_{0}/\epsilon]\end{split} \tag{1}\]

to show that the image of \(h(\cdot,\cdot,X)\) with embedding dimension \(2m\) is dense [6, Prop. 4]. Bubeck et al [6] used this trick to show that if \(\psi\) is ReLU (i.e. \(\psi(x)=\max\{0,x\}\)), then \(m\geq 4\lceil n/d\rceil\) is sufficient to guarantee that, for all \(X\) in general linear position, \(h(\cdot,\cdot,X)\) is surjective (since in this case we don't have to take \(\epsilon\) all the way to zero). Baum [4] had already proved a similar result if \(\psi\) is the Heaviside function (i.e. \(\psi(x)=\mathbb{I}\left\{x\geq 0\right\}\)) and the image of \(h(\cdot,\cdot,X)\) only needs to contain \(\{0,1\}^{n}\), and Yun et al [20] had extended this to ReLU.

Recently, Zhang et al [21] used the Inverse Function Theorem to generalize Eq. (1), demonstrating that if \(\psi\) is smooth and if \(\operatorname{rank}(\Phi)=n\) at some \((W_{0},v_{0},X)\), then \(h(\cdot,\cdot,X)\) with embedding dimension \(2m\) is surjective. Their approach inspired our Theorem 11, which further extends their result to encompass a broader range of machine learning models.

Regarding the conditions that ensure \(\operatorname{rank}(\Phi)=n\) for smooth activations, it is shown in Corollary 3.1 of [15] that, given \(n\in\mathbb{N}\), there exists \(C(n)>0\) such that \(md/\log^{C(n)}(md)\geq n\) is sufficient to guarantee that, with high probability over random \(X\), \(h(\cdot,\cdot,X)\) is surjective. Ignoring the dependence of \(C(n)\) on \(n\), this bound has extra log factors and only holds for \(X\) with high probability. Thus, our results represent an improvement in both these aspects. To better understand the basis for these improvements, it's helpful to delve into the origins of their result, which is actually a corollary of an intermediate step in the proof of a convergence result, as elaborated below. In order to prove that \(\operatorname{rank}(\Phi)=n\), they show that the smallest eigenvalue of \(\Phi^{T}\Phi\) is positive by bounding the minimum eigenvalue of \(\mathbb{E}_{W,v}[\Phi^{T}\Phi]\) away from zero and applying the matrix Chernoff inequality. For example, letting \(\lambda\) denote \(\lambda_{\min}(\mathbb{E}_{W,v}[\Phi^{T}\Phi/m])\)
then applying Remark 5.3 of [18] gives the following: if

\[m\geq\frac{2\|X\|_{2}^{2}\log(n/\delta)}{\lambda}\]

then, with probability greater than \(1-\delta\),

\[\lambda_{\min}(\Phi^{T}\Phi/m)\geq\lambda-\frac{\|X\|_{2}}{\sqrt{m}}\sqrt{2 \lambda\log(n/\delta)}.\]

This bound on \(\lambda_{\min}(\Phi^{T}\Phi/m)\) was first proved in [16], a paper which, along with [17], tightened the analysis of the landmark paper [9]. Subsequently, [15] established a lower bound on \(\lambda\), which aligns with empirical investigations outlined in [19]. But, while bounding the distance of \(\Phi^{T}\Phi\) from \(\mathbb{E}_{W,v}[\Phi^{T}\Phi]\) ends up being useful for the convergence analysis, it is unnatural for memory capacity analysis: there is no reason why \(\Phi^{T}\Phi\) needs to be close to \(\mathbb{E}_{W,v}[\Phi^{T}\Phi]\) in order for \(\operatorname{rank}(\Phi)=n\), since, as we show, \(\operatorname{rank}(\Phi)=n\) generically.

For the rank results without the Khatri-Rao product, while [8] recently derived the generic rank of \((AB^{T})^{(k)}\), it seems the generic rank of \(\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\) has actually been known for some time, though it is difficult to find precise statements of equality rather than upper bounds. For example, Lemma 2.3 of [1] proved in four lines that the rank of \((AB^{T})^{(k)}\) and \(\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\) are bounded by \(\binom{k+d-1}{k}\) and \(\binom{K+d}{K}\) respectively. Lemma 4.4 of [3] proved the latter bound, calling it a "standard linear algebra fact." Moreover, if we slightly modify his proof by including the coefficients \(\mathbb{I}\left\{\alpha_{m}\neq 0\right\}\) in the final expression, then a little more work proves our Theorem 4. We include this alternative proof in Appendix B in order to explain why it cannot be extended to Khatri-Rao products.

Finally, for the rank results involving the Khatri-Rao product, the only previous result, other than corollaries of convergence results, was Lemma E.1 of [21], which corresponds to our Theorem 9. Upon a careful examination of their proof, we encountered inconsistencies that appeared unresolvable. Only after the initial release of our preprint, a correspondence with the authors of [21] revealed that these inconsistencies stemmed from typos and convoluted presentation of their methodology. During this discussion, we realized that their idea behind their proof is actually correct and can, in fact, be presented in a rather transparent manner, which we do in Appendix A for completeness. Overall, our proof technique is independent and entirely distinct from theirs. We believe our approach provides a more comprehensive and in-depth understanding of the matter since it computes the generic rank of \(B^{T}\odot\phi(AB^{T})\) for all real analytic \(\phi\), including polynomials. The proof in [21] can be extended to polynomials as well, as we show in Appendix A, but it provides a loose lower bound on the generic rank rather than giving the precise generic rank. In particular, it can only be used to justify using polynomials with an extremely large number of nonzero coefficients.
### Organization

Our paper is organized as follows. In Section 2, we go through the necessary preliminaries. In Section 3, we present our main proof idea and prove Theorems 3 and 4. In Section 4, we prove Theorems 6-9. In Section 5, we prove Theorems 11 and 12. In Section 6, we conclude. In the appendix we go into further details about some of the related work.

## 2 Preliminaries

In this section we discuss the necessary preliminaries. In Section 2.1 we define the different notions of rank and discuss the linear algebra tools that we will employ. In Section 2.2, we discuss some notions from the theory of analytic functions of several variables. In Section 2.3, we discuss some basic facts about weak compositions, which we will index some of our matrices by.

Throughout the present paper, the following notation will be used: \(\mathbb{Z}_{+}\) denotes \(\mathbb{N}\cup\{0\}\), \([n]\) denotes \(\{1,2,\ldots,n\}\), \(\binom{A}{n}\) denotes \(\{B\subset A\mid|B|=n\}\), \(\circ\) denotes the Hadamard product (and function composition), \(\odot\) denotes the Khatri-Rao product, the exponent \((k)\) denotes the \(k\)th Hadamard power, and "Hadamard function" refers to univariate functions applied coordinate-wise.

Let \(A\in\mathbb{R}^{m\times n}\). We use \(a_{i}\) to denote the \(i\)th column of \(A\) and \(a_{i,j}\) to denote the \((i,j)\)th entry of \(A\). Given \(I\subset[m]\), and \(J\subset[n]\), we denote the submatrix formed from the rows \(I\) and columns \(J\) of \(A\) as \(A_{I,J}\). We use \(\mathfrak{S}_{n}\) to denote the symmetric group of degree \(n\). Note that we can write \(\mathfrak{S}_{n}=\{\sigma:[n]\hookrightarrow[n]\}\). More generally, consider a matrix \(A\) with rows indexed by a set \(I\) with \(|I|=m\) and columns indexed by a set \(J\) with \(|J|=n\). We order \(I\) and \(J\) lexicographically if they consist of pairs, i.e. the first entry in the pair changes slower than the second entry.

Finally, we say a property holds for generic \(x\) if it holds for all \(x\in\mathbb{R}^{n}\) except on the zero set of a non-identically zero real analytic function.

### Rank of a matrix

Let \(A\in\mathbb{R}^{m\times n}\). The rank of \(A\) is the dimension of its column space or, equivalently, its row space. Let \(I\subset[m]\) and \(J\subset[n]\) with \(|I|=|J|\leq\min\{m,n\}\). Then the \((I,J)\) minor of \(A\), denoted \(\det_{I,J}(A)\), is the determinant of the submatrix \(A_{I,J}\). The order of the minor is \(|I|\). Using minors, the rank of \(A\) can be equivalently defined as the largest \(r\) such that there is a nonzero minor of order \(r\). This allows us to write the following rank condition:

\[\operatorname{rank}(A)\geq r\iff\sum_{\begin{subarray}{c}(I,J)\subset[m] \times[n]\\ |I|=|J|=r\end{subarray}}\det_{I,J}(A)^{2}\neq 0.\]
Note that

\[\sum_{\begin{subarray}{c}(I,J)\subset[m]\times[n]\\ |I|=|J|=r\end{subarray}}\det_{I,J}(A)^{2}\]

is a multivariate polynomial in the entries of \(A\). If we replace \(A\) with a matrix-valued real analytic function of several variables \(A(x)\), then the composition of the polynomial with \(A\) is a real analytic function. We call this composite function the "rank condition function of order \(r\) associated with \(A\)". Thus, we have that \(\operatorname{rank}(A(x))\geq r\) if and only if \(x\) is not in the zero set of the rank condition function of \(r\) associated with \(A\). If the zero set is not the whole domain (i.e. if the rank condition function is not identically zero), then it is very limited as we will explain in Section 2.2 (in particular, it is measure zero and closed). So, our task lies in showing that the rank condition function is not identically zero. To do so we use Leibniz's determinant formula [2, Def. 10.33],

\[\det(A)=\sum_{\sigma\in\mathfrak{S}_{n}}\operatorname{sgn}(\sigma)\prod_{i=1 }^{n}a_{i,\sigma(i)}=\sum_{\sigma\in\mathfrak{S}_{n}}\operatorname{sgn}( \sigma)\prod_{i=1}^{n}a_{\sigma(i),i}\text{ for }A\in\mathbb{R}^{n\times n},\]

and the Cauchy-Binet formula [10, Sec. I.2.4],

\[\det(AB^{T})=\sum_{S\in\binom{[n]}{m}}\det_{[m],S}(A)\det_{[m],S}(B)\text{ for }A,B\in\mathbb{R}^{m\times n}\ (n\geq m).\]

Specifically, we use the following corollary of the Cauchy-Binet formula.

**Lemma 1**: _Let \(A\in\mathbb{R}^{m\times N}\) and \(B\in\mathbb{R}^{n\times N}\), and let \(D\in\mathbb{R}^{N\times N}\) be diagonal. Let \(I\subset[m]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{m,n,N\}\). Then_

\[\det_{I,J}\left(ADB^{T}\right)=\sum_{S\in\binom{[N]}{s}}\left(\prod_{\ell\in S }D_{\ell}\right)\det_{I,S}(A)\det_{J,S}(B).\]

_Proof_ Applying the Cauchy-Binet formula, we get

\[\det_{I,J}\left(ADB^{T}\right) =\sum_{S\in\binom{[N]}{s}}\det_{I,S}(A)\det_{S,J}\left(DB^{T}\right)\] \[=\sum_{S,S^{\prime}\in\binom{[N]}{s}}\det_{I,S}(A)\det_{S,S^{ \prime}}(D)\det_{J,S^{\prime}}(B)\]

but, since \(D\) is diagonal, \(\det(D_{S,S^{\prime}})=0\) unless \(S=S^{\prime}\), in which case it equals \(\prod_{\ell\in S}D_{\ell}\) and so the result follows. \(\Box\)

These are powerful tools because they can be used to write the minor of a matrix-valued polynomial as a sum of polynomials. Thus, the question of rank becomes a question of the linear independence of multivariate polynomials.
In addition to the usual notion of rank, there are stronger notions of rank. For example, the Kruskal rank of \(A\) is the largest \(r\) such that every subset of \(r\) columns of \(A\) is linearly independent [12]. Given \(J\subset[n]\) such that \(|J|=r\leq m\), the columns of \(A_{[m],J}\) are linearly independent if and only if the rank of \(A_{[m],J}\) is \(r\). Thus, we have the following Kruskal rank condition:

\[\text{the Kruskal rank of }A\geq r\iff\prod_{\begin{subarray}{c}J\subset[n] \\ |J|=r\end{subarray}}\sum_{\begin{subarray}{c}I\subset[m]\\ |I|=r\end{subarray}}\det_{I,J}(A)^{2}\neq 0.\]

This naturally extends to an even stronger notion of rank defined as the largest \(r\) such that

\[\prod_{\begin{subarray}{c}(I,J)\subset[m]\times[n]\\ |I|=|J|=r\end{subarray}}\det_{I,J}(A)\neq 0.\]

### Real analytic functions of several variables

We will use properties of analytic functions to (1) extend our results from polynomial \(A\) to real analytic \(A\) and (2) to interpret the rank being deficient on the zero set of a non-identically zero analytic function.

First, an analytic function is uniquely determined by the coefficients of its power series expansion at each point. This is a corollary of Taylor's theorem, which gives these coefficients in terms of the partial derivatives (of all orders) of the function at a point. Thus, to show that the rank condition associated with \(A\) is not identically zero, we only have to show that a subset of its coefficients are not all zero.

Second, the zero set of a non-identically zero analytic function is measure zero by Corollary 10 of [11], a corollary of the identity theorem [11, Thm. 6] and Jensen's inequality [11, Thm. 9]. The identity theorem states that if \(f\) and \(g\) are analytic on an open connected domain and \(f=g\) on a nonempty open subset, then \(f=g\) on the whole domain. The identity theorem and its corollary hold for real analytic functions as well (this is clear from the proofs), so we have shown the measure zero part of the following proposition. To show the closed part, just use that the pre-image of \(\mathbb{R}\backslash\{0\}\) is open since \(f:\mathbb{R}^{n}\rightarrow\mathbb{R}\) is continuous.

**Lemma 2**: _The zero set of a non-identically zero real analytic function is measure zero and closed._

### Weak compositions

We will index our decompositions by weak compositions. There is a well-known bijection between multisets of cardinality \(k\) taken from \([d]\)--\(i_{1},\ldots,i_{k}\in[d]\) such that \(i_{1}\leq\ldots\leq i_{k}\)--and \(d\)-tuples of non-negative integers whose sum is \(k\), i.e. weak compositions of \(k\) into \(d\) parts--\(k_{1},\ldots,k_{d}\in\mathbb{Z}_{+}\) such that \(k_{1}+\cdots+k_{d}=k\). It can be seen
by viewing \(k_{i}\) as the multiplicity of \(i\), i.e. \(k_{i}=|\{\ell\in[k]\mid i=i_{\ell}\}|\). The total number of either is \(\binom{d}{k}=\binom{k+d-1}{k}=\binom{k+d-1}{d-1}\) by stars and bars [5, Thm. 2.5.1].

Let

\[\lambda(k) =\Big{\{}\vec{k}\in\mathbb{Z}_{+}^{d}\mid k_{1}+\cdots+k_{d}=k \Big{\}}\] \[\text{and }\Lambda(K) =\Big{\{}\vec{k}\in\mathbb{Z}_{+}^{d}\mid k_{1}+\cdots+k_{d}\leq K \Big{\}}.\]

Note that

\[|\Lambda(K)|=\sum_{k=0}^{K}\binom{d}{k}=\sum_{k=0}^{K}\binom{k+d-1}{d-1}=\sum_ {i=d-1}^{K+d-1}\binom{i}{d-1}=\binom{K+d}{d}\]

by Zhu's Theorem [14, Thm. 1.5.2], which was published by Zhu Shijie in 1303 [22].

## 3 Results involving Hadamard powers

Here we present the main idea that allows us to prove the generic full rankness of \(B^{T}\odot\phi(AB^{T})\). First, we sketch the proof idea in Section 3.1. Then, we apply the proof technique to \(AB^{T}\) in Section 3.2, \((AB^{T})^{(k)}\) in Section 3.3, and \(\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\) in Section 3.4.

### Proof sketch

Let \(f:\mathbb{R}^{d}\to\mathbb{R}^{m\times n}\) be real analytic. For all \(I\subset[m]\) and \(J\subset[n]\) such that \(|I|=|J|\leq\min\{m,n\}\), define

\[g_{I,J}:\mathbb{R}^{d} \to\mathbb{R}\] \[x \mapsto\det_{I,J}(f(x)). \tag{2}\]

Let \(g\) be a product of \(g_{I,J}\)'s or a product of sums of \(g_{I,J}\)'s. Then \(g\) is real analytic. We would like to show that it is not identically zero so that we can apply Lemma 2.

To start with, consider polynomial \(f\). Then we want to find an appropriate decomposition \(f(x)=A(x)DB(x)^{T}\) where \(A\) and \(B\) are matrix-valued real analytic functions and \(D\in\mathbb{R}^{N\times N}\) is a diagonal matrix with no zeros. Let \(|I|=|J|=s\leq\min\{m,n,N\}\) and enumerate \(I\) as \(\{i_{1},\ldots,i_{s}\}\) and \(J\) as \(\{j_{1},\ldots,j_{s}\}\). Then, by the Cauchy-Binet formula,

\[\det_{I,J}\big{(}A(x)DB(x)^{T}\big{)} =\sum_{S\in\binom{[N]}{s}}\left(\prod_{\ell\in S}D_{\ell}\right) \det_{I,S}(A(x))\det_{J,S}(B(x))\] \[:=\sum_{S\in\binom{[N]}{s}}\left(\prod_{\ell\in S}D_{\ell}\right) p_{S}(x),\]
and by Leibniz's determinant formula,

\[p_{S}(x) =\left(\sum_{\sigma:I\hookrightarrow S}\operatorname{sgn}(\sigma) \prod_{t=1}^{s}a_{i_{t},\sigma(i_{t})}(x)\right)\left(\sum_{\tau:J \hookrightarrow S}\operatorname{sgn}(\tau)\prod_{t=1}^{s}b_{i_{t},\tau(i_{t})}( x)\right)\] \[\coloneqq p_{A}(x)p_{B}(x)\] \[=\sum_{\sigma:I\hookrightarrow S}\sum_{\tau:J\hookrightarrow S} \operatorname{sgn}(\sigma)\operatorname{sgn}(\tau)\prod_{t=1}^{s}a_{i_{t}, \sigma(i_{t})}(x)b_{j_{t},\tau(j_{t})}(x).\]

We call the monomials corresponding to the individual terms in each sum the "Leibniz monomials" of \(p_{A}\), \(p_{B}\), and \(p_{S}\) respectively. Note that these monomials may or may not be in their corresponding polynomial depending on whether they cancel or not.

We want to show that the non-identically zero \(p_{S}\) are linearly independent and that there is at least one of them.

One way we will do this is by showing that, for all \(S\in\binom{[N]}{s}\), \(p_{S}\) has distinct Leibniz monomials (so they don't cancel) that do not appear in any other \(p_{S^{\prime}}\).

The other way we will show it is a little more involved. We will show that \(p_{A}\) is not identically zero if and only if \(S\) is in a particular set, that \(p_{B}\) is not identically zero if and only if \(S\) is in another particular set, that \(p_{B}\) has distinct Leibniz monomials for \(S\) in that set, that those monomials do not appear in \(p_{B}\) for any other \(S^{\prime}\), and that the two sets of \(S\) have non-empty intersection. Let \(\widetilde{N}\) denote the maximum size of \(S\) in the intersection.

If the non-identically zero \(p_{S}\) are linearly independent and there is at least one of them, then \(g_{I,J}\) is identically zero if and only if \(\prod_{\ell\in S}D_{\ell}=0\) for all \(S\) such that \(p_{S}\) is not identically zero, which can't happen if \(D\) has no zeros. Thus, \(g\) equal to the product of all \(g_{I,J}\) such that \(|I|=|J|\leq\min\{m,n,N\}\) is not identically zero. And so, all order \(\min\{m,n,N\}\) or less minors of \(f(x)\) are nonzero for generic \(x\).

If, instead, there is a restriction on \(I\) for \(g_{I,J}\) to not be identically zero, then

\[g=\prod_{\begin{subarray}{c}J\subset[n]\\ |J|\leq\min\{m,n,\widetilde{N}\}\end{subarray}}\sum_{\begin{subarray}{c}I \subset[m]\\ |I|=|J|\end{subarray}}g_{I,J}^{2},\]

is not identically zero. And so, \(f(x)\) has Kruskal rank at least \(\min\{m,n,\widetilde{N}\}\) for generic \(x\).

Now, consider the setting where \(f\) is not a polynomial. Since \(g_{I,J}\) is real analytic, it is uniquely determined around zero by its power series expansion there (by Taylor's theorem). For any \(K\in\mathbb{N}\), let \(g_{I,J}^{K}\) be the sum of the monomials in the Taylor series of \(g_{I,J}\) that we get by truncating the Taylor series of \(f\) to only degree \(K\) monomials. Then we can take \(K\) as high as we want and reduce to the corresponding result for polynomial \(f\).
### Matrix products

First let's demonstrate the proof technique for matrix products. Let \(A\in\mathbb{R}^{m\times d}\) and \(B\in\mathbb{R}^{n\times d}\). Let \(I\subset[m]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{m,n,d\}\). Enumerate \(I\) as \(\{i_{1},\ldots,i_{s}\}\) and \(J\) as \(\{j_{1},\ldots,j_{s}\}\). We want to show that the \((I,J)\) minor of \(AB^{T}\) is not identically zero. By the Cauchy-Binet formula,

\[p(a_{i_{t},\ell},b_{j_{t},\ell}) \coloneqq\det_{I,J}\left(AB^{T}\right)\] \[=\sum_{S\in\binom{[d]}{s}}\det_{I,S}(A)\det_{J,S}(B)\] \[\coloneqq\sum_{S\in\binom{[d]}{s}}p_{S}(a_{i_{t},\ell},b_{j_{t}, \ell}),\]

and by Leibniz's determinant formula,

\[p_{S}=\sum_{\sigma:I\hookrightarrow S}\sum_{\tau:J\hookrightarrow S}\text{ sgn}(\sigma)\text{sgn}(\tau)\prod_{t=1}^{s}a_{i_{t},\sigma(i_{t})}b_{j_{t},\tau(j_{t})}.\]

The \((\sigma,\tau)\) Leibniz monomial is the only one that involves \(a_{i_{1},\sigma(i_{1})},\ldots,a_{i_{s},\sigma(i_{s})}\) and

\(b_{i_{1},\tau(i_{1})},\ldots,b_{i_{s},\tau(i_{s})}\) and so it is distinct. Thus, it does not cancel in \(p_{S}\). Moreover, if it is the same monomial as the \((\sigma^{\prime},\tau^{\prime})\) term in \(p_{S^{\prime}}\), then \(S=\sigma(I)=\sigma^{\prime}(I)=S^{\prime}\) where we view \(\sigma:I\hookrightarrow\binom{\Lambda(K)}{s}\). Thus, distinct \(p_{S}\) have distinct monomials and so the \(p_{S}\) are linearly independent. Thus, \(p\) is not identically zero and so all order \(\min\{m,n,d\}\) or less minors of \(AB^{T}\) are nonzero for generic \((A,B)\). We discuss further implications of this in Appendix B.

### Hadamard powers

To show how to extend from \((AB^{T})^{(k)}\) to \(B^{T}\odot(AB^{T})^{(k)}\), we first demonstrate our proof technique on the former.

**Theorem 3**: _Let \(k\in\mathbb{N}\). Then all order \(\min\{m,n,\binom{d}{k}\}\) or less minors of \((AB^{T})^{(k)}\) are nonzero for generic \((A,B)\in\mathbb{R}^{m\times d}\times\mathbb{R}^{n\times d}\)._

Proof: First,

\[\left(AB^{T}\right)^{(k)} =\left(\sum_{i=1}^{d}a_{i}b_{i}^{T}\right)^{(k)}\] \[=\sum_{i_{1},\ldots,i_{k}=1}^{d}\left(a_{i_{1}}b_{i_{1}}^{T} \right)\circ\cdots\circ\left(a_{i_{k}}b_{i_{k}}^{T}\right)\]
\[=\sum_{i_{1},\ldots,i_{k}=1}^{d}(a_{i_{1}}\circ\cdots\circ a_{i_{k}})(b_{i_{1}} \circ\cdots\circ b_{i_{k}})^{T}\]

\[\stackrel{{ s}}{{=}}\sum_{\vec{k}\in\lambda(k)}\binom{k}{k_{1}, \ldots,k_{d}}\left(a_{1}^{(k_{1})}\circ\cdots\circ a_{d}^{(k_{d})}\right)\left( b_{1}^{(k_{1})}\circ\cdots\circ b_{d}^{(k_{d})}\right)^{T}\]

\[=\widetilde{A}D\widetilde{B}^{T}\]

where \(A=[a_{1}|\cdots|a_{d}]\), \(B=[b_{1}|\cdots|b_{d}]\), \((*)\) follows from the commutativity of the Hadamard product, the columns of \(\widetilde{A}\) are the unique Hadamard products of the columns of \(A\), the columns of \(\widetilde{B}\) are the unique Hadamard products of the columns of \(B\), and \(D\) is a diagonal matrix with the corresponding multinomial coefficients. Note that

\[\widetilde{A}=\left[\prod_{\ell=1}^{d}a_{i,\ell}^{k_{\ell}}\right]_{(i,\vec{ k})\in[m]\times\lambda(k)}\text{ and }\widetilde{B}=\left[\prod_{\ell=1}^{d}b_{i,\ell}^{k_{\ell}}\right]_{(i,\vec{k}) \in[n]\times\lambda(k)}.\]

The inner dimension is \(N=|\lambda(k)|=\binom{(d)}{k}\). Let \(I\subset[m]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{m,n,N\}\). Enumerate \(I\) as \(\{i_{1},\ldots,i_{s}\}\) and \(J\) as \(\{j_{1},\ldots,j_{s}\}\). We want to show that the \((I,J)\) minor is not identically zero. By the Cauchy-Binet formula,

\[p(a_{i_{t},\ell},b_{j_{t},\ell}) \coloneqq\det_{I,J}\left(\widetilde{A}D\widetilde{B}^{T}\right)\] \[=\sum_{S\in\binom{\lambda(k)}{s}}\left(\prod_{\ell\in S}D_{\ell} \right)\det_{I,S}\left(\widetilde{A}\right)\det_{J,S}\left(\widetilde{B}\right)\] \[\coloneqq\sum_{S\in\binom{\lambda(k)}{s}}\left(\prod_{\ell\in S}D _{\ell}\right)p_{S}(a_{i_{t},\ell},b_{j_{t},\ell}),\]

and by Leibniz's determinant formula,

\[p_{S}=\sum_{\sigma:I\hookrightarrow S}\sum_{\tau:J\hookrightarrow S}\text{ sgn}(\sigma)\text{sgn}(\tau)\prod_{t=1}^{s}\prod_{\ell=1}^{d}a_{i_{t},\ell}^{ \sigma(i_{t})_{\ell}}b_{j_{t},\ell}^{\tau(j_{t})_{\ell}}.\]

Consider the \((\sigma,\tau)\) Leibniz monomial. Suppose it is equal to the \((\sigma^{\prime},\tau^{\prime})\) Leibniz monomial. Let \(t\in[s]\). The \(a_{i_{t},1},\ldots,a_{i_{t},d}\) have degrees \(\sigma(i_{t})_{1}=\sigma^{\prime}(i_{t})_{1},\ldots,\sigma(i_{t})_{d}=\sigma^ {\prime}(i_{t})_{d}\) respectively, therefore \(\sigma(i_{t})=\sigma^{\prime}(i_{t})\). Since this was for arbitrary \(t\in[s]\), we have shown \(\sigma=\sigma^{\prime}\). Similarly, it is the case that \(\tau=\tau^{\prime}\). Thus, the Leibniz monomials are distinct, so they don't cancel in \(p_{S}\).

Similarly, if the \((\sigma,\tau)\) monomial in \(p_{S}\) is the same as the \((\sigma^{\prime},\tau^{\prime})\) monomial in \(p_{S^{\prime}}\), then \(S=\sigma(I)=\sigma^{\prime}(I)=S^{\prime}\) where we view \(\sigma:I\hookrightarrow\binom{\lambda(k)}{s}\). Thus, distinct \(p_{S}\) have distinct monomials and so the \(p_{S}\) are linearly independent. Thus, \(p\) is not identically zero and so all order \(\min\{m,n,\binom{d}{k}\}\) or less minors of \((AB^{T})^{(k)}\) are nonzero for generic \((A,B)\). \(\Box\)

### Polynomial Hadamard functions

The proof of the previous section easily extends to \(\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\).

**Theorem 4**: _Let \(K\in\mathbb{N}\) and \((c_{k})\subset\mathbb{R}\). Then all order_

\[\min\left\{m,n,\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left( \binom{d}{k}\right)\right\}\]
_or less minors of_

\[\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\]

_are nonzero for generic \((A,B)\in\mathbb{R}^{m\times d}\times\mathbb{R}^{n\times d}\)._

Proof: First, our decomposition is

\[\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\] \[=\sum_{\begin{subarray}{c}k=0,\ldots,K\\ c_{k}\neq 0\end{subarray}}c_{k}\sum_{\begin{subarray}{c}k\in\lambda(k)\\ k_{1},\ldots,k_{d}\end{subarray}}\left(a_{1}^{(k_{1})}\circ\cdots\circ a_{d}^{ (k_{d})}\right)\left(b_{1}^{(k_{1})}\circ\cdots\circ b_{d}^{(k_{d})}\right)^{T}\] \[\coloneqq\widetilde{A}D\widetilde{B}^{T}\]

with inner indices in

\[\Lambda(K,(c_{k}))\coloneqq\{\vec{k}\in\mathbb{Z}_{+}^{d}\mid k_{1}+\cdots+k_ {d}\leq K,c_{k_{1}+\cdots+k_{d}}\neq 0\}.\]

which has size

\[N=\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left(\binom{d}{k}\right).\]

The rest of the proof proceeds exactly as in the proof of Theorem 3, except with \(\lambda(k)\) replaced with \(\Lambda(K,(c_{k}))\). 

## 4 Results involving the Khatri-Rao product

Here we prove the generic rank of the objects \(B^{T}\odot(AB^{T})^{(k)}\), \(B^{T}\odot\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\), \(\phi(AB^{T})\), and \(B^{T}\odot\phi(AB^{T})\) in Sections 4.1, 4.2, 4.3, and 4.3 respectively.

To do so, we will employ the fact that the non-identically zero minors of "rectangular block diagonal" matrices are precisely the ones corresponding to (square) block diagonal submatrices, in which case the determinant is the product of the determinants of the blocks.

**Lemma 5**: _Let \(A_{\ell}\in\mathbb{R}^{m\times n}\)\(\forall\ell\in[d]\) and let_

\[A=\begin{bmatrix}A_{1}&&\\ &\ddots&\\ &&A_{d}\end{bmatrix}\]

_with everything else zero. Let \(I_{\ell}\subset[m(\ell-1)+1:m\ell]\) and \(J_{\ell}\subset[n(\ell-1)+1:n\ell]\) for all \(\ell\in[d]\). Let \(I=\cup_{\ell=1}^{d}I_{\ell}\) and \(J=\cup_{\ell=1}^{d}J_{\ell}\). Suppose \(|I|=|J|\leq\min\{md,nd\}\). Then \(|I_{\ell}|=|J_{\ell}|\) for all \(\ell\in[d]\) is necessary for \(\det_{I,J}(A)\) to be nonzero and sufficient for \(\det_{I,J}(A)\) to be equal to_

\[\prod_{\ell=1}^{d}\det_{I_{\ell},J_{\ell}}(A_{\ell}).\]
Proof: To prove the necessary part, suppose \(|I_{\ell}|\neq|J_{\ell}|\) for some \(\ell\in[d].\) If \(|I_{\ell}|<|J_{\ell}|,\) then the columns corresponding to \(A_{\ell}\) in the \((I,J)\) submatrix are linearly dependent; if \(|I_{\ell}|>|J_{\ell}|\) then the rows are; either way, \(\det_{I,J}(A)=0.\) The sufficient part is a well known fact and can be proved with Leibniz's determinant formula: the only permutations that give non-zero products are the ones that permute within each \(A_{\ell}\) separately, and so we can factor out \(\det_{I_{\ell},J_{\ell}}(A_{\ell})\) for each \(\ell\in[d].\) 

### Hadamard powers with Khatri-Rao products

**Theorem 6**: _Let \(k\in\mathbb{N}.\) Then \(B^{T}\odot(AB^{T})^{(k)}\) has Kruskal rank at least \(\min\{md,n,\left(\binom{d}{k+1}\right)\}\) for generic \((A,B)\in\mathbb{R}^{m\times d}\times\mathbb{R}^{n\times d}.\) Moreover, the rank is bounded above by the same for all \((A,B).\)_

Proof: Let \(u\in\mathbb{R}^{m},\)\(v\in\mathbb{R}^{n},\) and \(W=[w_{1}|\cdots|w_{d}]\in\mathbb{R}^{n\times d}.\) Then

\[W^{T}\odot w^{T} =[w_{j,i_{1}}u_{i_{2}}v_{j}]_{(i_{1},i_{2}),j}\] \[=[e_{1}\otimes u|\cdots|e_{d}\otimes u][v\circ w_{1}|\cdots|v \circ w_{d}]^{T}\] \[=\sum_{\ell=1}^{d}(e_{\ell}\otimes u)(v\circ w_{\ell})^{T}\]

where the \(e_{\ell}\) denote the basis vectors of \(\mathbb{R}^{d}.\) Thus,

\[B^{T}\odot\left(AB^{T}\right)^{(k)}\] \[=B^{T}\odot\sum_{\vec{k}\in\lambda(k)}\binom{k}{k_{1},\ldots,k_{d }}\left(a_{1}^{(k_{1})}\circ\cdots\circ a_{d}^{(k_{d})}\right)\left(b_{1}^{(k _{1})}\circ\cdots\circ b_{d}^{(k_{d})}\right)^{T}\] \[=\sum_{\ell=1}^{d}\sum_{\vec{k}\in\lambda(k)}\binom{k}{k_{1}, \ldots,k_{d}}\left(e_{\ell}\otimes a_{1}^{(k_{1})}\circ\cdots\circ a_{d}^{(k _{d})}\right)\left(b_{\ell}\circ b_{1}^{(k_{1})}\circ\cdots\circ b_{d}^{(k_{d })}\right)^{T}\] \[\coloneqq\overline{A}D\overline{B}^{T}\]

where \(\overline{A}\) is rectangular block diagonal with \(d\) identical blocks

\[\widetilde{A}=\left[\prod_{\ell=1}^{d}a_{i,\ell}^{k_{\ell}}\right]_{i\in[m], \vec{k}\in\lambda(k)}\quad\text{ and }\quad\quad\overline{B}=\left[b_{i,j}\prod_{\ell=1}^{d}b_{i,\ell}^{k_{\ell}} \right]_{i\in[n],(j,\vec{k})\in[d]\times\lambda(k)}.\]

The inner dimension is \(Nd=\binom{d}{(k)}d.\) Let \(I\subset[md]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{md,n,\left(\binom{d}{k+1}\right)\}.\) Enumerate \(I\) as \(\{i_{1},\ldots,i_{s}\}\) and \(J\) as \(\{j_{1},\ldots,j_{s}\}.\) We want to show that the \((I,J)\) minor is not identically zero. By the Cauchy-Binet formula,

\[p(a_{i_{\ell},\ell},b_{j_{\ell},\ell}) \coloneqq\det_{I,J}\left(\overline{A}D\overline{B}^{T}\right)\] \[=\sum_{S\in\binom{[d]\times\lambda(k)}{s}}\left(\prod_{\ell\in S }D_{\ell}\right)\det_{\underbrace{I,S}_{\cdot=PAPB=p_{S}}}.\]

Decompose \(I\) and \(S\) into \(\cup_{\ell=1}^{d}I_{\ell}\) and \(\cup_{\ell=1}^{d}S_{\ell}\) respectively, where \(I_{\ell}\in[m(\ell-1)+1:m\ell]\) and \(S_{\ell}\in[N(\ell-1)+1:N\ell].\) Then, by Lemma 5, \(\det_{I,S}(\overline{A})\) can only be non-identically zero if
\(|I_{\ell}|=|S_{\ell}|\) for all \(\ell\in[d]\). In this case, \(\overline{A}_{I,S}\) is block diagonal and so its determinant is the product of the determinants of its blocks, none of which are identically zero since the blocks are square submatrices of \(\widetilde{A}\) from the proof of Theorem 3. Thus, \(p_{A}\) is not identically zero if and only if \(|I_{\ell}|=|S_{\ell}|\) for all \(\ell\in[d]\).

On the other hand, \(\overline{B}\) has repeated columns. In particular, distinct columns \((i,\vec{k})\) and \((j,\vec{r})\) are equal if and only if \(\vec{k}+e_{i}=\vec{r}+e_{j}\). Thus, we can break \([d]\times\lambda(k)\) up into the distinct preimages of \(\varphi:[d]\times\lambda(k)\allowbreak\mathrel{\mathop{\kern 0.0pt\hbox to 0.0pt{\vrule heig ht ight 6.0pt height 6.0pt height 6.0pt depth -0.2pt\hss\raise 0.43pt\hbox{$\rightarrow$}}} \limits}\lambda(k+1):(i,\vec{k})\mapsto\vec{k}+e_{i}\). Then, \(p_{B}\) is not identically zero if and only if \(\varphi(S)\) has distinct elements. Suppose \(\varphi(S)\) has distinct elements and consider \(p_{B}\). By Leibniz's determinant formula

\[p_{B}=\sum_{\tau:J\mapsto S}\operatorname{sgn}(\tau)\prod_{t=1}^{s}\prod_{ \ell=1}^{d}b_{i_{t},\ell}^{\varphi(\tau(i_{t}))_{\ell}}.\]

Consider the \(\tau\) Leibniz monomial. Suppose it is equal to the \(\tau^{\prime}\) Leibniz monomial. Let \(t\in[s]\). The \(b_{i_{t},1},\ldots,b_{i_{t},d}\) have degrees \(\varphi(\tau(i_{t}))_{1}=\varphi(\tau^{\prime}(i_{t}))_{1},\ldots,\varphi(\tau (i_{t}))_{d}=\varphi(\tau^{\prime}(i_{t}))_{d}\) respectively, therefore \(\varphi(\tau(i_{t}))=\varphi(\tau^{\prime}(i_{t}))\). Since \(\varphi(S)\) has distinct elements, \(\tau(i_{t})=\tau^{\prime}(i_{t})\). And since this was for arbitrary \(t\in[s]\), we have shown \(\tau=\tau^{\prime}\).

Similarly, if \(\varphi(S)\) has distinct elements and \(\varphi(S^{\prime})\) has distinct elements, and if the \(\tau\) monomial in \(p_{B}\) with \(S\) is the same as the \(\tau^{\prime}\) monomial in \(p_{B}\) with \(S^{\prime}\), then \(S=\tau(J)=\tau^{\prime}(J)=S^{\prime}\) where we view \(\tau:J\hookrightarrow\binom{[d]\times\lambda(k)}{s}\).

Thus, if \(\varphi(S)\) has distinct elements, then \(p_{B}\) has distinct Leibniz monomials and those monomials do not appear in \(p_{B}\) for any other \(S^{\prime}\).

All that is left to show is that there is at least one \(S\in\binom{[d]\times\lambda(k)}{s}\) such that \(|S_{\ell}|=|I_{\ell}|\ \forall\ell\in[d]\) and \(\varphi(S)\) has distinct elements. Since \(s\leq\binom{d}{k+1}\), there is at least one \(S\) such that \(\varphi(S)\) has unique elements and so we just need to restrict to \(I\) such that \(|S_{\ell}|=|I_{\ell}|\ \forall\ell\in[d]\). Thus, for all \(J\subset[n]\) such that \(|J|=s\), there is at least one \(I\subset[m]\) such that \(|I|=s\) and \(g_{I,J}\) is not identically zero, returning to the notation of Section 3.1. Let \(s=\min\{md,n,\binom{d}{k+1}\}\). Then we have show that

\[g=\prod_{\begin{subarray}{c}J\subset[n]\\ |J|\leq s\end{subarray}}\sum_{\begin{subarray}{c}I\subset[md]\\ |I|=|J\end{subarray}}g_{I,J}^{2}\]

is not identically zero. Thus, \(B^{T}\odot(AB^{T})^{(k)}\) has Kruskal rank at least \(\min\{m,n,\binom{d}{k+1}\}\) for generic \((A,B)\). The upper bound follows from the decomposition. \(\Box\)

### Polynomial Hadamard functions with Khatri-Rao products

Now we would like to combine the proofs of Theorems 4 and 6 to prove the following theorem.

**Theorem 7**: _Let \(K\in\mathbb{N}\) and \((c_{k})\subset\mathbb{R}\). Then_

\[B^{T}\odot\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\]

_has Kruskal rank at least_

\[\min\left\{md,n,\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left( \binom{d}{k+1}\right)\right\}\]

_for generic \((A,B)\in\mathbb{R}^{m\times d}\times\mathbb{R}^{n\times d}\). Moreover, the rank is bounded above by the same for all \((A,B)\)._
Proof: Here, our decomposition is

\[B^{T}\odot\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\] \[= \sum_{\ell=1}^{d}\sum_{\begin{subarray}{c}k=0,\ldots,K\\ c_{k}\neq 0\end{subarray}}c_{k}\sum_{\tilde{k}\in\lambda(k)}\binom{k}{k_{1}, \ldots,k_{d}}\left(e_{\ell}\otimes a_{1}^{(k_{1})}\circ\cdots\circ a_{d}^{(k_{ d})}\right)\left(b_{\ell}\circ b_{1}^{(k_{1})}\circ\cdots\circ b_{d}^{(k_{d})} \right)^{T}\] \[\coloneqq\overline{A}D\overline{B}^{T}\]

with inner indices in \([d]\times\Lambda(K,(c_{k}))\) which has size

\[Nd=d\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\binom{\left(d\right)}{k}.\]

The rest of the proof proceeds exactly as in the proof of Theorem 6, except with \(\lambda(k)\) replaced with \(\Lambda(K,(c_{k}))\), \(\binom{d}{\binom{d}{k+1}}\) replaced with

\[\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\binom{d}{k+1},\]

and \(\lambda(k+1)\) replaced with

\[\{\vec{k}\in\mathbb{Z}_{+}^{d}\ |\ 1\leq k_{1}+\cdots+k_{d}\leq K+1,c_{k_{1}+ \cdots+k_{d}-1}\neq 0\},\]

which has size equal to the previous expression. 

### Extension to real analytic Hadamard functions

Let \(\phi\) be a real analytic Hadamard function. Then, in particular, it has a convergent power series expansion centered at zero. Let \(c_{k}\) be the corresponding coefficients and let \(r\) be the radius of convergence. Define \(R\) as the set of \((A,B)\) such that all the entries of \(AB^{T}\) have absolute value smaller than \(r\). This is clearly open. Let \(I\subset[m]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{m,n\}\). Let \(K\in\mathbb{N}\). Define

\[g_{I,J}:R\rightarrow\mathbb{R}:(A,B) \mapsto\det_{I,J}\left(\sum_{k=0}^{\infty}c_{k}\left(AB^{T} \right)^{(k)}\right)\] \[\text{and }\tilde{g}_{I,J}:R\rightarrow\mathbb{R}:(A,B) \mapsto\det_{I,J}\left(\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{( k)}\right).\]

Let \(g_{I,J}^{K}\) be the Taylor expansion around zero of \(g_{I,J}\) with only the monomials that are in \(\tilde{g}_{I,J}\). By uniqueness, \(g_{I,J}^{K}=\tilde{g}_{I,J}\). By Theorem 4, if

\[s\leq\min\Bigg{\{}m,n,\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\} \binom{d}{k}\Bigg{\}},\]
then \(\tilde{g}_{I,J}\) is not identically zero. Thus, if we pick \(K\) such that

\[\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left(\binom{d}{k}\right)\geq \min\{m,n\},\]

then \(g_{I,J}\) is not identically zero. Thus,

\[\bar{g}_{I,J}:\mathbb{R}^{m\times d}\times\mathbb{R}^{n\times d}\to\mathbb{R}: (A,B)\mapsto\det_{I,J}\phi\left(AB^{T}\right)\]

is not identically zero, and so \(g\), the product of all \(\bar{g}_{I,J}\) such that \(|I|=|J|\leq\min\{m,n\}\), is not identically zero. So, we have proved the following theorem.

**Theorem 8**: _If \(A\in\mathbb{R}^{m\times d}\), \(B\in\mathbb{R}^{n\times d}\), and \(\phi\) is real analytic but not a polynomial, then all order \(\min\{m,n\}\) or less minors of \(\phi(AB^{T})\) are nonzero for generic \((A,B)\)._

Now let \(I\subset[md]\) and \(J\subset[n]\) such that \(|I|=|J|=s\leq\min\{md,n\}\). Let \(K\in\mathbb{N}\). Define

\[g_{I,J}:R\to\mathbb{R}:(A,B)\mapsto\det_{I,J}\left(B^{T}\odot \sum_{k=0}^{\infty}c_{k}\left(AB^{T}\right)^{(k)}\right)\] \[\text{and }\tilde{g}_{I,J}:R\to\mathbb{R}:(A,B)\mapsto\det_{I,J} \left(B^{T}\odot\sum_{k=0}^{K}c_{k}\left(AB^{T}\right)^{(k)}\right).\]

Proceeding similarly, we get, by Theorem 7, that if we pick \(K\) such that

\[\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left(\binom{d}{k}\right)\geq \min\{m,n\},\]

then there is an \(I\) such that \(g_{I,J}\) is not identically zero, and so

\[g=\prod_{\begin{subarray}{c}J\subset[n]\\ |J|\leq\min\{md,n\}\end{subarray}}\sum_{\begin{subarray}{c}I\subset[md]\\ |I|=|J|\end{subarray}}\det_{I,J}\left(B^{T}\odot\phi\left(AB^{T}\right)\right)\]

is not identically zero. So, we have proved the following theorem.

**Theorem 9**: _If \(A\in\mathbb{R}^{m\times d}\), \(B\in\mathbb{R}^{n\times d}\), and \(\phi\) is real analytic but not a polynomial, then \(B^{T}\odot\phi(AB^{T})\) has Kruskal rank \(\min\{md,n\}\) for generic \((A,B)\)._
## 5 Application to machine learning models

Here we apply the results about the rank of Khatri-Rao products of Hadamard functions to the memory capacity of machine learning models. In Section 5.1 we show that for any model that consists of a linear model applied to an embedding, if there is a point where the derivative is surjective, then the "doubled model" with twice the number of parameters is surjective. In Section 5.2 we combine this with the fact that the Jacobian of the two layer neural network has generically full rank to show that two layer neural networks have memory capacity equal to at least half their number of parameters.

### Memory capacity from Jacobian rank

Consider an embedding \(\bar{f}:\mathbb{R}^{k}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}\), which maps feature vectors \(x\in\mathbb{R}^{d}\) to embedding vectors \(\hat{x}\in\mathbb{R}^{m}\) based on parameters \(w\in\mathbb{R}^{k}\). Define the model \(\bar{F}:\mathbb{R}^{k}\times\mathbb{R}^{m}\times\mathbb{R}^{d}\rightarrow \mathbb{R}:(w,v,x)\mapsto\langle v,\bar{f}(w,x)\rangle\), which applies a linear model to embedding vectors. Also define the batch versions of these: \(f:\mathbb{R}^{k}\times\mathbb{R}^{d\times n}\rightarrow\mathbb{R}^{m\times n }:(w,X)\mapsto[f(w,x_{1})|\cdots|f(w,x_{n})]\) and \(F:\mathbb{R}^{k}\times\mathbb{R}^{m}\times\mathbb{R}^{d\times n}\rightarrow \mathbb{R}^{n}:(w,v,X)\mapsto v^{T}f(w,X)\).

As an example, for the two layer neural network model, we have \(\bar{f}:\mathbb{R}^{d\times m}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}:( W,x)\mapsto\psi(W^{T}x)\). Suppose that the derivative (i.e. Jacobian) with respect to the hidden layer \(\partial_{W}F\), is surjective at a point \((W_{0},v_{0},X)\), i.e. \(\text{rank}(\partial_{W}F(W_{0},v_{0},X))=n\). It turns out that we can actually show surjectivity of the model from this by doubling the number of parameters. Specifically, define \(\bar{g}:\mathbb{R}^{d\times 2m}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{2m}:([W \ U],x)\mapsto\psi([W\ U]^{T}x)=[\bar{f}(W,x);\bar{f}(U,x)]\) and \(\bar{G}:\mathbb{R}^{d\times 2m}\times\mathbb{R}^{2m}\times\mathbb{R}^{d} \rightarrow\mathbb{R}:([W\ U],[v;z],x)\mapsto\langle[v;z],\bar{g}([W\ U],x) \rangle=\bar{F}(W,v,x)+\bar{F}(U,z,x)\). Define their batch versions \(g\) and \(G\) as well. Then we have that \(G([W_{0}\ W_{0}],[v_{0};-v_{0}],X)=0\) and \(\text{rank}(\partial_{[W\ U]}G([W_{0}\ W_{0}],[v_{0};-v_{0}],X))=n\). The latter fact allows us to apply the Constant Rank Theorem [13, 4.12], which, along with the former fact, allows us to scale any \(y\in\mathbb{R}^{n}\) to be in the image of \(G(\cdot,[v_{0};-v_{0}],X)\). The scaling can then be absorbed into the linear model so that \(y\) is in the image of \(G(\cdot,[v;-v],X)\) for some \(v\). Thus, \(G(\cdot,\cdot,X)\) is surjective.

Going back to the general framework, we can define \(\bar{g}:\mathbb{R}^{2k}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{2m}:([w;u], x)\mapsto[\bar{f}(w,x);\bar{f}(u,x)]\) and \(\bar{G}:\mathbb{R}^{2k}\times\mathbb{R}^{2m}\times\mathbb{R}^{d}\rightarrow \mathbb{R}:([w;u],[v;z],x)\mapsto\langle[v;z],\bar{g}([w;u],[v;z],x)\rangle= \bar{F}(w,v,x)+\bar{F}(u,z,x)\) to get the same surjectivity result. But in order to apply the result, we need \(\bar{G}\) to actually be in the model class, as it is for the two layer neural network example.

Another example where the doubled model is actually in the model class is for deep neural networks. Let \(m_{0}=d\) and for \(\ell\in[L]\) define \(\bar{f}_{\ell}:\mathbb{R}^{m_{\ell-1}\times m_{\ell}}\times\mathbb{R}^{m_{ \ell-1}}\rightarrow\mathbb{R}^{m_{\ell}}:(W,x)\mapsto\psi(W^{T}x)\). Define \(\bar{f}:(W_{1},\ldots,W_{L},x)\mapsto\bar{f}_{L}(W_{L},\cdot)\circ\cdots\circ \bar{f}_{1}(W_{1},\cdot)(x)\). Then we can define \(\bar{g}_{1}:\mathbb{R}^{d\times 2m_{1}}\times\mathbb{R}^{d}\rightarrow\mathbb{R}^{2m_{1}}: ([W\ U],x)\mapsto[\bar{f}_{1}(W,x);\bar{f}_{1}(U,x)]\) and, for all \(\ell\in\{2,\ldots,L\}\), we can define \(\bar{g}_{\ell}:\mathbb{R}^{2m_{\ell-1}\times 2m_{\ell}}\times\mathbb{R}^{2m_{\ell-1}} \rightarrow\mathbb{R}^{2m_{\ell}}:(W\oplus U,[x;x^{\prime}])\mapsto[\bar{f}_{ \ell}(W,x);\bar{f}_{\ell}(U,x^{\prime})]\). Define \(\bar{g}:([W_{1}\ U_{1}],W_{2}\oplus U_{2},\ldots,W_{L}\oplus U_{L},x)\mapsto \bar{g}_{L}(W_{L}\oplus U_{L},\cdot)\circ\cdots\circ\bar{g}_{2}(W_{2}\oplus U _{2},\cdot)\circ\bar{g}_{1}([W_{1}\ U_{1}],\cdot)(x)\). Note that the surjectivity result we get is for a model with twice the number of parameters, but it is not the most general neural network model since the parameters for the middle layers are block-diagonal, i.e. \(W\oplus U\). However, surjectivity of this model clearly implies surjectivity
of the more general model, which has \(2m_{1}d+4\sum_{\ell=2}^{L}m_{\ell}m_{\ell-1}+2m_{L}\) parameters as opposed to the original \(m_{1}d+\sum_{\ell=2}^{L}m_{\ell}m_{\ell-1}+m_{L}\).

To summarize, for any model composed of an embedding followed by a linear model, surjectivity of the derivative at a single point implies surjectivity of its doubled model, which then has to be interpreted based on the structure of the model. This result, Theorem 11, follows from the following corollary of the Constant Rank Theorem.

**Lemma 10**: _Let \(F:\mathbb{R}^{k}\to\mathbb{R}^{n}\) be \(C^{1}\). If there exists \(x_{0}\in\mathbb{R}^{k}\) such that \(F(x_{0})=0\) and \(\text{rank}(DF(x_{0}))=n\), then for all \(y\in\mathbb{R}^{n}\) there are \(\epsilon>0\) and \(x\in\mathbb{R}^{k}\) such that \(F(x)=\epsilon y\)._

_Proof_ First, since \(n\) is the highest possible rank, the set of \(x\) such that \(\text{rank}(DF(x))=n\) is the pre-image of \(\mathbb{R}\backslash\{0\}\) under the rank condition function (the sum of the squares of the minors of order \(n\))--the rank condition function is continuous since \(F\) is \(C^{1}\) so this set is open. Thus, \(\text{rank}(DF(x))=n\) for all \(x\) near \(x_{0}\). In other words, \(F\) is a local \(C^{1}\)-submersion, so, by the Constant Rank Theorem [13, 4.12], there exist \(C^{1}\)-charts \((A,\theta)\) and \((B,\varphi)\) centered at \(x_{0}\) and \(F(x_{0})=0\) respectively, such that \(F(A)\subset B\) and \(\varphi\circ F\circ\theta^{-1}(x^{1},\ldots,x^{k})=(x^{1},\ldots,x^{n})\). This is shown in the following diagram.

\(\theta\) and \(\varphi\) are \(C^{1}\)-diffeomorphisms; \(A\), \(B\), \(\theta(A)\), and \(\varphi(B)\) are open; \(\theta(x_{0})=0\), \(F(x_{0})=0\), and \(\varphi(0)=0\); \(\hat{F}(x^{1},\ldots,x^{k})=(x^{1},\ldots,x^{n})\); and the diagram commutes. Thus, \(F(A)=B\) (since \(\theta\) and \(\varphi\) are bijective and \(\hat{F}\) is surjective). Let \(y\in\mathbb{R}^{n}\). Since \(0\in B\), there exists \(\epsilon>0\) such that \(\epsilon y\in B\) and so there exists \(x\in A\) such that \(F(x)=\epsilon y\). \(\square\)

**Theorem 11**: _Let \(f:\mathbb{R}^{k}\to\mathbb{R}^{n\times m}\) be \(C^{1}\). Define \(g:\mathbb{R}^{k}\times\mathbb{R}^{k}\to\mathbb{R}^{n\times 2m}:(w,u)\mapsto[f(w)\ f(u)]\). For all \(v,z\in\mathbb{R}^{m}\), define \(F_{v}:\mathbb{R}^{k}\to\mathbb{R}^{n}:w\mapsto f(w)v\) and \(G_{v,z}:\mathbb{R}^{k}\times\mathbb{R}^{k}\to\mathbb{R}^{n}:(w,u)\mapsto g(w, u)[v;z]\). If there exists \(v_{0}\) and \(w_{0}\) such that \(\text{rank}(DF_{v_{0}}(w_{0}))=n\), then \(G\) is surjective as a function of \((v,z)\) and \((w,u)\)._

_Proof_ Let \(y\in\mathbb{R}^{n}\). Observe

\[G_{v,z}(w,u) =g(w,u)[v;z]\] \[=f(w)v+f(u)z\] \[=F_{v}(w)+F_{z}(u).\]

So \(G_{v_{0},-v_{0}}(w_{0},w_{0})=0\) and \(\text{rank}(DG_{v_{0},-v_{0}}(w_{0},w_{0}))=n\). Applying Lemma 10, there exists \(\epsilon>0\) and \((w,u)\) such that \(G_{v_{0},-v_{0}}(w,u)=\epsilon y\). Set \(v=v_{0}/\epsilon\) and \(z=-v_{0}/\epsilon\). Then \(G_{v,z}(w,u)=y\). \(\square\)
### Memory capacity of two layer neural network

In Theorems 7 and 9 we derived the generic rank of the Jacobian of the two layer neural network, with respect to the hidden layer, for real analytic activation function. In Theorem 11 we showed that for many models, including two layer neural networks, surjectivity of the derivative at a point implies surjectivity of the doubled model. Combining these, we get the following result about the memory capacity of two layer neural networks.

**Theorem 12**: _Define \(h:\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\times\mathbb{R}^{d\times n}:(W,v,X )\mapsto\psi(X^{T}W)v\) where \(\psi\) is a real analytic function applied coordinate-wise. In the special case of \(\psi(x)=\sum_{k=0}^{K}c_{k}x^{k}\), assume \(\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\left(\binom{d}{k+1}\right)\geq n\). If \(md\geq 2n\) and \(m\) is even, then \(h(\cdot,\cdot,X)\) is surjective for all \(X\) except on a measure zero and closed set._

_Proof_ By Theorem 7 or 9, the set of \((W,X)\in\mathbb{R}^{d\times m/2}\times\mathbb{R}^{d\times n}\) for which \(\psi^{\prime}(W^{T}X)\odot X\) has rank \(<n\) is measure zero and closed. Letting \(v_{0}\in\mathbb{R}^{m/2}\) be the vector of ones and applying Theorem 11 proves the result. \(\Box\)

Note that the additional assumption when \(\psi\) is a polynomial is actually quite mild. If \(\psi\) is a polynomial with all of its coefficients nonzero, then the assumption becomes \(\binom{d+K+1}{d}\geq n+1\) by Zhu's Theorem (see Section 2.3). Or, if \(\psi\) is the monomial \(x^{K}\), then the assumption becomes \(\binom{d+K}{d-1}\geq n\). As an example, the assumption is satisfied if \(d=1e2\), \(n=1e5\), and \(\psi=x^{2}\).

Also, Theorem 12 is actually tight up to a factor of \(2(1+1/d)\approx 2\) by Sard's theorem.

**Theorem 13**: _Define \(h:\mathbb{R}^{d\times m}\times\mathbb{R}^{m}\times\mathbb{R}^{d\times n}:(W,v,X )\mapsto\psi(X^{T}W)v\) where \(\psi\) is a continuously differentiable function applied coordinate-wise. If \(m(d+1)<n\), then, for all \(X\), \(h(\cdot,\cdot,X)\) is not surjective._

_Proof_ If \(m(d+1)<n\) then, by Sard's theorem [13, Thm. 6.10], the image of \(h(\cdot,\cdot,X)\) has measure zero in \(\mathbb{R}^{n}\). In particular, this implies the result. \(\Box\)

## 6 Conclusion

In this paper we proved results about the ranks of \(\phi(W^{T}X)\) and \(\phi(W^{T}X)\odot X\) for real analytic Hadamard functions \(\phi\). In particular, if \(\phi\) is either a polynomial with sufficiently high degree or not a polynomial, then both objects are full rank for all \((W,X)\) except on the zero set of a non-identically zero analytic function, and so the set of exceptions is measure zero and closed. In the context of machine learning, this rank result implies that a two layer neural network model is able to interpolate sets of \(n\) data points almost everywhere if the number of trainable parameters is \(\geq 2n(1+1/d)\), which is tight up to the factor of \(2(1+1/d)\). We hope that viewing the rank of the neural network Jacobian from the perspective of analytic functions of several variables
leads to a better understanding of the convergence and generalization properties of two layer neural networks.

Acknowledgments.We would like to thank Jason Altschuler for pointing out the references [1] and [3]. We would also like to thank the authors of [21] for helpful discussions concerning their findings. This work was partially funded by a UBC DSI Postdoctoral Fellowship and NSERC Discovery Grant No. 2021-03677.

## Appendix A Non-polynomial real analytic activations

After corresponding with the authors of [21], we came to understand that the following was the idea behind the proof of their Lemma E.1 (typos on top of convoluted presentation had previously prevented us from gleaning this):

Suppose \(d\mid n\). Let \(A=[a_{1}|\cdots|a_{d}]\in\mathbb{R}^{m\times d}\) and

\[B=\begin{bmatrix}b_{1}&&\\ &\ddots&\\ &&b_{d}\end{bmatrix}\] (A1)

where each \(b_{i}\in\mathbb{R}^{n/d}\). Then

\[B^{T}\odot\phi(AB^{T}) =B^{T}\odot\phi\left([a_{1}b_{1}^{T}|\cdots|a_{d}b_{d}^{T}]\right)\] \[=\begin{bmatrix}b_{1}^{T}&&\\ &\ddots&\\ &&b_{d}^{T}\end{bmatrix}\odot\left[\phi\left(a_{1}b_{1}^{T}\right)|\cdots| \phi\left(a_{d}b_{d}^{T}\right)\right]\] \[=\begin{bmatrix}b_{1}^{T}\odot\phi\left(a_{1}b_{1}^{T}\right)& \\ &&\ddots&\\ &&b_{d}^{T}\odot\phi\left(a_{d}b_{d}^{T}\right)\end{bmatrix}.\]

Since generic \(b_{i}\) have no zeros, the problem comes down to the generic rank of the \(\phi(a_{i}b_{i}^{T})\). [21] use that the \(\phi(a_{i}b_{i}^{T})\) have generically full rank if \(\phi\) is not a polynomial. This is a corollary of Theorem 8, which has been known for some time.

While Zhang et al [21] do not explicitly consider polynomials, we can extend to polynomials by applying Theorem 4, which has also been known for some time. Consider \(\phi=\sum_{k=0}^{K}c_{k}x^{k}\). Note that \(d=1\) here and so, by Theorem 4, the generic rank of \(\phi(a_{i}b_{i}^{T})\) is precisely

\[\min\bigg{\{}m,\frac{n}{d},\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\} \bigg{\}}.\]
Thus, the generic rank of \(B^{T}\odot\phi(AB^{T})\) where \(B\) has the form of Eq. (A1) is exactly

\[\min\bigg{\{}md,n,d\sum_{k=0}^{K}\mathbb{I}\left\{c_{k}\neq 0\right\}\bigg{\}},\] (A2)

which is much smaller than the generic rank which we derived in Theorem 7. In particular, suppose \(\textit{md}\geq n\). If all the \(c_{k}\) are nonzero, then \(K\) has to be greater than or equal to \(n/d-1\) in order for Eq. (A2) to equal \(n\). Furthermore, if \(\phi\) is a monomial, such as \(x^{K}\), then Eq. (A2) will not equal \(n\) for any \(K\in\mathbb{N}\).

To compare this to our Theorem 7, consider the example \(d=1e2\), \(n=1e5\), and \(m\geq 1e3\): \(\phi=x^{2}\) is sufficient for the generic rank in Theorem 7 to be \(n\), while it is necessary that \(\phi\) has at least \(1000\) nonzero coefficients for Eq. (A2) to be \(n\).

## Appendix B Inner product decompositions

Using the result from Section 3.2, we have an immediate corollary. If the rows of \(\widetilde{A}\in\mathbb{R}^{m\times N}\) and \(\widetilde{B}\in\mathbb{R}^{n\times N}\) are arbitrary vectors in a \(d\)-dimensional subspace \(V\subset\mathbb{R}^{N}\), then the generic rank of \(\widetilde{AB}^{T}\) is the same as the generic rank of \(AB^{T}\). In particular, we can apply this to the following decomposition from Lemma 4.4 of [3],

\[\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}=\left[\bigoplus_{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{1}^{\otimes k}\right|\cdots\bigg{|}\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{m}^{\otimes k}\right]^{T}\left[\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}b_{1}^{\otimes k}\right|\cdots\bigg{|}\bigoplus _{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}b_{n}^{\otimes k}\right]\]

where \(A=[a_{1}|\cdots|a_{m}]^{T}\) and \(B=[b_{1}|\cdots|b_{n}]^{T}\). The vectors in this decomposition are arbitrary vectors in

\[\bigoplus_{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}\text{Sym}^{k}(\mathbb{R}^{d})\]

where \(\text{Sym}^{0}(\mathbb{R}^{d})=\mathbb{R}\) and, for \(k\in\mathbb{N}\), \(\text{Sym}^{k}(\mathbb{R}^{d})\) is the vector space of symmetric tensors of order \(k\) defined on \(\mathbb{R}^{d}\). The dimension of this space is

\[\sum_{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}\binom{d}{k},\]

proving our Theorem 4.

It turns out we can construct a similar decomposition for \(B^{T}\odot\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}\). Observe that the \(((i_{1},i_{2}),j)\) element is

\[\langle e_{i_{1}},b_{j}\rangle\sum_{k=0}^{K}c_{k}\langle a_{i_{2}},b_{j} \rangle^{k}=\langle e_{i_{1}},b_{j}\rangle\sum_{k=0}^{K}c_{k}\langle a_{i_{2}} ^{\otimes k},b_{j}^{\otimes k}\rangle\]
\[=\left\langle e_{i_{1}},b_{j}\right\rangle\Bigg{\langle}\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{i_{2}}^{\otimes k},\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}b_{j}^{\otimes k}\Bigg{\rangle}\] \[=\left\langle e_{i_{1}}\otimes\bigoplus_{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{i_{2}}^{\otimes k},\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}b_{j}^{\otimes(k+1)}\right\rangle\]

and so we can write

\[B^{T}\odot\sum_{k=0}^{K}c_{k}(AB^{T})^{(k)}=\begin{bmatrix} \widetilde{A}\\ \ddots\\ \widetilde{A}\end{bmatrix}^{T}\begin{bmatrix}\bigoplus_{\begin{subarray}{c}k=0 \\ c_{k}\neq 0\end{subarray}}^{K}b_{1}^{\otimes(k+1)}\Big{|}\cdots\Big{|}\bigoplus _{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}b_{n}^{\otimes(k+1)}\end{bmatrix}\] (B3)

where

\[\widetilde{A}=\begin{bmatrix}\bigoplus_{\begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{1}^{\otimes k}\Big{|}\cdots\Big{|}\bigoplus_{ \begin{subarray}{c}k=0\\ c_{k}\neq 0\end{subarray}}^{K}c_{k}a_{m}^{\otimes k}\end{bmatrix},\]

but this does not reduce to \(AB^{T}\).
