mldivide algorithm for an underdetermined system of equations

15 views (last 30 days)
Juan Gallego on 27 Apr 2021
Edited: Bruno Luong on 27 Apr 2021
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.

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.
Juan Gallego on 27 Apr 2021
Thanks a lot, this is exactly the answer I was looking for!