To address the question of finding dimension-free bounds for the covering number of the unit ball with respect to the Mahalanobis distance, we start by clarifying the setup. Let ( B ) denote the Euclidean unit ball in ( \mathbb{R}^d ), i.e., ( B = { x \in \mathbb{R}^d : |x|_2 \leq 1 } ). The Mahalanobis distance induced by a positive definite matrix ( S ) is ( d_S(x, y) = | S^{-1/2}(...

Short answer

• If S is positive definite (full rank), there is no dimension-free exponent f(S) independent of ε: asymptotically as ε→0 one always has N(ε, B2^d, dS) ≍ c(S) ε−d. In particular, any bound of the form N(ε, B, dS) ≤ C(S) ε−f(S) with f(S) < d fails for small ε. The only “ε–independent” exponent possible is f(S) = rank(S), which equals d when S ≻ 0.

• What you can get (and what is often...

Introduce the linear map
T = S−1/2 .
Because dS (x , y) = ∥T (x–y)∥2 , covering B with dS–balls of radius ε is exactly the same as covering the image

E := T B = {y∈ℝd : y = T x , ‖x‖2 ≤ 1} ⊂ ℝd

with ordinary Euclidean balls of radius ε.
The set E is an ellipsoid; if λ1 , … , λd are the eigen–values of S (0<λ1 ≤⋯≤λd) and r i = 1/√λ i , then after a suitable rotation

E = {y : y1 2 / r1 2 +...

First, observe that covering the Euclidean unit‐ball (B_2^d={x:|x|_2\le1}) in the Mahalanobis metric [ d_S(x,y);=;|S^{-1/2}(x-y)|_2 ] is exactly equivalent to covering the ellipsoid [ E ;=;\bigl{,z\in\R^d : z^T S z\le1\bigr} ;=;{,S^{-1/2}x: x\in B_2^d} ] in the ordinary Euclidean norm. In other words [ N\bigl(\e,;B_2^d,;d_S\bigr) ;=; N\bigl(\e,;E,;...

Recall that the covering number is the smallest number ...

For the Mahalanobis distance

  dS (x ,y)= ‖S–1/2 (x–y)‖2, S≻0 ,

the problem of covering the ordinary Euclidean unit ball

  B2d={x∈ℝd : ‖x‖2 ≤1}

is equivalent to covering the ellipsoid

  E=S–1/2 B2d ={z∈ℝd : z=S–1/2 x , ‖x‖2 ≤1}

with the ordinary Euclidean distance.
Indeed

  N (ε ,B2d ,dS)=N (ε ,E ,‖·‖2). (1)

Hence we have to understand ε–covers of an ellipsoid...

This is an excellent question that combines geometry with analysis of sequences. Let's break down the problem to find the infimum and supremum.

Summary of the Solution

1. Identify the Largest Non-Centre Cell: The question relies on finding the area of the largest cell (excluding the central one for odd ). There is strong evidence and proofs for large that the largest non-central c...

Covering Number and Metric Entropy with Mahalanobis Distance

This is an interesting question about finding dimension-free bounds for covering numbers when using the Mahalanobis distance. Let me provide a thorough analysis.

Understanding the Problem

The question asks about bounding the covering number where:

• is the unit ball in
• $d_S(x,y) = |S^{-...

I'll analyze the covering number of the unit ball with respect to the Mahalanobis distance and explore dimension-free bounds.

Understanding the Setup

The Mahalanobis distance is defined as:

The unit ball with respect to this distance is: