Given an $m \times n$ matrix $A$ and a vector $x\in\mathbb R^n$, with $m<n$, what's an efficient way of computing the projection of $x$ onto the kernel of $A$?
One part of the fundamental theorem of linear algebra is that the kernel/nullspace of $\mathbf A$ is orthogonal to the range of $\mathbf A^T$. By applying the $\mathbf Q \mathbf R$ decomposition to $\mathbf A^T$, you can generate the orthogonal projector $\mathbf P = \mathbf I - \mathbf Q \mathbf Q^T$. The vector $\mathbf P \mathbf x$ is what you're looking for. A brief matlab demo follows:
clear all close all % Form random A and x. m = 23; n = 39; A = rand(m,n); x = rand(n,1); % Find Q = span(A') [Q,~] = qr(A',0); % Decompose x = Qx + Px Qx = Q*(Q'*x); Px = x-Qx; norm_Px = norm(Px) norm_Qx = norm(Qx) error_x = norm(x-Px-Qx) % Verify Px is in nullspace of A. error_APx = norm(A*Px)
If $\mathbf A$ is too large but has exploitable structure (sparsity? some kind of H-matrix like rank-deficiency?), you might be better off using using randomized sampling / Krylov ideas, instead of dense $\mathbf Q \mathbf R$ decomposition.