# Fast projection of multiple points on a line

Assume the following setup, taken from this source.

I will omit the arrows from now on. Then the projection of $v$ onto $s$ is given by \begin{align} proj_v = \frac{ \langle v,s \rangle}{\langle s,s\rangle} s \end{align}

I have a simulation, where I want to compute the projection of multiple points onto one line. Assume, that my points can be reached via $v_1,v_2,...,v_N$. Then define $V=(v1,...,v_N)\in \mathbb{R}^{Dim\times N}$ where $Dim$ is either 2 or 3. I should then obtain \begin{align} proj_V = \frac{V^Ts}{\langle s,s\rangle} s \end{align} But $V^Ts\in \mathbb{R}^{N\times 1}$ and $s\in \mathbb{R}^{Dim \times 1}$. So this doesn't match. Do I simply take \begin{align} proj_V =s \left(\frac{V^Ts}{\langle s,s\rangle} \right)^T \end{align} which would be in $Dim \times N$.

The reason, why I want to follow this approach is , that it would allow me to make use of fast matrix vector multiplication instead of iterating over all points. Thanks!

• In case of a non-orthogonal basis, you could for instance use: $$proj_W(\vec u)=A(AA^T)^{-1}A^T\vec u$$This will not do everything in one step, but at least you are not required to have an orthogonal basis . NB: This only works if $(AA^T)$ is invertible. Mar 12, 2015 at 10:32

## 2 Answers

You take $$\text{Proj}_{s}(\mathbf{V}) = \mathbf{s}\frac{1}{\|\mathbf{s}\|^{2}}\mathbf{s}^{T}\mathbf{V},$$ which is indeed what you wrote.

More generally, instead of a single vector $\mathbf{s}$, you could have a $k$-dimensional subspace of $\mathbb{R}^{d}$. Let $\mathbf{X} \in \mathbb{R}^{d \times k}$ be a matrix whose $k$ columns form an orthonormal basis for that subspace. The projection of (each of the $N$ columns of) $\mathbf{V}$ onto that subspace is $$\text{Proj}_{\mathbf{X}}(\mathbf{V}) = \mathbf{X}\mathbf{X}^{T}\mathbf{V}.$$

Here the target subspace is the one-dimensional span of $\mathbf{s}$, and $1/\|\mathbf{s}\|$ is its orthonormal basis.

Edit: With respect to computational complexity, note that $\mathbf{s}\mathbf{s}^{T}$ should not be explicitly computed. The multiplication should be carried out as the parentheses in the OP's question dictate.

• Thanks, but I think for an efficient computation, the first approach is faster, since I only need two matrix-vector multiplication (assuming that $s$ is normalized). Mar 12, 2015 at 11:33
• Oh yes of course. The order you will perform the multiplications makes a difference. Mar 12, 2015 at 14:37

You could for instance change the basis where one basis vector includes the direction vector of a line. For instance, if the line has the equation $\vec r = t(1,1,1)$, you could construct a new basis such as $$f_1=(1,1,1), f_2=(1,-1,0), f_3=(1,1,-2)$$ In this basis, it's much easier to project on either the xy-plane or on x axis. To project on the axis, you simply have to consider the x coordinate. Then, convert it back and you have the desired vector. These steps can be summarized as one matrix. Also, it is faster if you normalize the basis vectors, because then you will have an orthogonal matrix and thus the inverse (when you convert back) is simply the transposition.