非对称伯努利矩阵是否满足 RIP?

信息处理 压缩传感
2022-01-12 17:40:53

定义一个n×N传感矩阵A经过Aij=0有概率p, 和Aij=1/n有概率1p. A满足受限等距性质?

作为参考,对称情况在以下论文中得到解答:

RG Baraniuk、MA Davenport、RA DeVore 和 MB Wakin,“随机矩阵受限等距属性的简单证明”,建设性近似,28(3) pp. 253-263,2008 年 12 月。 ( pdf )

1个回答

正如其他人在评论中所说,答案是“不”。矩阵的非零均值表明非零均值向量(例如,全为 1)将比具有零均值的随机向量(例如均匀随机 +1,-1)具有显着更高的增益。

考虑 A 乘以常数向量 y 的平方范数,预期为 n*(p*N)^2。(期望的迭代)

A 乘以从 (-1,+1) 均匀绘制的向量 x 的平方范数预计为 n*(p*N)。(可通过二项分布的方差之和计算)

x 和 y 的范数相同,但转换后的范数的期望值相差 p*N 倍——随着维度变大而发散。

这是帮助演示的matlab代码。

n=2000;
N=1000;
p=.9;
A=double(rand(n,N)<p); 
x=sign(randn(N,1)); 
y=ones(N,1);
Ex_normSqAx = n*(N*p);  % E[ squared norm of A times random signs ]
Ex_normSqAy = n*(N*p)^2; % E[ squared norm of A times constant vector ]
normSqAx = norm(A*x)^2;
normSqAy = norm(A*y)^2;