2
$\begingroup$

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

$\endgroup$
8
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ Good answer! Only one remark: this method only works when that $A$ has full row rank. Otherwise one needs to use the first factor of a rank-revealing decomposition (QRP or SVD). $\endgroup$ Jul 9 '20 at 6:50
  • $\begingroup$ @FedericoPoloni Can you expand? I'm not sure what you mean by "rank-revealing decomposition" $\endgroup$
    – becko
    Sep 9 at 22:42
  • $\begingroup$ @becko Some decompositions give you numerically stable information on the rank of a matrix; among them QRP and SVD. QR is not one of them. There is a discussion of this in the Golub-Van Loan book, for instance. $\endgroup$ Sep 10 at 7:17
  • $\begingroup$ @FedericoPoloni But why is this relevant in this context? Why does the above answer fail when $A$ is not full rank? $\endgroup$
    – becko
    Sep 10 at 7:19
  • 1
    $\begingroup$ @becko It's easy to construct examples where it fails; for instance taking A = [1 0; 0 0] and a QR decomposition with $Q = I$; then $P=0$ is wrong. $\endgroup$ Sep 10 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.