Suppose I have $M$ vectors $a_1, a_2, ..., a_M$ in $\mathbb R^N$, with $M < N$. Given another vector $x\in\mathbb R^N$, I want to find the projection of $x$ in the sub-space orthogonal to all the $a_1,...,a_M$.
How can I compute this projection efficiently? Note that the $a_1,...,a_M$ need not be orthogonal. But we can assume that they are independent.
Let $A$ denote the matrix with columns $a_1,\dots,a_M$. The matrix of the (orthogonal) projection onto this subspace is given by $P = A(A^TA)^{-1}A$, and the projection onto the orthogonal complement of this subspace is given by $I - P$.
So, your desired vector is $$ (I - P)x = x - A(A^TA)^{-1}A^Tx. $$ For increased efficiency, we might compute the product $(A^TA)^{-1}(A^Tx)$ by solving the system $(A^TA)y = A^Tx$ instead of explicitly computing $(A^TA)^{-1}$.