mldivide algorithm for an underdetermined system of equations
11 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
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;
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
[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
TMW calls it "basis/basic" solution.