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?
1 个评论
Alex Mcaulley
2019-5-14
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 "\"?
采纳的回答
Christine Tobler
2019-5-14
2 个投票
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.
4 个评论
marnovaes
2019-5-14
Alex Mcaulley
2019-5-16
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
2019-5-16
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
2019-5-16
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Linear Least Squares 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
