3
$\begingroup$

Let $C$ be a family of convex sets in $\mathbb{R}^d$ and assume further that $C$ is closed under translation: for all $A\in C$ and $x\in\mathbb{R}^d$, we have $A+x\in C$.

Let $P:\mathbb{R}^d\to\mathbb{R}^k$ be a linear projection and define $C'$ to be the image of $C$ (elementwise) under $P$. Question: is it ever the case that the VC-dimension of $C'$ is greater than that of $C$?

$\endgroup$

1 Answer 1

3
$\begingroup$

Yes, of course.

Claim 1: the VC dimension of translations of a fixed triangle on the plane is at most $3$.

Proof: Take any $4$ points consider the $3$ points lying farthest in the directions of the outer unit normals to the triangle sides. If you cover them all, you have to cover the fourth point as well, so no 4-shattering here.

Claim 2: The VC dimension of the family of all triangles on the plane is at least $7$.

Proof: Consider the vertices of a regular heptagon. If you have a subset of cardinality $\le 3$, take its convex hull and add extra vertices nearby if necessary. If you have a subset of cardinality $\ge 4$, cut off its complement by 3 lines (note that adjacent vertices can be cut off together by a single line, so we will never be forced to make an "outside" triangle in this construction).

Claim 3: The VC dimension of the set of all intervals on the plane parallel to some fixed direction is at most $2$.

Proof: Take any $3$ points. If they do not lie on a line in that direction, there is no chance to cover them all. If they do, any interval covering the two extreme points has to cover the middle one.

Now choose some set of $2^7$ triangles shattering the $7$ points above, a line $L$ in the original plane and create $2^7$ different planes in the space passing through $L$. For each triangle choose its own plane and take its pre-image under the projection from that plane to the original one.

Claim 4: The VC dimension of the resulting family is at most $5$.

Proof: Take any $6$ points in the space. If they do not lie in a plane parallel to one of the chosen ones, there is no way to cover them all. Otherwise, we have the family of translates of a fixed triangle in that plane plus at most the family of all intervals in the direction of $L$. The total number of different sets the translates of a fixed triangle can create is at most ${6\choose 0}+{6\choose 1}+{6\choose 2}+{6\choose 3}$ (I wish I could remember the name of the corresponding theorem; as it is, I can just provide the proof upon request). Similarly, the intervals can create only ${6\choose 0}+{6\choose 1}+{6\choose 2}$ different subsets. Those bounds sum to $2^6$, but the empty set has obviously been counted twice, so we are at least one set too short for $6$-shattering.

This construction is a bit degenerate, of course, but you can see the nature of the corresponding effect from it.

$\endgroup$
12
  • $\begingroup$ I'm trying to follow Claim 4. What is the "resulting family"? A set of 2^7 vertical prisms with triangular cross-section? $\endgroup$ Commented Jul 23, 2017 at 9:29
  • 1
    $\begingroup$ The theorem whose name you couldn't remember is the Sauer-Shelah lemma. en.m.wikipedia.org/wiki/Sauer%E2%80%93Shelah_lemma $\endgroup$ Commented Jul 23, 2017 at 11:38
  • 1
    $\begingroup$ @Aryeh: ...or maybe we could go right away and ask for the case where $C$ is closed under all affine transformations $\endgroup$ Commented Jul 23, 2017 at 14:58
  • 1
    $\begingroup$ @Aryeh: Ok. Invertible affine transformations $\endgroup$ Commented Jul 23, 2017 at 17:58
  • 1
    $\begingroup$ @Aryeh: "Dilations" preserve angles. They don't let you get an ellipse from a circle, for example. en.m.wikipedia.org/wiki/Homothetic_transformation $\endgroup$ Commented Jul 23, 2017 at 18:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .