Low-Rank Riemannian Optimization for Graph-Based Clustering Applications

• Published in: IEEE transactions on pattern analysis and machine intelligence 2022-09, Vol.44 (9), p.5133-5148
• Main Authors: Douik, Ahmed, Hassibi, Babak
• Format: Article
• Language: English
• Subjects: Algorithms; Clustering; Clustering algorithms; Complexity; convex and non-convex optimization; Design optimization; Factorization; Geometry; graph-based clustering; low-rank factorization; Machine learning; Manifolds; Mathematical analysis; Matrices (mathematics); Operators (mathematics); Optimization; Quotients; Riemann manifold; Riemannian manifolds; Search problems; Statistical analysis; Symmetric matrices
• ISSN: 0162-8828; 1939-3539; 2160-9292
• DOI: 10.1109/TPAMI.2021.3074467

With the abundance of data, machine learning applications engaged increased attention in the last decade. An attractive approach to robustify the statistical analysis is to preprocess the data through clustering. This paper develops a low-complexity Riemannian optimization framework for solving optimization problems on the set of positive semidefinite stochastic matrices. The low-complexity feature of the proposed algorithms stems from the factorization of the optimization variable \mathbf {X}=\mathbf {Y}\mathbf {Y}^{\mathrm{T}} X=YYT and deriving conditions on the number of columns of \mathbf {Y} Y under which the factorization yields a satisfactory solution. The paper further investigates the embedded and quotient geometries of the resulting Riemannian manifolds. In particular, the paper explicitly derives the tangent space, Riemannian gradients and Hessians, and a retraction operator allowing the design of efficient first and second-order optimization methods for the graph-based clustering applications of interest. The numerical results reveal that the resulting algorithms present a clear complexity advantage as compared with state-of-the-art euclidean and Riemannian approaches for graph clustering applications.