子采样傅里叶矩阵的有限等距特性
通过对具有 k 阶和级别 δ 的稀疏矩阵 Phi 进行列符号随机化,该结果可以很好地嵌入 R^N 中的任何固定点集至 R^m 中,是 Johnson-Lindenstrauss 嵌入的最优算法,在部分 Fourier 和部分 Hadamard 矩阵中,该算法优于各种最优算法。此外,该研究结果在冗余字典的压缩感知中也具有直接应用。
Sep, 2010
本文探讨了一类随机矩阵是否满足 Restricted Eigenvalue 条件,引入了额外的协方差结构,借助几何泛函分析的工具来分析样本复杂性,并了解其对高维数据的统计影响。
Dec, 2009
本文表明一个特定结构的随机矩阵在降维方面类似于随机高斯矩阵,并且包括一些可以对矩阵 - 向量乘法进行 O (log n) 次计算的矩阵,从而提供了一种有效的通用集降维方法。通过连接任何集降维并使用链式论证将其连接到稀疏向量的降维,我们表明使用此类矩阵可以将高维度的任何集嵌入到较低的维度中,并且失真非常小。
Jun, 2015
本文研究了压缩感知中的 $\ell_1$ 最小化问题,证明了只要压缩感知矩阵的限制等距常数 $\delta_k$ 满足 $\delta_k < 0.307$,在无噪声情况下可以完美地恢复 $k$- 稀疏信号,并且可以在有噪声情况下稳定地估计 $k$- 稀疏信号。
Nov, 2009
本文研究矩阵的 Restricted Isometry Property(RIP),即在限制了稀疏向量时,矩阵能够给出一个近似的等度映射。先前研究表明,确定一个矩阵是否具有 RIP 是 NP 难的,但仅限于一定范围的参数。就算我们将实例局限于 RIP 或与之相差甚远,我们仍然不能在任何精度参数下确定矩阵是否拥有该特性。这个结果意味着在一个常数范围内,精度无法达到比简化参数更好的程度,因此无法近似确定矩阵具有 Restricted Isometry Property 的参数范围。我们是第一个在不依赖额外假设的前提下证明这种结论的研究。
Apr, 2017
用子空间嵌入保证黑盒方式证明,通过降维映射可实现近似矩阵乘法的谱范数保障,其中降维映射具有 O(~r/ε^2)行,且优于以前的工作 [MZ11,KVZ14],对于任何混淆的降维映射也是最佳的。
Jul, 2015
该论文介绍了最近引入的 Restricted Eigenvalue 条件,这是关于矩阵的最一般假设之一,我们证明了可以通过在一定的低维子空间上检查受限等距性质来保证 RE 条件成立,从而建立了一些广泛类存在依赖项的随机矩阵上的 RE 条件及其保证。
Jun, 2011
本文提出了一种随机构建压缩感知中支持快速矩阵向量乘法的受限等距矩阵(RIP)矩阵 Phi,其保留了几乎 k - 稀疏向量 x 的 L_2 范数,行数在 eps^{-2} klog dlog^2 (klog d) 左右,相对于先前的构造方法更加高效,而且可以用于快速迭代重构算法。此外,该技术还与 Johnson-Lindenstrauss 引理相联系,实现了渐近行数更少的快速 Johnson-Lindenstrauss 嵌入。
Nov, 2012