# Directional Support Vector Machines
## Appendix A Kernelized Symmetric Directional SVM
### VC Dimension: Proof of Theorem 2  
Before going into the details of the proof of Theorem 2, we need the result presented in Lemma A1. **Lemma A1**. : _Let \(\mathbb{F}=\{\phi_{1},\cdots,\phi_{N}\}\) be a set of square integrable and non-zero functions \(\phi_{i}:\mathbb{I}\subseteq\mathbb{R}\mapsto\mathbb{R}\), where \(\mathbb{I}\) is an interval, that satisfy:_  
\[\int_{\mathbb{I}}\phi_{i}(x)^{2}\
eq 0,\,\forall i,\,\,\int_{\mathbb{I}}\phi_{i} (x)\phi_{j}(x)=0,\,\forall i\
eq j. \tag{11}\]  
_There exists a vector \(\mathbf{x}=(x_{1},...,x_{N})^{\intercal}\in\mathbb{I}^{N}\) such that the matrix:_  
\[\Phi(\mathbf{x})= \begin{pmatrix}\phi_{1}(x_{1})&...&\phi_{N}(x_{1})\\ \vdots&\ddots&\vdots\\ \phi_{1}(x_{N})&...&\phi_{N}(x_{N})\end{pmatrix}  \tag{12}\]  
_has full rank._  
Proof. : We shall prove by contradiction that such \(\mathbf{x}\) actually exists. Suppose that \(\Phi(\mathbf{x})\) is rank deficient for all \(\mathbf{x}\). Then, there exists a function \(\mathbf{v}:\mathbb{I}^{N}\mapsto\mathbb{R}^{N}\) such that:  
\[\Phi(\mathbf{x})\mathbf{v}(\mathbf{x})=\mathbf{0}\text{ and }\mathbf{v}(\mathbf{x})\
eq\mathbf{0},\,\forall \,\mathbf{x}. \tag{13}\]  
Due to the orthogonality of the functions in \(\mathbb{F}\), no non-trivial linear combination of them vanishes identically in \(\mathbb{I}\), and consequently, \(\mathbf{v}\) may not be a constant function. However, if \(\mathbf{v}\) is not constant, there exist distinct vectors \(\mathbf{x}^{(1)},...,\mathbf{x}^{(k)}\) with dimension \(N\) such that no non-zero vector belongs to the null spaces of all the matrices \(\Phi\left(\mathbf{x}^{(1)}\right),...,\Phi\left(\mathbf{x}^{(k)}\right)\). This means that the space generated by the rows of these matrices stacked altogether has dimension \(N\), so we may choose \(N\) linearly-independent rows from this stacked matrix. Since each row is defined by a single element in one of the vectors \(\mathbf{x}^{(1)},...,\mathbf{x}^{(k)}\), choosing linearly-independent rows corresponds to finding a dataset \(\mathbf{x}^{*}\) with size \(N\) such that \(\Phi(\mathbf{x}^{*})\) has full rank, contradicting the initial hypothesis. Now, we may proceed to the proof of Theorem 2. Let \(VC(l)\) denote the VC dimension of the class of classifiers \(l\). Firstly, we are going to prove that \(VC(l)\leq 2N+1\). If we proceed as in the proof of Theorem 1, \(\mathbf{\phi}\) may be defined as a feature space over \(\mathbb{R}^{2N}\), by suppressing all components whose coefficients are zero. Therefore, \(f\) becomes a hyperplane in \(\mathbb{R}^{2N}\), and so, it cannot shatter more than \(2N+1\) data points. Now, it suffices to prove that \(VC(l)\geq 2N+1\). Let us denote the period of \(g\) by \(T\) and consider a dataset with \(\bar{N}=2N\) examples, namely \(\mathbf{x}=(x_{1},...,x_{\bar{N}})^{\intercal}\), where \(0\leq x_{i}<T\), \(\forall i\). Like before, we obtain \(\mathbf{\phi}\) as in the proof of Theorem 1, and we build the \(\bar{N}\times\bar{N}\) matrix \(\Phi\), defined as:  
\[\Phi(\mathbf{x})= \begin{pmatrix}\mathbf{\phi}(x_{1})^{\intercal}\\ \vdots\\ \mathbf{\phi}(x_{\bar{N}})^{\intercal}\end{pmatrix} . \tag{10}\]  
By further defining \(\mathbf{f}(\mathbf{x}|w_{0},\mathbf{w}_{d})=(f(x_{1}|w_{0},\mathbf{w}_{d}),...,f(x_{\bar{N}}|w_ {0},\mathbf{w}_{d}))^{\intercal}\), the following equality is straightforward to check:  
\[\mathbf{f}(\mathbf{x}|w_{0},\mathbf{w}_{d})=w_{0}\oplus\Phi(\mathbf{x})\mathbf{w}_{d}, \tag{11}\]  
where \(\oplus\) denotes the operation of summing the scalar on the left-hand side to every element of the vector on the right-hand side. Let us denote the ground truth label of each \(x_{i}\) as \(y_{i}\in\{-1,1\}\). Because the elements of \(\mathbf{\phi}(x)\) form a set of orthogonal functions, we know from Lemma A1 that there exists a dataset \(\mathbf{x}\) such that \(\Phi(\mathbf{x})\) has full rank. Thus, from now on, assume this condition holds.