Null space solutions in the presence of noise

6 views (last 30 days)
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?
Thanks in advance for your time.

Accepted Answer

Matthew Dvorsky
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
% Add noise to A
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
  4 Comments
Phillip
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.

Sign in to comment.

More Answers (1)

Bruno Luong
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.

Categories

Find more on Linear Algebra in Help Center and File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!