Fast projection of multiple points on a line

Question

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!

Answer 1

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.

Answer 2

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.