压缩感知中的lp球：p范数最优化为什么总会导致一个稀疏的解的原因 论文, 琼海

yuyang911220

转载自：http://blog.csdn.net/jbb0523/article/details/40268943
这篇博文的作者专栏是我的压缩感知入门学习的地方，再次感谢博主
题目：  压缩感知中的lp球：p范数最优化为什么总会导致一个稀疏的解的原因
================问题的引出================
压缩感知中为了解释0范数或1范数最优化为什么总会导致一个稀疏解的原因在解释时经常使用lp球与直线的交点去解释，下面论文中就是这样子解释的：
戴琼海，付长军，季向阳.压缩感知研究[J].计算机学报，2011，34(3)：425-434.
在上面论文的第2小节压缩感知原理中就是这样子解释的，为了完整说明问题，这里将论文中的部分内容截图出来：










上面这幅图2让我看了好久也没看明白，在博主Rachel_Zhang博客的文章“压缩感知进阶——有关稀疏矩阵”中，也提到了类似的内容：

===============================

怎样恢复原信号？

我们已知所选择的最稀疏的x即x中非零元素最少的，即x的零范数最小的（向量的零范数即为其稀疏度sparsity）。然而，求x=argmin||x||0使得x满足Ax=b的一个子问题是一个NP完全问题，需要在S个compoments中选出1,2,...,n个，看能从中选出最少多少个，满足Ax=b,这样，对于每一个n都有排列组合C(S,n)种方法，显然不可行。所以我们想能不能换个什么方法来恢复信号，自然而然的，我们想到了最小平方法。具体见下图Fig B。

Fig B. L2范数下寻找满足Ax=b的x，发现有一定偏差。

yuchengze

感谢分享这些资料，对于压缩感知我有了一定的了解