Average best \(m\)-term approximation
type: Item
instance of: scholarly article
title: Average best \(m\)-term approximation
zbMATH Open document ID: 1262.41016
author: Jan Vybíral
published in: Constructive Approximation
publication date: 2012-08-13T00:00:00Z
full work available at URL: https://arxiv.org/abs/1009.1751
review text: 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.
Mathematics Subject Classification ID: 41A46
Mathematics Subject Classification ID: 41A50
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 60B11
Mathematics Subject Classification ID: 94A12
zbMATH DE Number: 6065201
zbMATH Keywords: nonlinear \(m\)-term approximation
zbMATH Keywords: sparse vectors
zbMATH Keywords: average width
zbMATH Keywords: cone measure
zbMATH Keywords: surface measure
reviewed by: Yuri A. Brudnyi
MaRDI profile type: Publication
OpenAlex ID: W2963281168
arXiv ID: 1009.1751
cites work: Q5558293
cites work: The central limit problem for convex bodies
cites work: The subindependence of coordinate slabs in \(l_p^n\) balls
cites work: Q4424436
cites work: A probabilistic approach to the geometry of the \(\ell^n_p\)-ball
cites work: Q4039801
cites work: Morphological Component Analysis: An Adaptive Thresholding Strategy
cites work: Q5491042
cites work: Decoding by Linear Programming
cites work: Stable signal recovery from incomplete and inaccurate measurements
cites work: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
cites work: Compressed sensing and best 𝑘-term approximation
cites work: Optimal approximation of elliptic problems by linear and nonlinear mappings. I
cites work: Q4215356
cites work: Compression of Wavelet Decompositions
cites work: Compressed sensing
cites work: Q4112551
cites work: The dimension of almost spherical sections of convex bodies
cites work: Q3078294
cites work: A mathematical introduction to compressive sensing
cites work: The octahedron is badly approximated by random subspaces
cites work: On the minimum of several random variables
cites work: Compressible Distributions for High-Dimensional Statistics
cites work: Dictionary Identification—Sparse Matrix-Factorization via $\ell_1$-Minimization
cites work: Q4349924
cites work: The concentration of measure phenomenon
cites work: Q3997990
cites work: Q4328334
cites work: Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
cites work: The surface measure and cone measure on the sphere of ℓ_{𝑝}ⁿ
cites work: Projecting the surface measure of the sphere of \({\ell}_p^n\)
cites work: POLYGONAL APPROXIMATION OF FUNCTIONS OF TWO VARIABLES
cites work: Approximate independence of distributions on spheres and their stability properties
cites work: Q3078293
cites work: On the Volume of the Intersection of Two L n p Balls
cites work: Nonlinear methods of approximation
DOI: 10.1007/S00365-012-9163-1
description: scientific article; zbMATH DE number 6065201