Dual Principal Component Pursuit for Learning a Union of Hyperplanes: Theory and Algorithms-猫眼课题宝

DOI：

发表时间：

2021

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Tianyu Ding;Zhihui Zhu;M. Tsakiris;R. Vidal;Daniel P. Robinson

最先进的子空间聚类方法是基于凸公式，其理论保证要求子空间是低维的。双主成分追踪（DPCP）是一种非凸方法，专门用于学习高维子空间，如超平面。然而，现有的分析DPCP在多超平面的情况下，缺乏一个精确的表征的数据的分布，涉及的数量是难以解释的。此外，基于递归线性规划的可证明算法效率不高。在本文中，我们引入了一个新的概念的几何优势，明确捕获的数据的分布，并推导出几何和概率条件下，DPCP的全局解决方案是一个正常的向量的几何占主导地位的超平面。然后，我们证明了超平面并的DPCP问题满足黎曼正则性条件，并使用这个结果来证明可扩展的黎曼次梯度方法表现出（局部）线性收敛到几何主导超平面的法向量。最后，我们表明，将DPCP集成到流行的子空间集群方案（例如K -集合）中，可以在集群超平面方面获得比最新技术更优越或有竞争力的上级性能。

State-of-the-art subspace clustering methods are based on convex formulations whose theoretical guarantees require the subspaces to be low-dimensional. Dual Principal Component Pursuit (DPCP) is a non-convex method that is speciﬁcally designed for learning high-dimensional subspaces, such as hyperplanes. However, existing analyses of DPCP in the multi-hyperplane case lack a precise characterization of the distribution of the data and involve quantities that are diﬃcult to interpret. Moreover, the provable algorithm based on recursive linear programming is not ef-ﬁcient. In this paper, we introduce a new notion of geometric dominance , which explicitly captures the distribution of the data, and derive both geometric and probabilistic conditions under which a global solution to DPCP is a normal vector to a geometrically dominant hyperplane. We then prove that the DPCP problem for a union of hyperplanes satisﬁes a Riemannian regularity condition, and use this result to show that a scalable Riemannian subgradient method exhibits (local) linear convergence to the normal vector of the geometrically dominant hyperplane. Finally, we show that integrating DPCP into popular subspace clustering schemes, such as K -ensembles, leads to superior or competitive performance over the state-of-the-art in clustering hyperplanes.

Dual Principal Component Pursuit for Learning a Union of Hyperplanes: Theory and Algorithms

文献摘要

相似文献