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

DOI10.1016/J.JCO.2018.05.003zbMATH Open1470.41025arXiv1702.06781OpenAlexW2592060370MaRDI QIDQ722765FDOQ722765

Authors: Sjoerd Dirksen, Tino Ullrich 

Publication date: 27 July 2018

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

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.

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

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\)

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)

Cites Work

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

Cited In (11)

• Estimates for the Kolmogorov widths of an intersection of two balls in a mixed norm
• The Gelfand widths of \(\ell_p\)-balls for \(0 < p \leq 1\)
• 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)