# Computing Bouligand stationary points efficiently in low-rank optimization

arXiv: https://arxiv.org/abs/2409.12298 · HTML: https://mlsanity.com/paper/2409.12298/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Sep 2024.

## Built on by (most cited first, 2 of 2)

- [Manifold constrained steepest descent for smooth and closed-set optimization](https://mlsanity.com/paper/2601.21487/) (2026)
- [A space-decoupling framework for optimization on bounded-rank matrices with orthogonally invariant constraints](https://mlsanity.com/paper/2501.13830/) (2025)

## Abstract (arXiv)

This paper considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the algebraic variety of all m-by-n real matrices of rank at most r. Several definitions of stationarity exist for this nonconvex problem. Among them, Bouligand stationarity is the strongest necessary condition for local optimality. Only a handful of algorithms generate a sequence in the variety whose accumulation points are provably Bouligand stationary. Among them, the most parsimonious with (truncated) singular value decompositions (SVDs) or eigenvalue decompositions can still require a truncated SVD of a matrix whose rank can be as large as minm, n-r+1 if the gradient does not have low rank, which is computationally prohibitive in the typical case where r ll minm, n. This paper proposes a first-order algorithm that generates a sequence in the variety whose accumulation points are Bouligand stationary while requiring SVDs of matrices whose smaller dimension is always at most r. A standard measure of Bouligand stationarity converges to zero along the bounded subsequences at a rate at least O(1/√i+1), where i is the iteration counter. Furthermore, a rank-increasing scheme based on the proposed algorithm is presented, which can be of interest if the parameter r is potentially overestimated.