# Efficient way to express a symmetric tensor in terms of rank one elements

Let

$$P(\mathbf{x})=P(x_1, \ldots, x_n)=x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$$ be a homogenous polynomial of degree $$k=k_1+\cdots+k_n$$.

It follows from a standard polarization identity (see for instance) that there are unit vectors $$\mathbf{v}_i\in \mathbb{S}^{n-1}$$ and constants $$c_i\in \mathbb{R}$$ for $$1\leq i \leq N$$ so that $$P(\mathbf{x})=\sum_{i=1}^N c_i (\mathbf{v}_i\cdot \mathbf{x})^k.$$ Using the polarization identity, we have the following (presumably non-optimal bounds) for $$N$$ and $$c_i$$:

• $$N\leq 2^{k}-1$$;
• $$|c_i|\leq \frac{(nk)^{k}}{k!}$$.

There seems to be a lot of research on finding optimal bounds on $$N$$ (the best such $$N$$ is called the symmetric rank of $$P$$). However, I haven't been able to find much information about the best possible bounds on the $$c_i$$.

Has this problem been studied? How reasonable is it to expect that one can find $$\mathbf{v}_i$$ so that $$\sum_{i=1}^N |c_i|$$ grows like a polynomial in $$k$$?

To give some context, for $$P(\mathbf{x})=P(x_1, \ldots, x_n)=x_1^{nk-1}x_2$$ set $$T(\mathbf{w}_1, \ldots, \mathbf{w}_{nk})=(\mathbf{w}_1\cdot \mathbf{x})\cdots (\mathbf{w}_{nk}\cdot \mathbf{x})$$ so $$P(\mathbf{x})=T(\mathbf{e}_1, \ldots, \mathbf{e}_1, \mathbf{e}_2)$$. Setting $$t(\mathbf{w})=T(\mathbf{w}, \ldots, \mathbf{w})=(\mathbf{w}\cdot \mathbf{x})^{nk}$$ the polarization identity gives $$P(\mathbf{x})=T(\mathbf{e}_1, \ldots, \mathbf{e}_1, \mathbf{e}_2)=\frac{1}{(nk)!} \left( t((n-1)\mathbf{e}_1+\mathbf{e}_2)-\cdots\right)$$ so $$\mathbf{v}_1=\frac{(nk-1)\mathbf{e}_1+\mathbf{e}_2}{\sqrt{n^2k^2-2nk +2}}$$ and $$c_1= \frac{(n^2k^2-2nk +2)^{nk/2}}{(nk)!}\leq \frac{(nk)^{nk}}{(nk)!}$$.

While, for $$P'(\mathbf{x})=x_1^k \cdots x_n^k$$ the same reasoning gives $$\mathbf{v}_1=\frac{\mathbf{e}_1+\cdots +\mathbf{e}_n}{\sqrt{n}}$$ and $$c_1=\frac{(nk^2)^{nk/2}}{(nk)!}=n^{-nk/2} \frac{(nk)^{nk}}{(nk)!}\leq \frac{(nk)^{nk}}{(nk)!}$$.

This is related to my earlier question

• When you say $P = x_1^{k_1} \dotsm x_n^{k_n}$ is a homogeneous polynomial, do you actually intend that $P$ is a monomial? If so, then you might wish to look at arxiv.org/abs/1201.2922 (sorry for self-promoting :( ). The paper gives a simple explicit decomposition of $P$ in which each $\mathbf{v}_i$ has roots of unity as entries, so I guess length $\sqrt{n}$, and each $c_i$ is also a root of unity; if you scale to use unit vectors then I guess $|c_i|=n^{k/2}$ if I'm understanding right. And $N = \left(\prod(k_i+1)\right)/(\min\{k_i+1\})$. The decompositions are not unique though. – Zach Teitler Jan 23 '19 at 22:37
• @ZachTeitler Yes I mean monomial--this is very far from my area of research so I am a bit out of my element even with terminology. Thank you for the reference! It certainly looks like the sort of result I am interested in. – RBega2 Jan 23 '19 at 22:51
• @ZachTeitler One question about how you go the bounds on $c_i$ from the article you linked to. If I am understanding equation (8) correctly, then there is a coefficient $1/C$ that should be pretty large, possibly making the bounds one gets on on $c_i$ smaller than what you wrote. – RBega2 Jan 23 '19 at 22:59
• Right, I forgot about that $1/C$. Anyway the obvious source of extra decompositions is by scaling each $x_i$ on the right hand side by some factor $t_i$, so you end up with $(t_1 x_1)^{k_1} \dotsm (t_n x_n)^{k_n}$; as long as the $t$'s multiply out to $1$, you got a different decomposition. I haven't thought about how to get $t$'s that minimize the $c_i$'s (or $\sum |c_i|$), hmm. And unfortunately there are other decompositions, these scalings don't hit all possible decompositions. I'm not sure how to describe the other ones, let alone minimize them. Interesting question. – Zach Teitler Jan 23 '19 at 23:05