Low-Rank Optimization Methods Based on Projected Projected-Gradient Descent That Accumulate at Bouligand Stationary Points

This paper considers the problem of minimizing a differentiable function with locally Lipschitz continuous gradient on the algebraic variety of real matrices of upper-bounded rank. This problem is known to enable the formulation of various machine learning or signal processing tasks such as dimensionality reduction, collaborative filtering, and signal recovery. Several definitions of stationarity exist for this nonconvex problem. Among them, Bouligand stationarity is the strongest necessary condition for local optimality. This paper proposes two first-order methods that generate a sequence in the variety whose accumulation points are Bouligand stationary. The first method combines the well-known projected projected-gradient descent map with a rank reduction mechanism. The second method is a hybrid of projected gradient descent and projected projected-gradient descent. Both methods stand out in the field of low-rank optimization methods when considering their convergence properties, their streamlined design, their typical computational cost per iteration, and their empirically observed numerical performance. The theoretical framework used to analyze the proposed methods is of independent interest.

Funding: This work was supported by the Fonds de la Recherche Scientifique–FNRS and the Fonds Wetenschappelijk Onderzoek–Vlaanderen [EOS Project 30468160], by the Fonds de la Recherche Scientifique–FNRS [Grant T.0001.23], by G-Statistics from the European Research Council under the European Union’s Horizon 2020 research and innovation program [Grant 786854], and by the French government through the 3IA Côte d’Azur Investments [Grant ANR-23-IACL-0001] managed by the National Research Agency. K. A. Gallivan was partially supported by the U.S. National Science Foundation [Grant CIBR 1934157]. This work was done in part when K. A. Gallivan was visiting UCLouvain, supported by the “Professeurs et chercheurs visiteurs” budget of the Science and Technology Sector.