1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – SV-97
    Jan 10, 2023 at 14:46
  • $\begingroup$ Numerical solution will suffice. $\endgroup$ Jan 10, 2023 at 14:59

1 Answer 1

1
$\begingroup$

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}$.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .