Riemannian Diffusion Adaptation over Graphs with Application to Online Distributed PCA

Xiuheng Wang, Ricardo Augusto Borsoi, Cédric RichardICASSP 2024 · DOI

Introduction

Distributed network learning has traditionally focused on Euclidean spaces, where data and parameters reside in "flat" geometric structures. However, many real-world problems, such as online Principal Component Analysis (PCA), are naturally constrained to non-Euclidean geometries known as Riemannian manifolds. In PCA, for instance, the solution must be an orthonormal matrix, defining a curved space. While incremental and consensus methods have been adapted for manifolds, diffusion strategies—valued for their stability and performance under constant learning rates—remained largely unexplored in this context. This paper bridges that gap by introducing Riemannian Diffusion Adaptation.

Proposed Framework: ATC and CTA Diffusion

The authors generalize standard diffusion strategies to curved manifolds through two decentralized architectures: Adapt-Then-Combine (ATC) and Combine-Then-Adapt (CTA). These strategies involve a two-stage process:

  1. Adaptation: Each agent performs a local update using Riemannian Stochastic Gradient Descent (SGD). To ensure the updated estimate remains on the manifold, "retractions" are employed (e.g., ensuring a matrix remains orthogonal after an update).
  2. Combination: Agents share their local estimates with neighbors. Averaging these estimates on a curved surface requires the weighted Fréchet mean, calculated locally via a few iterations of Riemannian steepest descent.

For PCA, the authors utilize the Grassmann manifold (the space of linear subspaces). This choice is more efficient than the Stiefel manifold because it treats equivalent basis sets as the same point, resulting in a unique and cleaner optimization landscape.

Experimental Evaluation

The proposed algorithms were tested on both synthetic and real-world datasets:

  • Synthetic Data: 1,000,000 points from a multivariate Gaussian model.
  • MNIST Dataset: 70,000 handwritten digits, where 20 agents collaboratively computed the top 10 principal components.
Performance of Riemannian Diffusion strategies on synthetic and real (MNIST) data across a 20-node graph topology.

Key Results and Insights

The experimental results highlight several critical findings regarding the effectiveness of distributed manifold learning:

  • Cooperation Gains: Diffusion strategies (ATC and CTA) significantly outperform non-cooperative agents. The communication between neighbors allows the network to approach the performance of a centralized processor.
  • Proximity to Centralized Performance: The Mean Square Deviation (MSD) for diffusion methods converges close to the centralized baseline, which represents the theoretical performance limit if all data were processed at a single node.
  • Strategy Comparison: Consistent with Euclidean space research, the ATC strategy demonstrated a slight performance advantage over CTA.
  • The Role of the Fréchet Mean: The Fréchet mean is essential for correctly sharing information across the graph; simple coordinate averaging fails on curved manifolds as the average of two points on a manifold is not necessarily on that manifold.

Limitations and Future Directions

While empirically robust, the paper identifies several areas for further research. Currently, there is a lack of formal mathematical proofs for convergence and stability in the Riemannian case. Additionally, calculating the Fréchet mean introduces computational overhead compared to Euclidean averaging, requiring an inner optimization loop at each step. Future work may also include broader comparisons with other decentralized manifold methods like Riemannian Consensus.

Summary updated

BibTeX
@inproceedings{wang2024riemannian,
  author = {Xiuheng Wang and Ricardo Augusto Borsoi and Cédric Richard},
  title = {{Riemannian Diffusion Adaptation over Graphs with Application to Online Distributed PCA}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2024},
  doi = {10.1109/icassp48485.2024.10446975},
}
Figure