For a non-linear feature transform which maps a d-dimensional vector $\vec{x}$ to a 1-dimensional vector $\vec{z}$ as follows:$$\phi_{(k)}(\vec{x})=(1,x_{k})$$where $x_{k}$ is kth coordinate of $\vec{x}$. I need to prove the following:$$d_{vc}(\cup_{k=1}^d H_k) \leq 2(log_2d+1)$$ where $H_k$ is the set of perceptrons in the new feature space and $d_{vc}$ is the VC dimension.Now, I know that the VC dimension of the individual hypothesis $H_{k}=2$. I also know that $$d_{vc}(\cup_{k=1}^d H_k) \leq d-1+\sum_{k=1}^{d} d_{vc}(H_k)=3d-1 $$ as $d_{vc}(H_k)=2$. However, this turns out to be a conservative bound. Could someone help me with the proof?
VC dimension of union of hypothesis
feature extraction