论文标题
离散随机矩阵的稀疏恢复特性
Sparse recovery properties of discrete random matrices
论文作者
论文摘要
由压缩感测的问题激发，我们确定随机$ n \ times d $ $ \ pm的阈值行为1 $矩阵$ m_ {n，d} $相对于属性“每个$ s $列都是线性独立的”。 In particular, we show that for every $0<δ<1$ and $s=(1-δ)n$, if $d\leq n^{1+1/2(1-δ)-o(1)}$ then with high probability every $s$ columns of $M_{n,d}$ are linearly independent, and if $d\geq n^{1+1/2(1-δ)+o(1)}$ then with高概率有一些线性依赖的列。
Motivated by problems from compressed sensing, we determine the threshold behavior of a random $n\times d$ $\pm 1$ matrix $M_{n,d}$ with respect to the property "every $s$ columns are linearly independent". In particular, we show that for every $0<δ<1$ and $s=(1-δ)n$, if $d\leq n^{1+1/2(1-δ)-o(1)}$ then with high probability every $s$ columns of $M_{n,d}$ are linearly independent, and if $d\geq n^{1+1/2(1-δ)+o(1)}$ then with high probability there are some $s$ linearly dependent columns.
