Distance between a point and a m-dimensional space in n-dimensional space ($m<n$)

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.

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(v_1,\ldots,v_k)=\det \begin{Vmatrix} \langle v_1,v_1 \rangle & \ldots & \langle v_1,v_k \rangle\\ \vdots & \ddots & \vdots\\ \langle v_k,v_1 \rangle & \ldots & \langle v_k,v_k \rangle \end{Vmatrix} $$ is a Gram determinant.

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

• solve the normal equations;
• perform a QR decomposition of A, either using Gram-Schmidt or Householder reflections;
• use the Moore–Penrose pseudoinverse, determined by singular value decomposition.

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