Null space solutions in the presence of noise

8 次查看（过去 30 天）
Phillip
Phillip 2021-2-18
评论： Phillip 2022-11-14
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.

请先登录，再回答此问题。

采纳的回答

Matthew Dvorsky
Matthew Dvorsky 2022-11-10
编辑：Matthew Dvorsky 2022-11-14
Ran in:
This is known as the homogeneous linear least squares problem.
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 个评论
显示 2更早的评论
Matthew Dvorsky
Matthew Dvorsky 2022-11-14
As Bruno pointed out in his answer, we can use the svds function, which will be more efficient, especially when the input matrix is large. I have edited my answer to give an example.
Phillip
Phillip 2022-11-14
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.

请先登录，再进行评论。

更多回答（1 个）

Bruno Luong
Bruno Luong 2022-11-13
编辑：Bruno Luong 2022-11-13
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.

类别

在 Help Center 和 File Exchange 中查找有关 Linear Algebra 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by