Duality of metric entropy

DOI10.4007/ANNALS.2004.159.1313MaRDI QIDQ1768032zbMATH OpenOpenAlexWikidataFDO

Authors S. Artstein-Avidan, Vitali Milman, Stanislaw J. Szarek

Publication date 11 March 2005

Published in Annals of Mathematics. Second Series (Search for Journal in Brave)

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

zbMATH Keywords

conjecture of Pietschcovering numbersduality of entropy numbersentropy numbers

Mathematics Subject Classification ID

Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Abstract: For two convex bodies K and T in $R^n$, the covering number of K by T, denoted N(K,T), is defined as the minimal number of translates of T needed to cover K. Let us denote by $K^o$ the polar body of K and by D the euclidean unit ball in $R^n$. We prove that the two functions of t, N(K, tD) and N(D, tK^o), are equivalent in the appropriate sense, uniformly over symmetric convex bodies K in $R^n$ and over positive integers n. In particular, this verifies the duality conjecture for entropy numbers of linear operators, posed by Pietsch in 1972, in the central case when either the domain or the range of the operator is a Hilbert space.

Review text

The covering number, \(N(K,T)\), of convex bodies \(K,T\subset{\mathbb R}^n\), is the smallest number of translates of \(T\) needed to cover \(K\). Let \(B\) denote the Euclidean unit ball in \({\mathbb R}^n\). The main result is the following. There exist constants \(\alpha, \beta>0\) such that for any convex body \(K\subset{\mathbb R}^n\) with \(K=-K\), we have \(N(B,\alpha^{-1} K^\circ)^{1/\beta}\leq N(K,B)\leq N(B,\alpha K^\circ)^\beta\), where \(K^\circ\) is the polar of \(K\). The constants \(\alpha, \beta\) are independent of \(n\) and \(K\). The technique of this paper gives \(\beta=2+\varepsilon\) for any \(\varepsilon > 0\). This solves a special case of a conjecture of Pietsch on entropy numbers of operators and their duals. The introduction of the paper discusses the relationship between the main result and entropy numbers, in particular the conjecture of Pietsch, as well as the uses of covering numbers in information theory and the theory of Gaussian processes.

Recommendations

• More on the duality conjecture for entropy numbers.
• Duality of metric entropy in Euclidean space.
• scientific article; zbMATH DE number 17995
• A remark on two duality relations
• scientific article; zbMATH DE number 4011345

Cited in

(34)

• Estimates of covering numbers
• Duality of metric entropy in Euclidean space.
• An isomorphic version of the slicing problem
• On convexified packing and entropy duality
• Regular random sections of convex bodies and the random quotient-of-subspace theorem
• Mapping properties of Fourier transforms
• Optimal robust mean and location estimation via convex programs with respect to any pseudo-norms
• Entropy numbers of finite-dimensional embeddings
• Gaussian approximation numbers and metric entropy
• On \(\mathcal{Z}_p\)-norms of random vectors
• Near-optimal mean estimators with respect to general norms
• Gelfand numbers and metric entropy of convex hulls in Hilbert spaces
• A remark on two duality relations
• Asymptotic shape of the convex hull of isotropic log-concave random vectors
• scientific article; zbMATH DE number 1574605 (Why is no real title available?)
• scientific article; zbMATH DE number 4011345 (Why is no real title available?)
• scientific article; zbMATH DE number 4011346 (Why is no real title available?)
• Kuelbs-Li inequalities and metric entropy of convex hulls
• scientific article; zbMATH DE number 17995 (Why is no real title available?)
• Convergence guarantees for Gaussian process means with misspecified likelihoods and smoothness
• Spectral Methods for Passive Imaging: Nonasymptotic Performance and Robustness
• Geometry of the \(L_{q}\)-centroid bodies of an isotropic log-concave measure
• Weighted covering numbers of convex sets
• Bounds for entropy numbers for some critical operators
• Metric entropy of high dimensional distributions
• On the Euclidean Metric Entropy of Convex Bodies
• Small ball probabilities for stable convolutions
• Small deviations of stable processes and entropy of the associated random operators
• Entropy pair realization
• Spectral theory for fractal pseudodifferential operators
• Metric entropy duality and the sample complexity of outcome indistinguishability
• Mapping properties of Fourier transforms, revisited
• Entropy extension
• Rough paths analysis of general Banach space-valued Wiener processes

This page was built for publication: Duality of metric entropy

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