On coverings of ellipsoids in Euclidean spaces
- Author(s): Dumer, Ilya
- Pinsker, M S
- Prelov, V V
- et al.
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 epsilon-entropy, which is the logarithm of the minimum number of the balls of radius e needed to cover this ellipsoid. A tight asymptotic bound on the epsilon-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\epsilon. The results can be applied to vector quantization performed when data streams from different sources are bundled together in one block.