Exact Rank-Space KL Projection for Shared-Marginal Low-Rank Factors: Application to Doubly Stochastic Clustering

Traditional doubly stochastic (DS) graph learning models often struggle with a fundamental trade-off: they either require an explicit n-by-n matrix, which is computationally prohibitive for large datasets, or they use low-rank approximations that fail to maintain exact DS feasibility throughout the optimization process. This paper addresses this gap by developing a low-rank factorization framework that enforces exact DS constraints while remaining scalable and efficient.

The author proposes a shared-marginal factorization, W = U Diag(g)^-1 V^T, where U and V are nonnegative factors and g is a learned shared column marginal. By imposing row-simplex constraints on U and V, the resulting graph W is guaranteed to be doubly stochastic. The core technical contribution is a theorem showing that the joint KL projection for these factors reduces to a strictly convex dual problem in only r-1 dimensions. This allows for an objective-independent projection operator that can be integrated into a mirror-descent optimization framework. To handle sparse graph data, the method incorporates observed-edge fitting and a stochastic anchor-reduced manifold regularizer, avoiding the need to materialize dense graphs.

The study demonstrates that the proposed geometry allows for exact feasibility at every accepted mirror-descent step. The reduced-space Hessian admits matrix-free Hessian-vector products in O((n+m)r) time, making the approach highly scalable. Theoretical analysis confirms that the method satisfies sufficient decrease and an O(1/N) mirror-stationarity bound. Empirical experiments on clustering tasks show that the method achieves competitive accuracy and feasibility residuals near numerical precision, outperforming or matching existing low-rank alternatives without the storage overhead of dense graphs.

This work provides a rigorous geometric foundation for low-rank doubly stochastic learning. By decoupling the representation from the need for dense updates, it enables the application of DS clustering to much larger datasets than previously feasible. The objective-independent nature of the KL projection theorem also suggests broader utility for other constrained low-rank optimization problems beyond clustering.