MATLAB: Sparsest solution for A\B

Question

Matlab says the command A\B finds a solution to Ax=B which has the smallest number of non-zero components. If A is nxm with n>m the system does not have an exact solution, in general, so A\B returns an approximate solution.

My problem is this: I have a system for which I know that a very sparse solution x0 should exist. However, A\B is not returning that solution. I imagine this can only be because Matlab finds a different solution x which is a "better" approximation in the sense that norm(Ax-B) < norm(Ax0-B).

I would like to "trade" the quality in the approximation for the sparsity in the solution. Namely, I want A\B to return the "worse" solution x0 instead of x, because x0 is more sparse than x. Is this possible?

Answer 1

That statement is wrong, x = A\b doesn't return the solution x with the smallest number of nonzero elements. What mldivide does, for rectangular matrices A, is return an output x with rank(A) nonzero elements. Compared to the other popular way of solving that system, x = pinv(A)*b which typically has no zero elements at all, this is indeed a small number of nonzeros. But there's no guarantee this is the smallest possible.

The current documentation and help text for mldivide do not say that it returns the fewest possible nonzero components. Can you point me to where you found that statement? I'll make sure it's fixed.

Finding the smallest number of nonzero elements in x for A*x=b is an NP-hard problem. There are methods that find a good approximation of this by minimizing the l1-norm of x instead, which are commonly used in Compressed Sensing. Here's a link to a blog post about using Compressed Sensing in MATLAB; it links to the l1-magic package of MATLAB functions.