摘要

基于 $\ell_1$、$\ell_2$ 或核范数正则化的子空间聚类方法因其简单性、理论保证和实证成功而变得非常流行。然而，正则化器的选择对理论和实践都有重大影响。例如，$\ell_1$ 正则化在广泛的条件下（如任意子空间和受污染的数据）可以保证生成子空间保持的亲和力（即不同子空间之间的点没有连接），但需要求解大规模的凸优化问题。另一方面，$\ell_2$ 和核范数正则化提供了高效的闭式解，但在保证生成子空间保持的亲和力时需要非常强的假设条件，例如独立子空间和未受污染的数据。本文研究了一种基于正交匹配追踪的子空间聚类方法。我们证明了该方法不仅计算效率高，而且在广泛的条件下也能保证生成子空间保持的亲和力。合成数据上的实验验证了我们的理论分析，而在手写数字和人脸聚类中的应用表明，我们的方法在准确性和效率之间取得了最佳平衡。