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.

• Do you want to have a closed form solution or do you just wanna solve this (numerically) on a computer? Numerically I'm pretty sure you can get good results by considering the convex optimization problem $$\min_{k \in \mathbb{R}^m} \sum_{i=1}^n \langle \hat{v}_{i+1} - \hat{v}_{i}, k \rangle^2$$ where $\hat{v}_i := \frac{v_i}{\lVert v_i \rVert}$, your sequence is of length $n$ and each vector has $m$ components. Note that this doesn't use any of the additional structure you have. EDIT: actually you might be able to just solve this directly without too much trouble. It looks quite tame. Jan 10, 2023 at 14:46
• Numerical solution will suffice. Jan 10, 2023 at 14:59

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}$$.
• Does $d_i < d_{i+1}$ hold if we allow $k$ to have negative entries? Jan 10, 2023 at 15:56
• @Andrey No, not necessarily. I think that this approach can be modified to get an optimal $k$ with non-negative entries, however Jan 10, 2023 at 15:58