奇异值投影保证秩最小化
针对在低秩矩阵中最小化凸函数的问题,本文提出了一种高效的贪心算法,并给出其形式化的逼近保证。算法的每次迭代都涉及到计算某个矩阵的最大奇异值对应的左、右奇异向量,这可以在线性时间内完成。该算法可应用于矩阵完成和鲁棒低秩矩阵逼近等多个领域中的大型矩阵问题。
Jun, 2011
本文研究了在满足给定的线性等式约束的前提下寻找一个满足最小秩的矩阵的问题,证明在线性变换满足一定的保型性条件下,可以通过解决一个凸优化问题来恢复最小秩解,即在给定仿射空间上,通过最小化核范数来建立几个随机方程整体满足保型性条件,进而将基数最小化的概念推广到秩最小化上。
Jun, 2007
本文提出了固定点迭代算法和 Bregman 迭代算法来解决核范数最小化的问题,并证明了前者的收敛性。通过使用同伦方法和近似奇异值分解过程,我们得到了一个非常快速,鲁棒和强大的算法,称为 FPCA(具有近似 SVD 的固定点连续化),它可以解决非常大的矩阵秩最小化问题。在随机生成和真实矩阵完成问题方面的数值结果表明,这个算法比如 SDPT3 等半定规划求解器更快,且能提供更好的恢复性能。在在线推荐,DNA 微阵列数据集和图像修复问题上的数值实验证明了我们算法的有效性。
May, 2009
本论文提出了一种改进版的鲁棒主成分分析方法,使用部分奇异值之和代替核范数,隐式地鼓励目标秩约束。实验结果表明,该方法在样本数不足时比传统鲁棒主成分分析方法有更高的成功率,在样本数充足时两种方法得到的解几乎相同。该方法在高动态范围成像、运动边缘检测、光度立体、图像对齐和恢复等低级视觉问题上都表现出优异的结果。
Mar, 2015
本文介绍了一种针对低秩矩阵恢复的秩 - 1 投影模型并提出了一种受约束的核范数最小化方法,该方法能够适应不同秩的矩阵并对细微扰动具有强鲁棒性,同时通过引入上下界对其精度进行了数学证明。此外,该方法对解决其他相关的统计问题具有启示作用。最后,将该方法应用于一维随机投影估算高维分布的协方差矩阵,证明了该方法的可行性和精度。
Oct, 2013
本文介绍了一种新的算法,用于近似矩阵和满足一组凸约束条件的所有矩阵中具有最小核范数的矩阵。该算法可在低阶矩阵完成问题上使用,具有快速计算的特点,通过少量存储空间实现低计算代价。
Oct, 2008
利用核范数正则化寻找结构化低秩矩阵的问题,我们采用线性映射来编码结构,并提出了一种更有效的方法,与同类方法相比,该方法在迭代次数和计算成本上都有所改善,并在随机系统实现和光谱压缩感知问题中表现出色。
Sep, 2015
本文提出一种简单的交替最小化算法,提供了带权重低秩矩阵恢复的可证明的等保障,并不需要关于噪声的假设,其误差随交替次数按指数级递减,初始矩阵可以由 SVD 或随机初始化得到,这是一种非常简单的算法,可以显着扩展矩阵补全的结果,特别是那些存在于现有研究工作中的二进制权重问题。
Feb, 2016
本文介绍了一种基于反正切函数的更紧密逼近秩函数的方法,并使用它来解决具有挑战性的子空间聚类问题,并开发了一种基于增广拉格朗日乘数方法的有效优化过程。实验结果表明,所提出的方法对于秩逼近问题十分有效。
Oct, 2015
本文提出了一种基于变分近似的经验贝叶斯程序,用于低秩矩阵估计,与核范数不同的是,该方法保留了很多有用约束下与秩函数相同的全局最小点估计。该方法适用于广泛的低秩学习应用,特别是强健主成分分析问题(RPCA)。
Aug, 2014