optimized distance betwee vectors using their linear combinations ?

**sirandreus** · June 5th 2008, 04:02 AM

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$ :

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

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

Thread: optimized distance betwee vectors using their linear combinations ?

LinkBack

Thread Tools

Display

optimized distance betwee vectors using their linear combinations ?

Similar Math Help Forum Discussions

[SOLVED] Why row vectors equal to linear combination of basis vectors of rowspc(in this case)?

vectors distance

vectors distance and velocity - FP3

Distance between vectors and absolute sum

optimized problem

Search Tags