g****t
发帖数: 31659 | 1 看上面回帖有感.
L1 norm优化貌似确实看到了革命胜利的曙光阿. |
A*******r
发帖数: 768 | 2 展开讲讲这是啥高级咚咚
【在 g****t 的大作中提到】
: 看上面回帖有感.
: L1 norm优化貌似确实看到了革命胜利的曙光阿.
|
d******e
发帖数: 7844 | 3 管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
到曙光了吧。
【在 g****t 的大作中提到】
: 看上面回帖有感.
: L1 norm优化貌似确实看到了革命胜利的曙光阿.
|
l******e
发帖数: 470 | 4 看看tao文章多少引用被
哪里的革命胜利？
【在 g****t 的大作中提到】
: 看上面回帖有感.
: L1 norm优化貌似确实看到了革命胜利的曙光阿.
|
c****n
发帖数: 2031 | 5 已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
超难的东西。应用也差不多，patent一大堆。。。
这年头很难赶在潮流前沿。
【在 g****t 的大作中提到】
: 看上面回帖有感.
: L1 norm优化貌似确实看到了革命胜利的曙光阿.
|
g****t
发帖数: 31659 | 6 最早的Lasso是统计方法的文章吧.那个文章确实好.
不过热起来还是上次数学大会candes做了报告.他们说清楚了
什么时候L1和L0等价.这样就justify了以前的很多启发式的想法和算法.
已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
超难的东西。应用也差不多，patent一大堆。。。
这年头很难赶在潮流前沿。
【在 c****n 的大作中提到】
: 已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
: 超难的东西。应用也差不多，patent一大堆。。。
: 这年头很难赶在潮流前沿。
|
g****t
发帖数: 31659 | 7 目前还没人用这个算法赚到钱,这就说明应用目前还是0.
小波变换的胜利是FBI那个指纹压缩项目为标志的.
当时光盘存储费用就节省了几亿刀.
【在 c****n 的大作中提到】
: 已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
: 超难的东西。应用也差不多，patent一大堆。。。
: 这年头很难赶在潮流前沿。
|
g****t
发帖数: 31659 | 8 L0 norm等价于L1 norm的条件已经基本清楚了.
另外L0 norm当然是可以求解的,不过速度远比L1 norm慢.
不加提高鲁邦性的惩罚项的L1,就是线性规划.
管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
到曙光了吧。
【在 d******e 的大作中提到】
: 管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
: 到曙光了吧。
|
d******e
发帖数: 7844 | 9 速度远比L1 Norm慢，这不跟没说一样么。
【在 g****t 的大作中提到】
: L0 norm等价于L1 norm的条件已经基本清楚了.
: 另外L0 norm当然是可以求解的,不过速度远比L1 norm慢.
: 不加提高鲁邦性的惩罚项的L1,就是线性规划.
:
: 管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
: 到曙光了吧。
|
g****t
发帖数: 31659 | 10 但是L1 norm很多情况下和L0 norm是
严格等价的(这不是近似). 等价的条件已经有很多种了.
这就相当于找到了很多L0 norm问题的解法.
速度远比L1 Norm慢，这不跟没说一样么。
【在 d******e 的大作中提到】
: 速度远比L1 Norm慢，这不跟没说一样么。
|
|
|
g****t
发帖数: 31659 | 11 看tao的blog
【在 A*******r 的大作中提到】
: 展开讲讲这是啥高级咚咚
|
c****n
发帖数: 2031 | 12 er。。。我老板半年前就卖了个专利，compressive sensing的算法
【在 g****t 的大作中提到】
: 目前还没人用这个算法赚到钱,这就说明应用目前还是0.
: 小波变换的胜利是FBI那个指纹压缩项目为标志的.
: 当时光盘存储费用就节省了几亿刀.
|
c****n
发帖数: 2031 | 13
并不总是L1快的，很多做dictionary based图像处理的人，用的就是
L0 norm，greedy 算法，比L1要快
【在 g****t 的大作中提到】
: L0 norm等价于L1 norm的条件已经基本清楚了.
: 另外L0 norm当然是可以求解的,不过速度远比L1 norm慢.
: 不加提高鲁邦性的惩罚项的L1,就是线性规划.
:
: 管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
: 到曙光了吧。
|
c****n
发帖数: 2031 | 14 哦，我应该说严格的研究L1和L0的关系是从Donoho开始的。L1能给出sparse的解这一点
的确是早就知道了的
【在 g****t 的大作中提到】
: 最早的Lasso是统计方法的文章吧.那个文章确实好.
: 不过热起来还是上次数学大会candes做了报告.他们说清楚了
: 什么时候L1和L0等价.这样就justify了以前的很多启发式的想法和算法.
:
: 已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
: 超难的东西。应用也差不多，patent一大堆。。。
: 这年头很难赶在潮流前沿。
|
l******e
发帖数: 470 | 15 我模糊的记得老师说L0 in general是NPC？懂的来讲讲。
【在 d******e 的大作中提到】
: 管用是管用，但是貌似目前还没有什么曙光吧。什么时候L0 Norm可以求解了，才叫看
: 到曙光了吧。
|
Q***5
发帖数: 994 | 16 真的？ L1 norm ， sparse coding 这麽偏应用的东西也能登数学大会的殿堂？
【在 g****t 的大作中提到】
: 最早的Lasso是统计方法的文章吧.那个文章确实好.
: 不过热起来还是上次数学大会candes做了报告.他们说清楚了
: 什么时候L1和L0等价.这样就justify了以前的很多启发式的想法和算法.
:
: 已经挺久了（Donoho 98年就开始promote这个东西），理论几乎做干净了，剩下的都是
: 超难的东西。应用也差不多，patent一大堆。。。
: 这年头很难赶在潮流前沿。
|
m****n
发帖数: 142 | 17 是真的。因为真正的应用数学是非常深刻，非常困难，和非常漂亮的。
【在 Q***5 的大作中提到】
: 真的？ L1 norm ， sparse coding 这麽偏应用的东西也能登数学大会的殿堂？
|
Q***5
发帖数: 994 | 18 这话到也没错，比如数学在理论物理中的应用，有许多深刻，漂亮的结果，而且导致新
的数学理论。
可是，像L1 norm 这种课题，侧重研究有效的数值计算方法，比较实用，但一般谈不上‘漂亮’。
【在 m****n 的大作中提到】
: 是真的。因为真正的应用数学是非常深刻，非常困难，和非常漂亮的。
|
Q***5
发帖数: 994 | 19 Don't know about the NPC property.
But, for P>1, L_P norm often leads to convex problem, therefore, effecient
numberical methods can be used to find the optimal solution.
When P = 1, it is still convex -- but the smoothness of the problem is poor,
therefore, need more care and computing time.
For P<1 (including 0), the problem is generally non-convex, ordinary
numerical routine (e.g. gradient descent) can only leads to local optimal
solution. Finding the global optimal solution can be charllengi
【在 l******e 的大作中提到】
: 我模糊的记得老师说L0 in general是NPC？懂的来讲讲。
|
m****n
发帖数: 142 | 20 "漂亮"与否要看你怎么看。寻找“有效”的数值计算不仅仅是实用，而是一件极端困难
的问题，如果能够在这上面做一些本质性的工作，这毫无疑问是非常漂亮的。
上‘漂亮’。
【在 Q***5 的大作中提到】
: 这话到也没错，比如数学在理论物理中的应用，有许多深刻，漂亮的结果，而且导致新
: 的数学理论。
: 可是，像L1 norm 这种课题，侧重研究有效的数值计算方法，比较实用，但一般谈不上‘漂亮’。
|
|
|
g****t
发帖数: 31659 | 21 greedy求的是L1的精确解吗？
L0精确解不是说是NP问题吗？
并不总是L1快的，很多做dictionary based图像处理的人，用的就是
L0 norm，greedy 算法，比L1要快
【在 c****n 的大作中提到】
: 哦，我应该说严格的研究L1和L0的关系是从Donoho开始的。L1能给出sparse的解这一点
: 的确是早就知道了的
|
g****t
发帖数: 31659 | 22 你老板做什么的？ 展开介绍下？
【在 c****n 的大作中提到】
: er。。。我老板半年前就卖了个专利，compressive sensing的算法
|
g****t
发帖数: 31659 | 23 上届数学会的论文集网上有。
http://www.icm2006.org/proceedings/vol3.html
【在 Q***5 的大作中提到】
: 真的？ L1 norm ， sparse coding 这麽偏应用的东西也能登数学大会的殿堂？
|
g****t
发帖数: 31659 | 24 看来我没记错，一般的L0是NP hard。
ref:
http://www.computer.org/portal/web/csdl/doi/10.1109/ICASSP.2009.4960346
Don't know about the NPC property.
But, for P>1, L_P norm often leads to convex problem, therefore, effecient
numberical methods can be used to find the optimal solution.
When P = 1, it is still convex -- but the smoothness of the problem is poor,
therefore, need more care and computing time.
For P<1 (including 0), the problem is generally non-convex, ordinary
numerical routine (e.g. gradient desc
【在 Q***5 的大作中提到】
: Don't know about the NPC property.
: But, for P>1, L_P norm often leads to convex problem, therefore, effecient
: numberical methods can be used to find the optimal solution.
: When P = 1, it is still convex -- but the smoothness of the problem is poor,
: therefore, need more care and computing time.
: For P<1 (including 0), the problem is generally non-convex, ordinary
: numerical routine (e.g. gradient descent) can only leads to local optimal
: solution. Finding the global optimal solution can be charllengi
|
d******e
发帖数: 7844 | 25 L0是NP Hard，全局最优是没谱的。
【在 g****t 的大作中提到】
: greedy求的是L1的精确解吗？
: L0精确解不是说是NP问题吗？
:
: 并不总是L1快的，很多做dictionary based图像处理的人，用的就是
: L0 norm，greedy 算法，比L1要快
|
g****t
发帖数: 31659 | 26 一定条件(稀疏)下，L1 norm方法导致的迭代算法，收敛到L0 问题的精确解。
这是严格的，这就是compressed sensing最大的理论突破。
L0是NP Hard，全局最优是没谱的。
【在 d******e 的大作中提到】
: L0是NP Hard，全局最优是没谱的。
|
h***i
发帖数: 3844 | 27 也就这样了
L0 的问题看来不能完全解决
【在 g****t 的大作中提到】
: 一定条件(稀疏)下，L1 norm方法导致的迭代算法，收敛到L0 问题的精确解。
: 这是严格的，这就是compressed sensing最大的理论突破。
:
: L0是NP Hard，全局最优是没谱的。
|
g****t
发帖数: 31659 | 28 什么叫完全解决呢？
【在 h***i 的大作中提到】
: 也就这样了
: L0 的问题看来不能完全解决
|
c****n
发帖数: 2031 | 29 Greedy是试图结L0，不保证总能解到ｇｌｏｂａｌ ｍｉｎ，但是对于很多实际情况是
解到了ｇｌｏｂａｌ ｍｉｎ
【在 g****t 的大作中提到】
: greedy求的是L1的精确解吗？
: L0精确解不是说是NP问题吗？
:
: 并不总是L1快的，很多做dictionary based图像处理的人，用的就是
: L0 norm，greedy 算法，比L1要快
|
g****t
发帖数: 31659 | 30 O,能有方法检测什么类问题,
可解出到global min么?
Greedy是试图结L0，不保证总能解到ｇｌｏｂａｌ ｍｉｎ，但是对于很多实际情况是
解到了ｇｌｏｂａｌ ｍｉｎ
【在 c****n 的大作中提到】
: Greedy是试图结L0，不保证总能解到ｇｌｏｂａｌ ｍｉｎ，但是对于很多实际情况是
: 解到了ｇｌｏｂａｌ ｍｉｎ
|
|
|
c****n
发帖数: 2031 | 31 不好意思，没太看明白你的问题
【在 g****t 的大作中提到】
: O,能有方法检测什么类问题,
: 可解出到global min么?
:
: Greedy是试图结L0，不保证总能解到ｇｌｏｂａｌ ｍｉｎ，但是对于很多实际情况是
: 解到了ｇｌｏｂａｌ ｍｉｎ
|
c****n
发帖数: 2031 | 32 其实比较著名的解：
Minimize |x|_0
s.t. Ax=b
的算法叫Orthogonal Matching Pursuit（OMP），可以ｇｏｏｇｌｅ一下
【在 g****t 的大作中提到】
: O,能有方法检测什么类问题,
: 可解出到global min么?
:
: Greedy是试图结L0，不保证总能解到ｇｌｏｂａｌ ｍｉｎ，但是对于很多实际情况是
: 解到了ｇｌｏｂａｌ ｍｉｎ
|
g****t
发帖数: 31659 | 33 比如给我一个问题,
有没办法能判别是否greedy能解出全局最优?
不好意思，没太看明白你的问题
【在 c****n 的大作中提到】
: 不好意思，没太看明白你的问题
|
c****n
发帖数: 2031 | 34 如果所要寻找的解ｓｐａｒｓｅ ｅｎｏｕｇｈ，会
【在 g****t 的大作中提到】
: 比如给我一个问题,
: 有没办法能判别是否greedy能解出全局最优?
:
: 不好意思，没太看明白你的问题
|
g****t
发帖数: 31659 | 35 OMP我知道.
不过据我所知,对OMP来说,回答不了我前面的问题.
其实比较著名的解：
Minimize |x|_0
s.t. Ax=b
的算法叫Orthogonal Matching Pursuit（OMP），可以ｇｏｏｇｌｅ一下
【在 c****n 的大作中提到】
: 其实比较著名的解：
: Minimize |x|_0
: s.t. Ax=b
: 的算法叫Orthogonal Matching Pursuit（OMP），可以ｇｏｏｇｌｅ一下
|
c****n
发帖数: 2031 | 36 也许你是对的，可能是不会
但是会得到真实的解ｘ，满足Ax=b
【在 g****t 的大作中提到】
: OMP我知道.
: 不过据我所知,对OMP来说,回答不了我前面的问题.
:
: 其实比较著名的解：
: Minimize |x|_0
: s.t. Ax=b
: 的算法叫Orthogonal Matching Pursuit（OMP），可以ｇｏｏｇｌｅ一下
|
c****n
发帖数: 2031 | 37 当然ｘ要ｓｐａｒｓｅ ｅｎｏｕｇｈ
Joel Tropp有篇很好文章：GREED IS GOOD: ALGORITHMIC RESULTS FOR SPARSE
APPROXIMATION
【在 c****n 的大作中提到】
: 也许你是对的，可能是不会
: 但是会得到真实的解ｘ，满足Ax=b
|
s********i
发帖数: 21 | 38 这个文章意思不大
【在 c****n 的大作中提到】
: 当然ｘ要ｓｐａｒｓｅ ｅｎｏｕｇｈ
: Joel Tropp有篇很好文章：GREED IS GOOD: ALGORITHMIC RESULTS FOR SPARSE
: APPROXIMATION
|
c****n
发帖数: 2031 | 39 any suggestion?
【在 s********i 的大作中提到】
: 这个文章意思不大
|
