Paper Info
Title
Gelfand numbers related to structured sparsity and Besov space embeddings with small mixed smoothness.
Abstract
We consider the problem of determining the asymptotic order of the Gelfand numbers of mixed-(quasi-)norm embeddings ℓpb(ℓqd)↪ℓrb(ℓud) given that p≤r and q≤u, with emphasis on cases with p≤1 and/or q≤1. 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 ℓ1b(ℓ2d) and ℓ2b(ℓ1d) into ℓ2b(ℓ2d) imply optimality assertions for the recovery of block-sparse and sparse-in-levels vectors, respectively. In addition, we apply our sharp estimates for ℓpb(ℓqd)-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 behavior as in the univariate situation. In the remaining cases they differ at most by a loglog factor from the univariate bound.
Year
DOI
Venue
2018
10.1016/j.jco.2018.05.003
Journal of Complexity
Keywords
DocType
Volume
Gelfand numbers, ℓp(ℓq)-spaces,Compressed sensing,Block sparsity,Sparsity-in-levels,Besov spaces with small mixed smoothness
Journal
48
ISSN
Citations 
PageRank 
0885-064X
2
0.41
References 
Authors
17
2
Name
Order
Citations
PageRank
Sjoerd Dirksen1322.75
tino ullrich2143.18