Let $n\in\mathbb{N}^+$, and let $\mathcal{S}_n=\{x\in\mathbb{C}^n \text{ s.t. }||x||=1\}$ be the $n$-sphere.
Let also $v_1,\cdots,v_k \in \mathcal{S}_n$ be a set of $k$ vectors on that $n$-sphere.
I am then trying to quantify how well these $k$ vectors approximate all the possible directions in $n$ dimensions, in the following sense :
For $u \in \mathcal{S}^n$, I want
$\max_{i \in \{1,\cdots,k\}}|\langle u | v_i\rangle|$
to be as high as possible. I am interested in this criteria since ideally I'd like for any $u\in\mathcal{S}^n$ to be equal to one of the $v_i$ (impossible by definition), and one necessary condition for this would be that, for that $i$, $|\langle u | v_i\rangle| = 1$. Since I am looking to see how well the $v_i$ behave in the worst case on that regard, I am actually interested in finding the worst direction $u\in\mathcal{S}^n$ :
$\min_{u\in\mathcal{S}^n}\max_{i \in \{1,\cdots,k\}}|\langle u | v_i\rangle|$
Equivalently, we can optimize on the square of the criterion, which leads us to the following minimization problem :
$\min_{u\in\mathbb{C}^n}\max_{i \in \{1,\cdots,k\}}|\langle u | v_i\rangle|^2$ under the constraint $||u||^2=1$
It is therefore a non-convex quadratic program that sadly cannot be solved exactly in general. I have therefore two questions :
Am I missing a way to solve this analytically ? Maybe with a geometrical approach ? Because it seems like it could be the case for n=2 for instance, but I'm not sure it can be generalized to any $n>2$
Is there a way to compute tight bounds for this problem ? If I can't find the optimal solution, finding good bounds could be alternatively of high interest for me. I tried to write the Lagrangian relaxation and reached the (hopefully correct...) conclusion that it can only produce the trivial bound "0". Then, I read that the Lagrangian relaxation is equivalent to the Schur's relaxation for non-convex QCQPs, so this looks like a dead-end. Are there any directions to investigate ?
Thank you !