On Coverings of Ellipsoids in Euclidean Spaces
Ilya I. Dumer, M.S. Pinsker, Vyacheslav Valer'evich Prelov · IEEE Transactions on Information Theory · 2004
The thinnest coverings of ellipsoids are studied in the Euclidean spaces of an arbitrary dimension n. Given any ellipsoid, the main goal is to find its /spl epsiv/-entropy, which is the logarithm of the minimum number of the balls of radius /spl epsiv/ needed to cover this ellipsoid. A tight asymptotic bound on the /spl epsiv/-entropy is obtained for all but the most oblong ellipsoids, which have very high eccentricity. This bound depends only on the volume of the sub-ellipsoid spanned over all the axes of the original ellipsoid, whose length (diameter) exceeds 2/spl epsiv/. The results can be applied to vector quantization performed when data streams from different sources are bundled together in one block.