Rounding of semidefinite programms using simplex

24 Views Asked by At

Suppose we have two unit vectors, $\mathbf{a}_1$ and $\mathbf{a}_2$, where $\mathbf{a}_1,\mathbf{a}_2\in\mathbb{R}^N$ and $\|\mathbf{a}_1\|_2 = \|\mathbf{a}_2\|_2 =1$. Also, we have their inner product as $\langle\mathbf{a}_1,\mathbf{a}_2\rangle = \cos{\theta}$. Consider a random equilateral $(K-1)$-simplex $\Sigma_{K-1}$, $2\leq K<N$, that has vertices at $\mathbf{z}_1,\dots,\mathbf{z}_K$ and has the centroid at $C_{K-1}=\sum_{k=1}^K \mathbf{z}_k/ K$. Let the vector from centroid to the $k$-th vertex as $\mathbf{v}_k = \mathbf{z}_k-C_{K-1}$, $\forall k$ (for simplicity, we assume that $\|\mathbf{v}_k\|_2=1,\forall k$). Define the following two vertex indices of the simplex for $\mathbf{a}_1$ and $\mathbf{a}_2$ respectively as \begin{equation} \begin{aligned} &k_1 = \arg \max_k \langle\mathbf{a}_1,\mathbf{v}_k\rangle \ ,\\ &k_2 = \arg \max_k \langle\mathbf{a}_2,\mathbf{v}_k\rangle \ . \end{aligned} \end{equation} What is the probability of $k_1=k_2$? Can this probability be expressed in $\theta$ and $K$? Thanks in advance!