Gelfand numbers, 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 ℓ p b (ℓ q d ) → ℓ r b (ℓ u d ) 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 ℓ 1 b (ℓ 2 d ) and ℓ 2 b (ℓ 1 d ) into ℓ 2 b (ℓ 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 ℓ p b (ℓ 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 log log factor from the univariate bound.