Sep, 2016

应用 Burer-Monteiro 方法消除虚假局部最小值的非方阵矩阵感知

PDF
TL;DR本文探讨了基于受限等距性质（RIP）假设的非方阵矩阵感知问题，并关注了非凸形式化的矩阵分解，证明了矩阵分解不会在 RIP 下引入任何虚假的局部最小值。
non-square matrix sensingrestricted isometry propertynon-convex formulationrank-r matrixmatrix factorization
发现论文，激发创造
  • 非凸矩阵恢复中不存在虚假局部极小值的尖锐保质区间界

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

    Jan, 2019

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

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

    May, 2018

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

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

    Feb, 2013

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

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

    Nov, 2012

  • 非凸 Burer-Monteiro 方法在光滑半定规划中的应用

    本文研究了一类包括最大割、随机块模型社区检测、鲁棒 PCA、相位恢复和旋转同步等应用的半定规划 SDP，表明以 Burer-Monteiro 公式为代表的低秩 SDP 几乎从不具有虚假的局部最优解。

    Jun, 2016

  • 一类范约束矩阵问题的可证明 Burer-Monteiro 分解

    本文研究在具有强凸目标的低秩矩阵问题上使用投影梯度下降法。我们利用 Burer-Monteiro 分解方法隐式实现低秩性；这种分解方法引入了目标函数的非凸性。我们着重研究包括半正定（PSD）约束和特定矩阵范数约束在内的约束集。这些标准出现在量子态重构和相位恢复应用程序中。我们表明，非凸投影梯度下降在分解空间中偏爱局部线性收敛。我们通过一个新颖的下降引理建立我们的理论，该引理在不受限制的问题上最近的结果得到了非平凡的扩展。 这种算法称为投影因式梯度下降，简称 ProjFGD，并在量子状态重构和稀疏相位恢复应用程序方面表现出优异性能。

    Jun, 2016

  • 非凸低秩问题中不存在虚假局部极小点：统一的几何分析

    发展了一种新框架，旨在捕捉一般非凸低秩矩阵问题的共同局面，包括矩阵感知，矩阵完成和鲁棒 PCA，在优化风景线的现有分析的基础上进行了连接和简化，自然地导致了不对称矩阵完成和鲁棒 PCA 的新结果

    Apr, 2017

  • 鲁棒二阶非凸优化及其在低秩矩阵感知中的应用

    使用强污染模型的泛用框架，以高效且可靠的算法逼近具有维度无关的精度保证的二阶稳定点，可应用于含异常值的优化问题，特别在低秩矩阵感知中表现出鲁棒性，并证明了样本复杂性与维度存在二次依赖关系的统计查询下界。

    Mar, 2024

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

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

    Apr, 2012

  • 采用 Burer-Monteiro 分解和梯度下降的矩形矩阵完成的收敛分析

    利用正定矩阵在更高维度上的升阶和简单的梯度下降算法，我们能够以高概率线性收敛到全局最优解，从而有效地解决了矩阵 Completion 问题。

    May, 2016