mldivide algorithm for an underdetermined system of equations

24 views (last 30 days)
I'm trying to solve an underdetermined equation (one equation with two unknowns) as a system of the form:
A * x = b
Where
A = [2, 1]
b = 1
If I solve it with the pseudoinverse, I get
x = pinv(A) * b
x = [0.4, 0.2]'
Which is the least squares solution. So far, so good.
However, if I use mldivide of backslash, I get the following solution.
x = A \ b
x = [0.5, 0]'
Which is the sparsest and minimum norm-1 solution. So my question is, how does MATLAB actually calculate this solution?
I've read some other questions, and they just mention that the solution using backslash has at most m nonzero components for an m-by-n matrix A, which is what I'm getting, but they don't say how it's computed.
In older versions (http://matlab.izmiran.ru/help/techdoc/ref/mldivide.html), they say it's calculated with QR decomposition with pivoting, but this yields to:
[Q, R, P] = qr(A)
Q = 1
R = [2, 1]
P = [1, 0;
0, 1]
Which doesn't help much... if I use this, I get the initial solution of least squares. So I guess it's using a different algorithm.

Accepted Answer

Bruno Luong
Bruno Luong on 27 Apr 2021
Edited: Bruno Luong on 27 Apr 2021
The outline of "\" goes as following:
% Test data
A=randi(10,3,2)*randi(10,2,5)
A = 3×5
108 67 38 86 70 137 96 52 122 85 109 84 44 106 65
b=randi(10,3,1)
b = 3×1
5 3 5
[Q, R, P] = qr(A,'vector');
r = rank(A); % real implementation: r is estimated mainly from diag(R)
x = zeros(size(A,2),1);
y = Q(:,1:r)'*b;
X = R(1:r,1:r); % X is upper triangular & square matrix with all diagonal terms ~= 0
x(P(1:r)) = inv(X)*y % real implementation this is a back substitution
x = 5×1
0.0440 0 0 -0.0097 0
A\b
Warning: Rank deficient, rank = 2, tol = 2.283770e-13.
ans = 5×1
0.0440 0 0 -0.0097 0
TMW calls it "basis/basic" solution.

More Answers (0)

Categories

Find more on Linear Algebra in Help Center and File Exchange

Tags

Community Treasure Hunt

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

Start Hunting!