Obtain null space or single dimensional space which is its best approximation efficiently

Question

I have been doing this using an svd computation

[U, S, V] = svd(A)

wherein I use the last column of A as my null space approximation. Since A gets really large, I realized that this is slowing down my computation.

For null(A), the documentation seems to suggest that it does an SVD anyways. Also, it does not work if A is full rank. An SVD proceeds by finding the largest singular value, then the next one and so on whereas I just need the smallest one.

This seems to be a big bottleneck. Will really appreciate help on this. Am using MATLAB.

Thanks.

Answer 1

If all points are from a plane, call SVD with just a sample.

Answer 2

This Wikipedia article describes three methods for the numerical computation of the null space: reduction (Gaussian elimination), SVD, and QR decomposition. In brief, (1) reduction is "not suitable for a practical computation of the null space because of numerical accuracy problems in the presence of rounding errors", (2) SVD is the "state-of-the art approach", but it "generally costs about the same as several matrix-matrix multiplications with matrices of the same size", and (3) the numerical stability and the cost of QR decomposition are "between those of the SVD and the reduction approaches".

So if SVD is too slow, you could give a chance to QR decomposition. The algorithm with your notations is as follows: "A is a 4xN matrix with 4<N. Using the QR factorization of A', we can find a matrix such that A'*P = Q*R = [Q1 Q2]*R, where where P is a permutation matrix, Q is NxN and R is Nx4. Matrix Q1 is Nx4 and consists of the first 4 columns of Q. Matrix Q2 is Nx(N-4) and is made up of the last N-4 columns of Q. Since A*Q2 = 0, the columns of Q2 span the null space of A."

Matlab implementation: [Q, R, P] = qr(A', 'matrix'); The columns of matrix Q2 = Q(:, 5:end); give the null space of A.

Answer 3

This answers builds on your comment that what you actually want to do is to solve Ax = 0. For this purpose, a complete nullspace computation is usually inefficient. If you want a least-squares approximation to x, have a look into the matlab operator \ (see help mldivide).

In other cases, an "economic" SVD via svd(A,0) might be helpful for non-square matrices (it does not compute the full S, but only the non-zero block).