Modulation Spaces and the Curse of Dimensionality
Rahul Parhi, Michael A. Unser · 2023
We investigate the L2-error of approximating functions in the modulation spaces $M_{1,1}^s\left({{{\mathbb{R}}^d}}\right),s \geq \,0$, by linear combinations of Wilson bases elements. We analyze a nonlinear method for approximating functions in $M_{1,1}^s\left({{{\mathbb{R}}^d}}\right)$ with N-terms from a Wilson basis. Its L2-approximation error decays at a rate of ${N^{ - \frac{1}{2} - \frac{g}{{2d}}}}$. We show that this rate is optimal by proving a matching lower bound. Remarkably, these rates do not grow with the input dimension d. Finally, we show that the best linear L2-approximation error cannot decay faster than ${N^{ - \frac{g}{{2d}}}}$. This shows that linear methods, contrary to the nonlinear ones, necessarily suffer the curse of dimensionality in these spaces.