A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis
A nonconvex formulation for low rank subspace clustering: algorithms and convergence analysis
复制标题
DOI：
10.1007/s10589-018-0002-6
复制
发表时间：
2018-03
影响因子：
2.2
通讯作者：
Hao Jiang;Daniel P. Robinson;R. Vidal;Chong You
中科院分区：
文献类型：
--
作者：
Hao Jiang;Daniel P. Robinson;R. Vidal;Chong You
我们考虑数据的子空间聚类问题，这些数据可能会被密集噪声和稀疏粗差错误破坏。特别是，我们研究了最近提出的基于非凸建模公式的低秩子空间聚类方法。该公式在目标函数中包含非凸谱函数，这使得优化任务具有挑战性，例如，未知提出用于求解非凸模型公式的交替方向乘子法（ADMM）框架是否可证明收敛。在本文中，我们证明谱函数是可微的，并给出了计算导数的公式。此外，我们证明谱函数的导数是 Lipschitz 连续的，并为 Lipschitz 常数提供了明确的值。然后，这些事实用于为应如何选择 ADMM 方法中的惩罚参数提供下限。只要根据这个界限选择惩罚参数，我们就可以证明 ADMM 算法计算的迭代具有满足一阶最优性条件的极限点。我们还提出了基于近端梯度计算的第二种解决非凸问题的策略。通过人脸、数字聚类和运动分割的真实数据实验验证了算法的收敛性和性能。
We consider the problem of subspace clustering with data that is potentially corrupted by both dense noise and sparse gross errors. In particular, we study a recently proposed low rank subspace clustering approach based on a nonconvex modeling formulation. This formulation includes a nonconvex spectral function in the objective function that makes the optimization task challenging, e.g., it is unknown whether the alternating direction method of multipliers (ADMM) framework proposed to solve the nonconvex model formulation is provably convergent. In this paper, we establish that the spectral function is differentiable and give a formula for computing the derivative. Moreover, we show that the derivative of the spectral function is Lipschitz continuous and provide an explicit value for the Lipschitz constant. These facts are then used to provide a lower bound for how the penalty parameter in the ADMM method should be chosen. As long as the penalty parameter is chosen according to this bound, we show that the ADMM algorithm computes iterates that have a limit point satisfying first-order optimality conditions. We also present a second strategy for solving the nonconvex problem that is based on proximal gradient calculations. The convergence and performance of the algorithms is verified through experiments on real data from face and digit clustering and motion segmentation.