Hilbert 空间中低维圆锥的稳定恢复:统一的 RIP
本文研究了低秩矩阵恢复的局部极小点问题,分析了一定程度的受限等距性并不能消除这些极小点,而随机梯度下降算法在某些情况下可能无法避免或逃脱这些极小点。因此,对于低秩矩阵恢复的精确恢复保证需要证明不存在这些局部极小点而不是仅仅基于范数的保持。
May, 2018
本文引入证明技巧,针对 rank-1 矩阵恢复问题,证明当受限等距特性常数 delta 小于 1/2 时,不存在伪局部极小值,并且任何收敛到二阶最优性的下降算法可以保证精确恢复。
Jan, 2019
研究压缩感知的一般框架,提出了一种非线性测量的自然推广方法,并证明了通过这些测量可以有效地计算和恢复稀疏信号。提出了三种算法,其中包括一种称为广义 OLS 的贪心算法,以及两种硬和软阈值迭代算法的自然推广方法,并证明了这些算法对于基于 Lipschitz 扰动的 RIP 矩阵的非线性测量具有强的恢复保证。
Nov, 2013
本文提出了一种随机构建压缩感知中支持快速矩阵向量乘法的受限等距矩阵(RIP)矩阵 Phi,其保留了几乎 k - 稀疏向量 x 的 L_2 范数,行数在 eps^{-2} klog dlog^2 (klog d) 左右,相对于先前的构造方法更加高效,而且可以用于快速迭代重构算法。此外,该技术还与 Johnson-Lindenstrauss 引理相联系,实现了渐近行数更少的快速 Johnson-Lindenstrauss 嵌入。
Nov, 2012
本文解析了正交匹配追踪算法,表明只需要 O (k̅ln d) 个随机投影,即可恢复一 k̅- 疏松信号的 2 - 范数,从而对于压缩感知应用,该方法比之前的方法所需的随机投影数量 O (k̅²ln d) 更小。
May, 2010
在素描用于压缩混合建模的背景下,我们重新审视了对某些混合模型的素描操作符具有有限保留同构性质的现有证明。通过检查现有保证的不足之处,我们提出了一种替代性分析方法,避免了在绘制随机傅里叶特征以构建随机素描操作符时需要假设重要性抽样。我们的分析是基于对仅依赖于用于定义素描操作符的频率集合的有限保留同构常数的新确定性界限;然后我们利用这些界限来建立随机素描操作符的浓度不等式,从而得出所需的保证。我们的分析还为与快速随机线性操作符相关的频率进行结构化素描提供了理论保证的可能性。
Dec, 2023
本文主要研究了在怎样的条件下可以通过高效算法来解决 NP 难问题,这个问题是在欠定线性系统中发现最稀疏的解。通过研究出了互惠相干、限制等距性质和零空间特征来解决该问题,本文证实了计算 RIP 和 NSP 的最佳常数是 NP 难问题,并且讨论了与上述概念相关的几个复杂性陈述。
May, 2012
本文研究矩阵的 Restricted Isometry Property(RIP),即在限制了稀疏向量时,矩阵能够给出一个近似的等度映射。先前研究表明,确定一个矩阵是否具有 RIP 是 NP 难的,但仅限于一定范围的参数。就算我们将实例局限于 RIP 或与之相差甚远,我们仍然不能在任何精度参数下确定矩阵是否拥有该特性。这个结果意味着在一个常数范围内,精度无法达到比简化参数更好的程度,因此无法近似确定矩阵具有 Restricted Isometry Property 的参数范围。我们是第一个在不依赖额外假设的前提下证明这种结论的研究。
Apr, 2017