Nov, 2012
新的 RIP 矩阵构建方法,支持快速乘法且行数更少
New constructions of RIP matrices with fast multiplication and fewer rows
Jelani Nelson, Eric Price, Mary Wootters
TL;DR本文提出了一种随机构建压缩感知中支持快速矩阵向量乘法的受限等距矩阵(RIP)矩阵 Phi,其保留了几乎 k - 稀疏向量 x 的 L_2 范数,行数在 eps^{-2} klog dlog^2 (klog d) 左右,相对于先前的构造方法更加高效,而且可以用于快速迭代重构算法。此外,该技术还与 Johnson-Lindenstrauss 引理相联系,实现了渐近行数更少的快速 Johnson-Lindenstrauss 嵌入。