Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness

DOI10.1016/J.JCO.2018.05.003MaRDI QIDQ722765zbMATH OpenOpenAlexFDO

Authors Sjoerd Dirksen, Tino Ullrich

Publication date 27 July 2018

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.06781

zbMATH Keywords

Gelfand numbers\(\ell_p(\ell_q)\)-spacesBesov spaces with small mixed smoothnessBlock sparsityCompressed sensingSparsity-in-levels

Mathematics Subject Classification ID

Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Abstract: We consider the problem of determining the asymptotic order of the Gelfand numbers of mixed-(quasi-)norm embeddings $el{l}_p^b(el{l}_q^d)hookrightarrowel{l}_r^b(el{l}_u^d)$ given that $pleqr$ and $qlequ$, with emphasis on cases with $pleq1$ and/or $qleq1$. These cases turn out to be related to structured sparsity. We obtain sharp bounds in a number of interesting parameter constellations. Our new matching bounds for the Gelfand numbers of the embeddings of $el{l}_1^b(el{l}_2^d)$ and $el{l}_2^b(el{l}_1^d)$ into $el{l}_2^b(el{l}_2^d)$ imply optimality assertions for the recovery of block-sparse and sparse-in-levels vectors, respectively. In addition, we apply the sharp estimates for $el{l}_p^b(el{l}_q^d)$-spaces to obtain new two-sided estimates for the Gelfand numbers of multivariate Besov space embeddings in regimes of small mixed smoothness. It turns out that in some particular cases these estimates show the same asymptotic behaviour as in the univariate situation. In the remaining cases they differ at most by a $loglog$ factor from the univariate bound.

Recommendations

• Gelfand numbers of embeddings of mixed Besov spaces
• Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness
• Gelfand and Kolmogorov numbers of embedding of radial Besov and Sobolev spaces
• Bernstein numbers of embeddings of isotropic and dominating mixed Besov spaces
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)

Cites work

• scientific article; zbMATH DE number 4015366 (Why is no real title available?)
• scientific article; zbMATH DE number 3115215 (Why is no real title available?)
• scientific article; zbMATH DE number 3129734 (Why is no real title available?)
• scientific article; zbMATH DE number 3133919 (Why is no real title available?)
• scientific article; zbMATH DE number 3877692 (Why is no real title available?)
• scientific article; zbMATH DE number 3814227 (Why is no real title available?)
• scientific article; zbMATH DE number 4061904 (Why is no real title available?)
• scientific article; zbMATH DE number 4080153 (Why is no real title available?)
• scientific article; zbMATH DE number 3676637 (Why is no real title available?)
• scientific article; zbMATH DE number 3743876 (Why is no real title available?)
• scientific article; zbMATH DE number 193625 (Why is no real title available?)
• scientific article; zbMATH DE number 3551404 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 3996455 (Why is no real title available?)
• A lower estimate for entropy numbers
• A mathematical introduction to compressive sensing
• A unified framework for high-dimensional analysis of \(M\)-estimators with decomposable regularizers
• Atoms of all channels, unite! Average case analysis of multi-channel sparse recovery using greedy algorithms
• Best \(m\)-term approximation and Sobolev-Besov spaces of dominating mixed smoothness -- the case of compact embeddings
• Block-Sparse Signals: Uncertainty Relations and Efficient Recovery
• Breaking the coherence barrier: a new theory for compressed sensing
• Capturing ridge functions in high dimensions from point queries
• Carl's inequality for quasi-Banach spaces
• Compressed sensing
• Concentration inequalities. A nonasymptotic theory of independence
• Constructive sparse trigonometric approximation for functions with small mixed smoothness
• Counting via entropy: new preasymptotics for the approximation numbers of Sobolev embeddings
• Entropy and sampling numbers of classes of ridge functions
• For most large underdetermined systems of linear equations the minimal 𝓁₁‐norm solution is also the sparsest solution
• Function spaces with dominating mixed smoothness
• Gelfand numbers and widths
• Gelfand numbers of embeddings of mixed Besov spaces
• Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
• Kolmogorov and linear widths of the weighted Besov classes with singularity at the origin
• Kolmogorov widths in finite-dimensional spaces with mixed norms
• Learning functions of few arbitrary linear parameters in high dimensions
• Linear widths of Hölder-Nikol'skij classes of periodic functions of several variables
• Locally bounded linear topological spaces
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?
• On the Absence of Uniform Recovery in Many Real-World Applications of Compressed Sensing and the Restricted Isometry Property and Nullspace Property in Levels
• One-bit compressed sensing by linear programming
• Optimal sampling recovery of mixed order Sobolev embeddings via discrete {L}ittlewood--{P}aley type characterizations
• Optimization with sparsity-inducing penalties
• Oracle inequalities and optimal inference under group sparsity
• Recovery Algorithms for Vector-Valued Data with Joint Sparsity Constraints
• Robust 1-bit Compressed Sensing and Sparse Logistic Regression: A Convex Programming Approach
• Robust Recovery of Signals From a Structured Union of Subspaces
• Stable signal recovery from incomplete and inaccurate measurements
• Statistics for high-dimensional data. Methods, theory and applications.
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• The benefit of group sparsity
• The product of octahedra is badly approximated in the \(\ell_{2,1}\)-metric
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Uniform recovery of fusion frame structured sparse signals
• Weyl numbers of embeddings of tensor product Besov spaces
• Widths of Hölder-Nikol'skij classes and finite-dimensional subsets in spaces with mixed norm
• Widths of embeddings in function spaces

Cited in

(11)

• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• Estimates for the Kolmogorov widths of an intersection of two balls in a mixed norm
• Sampling numbers of smoothness classes via \(\ell^1\)-minimization
• Entropy numbers of finite dimensional mixed-norm balls and function space embeddings with small mixed smoothness
• Optimal sampling recovery of mixed order Sobolev embeddings via discrete {L}ittlewood--{P}aley type characterizations
• The restricted isometry property of block diagonal matrices for group-sparse signal recovery
• Monte Carlo methods for uniform approximation on periodic Sobolev spaces with mixed smoothness
• Gelfand numbers of embeddings of Schatten classes
• Gelfand numbers of embeddings of mixed Besov spaces
• Kolmogorov widths of anisotropic function classes and finite-dimensional balls
• Kolmogorov widths of the intersection of two finite-dimensional balls in a mixed norm

This page was built for publication: Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722765)