For $x\in \mathbb{R}^d$ and multi-index $J=(j_1,\dots,j_d)$ denote $x^J=x_1^{j_1}\cdots x_d^{j_d}$.

We are given some polynomial: $p(x) = \sum_{J\leq k}\alpha_Jx^J$ where $J\leq k$ means that $j_1+\dots+j_d \leq k$. I need to find a function $g(w):\mathbb{R}^d\rightarrow \mathbb{R}$ s.t:

1) $\sum_{i=0}^k\int_{w\in [\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}]^d} \langle w,x\rangle^i g(w)= p(x) $
2) $\max_{w\in [\frac{-1}{\sqrt{d}},\frac{1}{\sqrt{d}}]^d}|g(w)|$ is bounded by $O(d^k)$

What I tried was to use multi-variable Legendre polynomials $P_J(w)=P_{j_1}(w_1)\cdots P_{j_d}(w_d)$ (in order for them to be orthogonal in our special domain it is needed to substitue the variables $w_i\mapsto \sqrt{d}w_i$). It is possible to set $g(w) = \sum_{J\leq k}c_JP_J(w)$ for some coefficients $c_J$, and use the Legendre expansion of $w^J$ to get exactly the required polynomial for any given polynomial $p(x)$. The problem is that the coefficients $c_J$ may be super polynomial in $d$, in this case even $c_{(0,\dots,0)} = O(\sqrt{d}^d)$.
My question, is there another method to find such $g(w)$? It does not need to be continuous, the important trait is that the bound is not exponential in d.
It is possible if it makes the question easier to assume that the target polynomial is of the form $p(x) = \sum_{i=0}^k \alpha_i \langle w^*,x \rangle ^i$ for some fixed $w^* \in \mathbb{R}^d$


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.