Apr, 2017

限制等距性的近似认证是困难的

PDF
TL;DR本文研究矩阵的 Restricted Isometry Property（RIP），即在限制了稀疏向量时，矩阵能够给出一个近似的等度映射。先前研究表明，确定一个矩阵是否具有 RIP 是 NP 难的，但仅限于一定范围的参数。就算我们将实例局限于 RIP 或与之相差甚远，我们仍然不能在任何精度参数下确定矩阵是否拥有该特性。这个结果意味着在一个常数范围内，精度无法达到比简化参数更好的程度，因此无法近似确定矩阵具有 Restricted Isometry Property 的参数范围。我们是第一个在不依赖额外假设的前提下证明这种结论的研究。
发现论文，激发创造
  • 保证限制等距性质是困难的

    本文讨论了压缩感知中的一种重要矩阵条件，即受限等距性质 (RIP)。我们证明了测试矩阵是否满足 RIP 是 NP 困难问题。由于我们的结果，如果 P≠NP，则无法有效测试 RIP。

    Apr, 2012

  • 压缩感知中的受限等距性质、零空间性质及相关概念的计算复杂度

    本文主要研究了在怎样的条件下可以通过高效算法来解决 NP 难问题，这个问题是在欠定线性系统中发现最稀疏的解。通过研究出了互惠相干、限制等距性质和零空间特征来解决该问题，本文证实了计算 RIP 和 NSP 的最佳常数是 NP 难问题，并且讨论了与上述概念相关的几个复杂性陈述。

    May, 2012

  • 非凸矩阵恢复需要多少有限制等比性？

    本文研究了低秩矩阵恢复的局部极小点问题，分析了一定程度的受限等距性并不能消除这些极小点，而随机梯度下降算法在某些情况下可能无法避免或逃脱这些极小点。因此，对于低秩矩阵恢复的精确恢复保证需要证明不存在这些局部极小点而不是仅仅基于范数的保持。

    May, 2018

  • 非凸矩阵恢复中不存在虚假局部极小值的尖锐保质区间界

    本文引入证明技巧，针对 rank-1 矩阵恢复问题，证明当受限等距特性常数 delta 小于 1/2 时，不存在伪局部极小值，并且任何收敛到二阶最优性的下降算法可以保证精确恢复。

    Jan, 2019

  • 新的 RIP 矩阵构建方法，支持快速乘法且行数更少

    本文提出了一种随机构建压缩感知中支持快速矩阵向量乘法的受限等距矩阵（RIP）矩阵 Phi，其保留了几乎 k - 稀疏向量 x 的 L_2 范数，行数在 eps^{-2} klog dlog^2 (klog d) 左右，相对于先前的构造方法更加高效，而且可以用于快速迭代重构算法。此外，该技术还与 Johnson-Lindenstrauss 引理相联系，实现了渐近行数更少的快速 Johnson-Lindenstrauss 嵌入。

    Nov, 2012

  • 稀疏信号和低秩矩阵恢复的锐 RIP 界限

    本研究提出限制等距性条件片断地和完全地恢复稀疏信号和低秩矩阵，考虑噪声情况并给出 Sharp RIP 条件下的 Oracle 不等式。

    Feb, 2013

  • 使用受限等距性质分析正交匹配追踪算法

    使用受限等距性质 (RIP) 分析正交匹配追踪 (OMP) 算法，得出对于任何 K 稀疏信号，RIP 阶数为 K+1 时 (等距常数 δ<1/3K^(1/2)) 足以完全恢复信号。同时，基于 OMP 和满足 RIP 的矩阵之间的简单直觉观察得出信号高度可压缩时，RIP 的放松边界。

    Sep, 2009

  • 通过受限等距性质进行任意集合的等角素描

    本文表明一个特定结构的随机矩阵在降维方面类似于随机高斯矩阵，并且包括一些可以对矩阵 - 向量乘法进行 O (log n) 次计算的矩阵，从而提供了一种有效的通用集降维方法。通过连接任何集降维并使用链式论证将其连接到稀疏向量的降维，我们表明使用此类矩阵可以将高维度的任何集嵌入到较低的维度中，并且失真非常小。

    Jun, 2015

  • Hilbert 空间中低维圆锥的稳定恢复：统一的 RIP

    本论文研究在信号处理中的反问题中，利用低维模型和适当的正则化方法稳健地估计未知数据的问题，详细介绍了使用稀疏模型与 1 - 范数或低秩模型与核范数相结合的有效方法，并且使用一般的 RIP 原则保证了锥的稳定回收，为无限维度情况下的块结构稀疏性提供了一系列可控制 RIP 常数的 正则化方法。

    Oct, 2015

  • 通过受限等距性质改进的 Johnson-Lindenstrauss 嵌入

    通过对具有 k 阶和级别 δ 的稀疏矩阵 Phi 进行列符号随机化，该结果可以很好地嵌入 R^N 中的任何固定点集至 R^m 中，是 Johnson-Lindenstrauss 嵌入的最优算法，在部分 Fourier 和部分 Hadamard 矩阵中，该算法优于各种最优算法。此外，该研究结果在冗余字典的压缩感知中也具有直接应用。

    Sep, 2010