【MIT博士论文】稀疏与低秩矩阵优化在机器学习应用中的进展

许多运筹学、机器学习和统计学中的基本问题可以自然地表示为带有基数或秩约束的优化问题。稀疏解因其良好的可解释性和存储优势而备受青睐。此外，在机器学习背景下，稀疏解展现了优越的模型泛化能力，并且在高维数据集中具有特征提取的自然意义。另一方面，由于矩阵的秩等同于其奇异值向量的基数，秩可以被视为稀疏性的矩阵推广。因此，低秩解继承了稀疏解的许多优点，同时提供了更灵活的建模能力。然而，基数和秩约束的优化问题通常是非凸的，并且在一般情况下是NP难问题，这导致研究者更多地依赖于凸松弛和启发式方法，而这些方法通常只能产生次优解。

本论文旨在推进稀疏与低秩矩阵优化的理论与应用，重点研究统计学和机器学习中的相关问题。我们通过混合整数和混合投影优化技术，开发了针对基数和秩约束问题的算法。所提出的算法在性能上超越了现有的凸松弛和启发式方法。通过严格的理论分析和实验验证，本研究致力于为优化理论的基础研究和统计与机器学习复杂问题的实践提供贡献。

第2章研究了稀疏加低秩矩阵分解问题。我们提出了一种交替最小化算法，该算法能够计算高质量的可行解，并在基准方法上表现优越，可扩展到维度n=10000n = 10000n=10000 的问题并在几分钟内完成计算。此外，我们设计了一种定制的分支定界算法，能够在几分钟内全局求解维度n=25n = 25n=25 的问题实例。

第3章探讨了压缩感知问题。针对该问题，我们提出了一种定制的分支定界算法，可以计算全局最优解。与当前最先进的基准方法相比，我们的方法在合成数据上平均稀疏性提高6.22%，在实际心电图（ECG）数据上稀疏性提高9.95%。此外，当用作多标签学习算法的一部分时，我们的方法在性能上也优于基准方法。

第4章研究了部分观测矩阵的学习问题，该问题旨在预测完全观测的辅助信息，这是矩阵补全问题的一个重要推广。我们将该问题重新表述为混合投影优化问题，并提出了一种基于交替方向乘子法（ADMM）的算法，可在不到一分钟内解决行列规模为n=10000n = 10000n=10000,m=10000m = 10000m=10000 的问题。在大规模真实数据上，该算法的解比基准方法的样本外误差低67%，执行时间减少97%。