发信人: Insomnia (完美主义是种病), 信区: AI
标 题: [合集] 请教：关于p-norm的最小化问题
发信站: 水木社区 (Thu Sep 13 08:31:57 2012), 站内
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 20:07:17 2012) 提到:
两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
2.当0
因为非凸函数f(a)的全局最小值，可能在多个不同的自变量处取得，比如f(a)=sin(a), a在-pi/2+2*k*pi(k为整数)，无穷多处都取得全局最小值-1.但是，我觉得这个p-norm问题不会，画了图，最优的a是唯一的。
恳请赐教、帮忙！
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 21:49:40 2012) 提到:
p<1不是norm
【 在 candes (candes) 的大作中提到: 】
: 两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
: 1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
: 2.当0
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 21:59:20 2012) 提到:
0
【 在 asker 的大作中提到: 】
: p<1不是norm
:
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 22:04:27 2012) 提到:
上条回复你的帖子漏了 p=+infinity，p=+infinity也是norm。另外p=0，||x||_0是向量x的非零元素个数，不是norm。数学家称其为伪norm。
【 在 asker 的大作中提到: 】
: p<1不是norm
:
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:14:48 2012) 提到:
试试 ‖(2,2)‖_0.5 和 ‖(0.5, 1.5) ‖_0.5 + ‖(1.5, 0.5) ‖_0.5
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:20:09 2012) 提到:
http://en.wikipedia.org/wiki/Minkowski_inequality
条件是 1<= p <= +inf
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 22:34:07 2012) 提到:
？？
Sorry，我真的记错了？
Thanks勘误。
但是不管它叫不叫norm，不影响这个问题。
p<1不是norm, 也是metric
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Minkowski_inequality
: 条件是 1<= p <= +inf
:
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:57:27 2012) 提到:
http://en.wikipedia.org/wiki/Metric_(mathematics)
d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
【 在 candes (candes) 的大作中提到: 】
: ？？
: Sorry，我真的记错了？
: Thanks勘误。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 23:07:02 2012) 提到:
http://en.wikipedia.org/wiki/Lp_space
第1.2节
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Metric_(mathematics)
: d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
:
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 23:10:18 2012) 提到:
OK。Thanks你的勘误。p<1也构成lp space.这个原因导致我之前一直把所有的都叫norm。这些不影响我的原问题。你对原问题有什么好的见解吗？thanks
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Metric_(mathematics)
: d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
:
☆─────────────────────────────────────☆
CrTn (求！包！养！) 于 (Mon Sep 3 00:03:16 2012) 提到:
这id牛逼
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Wed Sep 5 06:45:49 2012) 提到:
能給講講0－norm和1－norm的關連性麼
【 在 candes (candes) 的大作中提到: 】
: 上条回复你的帖子漏了 p=+infinity，p=+infinity也是norm。另外p=0，||x||_0是向
量x的非零元素个数，不是norm。数学家称其为伪norm。
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 11:32:57 2012) 提到:
我就说说基本的，轻拍。。。
在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
求解A*x=b的最稀疏解，可以表示成：
min ||x||_0 （P0）
s.t. A*x=b
由于信号非零个数||x||_0导致组合优化问题，这个问题是NP-hard。采用和0-norm最接近的凸函数norm，就是1-norm，来relax这个0-norm，导致一个凸优化问题：
min ||x||_1 （P1）
s.t. A*x=b
（P1）可以用Linear Programming有效搞定。
问题是，(P0)给出的解和(P1)给出的解是一样吗？这个可能就是你问要问的两者的联系。
这个问题是整个sparse approximation的核心问题之一，Donoho，Candes， Tao等人证明了，在满足某些条件时（请看他们论文），(P0)给出的解和(P1)给出的解exactly the same！这也许是你想问的0-norm和1-norm的关联吧。
【 在 chengyue 的大作中提到: 】
: 能給講講0－norm和1－norm的關連性麼
: 量x的非零元素个数，不是norm。数学家称其为伪norm。
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Wed Sep 5 12:35:34 2012) 提到:
其实我想问的就是这个证明...
这个证明的结果是概率意义上的收敛，但是我就没看懂是对于什么收敛，还有就是收敛速度到底多快。另外就是整个证明的中心思想到底是什么，看到了一堆引理定理，但是主线没看懂。
【 在 candes (candes) 的大作中提到: 】
: 我就说说基本的，轻拍。。。
: 在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
: 求解A*x=b的最稀疏解，可以表示成：
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Wed Sep 5 12:57:03 2012) 提到:
最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
【 在 candes (candes) 的大作中提到: 】
: 标 题: Re: 请教：关于p-norm的最小化问题
: 发信站: 水木社区 (Wed Sep 5 11:32:57 2012), 站内
:
: 我就说说基本的，轻拍。。。
: 在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
: 求解A*x=b的最稀疏解，可以表示成：
: min ||x||_0 （P0）
: s.t. A*x=b
: 由于信号非零个数||x||_0导致组合优化问题，这个问题是NP-hard。采用和0-norm最接近的凸函数norm，就是1-norm，来relax这个0-norm，导致一个凸优化问题：
: min ||x||_1 （P1）
: s.t. A*x=b
: （P1）可以用Linear Programming有效搞定。
: 问题是，(P0)给出的解和(P1)给出的解是一样吗？这个可能就是你问要问的两者的联系。
: 这个问题是整个sparse approximation的核心问题之一，Donoho，Candes， Tao等人证明了，在满足某些条件时（请看他们论文），(P0)给出的解和(P1)给出的解exactly the same！这也许是你想问的0-norm和1-norm的关联吧。
:
:
:
: 【 在 chengyue 的大作中提到: 】
: : 能給講講0－norm和1－norm的關連性麼
: : 量x的非零元素个数，不是norm。数学家称其为伪norm。
:
: --
:
: ※ 来源:·水木社区 http://newsmth.net·[FROM: 144.214.108.*]
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Wed Sep 5 14:27:16 2012) 提到:
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
x这里是n维的吧？要变成d维 最后补零吗？
: 所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
: 而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 17:25:47 2012) 提到:
这个不是迭代算法，没有收敛速度一说。这是证明在RIP条件下，（P1）和（P0）会以概率1给出等价的解。他们的证明的框架确实是基于概率，即这这面的矩阵A（measurement matrix）是一个随机矩阵，可以使randon Gaussian, randon 伯努利等，这样每个观测，就是原信号x的随机线性组合。
另外，当信号不是那么稀疏时（稀疏度（非零个数）不会远远小于观测数目），ell_1搞不定的。有一些改进，比如Candes的reweighted ell_1（本质上已经采用非凸的log(1+|x|)函数了），就提高了精确恢复概率。
这个证明确实太复杂了，我也没有完全都搞明白。我觉得，这个证明必然不是那么容易搞定的。我看了几遍，没有完全懂，我也不急。不懂完全是正常的。因为，这本来就是很难的问题，在Candes和Tao证明之前。很多牛人也做了大量工作，包括Donoho和Elad等。否则不会吸引那么多顶级的头脑去（包括Tao）去做这个工作。而且成为milestone的工作。
轻拍。。。
【 在 chengyue 的大作中提到: 】
: 其实我想问的就是这个证明...
: 这个证明的结果是概率意义上的收敛，但是我就没看懂是对于什么收敛，还有就是收敛速度到底多快。另外就是整个证明的中心思想到底是什么，看到了一堆引理定理，但是主线没看懂。
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 17:41:30 2012) 提到:
y=A*x, A 是n by m, x是m-dimensional,CS和sparse里面讨论的是underdetermined情况，即nK，而且n要在这个量级 O(K*log(n))。这个量级比起之前的O(K^2)是个进步了。
这样，你说的，随便取出n列，求逆，得到的结果，还有n个非零元素，稀疏度明显大于K。怎么可能是min L0 norm解？你的这个结论是不正确的。
你说min L0 norm给出的解不是唯一的这个结论也未必正确。非凸问题的全局最优可能是唯一的，也可能不是唯一的。
min L1 norm的解也不能保证唯一(可能唯一，也可能不唯一)，导致这个问题的本质原因在于：虽然L1-norm是凸的，但不是严格凸的。但是满足一些条件时，（P1）会给出（P0）的exact solution。
【 在 SPAM 的大作中提到: 】
: 最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
: 所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
: 而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
: ...................
☆─────────────────────────────────────☆
likesnow (还能像喜欢雪一样单纯的喜欢冬天嘛?) 于 (Thu Sep 6 00:54:07 2012) 提到:
p<1是唯一不好证。不过全局最优解很好求啊。
每一维的解yi/xi排序，分段内都是凹的，最优点必定在段边界。遍历一遍yi/xi就得到最优解了。如果唯一的话，估计也是遍历yi/xi来证。
【 在 candes (candes) 的大作中提到: 】
: 两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
: 1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
: 2.当0
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 05:19:16 2012) 提到:
我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
【 在 candes (candes) 的大作中提到: 】
: y=A*x, A 是n by m, x是m-dimensional,CS和sparse里面讨论的是underdetermined情况，即nK，而且n要在这个量级 O(K*log(n))。这个量级比起
: 这样，你说的，随便取出n列，求逆，得到的结果，还有n个非零元素，稀疏度明显大于K。怎么可能是min L0 norm解？你的这个结论是不正确的。
: 你说min L0 norm给出的解不是唯一的这个结论也未必正确。非凸问题的全局最优可能是唯一的，也可能不是唯一的。
: ...................
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 09:11:12 2012) 提到:
这里的C是存在的某个常数吧。有没有具体取值？或者说这个条件只是一个存在性证明而无法实际用来检验
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 09:26:37 2012) 提到:
目前最sharp的分析结果是
n>=t+1, exact recovery的概率是1-exp(-0.5*(W-sqrt(t))^2)
t = 2K*log(m/K)+1.25K
W = n/sqrt(n+1)
常数的确往往很难通过实验准确验证。最多只能给个n,m,K变化的scale
【 在 chengyue (chengyue) 的大作中提到: 】
: 这里的C是存在的某个常数吧。有没有具体取值？或者说这个条件只是一个存在性证明而无法实际用来检验
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:19:25 2012) 提到:
对于underdetermed系统，解的uniqueness根本就没有。不加其他约束（比如sparse约束），uniqueness根本就没有讨论的意义。这是连大一学生都知道的事。
只有添加了约束才可能有。就算引入L1 norm norm constratint，uniqueness也未必就能保证。
我说的结论是OMP算法结果。（OMP并不会比基于L1的BP差多少，很多实验中下，我做仿真OMP比BP还更好）你再熟，你也没有Tropp熟悉。我陈述的结论是Tropp那篇TIT文章（现被引一千多次）。如果我的结论不对，那就是Tropp结论不对，你去Comments人家嘛。
【 在 SPAM 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:28:08 2012) 提到:
哎，现在的人，说话攻击别人欲望怎么就这么强。好好的讨论学术问题，你非得比来比去，说什么“至于说Compressive Sensing的理论，我自认比你熟...”。有什么问题都好好说，心平气和讨论。我上来问问题，和别人讨论。我们讨论的水平是有高低，甚至也有错误。有错误你指正，犯不着像你这么抬高自己，贬低别人。就算你比我熟悉，又能怎么样？
【 在 SPAM 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:31:24 2012) 提到:
谢谢！这个解法已经搞定了。我特别关心的事全局最优点的唯一性问题。
如果不做什么假设，唯一性不能确定。
【 在 likesnow 的大作中提到: 】
: p<1是唯一不好证。不过全局最优解很好求啊。
: 每一维的解yi/xi排序，分段内都是凹的，最优点必定在段边界。遍历一遍yi/xi就得到最优解了。如果唯一的话，估计也是遍历yi/xi来证。
:
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:12:37 2012) 提到:
你引的根本就不对！
你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
【 在 candes (candes) 的大作中提到: 】
: 对于underdetermed系统，解的uniqueness根本就没有。不加其他约束（比如sparse约束），uniqueness根本就没有讨论的意义。这是连大一学生都知道的事。
: 只有添加了约束才可能有。就算引入L1 norm norm constratint，uniqueness也未必就能保证。
: 我说的结论是OMP算法结果。（OMP并不会比基于L1的BP差多少，很多实验中下，我做仿真OMP比BP还更好）你再熟，你也没有Tropp熟悉。我陈述的结论是Tropp那篇TIT文章（现被引一千多次）。如果我的结论不对，那就是Tropp结论不对，你去Comments人家嘛。
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:13:42 2012) 提到:
我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
【 在 candes (candes) 的大作中提到: 】
: 哎，现在的人，说话攻击别人欲望怎么就这么强。好好的讨论学术问题，你非得比来比去，说什么“至于说Compressive Sensing的理论，我自认比你熟...”。有什么问题都好好说，心平气和讨论。我上来问问题，和别人讨论。我们讨论的水平是有高低，甚至也有错误。有错误你指正
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:17:49 2012) 提到:
我说的是求解underdetermined 系统 A*x=b的solution的唯一性问题。
谁扯了？谁说sample compleixity问题了？你自己读清楚别人讨论的问题。
说话不要那么粗鲁！！！嘴巴不干净，学问也干净不到哪里去。
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:20:21 2012) 提到:
讨论学术问题，谁都可以犯错误（再说我的结论根本没错误）。就算有争议，你觉得别人有错，你指出来就行了，你说，“我哪里哪里错了”，别攻击别人。reviewer对投稿作者还不许任何攻击。亏你还是做学术的。
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:24:47 2012) 提到:
我引的就是是Tropp 2007年TIT的文章。摘要里就是我引的结论，哪里错了？
退一步说。Tropp以后的文章有提高，那只是提高了，并不代表之前的结论就错误了。
看来，你的逻辑都有大问题！Tropp 2007年发了文章提高了，那他之前发的文章就是错了？？你什么逻辑啊！那他以后再发一篇提高了的，你又说，2007年这篇又错了。。。
【 在 SPAM 的大作中提到: 】
: 你引的根本就不对！
: 你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:29:35 2012) 提到:
我一直就在围绕underdetermined系统的解的唯一性在讨论。只是为了说明和讨论清楚这个问题，不得不把sample 个数（measure number）。你这么熟悉，你应该知道，smaple个数的多少直接影响解的唯一性。讨论问题A，A可能会和很多因素相关。这些因素必须拿进来讨论。这个叫“扯”？？？看来你的逻辑不止只有一个地方有问题！
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:33:19 2012) 提到:
你再去把2007 Tropp的paper “Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit”打开，睁大眼睛，看清楚，然后再说。
我说的K，就是Tropp里面的m，是稀疏度 （nonzero entries in dimension d）。我说的两个数量级，哪个错了？
【 在 SPAM 的大作中提到: 】
: 你引的根本就不对！
: 你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
:
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 12:46:52 2012) 提到:
据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 目前最sharp的分析结果是
: n>=t+1, exact recovery的概率是1-exp(-0.5*(W-sqrt(t))^2)
: t = 2K*log(m/K)+1.25K
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:52:45 2012) 提到:
原文里说的是原来对OMP的分析拿不到optimal rate罢了。
你原文里那句话说你的结论是对OMP的。
如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
说到底你根本分不清楚，算法的upper bound和问题本身的lower bound。
【 在 candes (candes) 的大作中提到: 】
: 你再去把2007 Tropp的paper “Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit”打开，睁大眼睛，看清楚，然后再说。
: 我说的K，就是Tropp里面的m，是稀疏度 （nonzero entries in dimension d）。我说的两个数量级，哪个错了？
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:54:44 2012) 提到:
是的，恢复概率和矩阵的mutual coherence息息相关的。
在 chengyue 的大作中提到: 】
: 据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 12:58:23 2012) 提到:
我想知道个具体的联系，而不是一种定性的关联。但是目前为止能看明白的就是那个越小慧覆盖率越大这样的定性联系
【 在 candes (candes) 的大作中提到: 】
: 是的，恢复概率和矩阵的mutual coherence息息相关的。
: 在 chengyue 的大作中提到: 】
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:58:40 2012) 提到:
我说的是最原始的Compressive Sensing的设定，Gaussian i.i.d Ensemble的结果，A矩阵每行来自i.i.d N(0,I)。
如果是来自任意的N(0,S)，对S的最小特征值的scaling有要求，这个概率和常数也很难给出这么精确的分析了，据大部分情况都是存在一个常数，使得如何如何了。
那个概率不等式是从Gordan ineqaulity推出来的，构造还是挺麻烦的，而且Gordan文章本身写得不是很容易懂。
【 在 chengyue (chengyue) 的大作中提到: 】
: 据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:01:10 2012) 提到:
我后来有补上OMP。而且我还说了，OMP很优秀，不比BP弱（有时仿真还更强）。而且OMP计算简单，是个极有代表性的算法。我拿OMP作为例子来说，没有问题。我不可能把所有算法的结论都拿出来，说一遍。
你也要搞清楚，n>=d和O(m^2)哪个要求高，不一定。万一m很小，d很大。你说哪个要求松？
“如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。”这句话，我还是不同意是对的。
【 在 SPAM 的大作中提到: 】
: 原文里说的是原来对OMP的分析拿不到optimal rate罢了。
: 你原文里那句话说你的结论是对OMP的。
: 如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 13:08:40 2012) 提到:
你有空去看看Tropp05的文章吧，他那个分析是很旧的东西了。实验的设定也不一样。
对于n/d->0的情况，m*log(d)是lower bound。
他那个m^2的upper bound和d无关，根本就是在不同的(n,d)的scaling下得到的。
【 在 candes (candes) 的大作中提到: 】
: 我后来有补上OMP。而且我还说了，OMP很优秀，不比BP弱（有时仿真还更强）。而且OMP计算简单，是个极有代表性的算法。我拿OMP作为例子来说，没有问题。我不可能把所有算法的结论都拿出来，说一遍。
: 你也要搞清楚，n>=d和O(m^2)哪个要求高，不一定。万一m很小，d很大。你说哪个要求松？
: “如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。”这句话，我还是不同意是对的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:23:33 2012) 提到:
我的意思是，直接求逆，得到的解不会（严格一点，不能保证）是unique的 最优的那个。
没有看到Tropp 在2005有发关于OMP的文章，只看过2004年有一篇。
【 在 SPAM 的大作中提到: 】
: 你有空去看看Tropp05的文章吧，他那个分析是很旧的东西了。实验的设定也不一样。
: 对于n/d->0的情况，m*log(d)是lower bound。
: 他那个m^2的upper bound和d无关，根本就是在不同的(n,d)的scaling下得到的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:33:29 2012) 提到:
我想自己还是分得清问题本身的lower bound和算法的upper bound。
问题本身的lower bound和矩阵A有关，有很多形式，来表达，比如A的mutual coherence，
矩阵的spark，Babel函数等。
好了，我们关于这个问题的讨论就这样吧，不再纠缠了。关于CS的东西，博大精深，还需要研究，感谢你的讨论。也祝你弄出更strong的结果。
【 在 SPAM 的大作中提到: 】
: 原文里说的是原来对OMP的分析拿不到optimal rate罢了。
: 你原文里那句话说你的结论是对OMP的。
: 如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
: ...................
☆─────────────────────────────────────☆
Insomnia (完美主义是种病) 于 (Thu Sep 6 15:47:46 2012) 提到:
好好讨论嘛，版上好不容易有高水平讨论。bbs上写字有时候问题表述不清引出争议再所
难免，只要对事不对人就好了
【 在 candes (candes) 的大作中提到: 】
: 我想自己还是分得清问题本身的lower bound和算法的upper bound。
: 问题本身的lower bound和矩阵A有关，有很多形式，来表达，比如A的mutual coherence，
: 矩阵的spark，Babel函数等。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 20:24:16 2012) 提到:
嗯。我也觉得应该是这样。要对事、对问题，不要对人。
比如谁在哪里错误了，我会指出来，你在哪里哪里有错误，或者我不赞同你的观点。
但是我一定不会说：“我比你熟悉、比你牛”类似这种话。这种话这就是对人了。
【 在 Insomnia 的大作中提到: 】
: 好好讨论嘛，版上好不容易有高水平讨论。bbs上写字有时候问题表述不清引出争议再所
: 难免，只要对事不对人就好了
:
: ...................
☆─────────────────────────────────────☆
Ella (陈嘉桦) 于 (Fri Sep 7 09:59:09 2012) 提到:
Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
☆─────────────────────────────────────☆
candes (candes) 于 (Fri Sep 7 11:29:26 2012) 提到:
Thanks.
学习了
【 在 Ella 的大作中提到: 】
: Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
☆─────────────────────────────────────☆
ezgz (老X) 于 (Fri Sep 7 12:28:58 2012) 提到:
re最后一句，小弟当年也试图看过一些CS的文章，没几篇文章就别符号绕晕了，只好敬而远之了。。。。
【 在 Ella (陈嘉桦) 的大作中提到: 】
: 标 题: Re: 请教：关于p-norm的最小化问题
: 发信站: 水木社区 (Fri Sep 7 09:59:09 2012), 站内
:
: Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
: --
:
: ※ 来源:·水木社区 http://newsmth.net·[FROM: 166.111.131.*]
标 题: [合集] 请教：关于p-norm的最小化问题
发信站: 水木社区 (Thu Sep 13 08:31:57 2012), 站内
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 20:07:17 2012) 提到:
两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
2.当0
因为非凸函数f(a)的全局最小值，可能在多个不同的自变量处取得，比如f(a)=sin(a), a在-pi/2+2*k*pi(k为整数)，无穷多处都取得全局最小值-1.但是，我觉得这个p-norm问题不会，画了图，最优的a是唯一的。
恳请赐教、帮忙！
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 21:49:40 2012) 提到:
p<1不是norm
【 在 candes (candes) 的大作中提到: 】
: 两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
: 1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
: 2.当0
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 21:59:20 2012) 提到:
0
【 在 asker 的大作中提到: 】
: p<1不是norm
:
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 22:04:27 2012) 提到:
上条回复你的帖子漏了 p=+infinity，p=+infinity也是norm。另外p=0，||x||_0是向量x的非零元素个数，不是norm。数学家称其为伪norm。
【 在 asker 的大作中提到: 】
: p<1不是norm
:
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:14:48 2012) 提到:
试试 ‖(2,2)‖_0.5 和 ‖(0.5, 1.5) ‖_0.5 + ‖(1.5, 0.5) ‖_0.5
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:20:09 2012) 提到:
http://en.wikipedia.org/wiki/Minkowski_inequality
条件是 1<= p <= +inf
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 22:34:07 2012) 提到:
？？
Sorry，我真的记错了？
Thanks勘误。
但是不管它叫不叫norm，不影响这个问题。
p<1不是norm, 也是metric
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Minkowski_inequality
: 条件是 1<= p <= +inf
:
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Sun Sep 2 22:57:27 2012) 提到:
http://en.wikipedia.org/wiki/Metric_(mathematics)
d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
【 在 candes (candes) 的大作中提到: 】
: ？？
: Sorry，我真的记错了？
: Thanks勘误。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 23:07:02 2012) 提到:
http://en.wikipedia.org/wiki/Lp_space
第1.2节
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Metric_(mathematics)
: d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
:
☆─────────────────────────────────────☆
candes (candes) 于 (Sun Sep 2 23:10:18 2012) 提到:
OK。Thanks你的勘误。p<1也构成lp space.这个原因导致我之前一直把所有的都叫norm。这些不影响我的原问题。你对原问题有什么好的见解吗？thanks
【 在 asker 的大作中提到: 】
: http://en.wikipedia.org/wiki/Metric_(mathematics)
: d(x, z) ≤ d(x, y) + d(y, z) (subadditivity / triangle inequality).
:
☆─────────────────────────────────────☆
CrTn (求！包！养！) 于 (Mon Sep 3 00:03:16 2012) 提到:
这id牛逼
【 在 candes (candes) 的大作中提到: 】
: 0
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Wed Sep 5 06:45:49 2012) 提到:
能給講講0－norm和1－norm的關連性麼
【 在 candes (candes) 的大作中提到: 】
: 上条回复你的帖子漏了 p=+infinity，p=+infinity也是norm。另外p=0，||x||_0是向
量x的非零元素个数，不是norm。数学家称其为伪norm。
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 11:32:57 2012) 提到:
我就说说基本的，轻拍。。。
在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
求解A*x=b的最稀疏解，可以表示成：
min ||x||_0 （P0）
s.t. A*x=b
由于信号非零个数||x||_0导致组合优化问题，这个问题是NP-hard。采用和0-norm最接近的凸函数norm，就是1-norm，来relax这个0-norm，导致一个凸优化问题：
min ||x||_1 （P1）
s.t. A*x=b
（P1）可以用Linear Programming有效搞定。
问题是，(P0)给出的解和(P1)给出的解是一样吗？这个可能就是你问要问的两者的联系。
这个问题是整个sparse approximation的核心问题之一，Donoho，Candes， Tao等人证明了，在满足某些条件时（请看他们论文），(P0)给出的解和(P1)给出的解exactly the same！这也许是你想问的0-norm和1-norm的关联吧。
【 在 chengyue 的大作中提到: 】
: 能給講講0－norm和1－norm的關連性麼
: 量x的非零元素个数，不是norm。数学家称其为伪norm。
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Wed Sep 5 12:35:34 2012) 提到:
其实我想问的就是这个证明...
这个证明的结果是概率意义上的收敛，但是我就没看懂是对于什么收敛，还有就是收敛速度到底多快。另外就是整个证明的中心思想到底是什么，看到了一堆引理定理，但是主线没看懂。
【 在 candes (candes) 的大作中提到: 】
: 我就说说基本的，轻拍。。。
: 在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
: 求解A*x=b的最稀疏解，可以表示成：
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Wed Sep 5 12:57:03 2012) 提到:
最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
【 在 candes (candes) 的大作中提到: 】
: 标 题: Re: 请教：关于p-norm的最小化问题
: 发信站: 水木社区 (Wed Sep 5 11:32:57 2012), 站内
:
: 我就说说基本的，轻拍。。。
: 在sparse approximation里面，描述信号稀疏性（sparsity）的量是信号非零元素个数。
: 求解A*x=b的最稀疏解，可以表示成：
: min ||x||_0 （P0）
: s.t. A*x=b
: 由于信号非零个数||x||_0导致组合优化问题，这个问题是NP-hard。采用和0-norm最接近的凸函数norm，就是1-norm，来relax这个0-norm，导致一个凸优化问题：
: min ||x||_1 （P1）
: s.t. A*x=b
: （P1）可以用Linear Programming有效搞定。
: 问题是，(P0)给出的解和(P1)给出的解是一样吗？这个可能就是你问要问的两者的联系。
: 这个问题是整个sparse approximation的核心问题之一，Donoho，Candes， Tao等人证明了，在满足某些条件时（请看他们论文），(P0)给出的解和(P1)给出的解exactly the same！这也许是你想问的0-norm和1-norm的关联吧。
:
:
:
: 【 在 chengyue 的大作中提到: 】
: : 能給講講0－norm和1－norm的關連性麼
: : 量x的非零元素个数，不是norm。数学家称其为伪norm。
:
: --
:
: ※ 来源:·水木社区 http://newsmth.net·[FROM: 144.214.108.*]
☆─────────────────────────────────────☆
asker (whoo-ah!) 于 (Wed Sep 5 14:27:16 2012) 提到:
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
x这里是n维的吧？要变成d维 最后补零吗？
: 所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
: 而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 17:25:47 2012) 提到:
这个不是迭代算法，没有收敛速度一说。这是证明在RIP条件下，（P1）和（P0）会以概率1给出等价的解。他们的证明的框架确实是基于概率，即这这面的矩阵A（measurement matrix）是一个随机矩阵，可以使randon Gaussian, randon 伯努利等，这样每个观测，就是原信号x的随机线性组合。
另外，当信号不是那么稀疏时（稀疏度（非零个数）不会远远小于观测数目），ell_1搞不定的。有一些改进，比如Candes的reweighted ell_1（本质上已经采用非凸的log(1+|x|)函数了），就提高了精确恢复概率。
这个证明确实太复杂了，我也没有完全都搞明白。我觉得，这个证明必然不是那么容易搞定的。我看了几遍，没有完全懂，我也不急。不懂完全是正常的。因为，这本来就是很难的问题，在Candes和Tao证明之前。很多牛人也做了大量工作，包括Donoho和Elad等。否则不会吸引那么多顶级的头脑去（包括Tao）去做这个工作。而且成为milestone的工作。
轻拍。。。
【 在 chengyue 的大作中提到: 】
: 其实我想问的就是这个证明...
: 这个证明的结果是概率意义上的收敛，但是我就没看懂是对于什么收敛，还有就是收敛速度到底多快。另外就是整个证明的中心思想到底是什么，看到了一堆引理定理，但是主线没看懂。
☆─────────────────────────────────────☆
candes (candes) 于 (Wed Sep 5 17:41:30 2012) 提到:
y=A*x, A 是n by m, x是m-dimensional,CS和sparse里面讨论的是underdetermined情况，即n
这样，你说的，随便取出n列，求逆，得到的结果，还有n个非零元素，稀疏度明显大于K。怎么可能是min L0 norm解？你的这个结论是不正确的。
你说min L0 norm给出的解不是唯一的这个结论也未必正确。非凸问题的全局最优可能是唯一的，也可能不是唯一的。
min L1 norm的解也不能保证唯一(可能唯一，也可能不唯一)，导致这个问题的本质原因在于：虽然L1-norm是凸的，但不是严格凸的。但是满足一些条件时，（P1）会给出（P0）的exact solution。
【 在 SPAM 的大作中提到: 】
: 最简单的例子，假设A是一个n by d的矩阵，取任何n列可以得到一个full rank的方阵A\'。那么x=A\'^{-1}b就是L0 norm问题的一个解（因为x的非零元素都是n个）。
: 所以L0 norm导致的不是无法求解，而是解根本不唯一，并且大部分情况下解都不唯一导致根本无法实现exact recovery。
: 而虽然L1 norm也存在解不唯一的问题，但是问题要小很多。在RIP的条件假下，exact recovery是完全可能的。
: ...................
☆─────────────────────────────────────☆
likesnow (还能像喜欢雪一样单纯的喜欢冬天嘛?) 于 (Thu Sep 6 00:54:07 2012) 提到:
p<1是唯一不好证。不过全局最优解很好求啊。
每一维的解yi/xi排序，分段内都是凹的，最优点必定在段边界。遍历一遍yi/xi就得到最优解了。如果唯一的话，估计也是遍历yi/xi来证。
【 在 candes (candes) 的大作中提到: 】
: 两个N维的非零向量x和y，a是一个标量，考虑优化问题 min f(a) =||y-a*x||_p，其中||.||_p表示向量的Lp-norm。
: 1. 当p>1时，f(a)是严格凸的，因此局部最小值唯一，并且等于唯一的全局最小值。
: 2.当0
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 05:19:16 2012) 提到:
我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
【 在 candes (candes) 的大作中提到: 】
: y=A*x, A 是n by m, x是m-dimensional,CS和sparse里面讨论的是underdetermined情况，即n
: 这样，你说的，随便取出n列，求逆，得到的结果，还有n个非零元素，稀疏度明显大于K。怎么可能是min L0 norm解？你的这个结论是不正确的。
: 你说min L0 norm给出的解不是唯一的这个结论也未必正确。非凸问题的全局最优可能是唯一的，也可能不是唯一的。
: ...................
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 09:11:12 2012) 提到:
这里的C是存在的某个常数吧。有没有具体取值？或者说这个条件只是一个存在性证明而无法实际用来检验
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 09:26:37 2012) 提到:
目前最sharp的分析结果是
n>=t+1, exact recovery的概率是1-exp(-0.5*(W-sqrt(t))^2)
t = 2K*log(m/K)+1.25K
W = n/sqrt(n+1)
常数的确往往很难通过实验准确验证。最多只能给个n,m,K变化的scale
【 在 chengyue (chengyue) 的大作中提到: 】
: 这里的C是存在的某个常数吧。有没有具体取值？或者说这个条件只是一个存在性证明而无法实际用来检验
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:19:25 2012) 提到:
对于underdetermed系统，解的uniqueness根本就没有。不加其他约束（比如sparse约束），uniqueness根本就没有讨论的意义。这是连大一学生都知道的事。
只有添加了约束才可能有。就算引入L1 norm norm constratint，uniqueness也未必就能保证。
我说的结论是OMP算法结果。（OMP并不会比基于L1的BP差多少，很多实验中下，我做仿真OMP比BP还更好）你再熟，你也没有Tropp熟悉。我陈述的结论是Tropp那篇TIT文章（现被引一千多次）。如果我的结论不对，那就是Tropp结论不对，你去Comments人家嘛。
【 在 SPAM 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:28:08 2012) 提到:
哎，现在的人，说话攻击别人欲望怎么就这么强。好好的讨论学术问题，你非得比来比去，说什么“至于说Compressive Sensing的理论，我自认比你熟...”。有什么问题都好好说，心平气和讨论。我上来问问题，和别人讨论。我们讨论的水平是有高低，甚至也有错误。有错误你指正，犯不着像你这么抬高自己，贬低别人。就算你比我熟悉，又能怎么样？
【 在 SPAM 的大作中提到: 】
: 我想说的是，引入L1 norm norm constratint是从undetermined linear system里，解的uniqueness开始就有了，而不是到了什么sparse的情况下才去研究的东西。
: 至于说Compressive Sensing的理论，我自认比你熟... ...你后面的陈述的根本就不对... ...
: 在i.i.d.的Gaussian Ensemble假设下，Compressive Sensing的exact recovery的条件是n>=C*K*log(m)。传统的求逆就是n>=m就行了，也不是你说的n>=K^2... ...
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 11:31:24 2012) 提到:
谢谢！这个解法已经搞定了。我特别关心的事全局最优点的唯一性问题。
如果不做什么假设，唯一性不能确定。
【 在 likesnow 的大作中提到: 】
: p<1是唯一不好证。不过全局最优解很好求啊。
: 每一维的解yi/xi排序，分段内都是凹的，最优点必定在段边界。遍历一遍yi/xi就得到最优解了。如果唯一的话，估计也是遍历yi/xi来证。
:
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:12:37 2012) 提到:
你引的根本就不对！
你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
【 在 candes (candes) 的大作中提到: 】
: 对于underdetermed系统，解的uniqueness根本就没有。不加其他约束（比如sparse约束），uniqueness根本就没有讨论的意义。这是连大一学生都知道的事。
: 只有添加了约束才可能有。就算引入L1 norm norm constratint，uniqueness也未必就能保证。
: 我说的结论是OMP算法结果。（OMP并不会比基于L1的BP差多少，很多实验中下，我做仿真OMP比BP还更好）你再熟，你也没有Tropp熟悉。我陈述的结论是Tropp那篇TIT文章（现被引一千多次）。如果我的结论不对，那就是Tropp结论不对，你去Comments人家嘛。
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:13:42 2012) 提到:
我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
【 在 candes (candes) 的大作中提到: 】
: 哎，现在的人，说话攻击别人欲望怎么就这么强。好好的讨论学术问题，你非得比来比去，说什么“至于说Compressive Sensing的理论，我自认比你熟...”。有什么问题都好好说，心平气和讨论。我上来问问题，和别人讨论。我们讨论的水平是有高低，甚至也有错误。有错误你指正
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:17:49 2012) 提到:
我说的是求解underdetermined 系统 A*x=b的solution的唯一性问题。
谁扯了？谁说sample compleixity问题了？你自己读清楚别人讨论的问题。
说话不要那么粗鲁！！！嘴巴不干净，学问也干净不到哪里去。
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:20:21 2012) 提到:
讨论学术问题，谁都可以犯错误（再说我的结论根本没错误）。就算有争议，你觉得别人有错，你指出来就行了，你说，“我哪里哪里错了”，别攻击别人。reviewer对投稿作者还不许任何攻击。亏你还是做学术的。
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:24:47 2012) 提到:
我引的就是是Tropp 2007年TIT的文章。摘要里就是我引的结论，哪里错了？
退一步说。Tropp以后的文章有提高，那只是提高了，并不代表之前的结论就错误了。
看来，你的逻辑都有大问题！Tropp 2007年发了文章提高了，那他之前发的文章就是错了？？你什么逻辑啊！那他以后再发一篇提高了的，你又说，2007年这篇又错了。。。
【 在 SPAM 的大作中提到: 】
: 你引的根本就不对！
: 你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:29:35 2012) 提到:
我一直就在围绕underdetermined系统的解的唯一性在讨论。只是为了说明和讨论清楚这个问题，不得不把sample 个数（measure number）。你这么熟悉，你应该知道，smaple个数的多少直接影响解的唯一性。讨论问题A，A可能会和很多因素相关。这些因素必须拿进来讨论。这个叫“扯”？？？看来你的逻辑不止只有一个地方有问题！
【 在 SPAM 的大作中提到: 】
: 我跟你说uniqueness的问题，你来跟我扯sample compleixity。扯得不对还不让人说啊。
:
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:33:19 2012) 提到:
你再去把2007 Tropp的paper “Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit”打开，睁大眼睛，看清楚，然后再说。
我说的K，就是Tropp里面的m，是稀疏度 （nonzero entries in dimension d）。我说的两个数量级，哪个错了？
【 在 SPAM 的大作中提到: 】
: 你引的根本就不对！
: 你自己去看原文, Tropp07对OMP的分析结果较Topp05对OMP的分析有所提高。
:
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 12:46:52 2012) 提到:
据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
【 在 SPAM (垃圾邮件) 的大作中提到: 】
: 目前最sharp的分析结果是
: n>=t+1, exact recovery的概率是1-exp(-0.5*(W-sqrt(t))^2)
: t = 2K*log(m/K)+1.25K
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:52:45 2012) 提到:
原文里说的是原来对OMP的分析拿不到optimal rate罢了。
你原文里那句话说你的结论是对OMP的。
如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
说到底你根本分不清楚，算法的upper bound和问题本身的lower bound。
【 在 candes (candes) 的大作中提到: 】
: 你再去把2007 Tropp的paper “Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit”打开，睁大眼睛，看清楚，然后再说。
: 我说的K，就是Tropp里面的m，是稀疏度 （nonzero entries in dimension d）。我说的两个数量级，哪个错了？
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 12:54:44 2012) 提到:
是的，恢复概率和矩阵的mutual coherence息息相关的。
在 chengyue 的大作中提到: 】
: 据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
☆─────────────────────────────────────☆
chengyue (chengyue) 于 (Thu Sep 6 12:58:23 2012) 提到:
我想知道个具体的联系，而不是一种定性的关联。但是目前为止能看明白的就是那个越小慧覆盖率越大这样的定性联系
【 在 candes (candes) 的大作中提到: 】
: 是的，恢复概率和矩阵的mutual coherence息息相关的。
: 在 chengyue 的大作中提到: 】
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 12:58:40 2012) 提到:
我说的是最原始的Compressive Sensing的设定，Gaussian i.i.d Ensemble的结果，A矩阵每行来自i.i.d N(0,I)。
如果是来自任意的N(0,S)，对S的最小特征值的scaling有要求，这个概率和常数也很难给出这么精确的分析了，据大部分情况都是存在一个常数，使得如何如何了。
那个概率不等式是从Gordan ineqaulity推出来的，构造还是挺麻烦的，而且Gordan文章本身写得不是很容易懂。
【 在 chengyue (chengyue) 的大作中提到: 】
: 据我所知，这个概率似乎还和A矩阵的coherence相关吧，不过具体关联还是没看明白
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:01:10 2012) 提到:
我后来有补上OMP。而且我还说了，OMP很优秀，不比BP弱（有时仿真还更强）。而且OMP计算简单，是个极有代表性的算法。我拿OMP作为例子来说，没有问题。我不可能把所有算法的结论都拿出来，说一遍。
你也要搞清楚，n>=d和O(m^2)哪个要求高，不一定。万一m很小，d很大。你说哪个要求松？
“如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。”这句话，我还是不同意是对的。
【 在 SPAM 的大作中提到: 】
: 原文里说的是原来对OMP的分析拿不到optimal rate罢了。
: 你原文里那句话说你的结论是对OMP的。
: 如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
: ...................
☆─────────────────────────────────────☆
SPAM (垃圾邮件) 于 (Thu Sep 6 13:08:40 2012) 提到:
你有空去看看Tropp05的文章吧，他那个分析是很旧的东西了。实验的设定也不一样。
对于n/d->0的情况，m*log(d)是lower bound。
他那个m^2的upper bound和d无关，根本就是在不同的(n,d)的scaling下得到的。
【 在 candes (candes) 的大作中提到: 】
: 我后来有补上OMP。而且我还说了，OMP很优秀，不比BP弱（有时仿真还更强）。而且OMP计算简单，是个极有代表性的算法。我拿OMP作为例子来说，没有问题。我不可能把所有算法的结论都拿出来，说一遍。
: 你也要搞清楚，n>=d和O(m^2)哪个要求高，不一定。万一m很小，d很大。你说哪个要求松？
: “如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。”这句话，我还是不同意是对的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:23:33 2012) 提到:
我的意思是，直接求逆，得到的解不会（严格一点，不能保证）是unique的 最优的那个。
没有看到Tropp 在2005有发关于OMP的文章，只看过2004年有一篇。
【 在 SPAM 的大作中提到: 】
: 你有空去看看Tropp05的文章吧，他那个分析是很旧的东西了。实验的设定也不一样。
: 对于n/d->0的情况，m*log(d)是lower bound。
: 他那个m^2的upper bound和d无关，根本就是在不同的(n,d)的scaling下得到的。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 13:33:29 2012) 提到:
我想自己还是分得清问题本身的lower bound和算法的upper bound。
问题本身的lower bound和矩阵A有关，有很多形式，来表达，比如A的mutual coherence，
矩阵的spark，Babel函数等。
好了，我们关于这个问题的讨论就这样吧，不再纠缠了。关于CS的东西，博大精深，还需要研究，感谢你的讨论。也祝你弄出更strong的结果。
【 在 SPAM 的大作中提到: 】
: 原文里说的是原来对OMP的分析拿不到optimal rate罢了。
: 你原文里那句话说你的结论是对OMP的。
: 如果A矩阵来自Gaussian i.i.d ensemble，只要n>=d就能搞定了，矩阵不可求逆的情况0概率，根本不用什么OMP。
: ...................
☆─────────────────────────────────────☆
Insomnia (完美主义是种病) 于 (Thu Sep 6 15:47:46 2012) 提到:
好好讨论嘛，版上好不容易有高水平讨论。bbs上写字有时候问题表述不清引出争议再所
难免，只要对事不对人就好了
【 在 candes (candes) 的大作中提到: 】
: 我想自己还是分得清问题本身的lower bound和算法的upper bound。
: 问题本身的lower bound和矩阵A有关，有很多形式，来表达，比如A的mutual coherence，
: 矩阵的spark，Babel函数等。
: ...................
☆─────────────────────────────────────☆
candes (candes) 于 (Thu Sep 6 20:24:16 2012) 提到:
嗯。我也觉得应该是这样。要对事、对问题，不要对人。
比如谁在哪里错误了，我会指出来，你在哪里哪里有错误，或者我不赞同你的观点。
但是我一定不会说：“我比你熟悉、比你牛”类似这种话。这种话这就是对人了。
【 在 Insomnia 的大作中提到: 】
: 好好讨论嘛，版上好不容易有高水平讨论。bbs上写字有时候问题表述不清引出争议再所
: 难免，只要对事不对人就好了
:
: ...................
☆─────────────────────────────────────☆
Ella (陈嘉桦) 于 (Fri Sep 7 09:59:09 2012) 提到:
Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
☆─────────────────────────────────────☆
candes (candes) 于 (Fri Sep 7 11:29:26 2012) 提到:
Thanks.
学习了
【 在 Ella 的大作中提到: 】
: Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
☆─────────────────────────────────────☆
ezgz (老X) 于 (Fri Sep 7 12:28:58 2012) 提到:
re最后一句，小弟当年也试图看过一些CS的文章，没几篇文章就别符号绕晕了，只好敬而远之了。。。。
【 在 Ella (陈嘉桦) 的大作中提到: 】
: 标 题: Re: 请教：关于p-norm的最小化问题
: 发信站: 水木社区 (Fri Sep 7 09:59:09 2012), 站内
:
: Compressed Sensing领域里07年的文章算是很老的了，这两年Candes，Donoho几个搞了很多新的结果，另外做machine learning和统计的人，比如Wainright及其学生、Zhang Tong也在搞类似的东西，在统计里把Compressed Sening推广成为high-dimsional inference，我觉得做的不比Candes等人的差，比如Wainwright 09 TIT的，那里面证明 n=2k log(p-k) 是LASSO能否recovery的临界点（渐进意义下）。另外，Compressed Sensing的关于维数的符号是一人一个习惯，比较乱，得提前交代清楚，否则容易起误会。
: --
:
: ※ 来源:·水木社区 http://newsmth.net·[FROM: 166.111.131.*]
No comments:
Post a Comment