# 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 $\displaystyle V = v_{1}, v_{2}, ..., v_{n}$ and a set of vectors $\displaystyle A = \alpha_{1}, \alpha_{2}, ..., \alpha_{k}$ where all $\displaystyle \alpha_{i}$ can be expressed as a convex combination of the vectors in $\displaystyle V$:

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

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

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

Suppose that the vectors in $\displaystyle 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 $\displaystyle A$
2) find $\displaystyle \alpha_{2}$ by comparing the distance of $\displaystyle \alpha_{1}$ to all vactors in $\displaystyle 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 $\displaystyle V$ do not change and that the vectors in $\displaystyle A$ are expressed as convex combination.

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

kind regards,
Andreas