Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

Spectral clustering is a cornerstone of unsupervised learning, yet its performance is notoriously sensitive to noise, outliers, and model perturbations. The authors address this by moving beyond standard spectral decomposition, which is prone to instability, and instead formulating the problem as a regularized optimization task on the Grassmann manifold. The goal is to recover a robust, sparse, and interpretable rank-K projection matrix that better reflects the underlying community structure.

The RPMA framework treats the projection matrix $X = UU^\top$ as the primary object of interest, effectively bypassing the rotational ambiguity inherent in traditional spectral embeddings. By defining the objective function as the minimization of the distance to the affinity matrix $A$ plus a regularization term $R(X)$, the authors incorporate structural priors—such as non-negativity, sparsity, and row-sum constraints—directly into the optimization.

To solve this nonconvex problem, the authors:

• Characterize the local geometry of the rank-K projection manifold, identifying it as equivalent to the Grassmann manifold.
• Derive first- and second-order optimality conditions using Lie-bracket representations.
• Develop a Riemannian gradient projection algorithm with backtracking line search.
• Introduce the Cayley-Sherman-Morrison-Woodbury (Cayley-SMW) method, which accelerates computation by avoiding repeated, expensive eigendecompositions.

The study demonstrates that incorporating entrywise regularization significantly improves the recovery of projection matrices in noisy environments. The theoretical analysis establishes the stability of the critical-point landscape under small regularization, confirming that the proposed approach is well-posed. Empirical results on both synthetic and real-world datasets show that RPMA consistently outperforms conventional spectral projection methods, yielding higher clustering accuracy and more robust community detection.