Li Yuanqing, Amari Shun-Ichi
School of Automation Science and Engineering, South China University of Technology, Guangzhou 510640, China.
IEEE Trans Neural Netw. 2010 Jul;21(7):1189-96. doi: 10.1109/TNN.2010.2049370. Epub 2010 Jun 14.
In sparse representation, two important sparse solutions, the 0-norm and 1-norm solutions, have been receiving much of attention. The 0-norm solution is the sparsest, however it is not easy to obtain. Although the 1-norm solution may not be the sparsest, it can be easily obtained by the linear programming method. In many cases, the 0-norm solution can be obtained through finding the 1-norm solution. Many discussions exist on the equivalence of the two sparse solutions. This paper analyzes two conditions for the equivalence of the two sparse solutions. The first condition is necessary and sufficient, however, difficult to verify. Although the second is necessary but is not sufficient, it is easy to verify. In this paper, we analyze the second condition within the stochastic framework and propose a variant. We then prove that the equivalence of the two sparse solutions holds with high probability under the variant of the second condition. Furthermore, in the limit case where the 0-norm solution is extremely sparse, the second condition is also a sufficient condition with probability 1.
在稀疏表示中，两种重要的稀疏解，即0范数解和1范数解，一直备受关注。0范数解是最稀疏的，但不易获得。虽然1范数解可能不是最稀疏的，但可以通过线性规划方法轻松得到。在许多情况下，0范数解可以通过找到1范数解来获得。关于这两种稀疏解的等价性存在许多讨论。本文分析了两种稀疏解等价的两个条件。第一个条件是充要条件，但难以验证。虽然第二个条件是必要条件但不是充分条件，但易于验证。在本文中，我们在随机框架内分析第二个条件并提出一个变体。然后我们证明在第二个条件的变体下，两种稀疏解的等价性以高概率成立。此外，在0范数解极其稀疏的极限情况下，第二个条件也是概率为1的充分条件。
