# A Polarity Capturing Sphere for Word to Vector Representation
## Appendix A Proof of Theorem 1: Convergence of the Algorithm  
When we consider a particular word, we apply Equations (9) and (11), in order to tune the position of the word's designated vector. To prove that the repeated application of this step (for one word after another) leads to convergence, we show that each application leads to a non-increase of the error function Equation (1). Since this error function is bounded from below by zero, the algorithm converges to some limit of the error function.  
This formulation of an optimization falls under the form of optimization of a quadratic function on the sphere, i.e., subject to the solution lying on the sphere \(\|x\|^{2}=r^{2}\). It has been studied in detail by [62; 63; 64; 65], as it is applied in types of optimization methods called trust region methods of nonlinear optimization.  
Let the errors before and after applying (9) be \(E_{1}\) and \(E_{2}\) respectively (we mean the errors given by Equation (1)). Since both before and after the update the vector \(x_{k}\) would be normalized to become unit length, we can use \(V\) (given in (3), (4)) in place of \(E\). The subtracted term \(\lambda\big{(}{x_{k}}^{T}x_{k}-1\big{)}\) will equal zero in both cases, so it will not impact it. Therefore  
\[E_{2}-E_{1} = V_{2}-V_{1} \tag{11}\] \[= x_{k}{}^{T}Ax_{k}-2b^{T}x_{k}-\left[{x_{k}^{\prime}}^{T}Ax_{k}^{ \prime}-2b^{T}x_{k}^{\prime}\right]\]  
where \(x_{k}^{\prime}\) is the word vector before the update. After applying Equation (9) it becomes \(x_{k}\), given by:  
\[x_{k} = A^{-1}b \tag{12}\] \[= \big{(}A^{\prime}-\lambda I\big{)}^{-1}b\]where the last step follows from the definitions of \(A\) and \(A^{\prime}\) (5) and (12). As mentioned, \(\lambda\) is determined from:  
\[b^{T}\big{[}A^{\prime}-\lambda I\big{]}^{-2}b=1 \tag{10}\]  
According to [62; 63; 64; 65] Equation (10) has at most \(2N\) solutions for \(\lambda\), where \(N\) is the dimension of the vector \(x_{k}\), with the smallest and largest solutions corresponding to respectively the minimum and the maximum of the optimization problem. The solutions in the middle correspond to the saddle points. The smallest solution obeys the condition \(\lambda\leq\) all eigenvalues of \(A^{\prime}\)[64], which means that \(A^{\prime}-\lambda I\) is positive semi-definite (because the eigenvalues of \(A^{\prime}-\lambda I\) equal the eigenvalues of \(A^{\prime}\) minus \(\lambda\)). Because of these conditions, the aforementioned works of [62; 63; 64; 65] prove that \(E_{2}-E_{1}\leq 0\).  
Irrespective of their proof, we formulated a simplified proof, given as follows: Substituting (11) into (12), we get  
\[E_{2}-E_{1} = b^{T}A^{-1}AA^{-1}b-2b^{T}A^{-1}b-\left[x_{k}^{\prime}Tx_{k}^{ \prime}-2b^{T}x_{k}^{\prime}\right] \tag{12}\] \[= -b^{T}A^{-1}b-\left[x_{k}^{\prime}Tx_{k}^{\prime}-2b^{T}x_{k}^{ \prime}\right]\] \[= -\Big{[}Ax_{k}^{\prime}-b\Big{]}^{T}A^{-1}\Big{[}Ax_{k}^{\prime }-b\Big{]}\]  
The latter line follows by expanding the two multiplied brackets. We find that it equals the expression in the preceding line. Since the matrix \(A=A^{\prime}-\lambda I\), and the latter is shown to be positive semi-definite,  
\[E_{2}-E_{1}\leq 0 \tag{13}\]  
because any quadratic form \(y^{T}Qy\geq 0\) for any positive semi-definite matrix \(Q\) and any vector \(y\). So the error reduces after each iteration, or stays the same. After applying the update for every word, and having a complete cycle where the error does not reduce any more for any of the vectors, convergence of the algorithm is signified.