mldivide for underdetermined matrices

What does A\b (mldivide) do for underdetermined matrices? Clearly it's not the same thing as pinv(A)*b. The documentation avoids this topic. In a 2009 post it was stated that "MLDIVIDE will pick the solution with least number of non-zero elements." This cannot be the answer, as it is a NP-hard problem. Some heuristic must be used to indeed provide a solution with restricted support, but which heuristic is it?

Answer 1

[Walter Roberson]

http://www.mathworks.com/help/techdoc/ref/mldivide.html

If A is an m-by-n matrix with m ~= n and B is a column vector with m components, or a matrix with several such columns, then X = A\B is the solution in the least squares sense to the under- or overdetermined system of equations AX = B. In other words, X minimizes norm(A*X - B), the length of the vector AX - B. The rank k of A is determined from the QR decomposition with column pivoting. The computed solution X has at most k nonzero elements per column. If k < n, this is usually not the same solution as x = pinv(A)*B, which returns a least squares solution.

[Laurent Demanet]

Thank you for your reply but I'm afraid this paragraph has issues. The first sentence happens to be wrong: A\B does not always return the least squares solution in the underdetermined case. This happens for instance when the matrix is rectangular, tall and thin, yet rank-deficient. The last sentence is of course a nod to this: the computed solution is indeed not the same as pinv(A)*B. Then, the claim that "the computed solution X has at most k nonzero elements per column" is fine, but this is almost never a feature of the least-squares solution. Having fewer than k nonzeros must be a result of this magic that mldivide does (which I'm looking for) and which sets it apart from pinv.

(Note in passing the self-contradiction: one sentence claiming that the solution is LS and another which says it isn't -- not so great in the first few lines of the official documentation of one of Matlab's best routines.)

[Lense]

Apologies for this late answer, but maybe other might be helped by it.

Be careful of the different uses of 'least squares'. mldivide minimizes |Ax - b|||, no matter what the shape or rank of A is. However, in the case that A does not have rank equal to the length of x, the solution of the minimization problem is not unique, but we have a space of solutions. From this space, mldivide selects one that has a certain amount of zeros. What pinv does (disregarding the truncation of singular values) is select the solution in this space that has the minimum norm in x! So pinv minimizes |Ax-b||| with secondary minimization of |x|||.