A Preconditioned Riemannian Gradient Descent Algorithm for Low-Rank Matrix Recovery

Fengmiao Bian, Jian-Feng Cai, Rui ZhangSIAM J. Matrix Anal. Appl 2024 · DOI

TL;DR

This paper introduces a novel algorithm called Preconditioned Riemannian Gradient Descent (PRGD) for efficiently recovering low-rank matrices from incomplete measurements. PRGD significantly speeds up existing methods by introducing a data-driven metric that adapts to the problem's specific characteristics, leading to up to a tenfold reduction in computation time for tasks like matrix completion.

What Problem Does This Paper Address?

Many real-world problems, from signal processing and machine learning to image science, involve recovering an underlying low-rank matrix from a limited number of linear measurements. This is challenging because the number of measurements is often much smaller than the total number of entries in the matrix, making direct recovery impossible. Traditional methods like nuclear norm minimization can be slow due to the non-smoothness of the objective function, while non-convex approaches often struggle with convergence speed or require complex initialization. Existing Riemannian gradient descent (RGD) methods offer improvements but their efficiency is heavily dependent on the chosen metric. This paper aims to address this by developing a more effective, data-driven metric for RGD to accelerate convergence.

Methods

The core of this work is the development of a Preconditioned Riemannian Gradient Descent (PRGD) algorithm. It builds upon the Riemannian Gradient Descent (RGD) framework, which operates on the manifold of low-rank matrices. The key innovation is the introduction of a data-driven metric that replaces the standard canonical metric used in previous RGD methods. This new metric is constructed by incorporating information from the measurement data (y), the linear operator (A), and the current iteration's matrix (Xt).

Specifically, PRGD uses a preconditioning technique inspired by methods like AdaGrad and Shampoo, but adapted for the low-rank manifold setting. It constructs weighting matrices (Lt and Rt) based on the diagonal elements of accumulated gradient information. This metric is then restricted to the tangent spaces of the low-rank manifold. The algorithm uses a truncated Singular Value Decomposition (SVD) for retraction and aims to minimize the condition number of the sensing operator restricted to the tangent space. This approach allows for faster convergence without significantly increasing the computational cost per iteration compared to standard RGD.

Datasets

The paper evaluates the PRGD algorithm on simulated data for three main tasks:

  • Matrix Completion: Simulated datasets were generated with varying matrix sizes (up to 20000x20000) and oversampling ratios.
  • Matrix Sensing: Simulated datasets were generated with matrices of size 150x150 and varying oversampling ratios.
  • Phase Retrieval: Simulated datasets were generated for both real and complex cases with a signal length of 128.

Additionally, the authors used the Movielens 1M dataset for evaluating matrix completion on real-world data.

Key Insights and Ideas

  • Data-Driven Metric is Key: The most significant insight is that tailoring the metric of the optimization process to the specific data and problem instance can dramatically improve performance. A "one-size-fits-all" metric (like the canonical one) is not always optimal.
  • Preconditioning on Manifolds: The paper successfully extends preconditioning techniques, commonly used in linear algebra optimization, to the non-linear setting of Riemannian manifolds for low-rank matrices.
  • Efficiency Gains are Substantial: The experimental results show that PRGD isn't just incrementally better; it offers order-of-magnitude improvements in iteration counts and computational time in certain scenarios, especially for challenging problems.
  • Theoretical Guarantees: The authors provide theoretical guarantees for PRGD's convergence, showing it linearly converges to the true low-rank matrix under the Restricted Isometry Property (RIP), which is a standard assumption in this field.

Key Results

  • Speedup: PRGD demonstrated up to a tenfold speedup compared to standard RGD in matrix completion tasks.
  • Iteration Reduction: PRGD consistently required significantly fewer iterations than other state-of-the-art algorithms (NIHT, RGD, Shampoo) across various experiments. For example, in matrix sensing, adaptive-PRGD required about 1/2.35, 1/7.5, 1/9.4, and 1/2 the iterations of adaptive-RGD, NIHT, Shampoo, and PRGD, respectively.
  • Robustness: PRGD showed robustness to additive noise, with the error of the recovered matrix being proportional to the noise level.
  • Success Rates: In matrix sensing, adaptive-PRGD achieved comparable or better success rates than adaptive-RGD and PRGD, especially in challenging scenarios with small numbers of measurements and higher ranks.
  • Real-world Performance: On the Movielens dataset, PRGD achieved the smallest fitting error and required fewer iterations than other algorithms to reach a similar error level.

Limitations and Future Work

  • Phase Retrieval Computational Cost: While PRGD reduces iterations for phase retrieval, its current implementation's computational time is not significantly better than adaptive-RGD. The authors suggest future research to explore more efficient implementations of PRGD for this specific problem.
  • Extension to Other Problems: The authors propose extending PRGD to other recovery problems, such as low-rank tensor completion.
  • New Preconditioners: They also plan to develop new and more effective preconditioners tailored to different types of problems.

Summary updated

BibTeX
@article{bian2024preconditioned,
  author = {Fengmiao Bian and Jian-Feng Cai and Rui Zhang},
  title = {{A Preconditioned Riemannian Gradient Descent Algorithm for Low-Rank Matrix Recovery}},
  journal = {SIAM J. Matrix Anal. Appl.},
  year = {2024},
  doi = {10.1137/23m1570442},
}
Figure