Sparsest solution for A\B

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?

[Alex Mcaulley]

The Matlab documentation says (comparing pinv and \ function)

x = pinv(A)*b

and

y = A\b 

These two are distinguished by the facts that norm(x) is smaller than the norm of any other solution and that y has the fewest possible nonzero components.

Then, you should obtain using "\" the sparsest solution. Are you sure that there is another x sparser than the one obtained with "\"?

Answer 1

[Christine Tobler]

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.

[marnovaes]

Sorry, I was under the impression that A\b claimed to give the sparsest solution, but it is as you say. I wil check the references you mentioned, thank you

[Alex Mcaulley]

Thanks for the information. I found this statement in the documentation of pinv function of my Matlab (R2016b). Probably it was fixed later.

[Christine Tobler]

Yes, I think I remember we fixed this recently in some parts of the doc. It's very tempting to say "smallest number of nonzeros", because that is true for most random matrices, and the description that it has "at most rank(A) nonzeros" is quite complex and can be confusing.

[marnovaes]

By the way, I am using the routine provided in the L1magic package, and it is great. There is a huge gain compared to A\b, at least as far as sparsity is concerned.