For a vector sequence find a vector that produces low discrepancy dot products I have a finite sequence $\{v_i\}$ of vectors in lexicographic order.
Elements of vectors are non-negative numbers (integers, if it is important) e.g.:
$(1, 0, 3),\space (1, 2, 6),\space (1, 7, 0),\space (3, 0, 5),\space (4, 3, 1),\space ...$
For some vector $k$ with non-negative elements it is possible to produce an ordered sequence $\{d_i\}, d_i < d_{i+1}$ of differences between adjacent normalized dot products of $v_i$ and $k$:
$d_i = \Large\frac{v_{i+1}\cdot k^T}{|v_{i+1}||k|} - \frac{v_{i}\cdot k^T}{|v_{i}||k|}$
I want to find $k$ that produces a low discrepancy $\{d_i\}$.
In other words I want a solution for any of the following problems or any similar problem:

*

*find $k$ that maximizes $d_i$ : $d_i \rightarrow \max$

*find $k$ that maximizes expectation of $d_i$ : $\mathbb{E}[d_i] \rightarrow \max$

*for a given $d_{min}$, find $k$ that satisfies $d_i > d_{min}$
Also I'd like to know if there is a specific name for this problem.
 A: First of all, note that nothing about the result is altered (i.e. the resulting $d_i$'s are the same) when each $v_i$ is replaced with the corresponding unit vector $u_i =  v_i/|v_i|$ and $k$ is replaced with the corresponding unit vector $\hat k = k/|k|$. So, without loss of generality, we can replace each $v_i$ with $u_i$ and restrict our search to unit vectors $k$. Note that $d_i = (u_i - u_{i+1})k^\top$. Suppose that the $u_i$ are numbered $u_0,u_1,\dots,u_n$. Let $m$ denote the number of entries in each of the vectors.
As the comment on your question notes, one reasonable question to solve in order to obtain "low-discrepancy" in some sense is
$$
\min \sum_{i=1}^n ((u_i - u_{i-1}) k^\top)^2  \quad \text{s.t.} \quad k \in \Bbb R^m, |k| = 1,
$$
noting that $d_i = (u_i - u_{i-1})k^\top$. If you prefer, we aim to minimize $\Bbb E[d_i^2]$, assuming that $i \in \{1,2,\dots,n\}$ is chosen in a uniformly random fashion.
If we allow $k$ to have negative entries, this can be framed as the solution to a well-known linear algebra problem. In particular, we can rewrite
\begin{align}
f(k) &= \sum_{i=1}^n ((u_i - u_{i-1}) k^\top)^2 = 
\sum_{i=1}^n k(u_i - u_{i-1})^\top (u_i - u_{i-1}) k^\top
\\&= 
k\underbrace{\left[\sum_{i=1}^n (u_i - u_{i-1})^\top (u_i - u_{i-1}) \right]}_{M}k^\top.
\end{align}
In other words, given the symmetric (and positive definite) matrix $M = \sum_{i=1}^n (u_i - u_{i-1})^\top (u_i - u_{i-1})$, we're looking for the unit vector $k$ that minimizes $kMk^\top$. The Rayleigh Ritz theorem gives us an easy way to both minimize and maximize the objective function $f$: when $k$ is an eigenvector of $M$ associated with the smallest eigenvalue of $M$, the function is minimized. When $k$ is an eigenvector of $M$ associated with the largest eigenvalue of $M$, the function is maximized.
Let $w$ denote a unit eigenvector of $M$ associated with the smallest eigenvalue. With this solution to this relaxed version of the problem in mind, an interesting choice of $k$ to consider is the closest non-negative unit vector to $w$. Let $w(1),\dots,w(m)$ denote the entries of $w$. Let $w_+$ denote the vector whose entries are $w_+(i) = w(i)$ where $w(i) \geq 0$ and $w_+(i) = 0$ otherwise. Then, the closest non-negative unit-vector $k$ to this $w$ is given by $k = w_+/|w_+|$. Note that since we can also replace $w$ with $-w$, we can guarantee that $|w_+|^2 \geq \frac 12$ (since $|w|^2 = |w_+|^2 + |(-w)_+|^2$).
With that, we can guarantee that $f(k) \leq \frac{\lambda_{\min} + \lambda_{\max}}{2}$.
