Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to find a method with a low computational cost to compute the distance of a point $P$ and a space $S$ that is defined by the origin $O$ and $m$ vectors $v_1, v_2, ..., v_m$ in an $n$-dimensional space ($m<n$). The vectors are not restricted by any means other than that they are not 0. Furthermore, I would like to identify the point in $S$ that is closest to $P$.

This calculation is part of a 'fitting function' for a machine learning problem and thus has to be executed rather often and should be fast. The input to the function is as defined above, $P$ and $v_1, v_2, ..., v_m$. This is just for context and I am happy for a mathematical solution and can of course do the implementation myself.

Thanks in advance and please let me know if I need to specify anything in more detail.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

I think the most efficient way is to compute projection $\mathrm{Pr}_L(p)$ of vector $p$ on linear subspace $L$ spanned by vectors $v_1,\ldots,v_m$ and the find length of the vector $p-\mathrm{Pr}_L(p)$. Using modified Gramm-Schmidt orthogonalization process you can find orthogonal basis of $L$, call it $\{e_1,\ldots,e_m\}$ and then compute $$ \mathrm{Pr}_L(p)=\sum\limits_{i=1}^m \langle p,e_i\rangle e_i $$ The desired distance is $$ d(p,L)=\left\Vert p-\sum\limits_{i=1}^m \langle p,e_i\rangle e_i\right\Vert $$

There is an elegant but useless for your purposes formula of the distance $d(p,L)$ from point $p\in\mathbb{R}^n$ to linear subspace $L$ spanned by vectors $v_1,\ldots, v_m$. It can be found by the formula $$ d^2(p,L)=\frac{G(v_1,\ldots,v_m,p)}{G(v_1,\ldots,v_m)}\tag{1} $$ where $$ G(x_1,\ldots,x_k)=\det \begin{Vmatrix} \langle v_1,v_1 \rangle & \ldots & \langle v_1,v_k \rangle\\ \ldots & \ldots & \ldots\\ \langle v_k,v_1 \rangle & \ldots & \langle v_k,v_k \rangle \end{Vmatrix} $$ is a Gram determinant.

share|improve this answer
    
Thanks for the answer. I hope to have some time today to work on the implementation and might be back with some questions. –  simmmons Jul 23 '12 at 7:33
    
@simmmons Fell free to ask questions, hope I can help you. Also I recommend you to ask this question on scicomp.stackexchange.com –  userNaN Jul 23 '12 at 7:48
    
Thanks a lot, I was able to implement your function but I do have an additional problem: I want to restrict the above problem where the space is defined by $X=t_1\cdot v_1 + ... + t_m\cdot v_m$ and $t_i\ge 0$. I do this by finding the point with the closest distance $P_c$ and solving the set of linear equations $Lt=P_c$ to find all $t$. Then I remove all vectors from $L$ where the corresponding $t$ is negative and calculate the distance again. I do this iteratively until there is no negative $t$ any more. This seems to be a rather wasteful computation, do you have a better idea? –  simmmons Jul 23 '12 at 16:25
    
What to do if subspace is translated? Say, (m - 1)-dimensional subspace is defined by a set $S:|S| = m \leq n$ of its points? –  Orient Dec 13 at 18:09
    
@Orient, clearly, you can simultaneously shift this subspace and vector p by some vector of this subspace. Thus you reduce this problem to the one discussed above. –  userNaN Dec 13 at 18:53

I'll assume that you're talking about Euclidean distance and that everything that's given is given in terms of Cartesian coordinates in the $n$-dimensional space.

Let $A$ be the matrix whose columns are your vectors $V_i$, and let $b$ be the vector of coordinates of $p$. Then you're looking for a vector $x$ of $m$ coefficients such that $\|Ax-b\|\to\min$.

There are various methods for finding this $x$: you can

Which of these is best may depend on your requirements for speed and accuracy. If your vectors may be linearly dependent or nearly so, I believe the last option is the most numerically stable, whereas otherwise solving the normal equations should be good enough and probably quickest. How best to proceed may also depend on whether $A$ and $b$ are different in each application, or whether you need to find $x$ for many $b$ with the same $A$.

share|improve this answer
    
Doesn't $\displaystyle\sum_{i=1}^m\langle p,e_i\rangle e_i$ as given in Norbert's answer also give the closest point? –  robjohn Jul 22 '12 at 16:50
    
@robjohn: It does; that's an edit he made $24$ seconds after I posted this answer :-) I've adapted the answer. –  joriki Jul 22 '12 at 18:33
    
Thanks for the reply. It definitely helped my understanding of the problem. –  simmmons Jul 23 '12 at 9:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.