# Thread: optimized distance betwee vectors using their linear combinations ?

1. ## optimized distance betwee vectors using their linear combinations ?

Hi,

given a set of fix vectors $V = v_{1}, v_{2}, ..., v_{n}$ and a set of vectors $A = \alpha_{1}, \alpha_{2}, ..., \alpha_{k}$ where all $\alpha_{i}$ can be expressed as a convex combination of the vectors in $V$:

$
a_{i} = \lambda_{i,1} \cdot v_{1} + \lambda_{i,2} \cdot v_{2} + ... + \lambda_{i,n} \cdot v_{n}
$

where $\lambda_{i,j}$ is the j'th coefficient of vector i.
Also $\lambda_{i,1} + \lambda_{i,2} + ... + \lambda_{i,n} = 1$ and $\lambda_{i,j} >= 0$

Now the mission is: given a vector $\alpha_{1} \in A$, find the vector $\alpha_{2} \in A$ which has the smallest distance to $\alpha_{1}$ using the squared euclid distance $\| \alpha_{1} - \alpha_{2} \|^{2}$(and of course $\alpha_{1}$ != $\alpha_{2}$).

Suppose that the vectors in $A$ are stored in their convex combination form and that the combination is not calculated yet.

An easy but expensive way to solve the problem is:
1) calculate the convex combinations for all vectors in $A$
2) find $\alpha_{2}$ by comparing the distance of $\alpha_{1}$ to all vactors in $A$ and picking the one with the smallest distance.

Is there an alternative way to efficiently calculate this (from a practical + implementation point of view) ? Probably by respecting the fact that the vectors in $V$ do not change and that the vectors in $A$ are expressed as convex combination.

(We assume that all vectors are in $R^{n}$.)

kind regards,
Andreas