Given a set of vectors $V \in \mathbb{R}^n$, is there any algorithm that I can use to find a subset $U \subset V$ of a chosen size $K$ such that the vectors in $U$ are "nearly orthogonal" with each other? By "nearly orthogonal", I mean that for each vector $v_i,v_j \in U$ their dot product $v_i^Tv_j$ is as close to zero as possible? To rephrase it, I am searching for a subset of $V$ of given size where each vectors are "nearly" mutually orthogonal to each other.
So far, my approach has been to brute force it, where, for any given size $K$, I enumerate all possible combinations of vectors in $V$ and calculate their dot products with each other and choose the combination which minimizes the maximum of their mutual dot products. Obviously, this will never scale for a $V$ with large number of vectors. Is there any efficient algorithm for this?
Best Answer
You can solve the problem via mixed integer linear programming as follows. Let binary decision variable $x_i$ indicate whether $i\in U$. Let $z$ represent the maximum absolute value of dot products of pairs of selected vectors. The problem is to minimize $z$ subject to \begin{align} \sum_i x_i &= K \tag1\\ z &\ge |v_i^T v_j| (x_i + x_j - 1) &&\text{for $i < j$}\tag2 \end{align} Constraint $(1)$ forces exactly $K$ vectors to be chosen. Constraint $(2)$ enforces $(x_i \land x_j) \implies z \ge |v_i^T v_j|$.