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\}$.

  • $\begingroup$ Can you answer this for $k = 1$? $\endgroup$ Commented Aug 6, 2021 at 22:14
  • $\begingroup$ When $k=1$, the class of 1-norm balls becomes the class of intervals whose VC Dimension is 2. $\endgroup$ Commented Aug 7, 2021 at 6:20
  • $\begingroup$ Does the answer change for larger $k$? $\endgroup$ Commented Aug 7, 2021 at 13:12
  • $\begingroup$ 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. $\endgroup$ Commented Aug 7, 2021 at 13:28
  • $\begingroup$ What happens for $k=3$? $\endgroup$ Commented Aug 7, 2021 at 13:30


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.