Dec, 2023

混合模型中草图操作符的 RIP 保证的再探讨

PDF
TL;DR在素描用于压缩混合建模的背景下，我们重新审视了对某些混合模型的素描操作符具有有限保留同构性质的现有证明。通过检查现有保证的不足之处，我们提出了一种替代性分析方法，避免了在绘制随机傅里叶特征以构建随机素描操作符时需要假设重要性抽样。我们的分析是基于对仅依赖于用于定义素描操作符的频率集合的有限保留同构常数的新确定性界限；然后我们利用这些界限来建立随机素描操作符的浓度不等式，从而得出所需的保证。我们的分析还为与快速随机线性操作符相关的频率进行结构化素描提供了理论保证的可能性。
发现论文，激发创造
  • Hilbert 空间中低维圆锥的稳定恢复：统一的 RIP

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

    Oct, 2015

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

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

    Nov, 2012

  • 压缩感知的概率和 RIP 缺失理论

    本研究介绍了一种压缩感知的简单且通用的理论，其传感机制会从概率分布 F 中独立随机选择感知向量，而且不需要约束等距性或随机信号模型即可从噪音测量的最小数量中忠实地恢复出近似稀疏信号。

    Nov, 2010

  • 准线性压缩感知

    研究压缩感知的一般框架，提出了一种非线性测量的自然推广方法，并证明了通过这些测量可以有效地计算和恢复稀疏信号。提出了三种算法，其中包括一种称为广义 OLS 的贪心算法，以及两种硬和软阈值迭代算法的自然推广方法，并证明了这些算法对于基于 Lipschitz 扰动的 RIP 矩阵的非线性测量具有强的恢复保证。

    Nov, 2013

  • 保证限制等距性质是困难的

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

    Apr, 2012

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

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

    Feb, 2013

  • RIP 下的正交匹配追踪稀疏恢复

    本文解析了正交匹配追踪算法，表明只需要 O (k̅ln d) 个随机投影，即可恢复一 k̅- 疏松信号的 2 - 范数，从而对于压缩感知应用，该方法比之前的方法所需的随机投影数量 O (k̅²ln d) 更小。

    May, 2010

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

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

    Jun, 2015

  • 时间到了：通过受限等距性质实现快速量化的随机嵌入

    该文研究了如何对线性嵌入进行量化，以实现快速处理时间，高效的数据压缩过程和新颖的保几何嵌入，证明了许多尊重受限等距性质的线性映射可以诱导出一个定量随机嵌入，并介绍了一种新的 “双矫正” 量化方案。

    Jul, 2016

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

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

    Apr, 2017