# VC Dimension of the class of $k$-dimensional cross-polytope (1-norm ($l_1$) ball)

What is the VC Dimension of the class of $$k$$-dimensional cross-polytope (1-norm ($$l_1$$) balls)?

A $$k$$-dimensional $$l_1$$ ball with radius $$r\in \mathcal R$$ and center $$\mathbb v\in \mathcal R^k$$ is

$$\{\mathbb x\in\mathcal R^k: ||\mathbb x-\mathbb v||_1\le r\}$$.

Namely, denote $$\mathbb x = [x_1,x_2,...,x_k]$$ and $$\mathbb v = [v_1,v_2,...,v_k]$$, A $$k$$-dimensional $$l_1$$ ball with radius $$r$$ and center $$\mathbb v$$ is

$$\{\mathbb x\in\mathcal R^k, |x_1-v_1|+|x_2-v_2|+...+|x_k-v_k|\le r\}$$.

• Can you answer this for $k = 1$? Commented Aug 6, 2021 at 22:14
• When $k=1$, the class of 1-norm balls becomes the class of intervals whose VC Dimension is 2. Commented Aug 7, 2021 at 6:20
• Does the answer change for larger $k$? Commented Aug 7, 2021 at 13:12
• Yes. When $k=2$, the class of $l_1$ balls is the class of squares whose edges parallel the $[1,1]$ or $[1,-1]$. The VC Dimension of such class of squares is 3. Commented Aug 7, 2021 at 13:28
• What happens for $k=3$? Commented Aug 7, 2021 at 13:30