Low rank approximation of polynomials

Abstract

Let $k\le n$. Each polynomial $p\in\oR[x_1,...,x_n]$ can be uniquely written as $p={\sum }_{\mu }\mu p_{\mu }$, where $\mu$ ranges over the set $M$ of all monomials in $\oR[x_1,...,x_k]$ and where $p_μ\in\oR[x_{k+1},...,x_n]$. If $p$ is $d$-homogeneous and $\epsilon >0$, we say that $p$ is {\em $\epsilon$-concentrated on the first $k$ variables} if $$\sum_{μ\in M\atop°(μ)<d}\max_{x\in\oR^{n-k}\atop\|x\|=1}p_μ(x)^2\leq\varepsilon\|p\|^2,$$ where $\Vert p\Vert$ is the Bombieri norm of $p$. We show that for each $d\in\oN$ and $\epsilon >0$ there exists $k_{d,\epsilon }$ such that for each $n$ and each $d$-homogeneous $p\in\oR[x_1,...,x_n]$ there exists $k\le k_{d,\epsilon }$ such that $p$ is $\epsilon$-concentrated on the first $k$ variables {\em after some orthogonal transformation of $\oR^n$}. (So $k_{d,\epsilon }$ is independent of the number $n$ of variables.) We derive this as a consequence of a more general theorem on low rank approximation of polynomials.