Null space solutions in the presence of noise

6 views (last 30 days)
Phillip on 18 Feb 2021
Commented: Phillip on 14 Nov 2022
Usually in linear algebra I end up posing problems of the form
A * x = b
These are usually easy to solve in a noise-robust manner with standard least squares approaches. I often end up with very big arrays where I would use lsqminnorm to solve A^-1 * b.
However I am currently faced with a problem of the form
A * x = 0
I have tried a variety of approaches to solve this: null(), lsqlin(), fmincon().... these all work fine when there is no noise, but return either garbage (null) or a fairly poor solution in the presence of a modest amount of noise. It seems that with noise, the true solution no longer minimises A*x.
Does anyone have any advice for working in the null space, in the presence of noise?
KALYAN ACHARJYA on 18 Feb 2021

Matthew Dvorsky on 10 Nov 2022
Edited: Matthew Dvorsky on 14 Nov 2022
You are trying to minimize the value of . The issue is that we can arbitrarily scale any arbitrary vector to make the value as small as we like (including the trival solution ). Thus, to find a unique solution, we must restrict the value of . So we can instead ask to minimize by choosing such that .
This minimization can be done by computing the singular value decomposition of A, whcih decomposes A as . If we take to be a column of V whose corresponding singular value is λ, then . Thus, we can minimize by choosing to be the column of V with the smallest corresponding singular value. This is demonstrated in the following MATLAB example.
% Generate A and x such that Ax = 0
A = rand(4, 3) * rand(3, 4);
x = null(A) % Returns a single null vector
x = 4×1
-0.7998 0.4316 -0.1600 0.3854
A_noise = A + 0.00001 * rand(size(A));
null(A_noise) % Does not work due to noise
ans = 4×0 empty double matrix
% Calculate least square solution using SVD.
[~, ~, V] = svd(A_noise);
x_lsq = V(:, end) % Gives a good approximation for x (or sometimes -x).
x_lsq = 4×1
-0.7998 0.4316 -0.1600 0.3853
Note that this method even works for non-square matrices A.
Edit: As Bruno pointed out in his answer, the we can use the MATLAB 'svds' function, to compute only the column of V that corresponds to the smallest singular value. This is efficient even for very large sparse matrices, as noted in the documentation of 'svds'.
[~, ~, x_lsq] = svds(A_noise, 1, "smallest") % Same result as the above code.
x_lsq = 4×1
-0.7998 0.4316 -0.1600 0.3853
Phillip on 14 Nov 2022
Thanks all, this is very useful for me -- and thanks for your many contributions to the file exchange over the years, especially Bruno and John! I have all manner of snippets of your code embedded into my workflow.

Bruno Luong on 13 Nov 2022
Edited: Bruno Luong on 13 Nov 2022
You can call
[x_lsq ,a] = eigs(@(x) (S'*S)\x, size(S,2), 1, 'smallestabs')
where S is your (sparse) matrix
sqrt(a) is the smallest singular value of S, and x_lsq is the corresponding singular vector.
Or
[~,~,x_lsq] = svds(S,1,0)
Span x_lsq approximates the null space of S, assuming its dimension is 1.