论文部分内容阅读
稀疏恢复是许多应用领域的关键问题，包括信号处理，压缩感知，机器学习和计算机视觉等等。例如，信号的稀疏表示可以处理由字典冗余而造成的表示不唯一性。多视角学习中，联合稀疏表示有助于选择同类邻点。通过矩阵的低秩和稀疏分解，人脸图片中的阴影可以被移除。然而，无论在何种应用中，精确求解稀疏问题通常需要对各种非零位置的组合进行搜索，是十分困难的。 本文首先提出了求解稀疏恢复问题的移动凸包方法。新方法的基本思想是通过引入基数函数在局部区域上的凸包函数，从而得到原稀疏问题的局部凸松弛模型。局部限制能够避免松弛函数与基数函数有较大的偏差。因此，局部凸松弛模型的解本身能够很好地逼近理想稀疏解。进一步，本文提出通过移动凸包来迭代改善不够好的解，减小逼近误差。本文具体讨论和分析了移动凸包方法在三类稀疏恢复问题中的应用以及相关理论和算法。其次，本文研究了联合稀疏表示在多视角数据学习中的应用。基于表示系数，本文提出了同类邻点的选择方法和多视角流形聚类的联合稀疏邻域图模型。文本的主要工作如下: (1)针对著名的稀疏表示问题，提出了其局部凸松弛模型，并从理论上分析了算法恢复O(ε)误差解所需要的条件。通常这个条件弱于经典l1松弛模型所需的条件。由于该条件依赖于局部区域的中心和半径，本文研究了最优中心和半径的选取范围，证明最优中心的可选范围至少包含一个无界的多面体。本文提出了迭代更新局部区域的移动凸包方法，并讨论了其对理想稀疏解的逼近。由于稀疏表示问题中局部凸包函数分段线性和截断的复杂结构，本文仅从数值上证明了迭代方法的收敛性。本文还讨论了两种求解局部凸松弛模型的算法:不定点方法和交替方向乘子法。 (2)讨论了局部凸包思想在联合稀疏表示问题中的应用。联合稀疏的特殊结构导致无法直接应用稀疏表示中的局部凸松弛模型。为此，本文引入了一个非线性变换，并结合变换后空间上的局部凸包函数提出了新的局部凸松弛模型。虽然该凸松弛函数并不理想，但本文证明它仍然是行基数函数在某个局部区域上的凸包函数。因此新的松弛模型也能较好地逼近原始模型。本文给出了逼近性分析，证明局部凸松弛模型的解与理想解在较弱的条件下有O(ε)-误差逼近。利用模型的加权截断结构，本文证明如果理想解满足一定的分布条件，则迭代序列是收敛的且误差上界下降。平均情况分析说明联合稀疏矩阵列数的增加可以提升松弛模型在无噪声情况下精确恢复的可能性。此外，本文将给出求解局部凸松弛模型的算法，分析其收敛性。 (3)介绍了局部凸松弛模型和移动凸包方法在低秩稀疏分解问题上的应用。不同于之前的分解方法着重关注低秩部分的恢复，新方法加强了对稀疏部分的估计。结合稀疏矩阵上的局部凸包函数和低秩矩阵上的核范数约束或显式的低秩约束，本文提出了两个新的最优化模型来寻找低秩稀疏分解。应用移动凸包的思想，本文给出了一个外循环来迭代地改善局部区域。本文还给出了一种后处理改良技术进一步提高稀疏部分的稀疏性，同时保持或减小了低秩部分的秩。本文也给出求解最优化模型的算法，包括收敛性分析。 (4)利用联合稀疏表示，提出了多视角数据同类邻点的选择方法。基于联合稀疏表示系数，本文构造了多视角数据的联合稀疏邻域图并提出相关的快速聚类算法。本文还给出了两种预处理单视角图的策略以提升其一致性。处理后的图有助于提高其他基于图的多视角聚类算法的有效性。 (5)结合大量模拟和真实数据的例子，本文全面比较了移动凸包方法，贪婪方法和l1松弛等方法，从数值效果上说明了新方法的有效性，并验证了算法的数值收敛性。同时，真实数据集上的实验说明了联合稀疏邻域图方法在多视角流形聚类中的有效性。