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$

1 Answer 1

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$ Commented Jul 9, 2020 at 6:50
  • $\begingroup$ @FedericoPoloni Can you expand? I'm not sure what you mean by "rank-revealing decomposition" $\endgroup$
    – a06e
    Commented Sep 9, 2021 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$ Commented Sep 10, 2021 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$
    – a06e
    Commented Sep 10, 2021 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$ Commented Sep 10, 2021 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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