Average best \(m\)-term approximation (Q443892)

Let \(\mu\) be a probability measure on the ball \(\| x\|_{\ell^n_p}\leq 1\), \(0\leq p\leq\infty\), where \(\| x\|_0:= \operatorname{card}(\operatorname{supp}x)\). Best nonlinear \(m\)-term approximation of \(x\in \ell^n_q\) is given by \[ \sigma_m(f)_q:= \inf\{\| x-y\|_{\ell^n_q};\| y\|_0\leq 1\}. \] The \(\mu\)-average measure of this object over a \(p\)-simplex \[ \Delta^n_p:= \Biggl\{x\in\mathbb{R}^n;\Biggl\{\sum^n_{j=1} x^p_i\Biggr\}^{1/p}= 1\Biggr\}, \] \(0< p\leq\infty\), is then denoted by \(\sigma^{p,q}_m(\mu)\). The author proves one- and two-sided estimates for this with respect to the Lebesgue \(n\)-measure on \([0,1]\times\Delta^n_p\) (cone measure), the Hausdorff \((n-1)\)-measure on \(\partial\Delta^n_p\) (surface measure) and the tensor-product measure. In the first case, the main result is \[ \sigma^{p,\infty}_m(\mu)\leq C_p\Biggl[{\log{e/2\over m+1}\over n}\Biggr]^{1/p} \] which is sharp up to a constant for \(0\leq m/n\leq\varepsilon_p\in (0,1)\). For the surface measure, the upper estimate is restricted to \(m=0\) and gives the bound \(C_p[{\log(n+1)\over n}]^{1/p}\). In the third case, the result is more technically involved. The paper concludes giving some numerical experiments.