L0是一个NP-hard problem！
2017-07-04 本文已影响0人
Persistently
L0-Norm:
L0-Norm
目的：计算非0的个数。
为什么L0可以用来计算非0的个数？
根据图下面的标识，当p 趋近于0的时候，这个函数就只有在x= 0的时候 等于0，其他的位置都为1！
L0-Norm可以用于表达vector的稀疏性！
求解L0-norm
这个公式与L2-norm有点相似；
不同之处：
L2-norm的解是唯一的，而且有特定的解决方法。
L0是NP-hard problem，非凸；所以，凸函数的求解方法对他并不适用。
为什么是NP-hard problem？
举个例子：
假设矩阵 = 500x2000(n = 500,m = 2000)，如果我们知道稀疏解为20（也就是说有20个非零），要想知道这20个点3.9E+47种可能，每次测试需要1E-9(s),那么需要1.2E+31years!!
