<figure><img src="image_1.png" /></figure>

HAL
open science

# Computing Bouligand stationary points efficiently in low-rank optimization

Guillaume Olikier, P. -A. Absil

► To cite this version:

Guillaume Olikier, P. -A. Absil. Computing Bouligand stationary points efficiently in low-rank optimization. 2024. hal-04866009

HAL Id: hal-04866009

https://inria.hal.science/hal-04866009v1

Preprint submitted on 6 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# COMPUTING BOULIGAND STATIONARY POINTS EFFICIENTLY IN LOW-RANK OPTIMIZATION*

GUILLAUME OLIKIER† AND P.-A. ABSIL‡

**Abstract.** 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 $\min\{m, n\} - r + 1$ if the gradient does not have low rank, which is computationally prohibitive in the typical case where $r \ll \min\{m, 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/\sqrt{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.

**Key words.** convergence analysis, stationary point, critical point, low-rank optimization, determinantal variety, first-order method, tangent cones, singular value decomposition, QR factorization

**MSC codes.** 14M12, 65K10, 90C26, 90C30, 40A05

**1. Introduction.** Low-rank optimization concerns the problem of minimizing a real-valued function over a space of matrices subject to an upper bound on their rank. Applications abound in various fields of science and engineering. The present work addresses specifically the problem

$$ (1.1) \qquad \min_{X \in \mathbb{R}^{m \times n} \succeq_r 0} f(X) $$

of minimizing a differentiable function $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ with locally Lipschitz continuous gradient on the determinantal variety

$$ (1.2) \qquad \mathbb{R}_{\le r}^{m \times n} := \{ X \in \mathbb{R}^{m \times n} \mid \mathrm{rank} X \le r \}, $$

$m$, $n$, and $r$ being positive integers such that $r < \min\{m, n\}$. The following basic facts about this problem are expounded in [15, §1]: (i) determinantal varieties have been well studied in algebraic geometry; (ii) several instances of (1.1) are important in many applications; (iii) in general, computing an exact or approximate minimizer of (1.1) is intractable [4], and algorithms are only expected to find a stationary point of (1.1) [21, 22, 7, 24, 11, 16, 10, 18, 19], preferably a B-stationary point because

<footnote>*September 20, 2024</footnote>

<footnote>**Funding:** This work was funded by the Fonds de la Recherche Scientifique - FNRS and the Fonds Wetenschappelijk Onderzoek - Vlaanderen under EOS Project no 30468160, by the Fonds de la Recherche Scientifique - FNRS under Grant no T.0001.23, by the ERC grant #786854 G-Statistics from the European Research Council under the European Union's Horizon 2020 research and innovation program, and by the French government through the 3IA Côte d'Azur Investments ANR-19-P3IA-0002 managed by the National Research Agency.</footnote>

<footnote>†Université Côte d'Azur and Inria, Epione Project Team, 2004 route des Lucioles - BP 93, 06902 Sophia Antipolis Cedex, France (guillaume.olikier@inria.fr).</footnote>

<footnote>‡ICTEAM Institute, UCLouvain, Avenue Georges Lemaître 4, 1348 Louvain-la-Neuve, Belgium (pa absil@uclouvain.be).</footnote>
B-stationarity is the strongest necessary condition for local optimality; (iv) PGD [17, Algorithm 4.2], P²GDR [15, Algorithm 6.2], RFDR [13, Algorithm 3], HRTR [9, Algorithm 1], and some of their hybridizations are the only algorithms known to generate a sequence in $\mathbb{R}_{\le r}^{m \times n}$ whose accumulation points are B-stationary for (1.1); (v) among these algorithms, RFDR is the most parsimonious with (truncated) singular value decompositions (SVDs) or eigenvalue decompositions [15, Table 8.1], though it can require a truncated SVD of a matrix whose rank can be as large as $\min\{m, n\}-r+1$ if the gradient does not have low rank, which is computationally prohibitive in the typical case where $r \ll \min\{m, n\}$.

This paper extends RFDR to a new class of methods, dubbed ERFDR, where “E” stands for “extended”, which generate a sequence in $\mathbb{R}_{\le r}^{m \times n}$ whose accumulation points are B-stationary for (1.1). This class includes a subclass, called CRFDR, where “C” stands for “cheap”, that involves SVDs of matrices whose smaller dimension is always at most $r$. A standard measure of B-stationarity converges to zero along bounded subsequences at a rate at least $O(1/\sqrt{i+1})$, where $i$ is the iteration counter. The same rate was achieved by [16], but without guaranteed accumulation at B-stationary points of (1.1). Furthermore, a general rank-increasing algorithm based on ERFDR is proposed, which can be of interest if the parameter $r$ in (1.1) is potentially overestimated.

Here is a brief explanation of how RFDR was modified into CRFDR. Both share the same architecture: combining backtracking line searches and a rank reduction mechanism. They differ in the choice of the search direction, using respectively the RFD map [13, Algorithm 1] and the CRFD map (Definition 6.3) for their backtracking line searches. Given an input $X \in \mathbb{R}_{\le r}^{m \times n}$, the RFD map chooses its search direction to be an arbitrary projection of $-\nabla f(X)$ onto the restricted tangent cone to $\mathbb{R}_{\le r}^{m \times n}$ at $X$, which can be computed by (2.15) with $Z := -\nabla f(X)$. The above-mentioned computationally-prohibitive truncated SVDs are required if the rank $\underline{r}$ of $X$ is smaller than $r$; they are due to the second term of (2.15), which involves a projection onto $\mathbb{R}_{\le r-\underline{r}}^{m \times n}$. In order to alleviate the computational burden due to this last projection, the proposed CRFD map replaces the restricted tangent cone to $\mathbb{R}_{\le r}^{m \times n}$ at $X$ with a drastically simpler cone $C$ of sparse matrices of rank at most $r-\underline{r}$, such as those mentioned in Table 6.1. It is readily seen that, for every $G \in P_C(-\nabla f(X))$, the plain sum $X+G$ is of rank at most $r$; the retraction-free nature of the RFD map is thus preserved. Moreover, this $G$ is a sufficient-descent direction in the sense of (3.1) (Proposition 6.2). With these two properties, the above-mentioned architecture yields a sufficient-descent map (Lemma 4.1) by an argument that was already used in the analysis of RFDR [13, §6]. The convergence to the set of B-stationary points of (1.1) follows right away (Theorem 4.2).

This paper is organized as follows. Preliminaries are covered in Section 2. The ERFD map, the ERFDR algorithm, and a rank-increasing algorithm based on ERFDR are defined and analyzed in Sections 3, 4, and 5, respectively. The CRFD map and the CRFDR algorithm are defined in Section 6. Their computational cost is analyzed in Section 7. Conclusions are drawn in Section 8.

**2. Preliminaries.** This section surveys the background material that is used throughout the paper; [15] and the references therein can be consulted for a more complete review of this material. Section 2.1 recalls basic facts about singular values, and Section 2.2 focuses on the background material from variational geometry.

The real vector space $\mathbb{R}^{m \times n}$ is endowed with the Frobenius inner product, defined by $\langle X, Y \rangle := \text{tr} Y^\top X$, and $\| \cdot \|$ denotes the Frobenius norm. For every $X \in \mathbb{R}^{m \times n}$
and $\rho \in (0, \infty)$, $B(X, \rho) := \{Y \in \mathbb{R}^{m \times n} \mid \|X - Y\| < \rho\}$ and $B[X, \rho] := \{Y \in \mathbb{R}^{m \times n} \mid \|X - Y\| \le \rho\}$ are respectively the open ball and the closed ball of center $X$ and radius $\rho$ in $\mathbb{R}^{m \times n}$. The zero matrix in $\mathbb{R}^{m \times n}$ is denoted by $0_{m \times n}$, and the identity matrix in $\mathbb{R}^{n \times n}$ is denoted by $I_n$. All operations on $\mathbb{R}$ or $\mathbb{R}^{m \times n}$ applied to subsets of $\mathbb{R}$ or $\mathbb{R}^{m \times n}$ are understood elementwise, and a singleton is identified with the element it contains.

Let $S$ be a nonempty subset of $\mathbb{R}^{m \times n}$. The boundary of $S$ is denoted by $\partial S$. The distance from $X \in \mathbb{R}^{m \times n}$ to $S$ is $d(X, S) := \inf_{Y \in S} \|X - Y\|$, and the projection of $X$ onto $S$ is $P_S(X) := \operatorname{argmin}_{Y \in S} \|X - Y\|$; the set $P_S(X)$ is nonempty and compact if $S$ is closed [20, Example 1.20]. The set $S$ is called a cone if, for all $X \in S$ and $\alpha \in [0, \infty)$, $\alpha X \in S$. The polar of a cone $C \subseteq \mathbb{R}^{m \times n}$ is

$$C^* := \{Y \in \mathbb{R}^{m \times n} \mid \langle X, Y \rangle \le 0 \forall X \in C\},$$

which is a closed convex cone [20, 6(14)].

**PROPOSITION 2.1** ([9, Proposition A.6]). Let $C \subseteq \mathbb{R}^{m \times n}$ be a closed cone. For all $X \in \mathbb{R}^{m \times n}$ and $Y \in P_C(X)$,

$$\langle X, Y \rangle = \|Y\|^2,$$

thus

$$\|Y\|^2 = \|X\|^2 - d(X, C)^2,$$

and $P_C(X) = \{0_{m \times n}\}$ if and only if $X \in C^*$.

**2.1. Basic facts about singular values.** For every $\underline{z} \in \{0, \dots, n\}$,

$$\mathrm{St}(\underline{z}, n) := \{U \in \mathbb{R}^{n \times \underline{z}} \mid U^\top U = I_{\underline{z}}\}$$

is a Stiefel manifold [1, §3.3.2]. Let $X \in \mathbb{R}^{m \times n}$. The singular values of $X$ are denoted by $\sigma_1(X) \ge \cdots \ge \sigma_{\min\{m,n\}}(X) \ge 0$. A full SVD of $X$ is a factorization $U\Sigma V^\top$ of $X$, where $U \in \mathrm{St}(m, m)$, $\Sigma = \mathrm{diag}(\sigma_1(X), \dots, \sigma_{\min\{m,n\}}(X), 0_{m-\underline{z}\times n-\underline{z}})$, $V \in \mathrm{St}(n, n)$, and $\underline{z} = \mathrm{rank} X$. (The diag operator returns a block diagonal matrix [5, §1.3.1] whose diagonal blocks are the arguments given to the operator.) Given a full SVD $U\Sigma V^\top$ of $X$, $s \in \{0, \dots, \min\{m, n\} - 1\}$, and $\underline{s} := \min\{\underline{z}, s\}$, the factorizations $U(\cdot, 1:\underline{z})\Sigma(1:\underline{z}, 1:\underline{z})V(\cdot, 1:\underline{z})^\top$ and $U(\cdot, 1:\underline{s})\Sigma(1:\underline{s}, 1:\underline{s})V(\cdot, 1:\underline{s})^\top$ are respectively called an SVD of $X$ and a truncated SVD of rank at most $s$ of $X$. By the Eckart-Young theorem [3], $P_{\mathbb{R}^{m \times n}}(X)$ is the set of all truncated SVDs of rank at most $s$ of $X$.

Proposition 2.2 states that the singular values are Lipschitz continuous with unit Lipschitz constant, a property that is used in the proof of Lemma 4.1.

**PROPOSITION 2.2** ([5, Corollary 8.6.2]). For every $X, Y \in \mathbb{R}^{m \times n}$ and $j \in \{1, \dots, \min\{m, n\}\}$,

$$|\sigma_j(X) - \sigma_j(Y)| \le \sigma_1(X - Y) \le \|X - Y\|.$$

**2.2. Elements of variational geometry.** Let $S$ be a nonempty subset of $\mathbb{R}^{m \times n}$. A matrix $Z \in \mathbb{R}^{m \times n}$ is said to be tangent to $S$ at $X \in S$ if there exist sequences $(X_i)_{i \in \mathbb{N}}$ in $S$ converging to $X$ and $(t_i)_{i \in \mathbb{N}}$ in $(0, \infty)$ such that the sequence $(\frac{X_i - X}{t_i})_{i \in \mathbb{N}}$ converges to $Z$ [20, Definition 6.1]. The set of all tangents to $S$ at $X \in S$ is a closed cone [20, Proposition 6.2] called the (Bouligand) tangent cone to $S$ at $X$ and denoted by $T_S(X)$.
DEFINITION 2.3. A point $X \in \mathbb{R}_{\le r}^{m \times n}$ is said to be Bouligand stationary (B-stationary) for (1.1) if $\langle \nabla f(X), Z \rangle \ge 0$ for all $Z \in T_{\mathbb{R}_{\le r}^{m \times n}}(X)$.

By Proposition 2.1, the function

$$ (2.1) \qquad s(\cdot; f, \mathbb{R}_{\le r}^{m \times n}) : \mathbb{R}_{\le r}^{m \times n} \to \mathbb{R} : X \mapsto \| P_{T_{\mathbb{R}_{\le r}^{m \times n}}(X)}(-\nabla f(X)) \| $$

is well defined. It is called a measure of B-stationarity for (1.1) because a point in $\mathbb{R}_{\le r}^{m \times n}$ is B-stationary for (1.1) if and only if it is a zero of this function; see [21, §2.1] or [9, Proposition 2.5]. This function is continuous on the smooth part

$$ \mathbb{R}_r^{m \times n} := \{ X \in \mathbb{R}^{m \times n} \mid \mathrm{rank} X = r \} $$

of $\mathbb{R}_{\le r}^{m \times n}$ but can fail to be lower semicontinuous at every point of the singular part

$$ \mathbb{R}_{<r}^{m \times n} := \{ X \in \mathbb{R}^{m \times n} \mid \mathrm{rank} X < r \} $$

of $\mathbb{R}_{\le r}^{m \times n}$ [15, §1.1] because $\mathbb{R}_{\le r}^{m \times n}$ is not Clarke regular on $\mathbb{R}_{<r}^{m \times n}$ [21, Remark 4].

Given an embedded submanifold $\mathcal{M}$ of $\mathbb{R}^{m \times n}$ [1, §3.3.1], the tangent and normal spaces to $\mathcal{M}$ at $X \in \mathcal{M}$, which are the orthogonal complements of each other, are respectively denoted by $T_{\mathcal{M}}(X)$ and $N_{\mathcal{M}}(X)$; this is consistent since, by [20, Example 6.8], the tangent cone to $\mathcal{M}$ at one of its points coincides with the tangent space to $\mathcal{M}$ at that point.

DEFINITION 2.4. Given $\mu \in (0, 1]$, a restricted tangent cone to $S$ is a map that associates with every $X \in S$ a closed cone $\tilde{T}_S(X)$ such that $\tilde{T}_S(X) \subseteq T_S(X)$, $X + \tilde{T}_S(X) \subseteq S$, and, for all $Z \in \mathbb{R}^{m \times n}$, $\|P_{\tilde{T}_S(X)}(Z)\| \ge \mu \|P_{T_S(X)}(Z)\|$.

The rest of this section reviews descriptions of the tangent cone and restricted tangent cone to $\mathbb{R}_{\le r}^{m \times n}$ at $X \in \mathbb{R}_{\le r}^{m \times n}$, and the projections onto them, based on the Moore-Penrose inverse $X^\dagger$; equivalent descriptions based on block matrices can be found, e.g., in [13, §3]. The practical implications of these descriptions for the RFD map [13, Algorithm 1] are also highlighted. Let $\underline{r} := \mathrm{rank} X$.

By [8, Proposition 4.1], the tangent space to $\mathbb{R}_{\underline{r}}^{m \times n}$ at $X$ is

$$ (2.2) \qquad T_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) = \mathbb{R}^{m \times m} X + X \mathbb{R}^{n \times n} $$

and thus the normal space to $\mathbb{R}_{\underline{r}}^{m \times n}$ at $X$ is

$$ (2.3) \qquad N_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) = (I_m - XX^\dagger)\mathbb{R}^{m \times n}(I_n - X^\dagger X). $$

By [21, Theorem 3.2], the tangent cone to $\mathbb{R}_{\le r}^{m \times n}$ at $X$ is

$$ (2.4) \qquad T_{\mathbb{R}_{\le r}^{m \times n}}(X) = T_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) + (N_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) \cap \mathbb{R}_{\le r-\underline{r}}^{m \times n}). $$

By [13, Definition 3.1], the restricted tangent cone to $\mathbb{R}_{\underline{r}}^{m \times n}$ at $X$ is

$$ (2.5) \qquad \tilde{T}_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) = \mathbb{R}^{m \times m} X \cup X \mathbb{R}^{n \times n} $$

and the restricted tangent cone to $\mathbb{R}_{\le r}^{m \times n}$ at $X$ is

$$ (2.6) \qquad \tilde{T}_{\mathbb{R}_{\le r}^{m \times n}}(X) = \tilde{T}_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) + (N_{\mathbb{R}_{\underline{r}}^{m \times n}}(X) \cap \mathbb{R}_{\le r-\underline{r}}^{m \times n}). $$
Crucially, by subadditivity of the rank, (2.2) implies

$$ (2.7) \qquad X + T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X) \subseteq \mathbb{R}_{\le 2\underline{\tau}}^{m \times n}, $$

and (2.5) implies

$$ (2.8) \qquad X + \tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X) \subseteq \mathbb{R}_{\le \underline{\tau}}^{m \times n}. $$

By subadditivity of the rank, (2.4) and (2.7) yield

$$ (2.9) \qquad X + T_{\mathbb{R}_{\le r}^{m \times n}}(X) \subseteq \mathbb{R}_{\le r+\underline{\tau}}^{m \times n}, $$

and (2.6) and (2.8) yield

$$ (2.10) \qquad X + \tilde{T}_{\mathbb{R}_{\le r}^{m \times n}}(X) \subseteq \mathbb{R}_{\le r}^{m \times n}. $$

By [21, Theorem 3.1 and Corollary 3.3] and [13, Proposition 3.2], for all $Z \in \mathbb{R}^{m \times n}$,

$$ (2.11) \qquad P_{T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) = XX^{\dagger}Z + ZX^{\dagger}X - XX^{\dagger}ZX^{\dagger}X, $$

$$ (2.12) \qquad P_{N_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) = Z - P_{T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) = (I_m - XX^{\dagger})Z(I_n - X^{\dagger}X), $$

$$ (2.13) \qquad P_{\tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) = \begin{cases} XX^{\dagger}Z & \text{if } \|XX^{\dagger}Z\| > \|ZX^{\dagger}X\|, \\ \{XX^{\dagger}Z, ZX^{\dagger}X\} & \text{if } \|XX^{\dagger}Z\| = \|ZX^{\dagger}X\|, \\ ZX^{\dagger}X & \text{if } \|XX^{\dagger}Z\| < \|ZX^{\dagger}X\|, \end{cases} $$

$$ (2.14) \qquad P_{T_{\mathbb{R}_{\le r}^{m \times n}}(X)}(Z) = P_{T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) + P_{\mathbb{R}_{\le r-\underline{\tau}}^{m \times n}}(P_{N_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z)), $$

$$ (2.15) \qquad P_{\tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) = P_{\tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z) + P_{\mathbb{R}_{\le r-\underline{\tau}}^{m \times n}}(P_{N_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z)), $$

$$ (2.16) \qquad \|P_{T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z)\| \ge \|P_{\tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z)\| \ge \frac{1}{\sqrt{2}} \|P_{T_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(Z)\|, $$

$$ (2.17) \qquad \|Z\| \ge \|P_{T_{\mathbb{R}_{\le r}^{m \times n}}(X)}(Z)\| \ge \sqrt{\frac{r-\underline{\tau}}{\min\{m, n\} - \underline{\tau}}} \|Z\|. $$

As indicated in Section 1, the RFD map performs a backtracking line search along an arbitrary element of $P_{\tilde{T}_{\mathbb{R}_{\underline{\tau}}^{m \times n}}(X)}(-\nabla f(X))$. If $\underline{\tau} = r$, (2.15) reduces to (2.13) because its second term is $0_{m \times n}$. Computing (2.13) merely requires orthonormal bases of the row and column spaces of X and matrix multiplications. If $\underline{\tau} < r$, then computing the second term of (2.15) requires a truncated SVD of rank at most $r - \underline{\tau}$ of a matrix whose rank can be as large as $\min\{m, n\} - \underline{\tau}$ by (2.12). This is computationally prohibitive in the typical case where $r \ll \min\{m, n\}$, and thus raises the question of the possibility of finding a computationally cheaper surrogate for (2.15) that preserves the properties of the RFD map. The question is answered positively in Section 6 based on the analysis conducted in Section 3.

**3. The ERFD map.** In this section, the ERFD map is defined (Algorithm 3.1) and analyzed (Corollary 3.2). This serves as a basis for the definition and analysis of the ERFDR algorithm in Section 4 since the latter uses the ERFD map as a subroutine.
Given parameters $\bar{\alpha} \in (0, \infty)$, $\kappa_1 \in (0, \frac{1}{2}]$, and $\kappa_2 \in (0, 1]$ and an input $X \in \mathbb{R}_{\le r}^{m \times n}$, the ERFD map chooses $G \in \mathbb{R}^{m \times n}$ such that

$$ (3.1) \qquad \langle G, -\nabla f(X) \rangle \ge \max\{\kappa_1 s(X; f, \mathbb{R}_{\le r}^{m \times n})^2, \kappa_2 \|G\|^2\} $$

and $X + \alpha G \in \mathbb{R}_{\le r}^{m \times n}$ for all $\alpha \in [0, \bar{\alpha}]$, then performs a backtracking line search along $G$: it computes $f(X + \alpha G)$ for decreasing values of the step size $\alpha \in (0, \bar{\alpha}]$ and outputs $X + \alpha G$ as soon as an Armijo condition is satisfied. Thus, the ERFD map is retraction-free: it updates its input by moving along a straight line.

The inequality (3.1) means that the decrease in $f$ along $G$ at $X$ is at least a fraction of that along an arbitrary element of $P_T_{\mathbb{R}_{\le r}^{m \times n}}(X)(-\nabla f(X))$, and that this cannot be achieved by choosing $G$ too large. It is related to [6, (2)-(3)] by the Cauchy-Schwarz inequality. Specifically, [6, (2)-(3)] implies (3.1) with $\kappa_1 = c_1$ and $\kappa_2 = \frac{c_1}{c_2^2}$, and (3.1) with $s(X; f, \mathbb{R}_{\le r}^{m \times n})$ replaced with $\|\nabla f(X)\|$ implies [6, (2)-(3)] with $c_1 = \kappa_1$ and $c_2 = \frac{1}{\kappa_2}$. The inequality (3.1) also implies the angle condition [21, (2.15)] with $\omega = \sqrt{\kappa_1 \kappa_2}$.

If $s(X; f, \mathbb{R}_{\le r}^{m \times n}) = 0$, then the set of all $G \in \mathbb{R}^{m \times n}$ satisfying (3.1) and $X + \alpha G \in \mathbb{R}_{\le r}^{m \times n}$ for all $\alpha \in [0, \bar{\alpha}]$ is $\{0_{m \times n}\}$. In practice, $s(X; f, \mathbb{R}_{\le r}^{m \times n})$ should not be computed if $\text{rank } X < r$; in that case, by the second inequality of (2.17), $s(X; f, \mathbb{R}_{\le r}^{m \times n}) = 0$ if and only if $\|\nabla f(X)\| = 0$.

By (2.10), if $G \in \tilde{T}_{\mathbb{R}_{\le r}^{m \times n}}(X)$, then $X + \alpha G \in \mathbb{R}_{\le r}^{m \times n}$ for all $\alpha \in (0, \infty)$. Moreover, the ERFD map extends the RFD map [13, Algorithm 1] because every $G \in P_{\tilde{T}_{\mathbb{R}_{\le r}^{m \times n}}(X)}(-\nabla f(X))$ satisfies (3.1) with $\kappa_1 = \frac{1}{2}$ and $\kappa_2 = 1$. Hence, the subset of $\mathbb{R}^{m \times n}$ in which the ERFD map chooses an element is not empty.

**Algorithm 3.1 ERFD map on $\mathbb{R}_{\le r}^{m \times n}$**

**Require:** $(f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$ where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $0 < \underline{\alpha} \le \bar{\alpha} < \infty$, $\beta, c \in (0, 1)$, $\kappa_1 \in (0, \frac{1}{2}]$, and $\kappa_2 \in (0, 1]$.

**Input:** $X \in \mathbb{R}_{\le r}^{m \times n}$.

**Output:** a point in ERFD($X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2$).

1. Choose $G \in \mathbb{R}^{m \times n}$ satisfying (3.1) and $X + \alpha G \in \mathbb{R}_{\le r}^{m \times n}$ for all $\alpha \in [0, \bar{\alpha}]$;

2. Choose $\alpha \in [\underline{\alpha}, \bar{\alpha}]$;

3. **while** $f(X + \alpha G) > f(X) + c\alpha \langle \nabla f(X), G \rangle$ **do**

4. &nbsp;&nbsp;&nbsp;&nbsp; $\alpha \leftarrow \alpha\beta$;

5. **end while**

6. Return $X + \alpha G$.

By [12, Lemma 1.2.3], since $\nabla f$ is locally Lipschitz continuous, i.e., for every closed ball $B \subset \mathbb{R}^{m \times n}$,

$$ \text{Lip}(\nabla f) := \sup_{\substack{X, Y \in B \\ X \neq Y}} \frac{\|\nabla f(X) - \nabla f(Y)\|}{\|X - Y\|} < \infty, $$

it holds for all $X, Y \in B$ that

$$ (3.2) \qquad |f(Y) - f(X) - \langle \nabla f(X), Y - X \rangle| \le \frac{\text{Lip}_B(\nabla f)}{2} \|Y - X\|^2. $$
Proposition 3.1 and Corollary 3.2 respectively extend [13, Proposition 4.1 and Corollary 4.2].

**PROPOSITION 3.1.** Let $\bar{\alpha} \in (0, \infty)$, $\kappa_1 \in (0, \frac{1}{2}]$, $\kappa_2 \in (0, 1]$, and $X \in \mathbb{R}_{\le r}^{m \times n}$.
Let $\mathcal{B} \subset \mathbb{R}^{m \times n}$ be a closed ball containing $B[X, \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X)\|]$ if $\|\nabla f(X)\| \ne 0$. Let
$G \in \mathbb{R}^{m \times n}$ satisfy (3.1) and $X+\alpha G \in \mathbb{R}_{\le r}^{m \times n}$ for all $\alpha \in [0, \bar{\alpha}]$. Then, for all $\alpha \in [0, \bar{\alpha}]$,

$$ (3.3) \qquad f(X + \alpha G) \le f(X) + \alpha \left( 1 - \frac{\alpha}{2\kappa_2} \mathrm{Lip}(\nabla f) \right) \langle \nabla f(X), G \rangle. $$

*Proof.* Since $\|G\|^2 \le \frac{1}{\kappa_2} \langle G, -\nabla f(X) \rangle \le \frac{1}{\kappa_2} \|G\| \|\nabla f(X)\|$, it holds that $\|G\| \le \frac{1}{\kappa_2} \|\nabla f(X)\|$. Thus, $X + \alpha G \in B[X, \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X)\|]$ for all $\alpha \in [0, \bar{\alpha}]$. The inequality (3.3) is based on (3.2):

$$ \begin{aligned} f(X + \alpha G) - f(X) &\le \langle \nabla f(X), (X + \alpha G) - X \rangle + \frac{\mathrm{Lip}_{\mathcal{B}}(\nabla f)}{2} \|(X + \alpha G) - X\|^2 \\ &= \alpha \langle \nabla f(X), G \rangle + \frac{\alpha^2}{2} \mathrm{Lip}(\nabla f) \|G\|^2 \\ &\le \alpha \left( 1 - \frac{\alpha}{2\kappa_2} \mathrm{Lip}(\nabla f) \right) \langle \nabla f(X), G \rangle. \quad \blacksquare \end{aligned} $$

Corollary 3.2 provides a lower bound on the step size of the ERFD map. It plays an instrumental role in the proof of Lemma 4.1.

**COROLLARY 3.2.** Let $\mathcal{B}$ be a closed ball as in Proposition 3.1. The while loop in Algorithm 3.1 terminates after at most

$$ (3.4) \qquad \max \left\{ 0, \left\lfloor \frac{\ln \left( \frac{2\kappa_2(1-c)}{\alpha_0 \mathrm{Lip}_{\mathcal{B}}(\nabla f)} \right)}{\ln(\beta)} \right\rfloor \right\} $$

iterations, where $\alpha_0$ is the initial step size chosen in line 2. Moreover, every $\tilde{X} \in$ ERFD($X$; $f$, $r$, $\underline{\alpha}$, $\bar{\alpha}$, $\beta$, $c$, $\kappa_1$, $\kappa_2$) satisfies the Armijo condition

$$ (3.5) \qquad f(\tilde{X}) \le f(X) + c\alpha \langle \nabla f(X), G \rangle $$

with a step size $\alpha \in [\min\{\underline{\alpha}, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{\mathcal{B}}(\nabla f)}\}, \bar{\alpha}]$, which implies

$$ (3.6) \qquad f(\tilde{X}) \le f(X) - c\kappa_1 \alpha s(X; f, \mathbb{R}_{\le r}^{m \times n})^2. $$

*Proof.* If $\langle \nabla f(X), G \rangle = 0$, then $G = 0_{m \times n}$, hence the while loop is not executed and $\tilde{X} = X$. Assume that $\langle \nabla f(X), G \rangle \ne 0$. Define $\alpha_* := \frac{2\kappa_2(1-c)}{\mathrm{Lip}_{\mathcal{B}}(\nabla f)}$. For all $\alpha \in (0, \infty)$,

$$ f(X) + \alpha \left( 1 - \frac{\alpha}{2\kappa_2} \mathrm{Lip}(\nabla f) \right) \langle \nabla f(X), G \rangle \le f(X) + c\alpha \langle \nabla f(X), G \rangle \quad \text{iff} \quad \alpha \le \alpha_* $$

Since the left-hand side of the first inequality is an upper bound on $f(X + \alpha G)$ for all $\alpha \in (0, \bar{\alpha}]$, the Armijo condition (3.5) is necessarily satisfied if $\alpha \in (0, \min\{\bar{\alpha}, \alpha_*\}]$. Therefore, at the latest, the while loop ends after iteration $i \in \mathbb{N} \setminus \{0\}$ with $\alpha = \alpha_0\beta^i$ such that $\frac{\alpha}{\beta} > \alpha_*$, hence $i < 1 + \ln(\alpha_*/\alpha_0)/\ln(\beta)$, and thus $i \le \lceil \ln(\alpha_*/\alpha_0)/\ln(\beta) \rceil$. $\blacksquare$
**4. The ERFDR algorithm and its convergence analysis.** The ERFDR map, defined as Algorithm 4.1, is the iteration map of the ERFDR algorithm. Given an input $X \in \mathbb{R}_{\le r}^{m \times n}$, the ERFDR map proceeds as follows: (i) it applies the ERFD map (Algorithm 3.1) to $X$, thereby producing a point $\tilde{X}$, (ii) if $\sigma_r(X)$ is positive but smaller than some threshold $\Delta \in (0, \infty)$, it applies the ERFD map to a projection $\tilde{X}$ of $X$ onto $\mathbb{R}_{r-1}^{m \times n}$, then producing a point $\tilde{X}^R$, and (iii) it outputs a point among $\tilde{X}$ and $\tilde{X}^R$ that maximally decreases $f$.

**Algorithm 4.1 ERFDR map on $\mathbb{R}_{\le r}^{m \times n}$**

**Require:** $(f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$ where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $0 < \underline{\alpha} \le \bar{\alpha} < \infty$, $\beta, c \in (0, 1)$, $\kappa_1 \in (0, \frac{1}{2}]$, $\kappa_2 \in (0, 1]$, and $\Delta \in (0, \infty)$.

**Input:** $X \in \mathbb{R}_{\le r}^{m \times n}$.

**Output:** a point in ERFDR($X$; $f$, $r$, $\underline{\alpha}$, $\bar{\alpha}$, $\beta$, $c$, $\kappa_1$, $\kappa_2$, $\Delta$).

1. Choose $\tilde{X} \in \text{ERFD}(X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$;

2. **if** $\sigma_r(X) \in (0, \Delta]$ **then**

3. Choose $\tilde{X} \in P_{\mathbb{R}_{r-1}^{m \times n}}(X)$;

4. Choose $\tilde{X}^R \in \text{ERFD}(\tilde{X}; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$;

5. Return $Y \in \text{argmin}_{\{\tilde{X}, \tilde{X}^R\}} f$.

6. **else**

7. Return $\tilde{X}$.

8. **end if**

The ERFDR algorithm is defined as Algorithm 4.2. It generates a sequence in $\mathbb{R}_{\le r}^{m \times n}$ along which $f$ is strictly decreasing.

**Algorithm 4.2 ERFDR on $\mathbb{R}_{\le r}^{m \times n}$**

**Require:** $(f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$ where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $0 < \underline{\alpha} \le \bar{\alpha} < \infty$, $\beta, c \in (0, 1)$, $\kappa_1 \in (0, \frac{1}{2}]$, $\kappa_2 \in (0, 1]$, and $\Delta \in (0, \infty)$.

**Input:** $X_0 \in \mathbb{R}_{\le r}^{m \times n}$.

**Output:** a sequence in $\mathbb{R}_{\le r}^{m \times n}$.

1. $i \leftarrow 0$;

2. **while** $s(X_i; f, \mathbb{R}_{\le r}^{m \times n}) > 0$ **do**

3. Choose $\Delta_i \in [\Delta, \infty)$;

4. Choose $X_{i+1} \in \text{ERFDR}(X_i; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta_i)$;

5. $i \leftarrow i + 1$;

6. **end while**

Algorithms 4.1 and 4.2 are analyzed in Section 4.1 by deploying the strategy laid out in [15, §3]. The crucial step is to prove that the ERFDR map is an $(f, \mathbb{R}_{\le r}^{m \times n})$-sufficient-descent map (Lemma 4.1). The choice of the parameter $\Delta$ is briefly discussed in Section 4.2.

**4.1. Convergence analysis.** Lemma 4.1 states that, for every $\underline{X} \in \mathbb{R}_{\le r}^{m \times n}$ that is not B-stationary for (1.1), the decrease in $f$ obtained by applying the ERFDR map to every $X \in \mathbb{R}_{\le r}^{m \times n}$ sufficiently close to $\underline{X}$ is bounded away from zero.
LEMMA 4.1. The ERFDR map (Algorithm 4.1) is an $(f, \mathbb{R}_{\le r}^{m \times n})$-sufficient-descent map in the sense of [15, Definition 3.1]: for every $\underline{X} \in \mathbb{R}_{\le r}^{m \times n}$ that is not B-stationary for (1.1), there exist $\varepsilon(\underline{X})$, $\delta(\underline{X}) \in (0, \infty)$ such that, for all $X \in B[\underline{X}, \varepsilon(\underline{X})] \cap \mathbb{R}_{\le r}^{m \times n}$ and $Y \in \text{ERFDR}(X; f, r, \underline{\alpha}, \underline{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$,

$$ (4.1) \qquad f(Y) - f(X) \le -\delta(\underline{X}). $$

Proof. Let $\underline{X} \in \mathbb{R}_{\le r}^{m \times n}$ be such that $s(\underline{X}; f, \mathbb{R}_{\le r}^{m \times n}) > 0$. Define $\underline{\tau} := \text{rank } \underline{X}$. This proof uses the same arguments as that of [13, Proposition 6.1]. It constructs $\varepsilon(\underline{X})$ and $\delta(\underline{X})$ based on (3.6). This requires a lower bound on $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ holding in a suitable neighborhood of $\underline{X}$. It first considers the case where $\underline{\tau} = r$, in which the lower bound on $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ follows from its continuity on $B(\underline{X}, \sigma_r(\underline{X})) \cap \mathbb{R}_{\le r}^{m \times n}$. Then, it focuses on the case where $\underline{\tau} < r$, in which the lower bound on $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ follows from the bounds (4.2) on $\nabla f$ by the second inequality of (2.17). If $\text{rank } \underline{X} < r$, then the second inequality of (2.17) readily gives a lower bound on $s(\underline{X}; f, \mathbb{R}_{\le r}^{m \times n})$. This is not the case if $\text{rank } \underline{X} = r$, however. This is where the rank reduction mechanism comes into play. It considers a projection $\hat{X}$ of $\underline{X}$ onto $\mathbb{R}_{r-1}^{m \times n}$, and the second inequality of (2.17) gives a lower bound on $s(\hat{X}; f, \mathbb{R}_{\le r}^{m \times n})$. The inequality (4.1) is then obtained from (4.5), which follows from the continuity of $f$ at $\underline{X}$.

By the first inequality of (2.17), $\|\nabla f(\underline{X})\| \ge s(\underline{X}; f, \mathbb{R}_{\le r}^{m \times n})$. Since $\nabla f$ is continuous at $\underline{X}$, there exists $\rho_1(\underline{X}) \in (0, \infty)$ such that, for all $X \in B[\underline{X}, \rho_1(\underline{X})]$, $\|\nabla f(X) - \nabla f(\underline{X})\| \le \frac{1}{2}\|\nabla f(\underline{X})\|$ and hence, as $\|\nabla f(X)\| - \|\nabla f(\underline{X})\| \le \|\nabla f(X) - \nabla f(\underline{X})\|$,

$$ (4.2) \qquad \frac{1}{2}\|\nabla f(\underline{X})\| \le \|\nabla f(X)\| \le \frac{3}{2}\|\nabla f(\underline{X})\|. $$

Define

$$ \bar{\rho}(\underline{X}) := \rho_1(\underline{X}) + \frac{3\bar{\alpha}}{2\kappa_2} \|\nabla f(\underline{X})\|, \quad \alpha_*(\underline{X}) := \min \left\{ \underline{\alpha}, \frac{2\beta\kappa_2(1-c)}{\text{Lip}_{B[\underline{X}, \bar{\rho}(\underline{X})]}(\nabla f)} \right\}. $$

Then, for every $X \in B[\underline{X}, \rho_1(\underline{X})]$, the inclusion $B[X, \frac{\underline{\alpha}}{\kappa_2} \|\nabla f(X)\|] \subseteq B[\underline{X}, \bar{\rho}(\underline{X})]$ holds since, for all $Z \in B[X, \frac{\underline{\alpha}}{\kappa_2} \|\nabla f(X)\|]$,

$$ \|Z - \underline{X}\| \le \|Z - X\| + \|X - \underline{X}\| \le \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X)\| + \rho_1(\underline{X}) \le \bar{\rho}(\underline{X}), $$

where the last inequality follows from the second inequality of (4.2). Thus, the closed ball $B[\underline{X}, \bar{\rho}(\underline{X})]$ satisfies the condition from Proposition 3.1. Hence, for all $X \in B[\underline{X}, \rho_1(\underline{X})] \cap \mathbb{R}_{\le r}^{m \times n}$ and $\hat{X} \in \text{ERFD}(X; f, r, \underline{\alpha}, \underline{\alpha}, \beta, c, \kappa_1, \kappa_2)$, Corollary 3.2 applies with this closed ball, and (3.6) yields

$$ (4.3) \qquad f(\tilde{X}) \le f(X) - c\kappa_1\alpha_*(\underline{X})s(X; f, \mathbb{R}_{\le r}^{m \times n})^2. $$

Define

$$ (4.4) \qquad \delta(\underline{X}) := \begin{cases} \frac{c}{4}\kappa_1\alpha_*(\underline{X})s(\underline{X}; f, \mathbb{R}_{\le r}^{m \times n})^2 & \text{if } \underline{\tau} = r, \\ \frac{c\kappa_1\alpha_*(\underline{X})\|\nabla f(\underline{X})\|^2}{12(\min\{m, n\} - r + 1)} & \text{if } \underline{\tau} < r. \end{cases} $$

Let us consider the case where $\underline{\tau} = r$. On $B(\underline{X}, \sigma_r(\underline{X})) \cap \mathbb{R}_{\le r}^{m \times n} = B(\underline{X}, \sigma_r(\underline{X})) \cap \mathbb{R}_{r}^{m \times n}$, $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ coincides with the norm of the Riemannian gradient of the restriction of $f$ to the smooth manifold $\mathbb{R}_{r}^{m \times n}$, which is continuous [21, §2.1]. Therefore, there exists $\rho_2(\underline{X}) \in (0, \sigma_r(\underline{X}))$ such that $s(B[\underline{X}, \rho_2(\underline{X})] \cap \mathbb{R}_{r}^{m \times n}; f, \mathbb{R}_{\le r}^{m \times n}) \subseteq$
$[\frac{1}{2} s(\underline{X}; f, \mathbb{R}_{\leq r}^{m \times n}), \frac{3}{2} s(\underline{X}; f, \mathbb{R}_{\leq r}^{m \times n})]$. Define

$$\varepsilon(\underline{X}) := \min\{\rho_1(\underline{X}), \rho_2(\underline{X})\}.$$

Let $X \in B[\underline{X}, \varepsilon(\underline{X})] \cap \mathbb{R}_{\leq r}^{m \times n}$ and $Y \in \text{ERFDR}(X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$. There exists $\tilde{X} \in \text{ERFD}(X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$ such that $f(Y) \leq f(\tilde{X})$. Therefore, (4.1) follows from (4.3) and (4.4), which completes the proof for the case where $\underline{\tau} = r$.

Let us now consider the case where $\underline{\tau} < r$. Since $f$ is continuous at $\underline{X}$, there exists $\rho_0(\underline{X}) \in (0, \infty)$ such that $f(B[\underline{X}, \rho_0(\underline{X})]) \subseteq [f(\underline{X}) - \delta(\underline{X}), f(\underline{X}) + \delta(\underline{X})]$. Define

$$\varepsilon(\underline{X}) := \min\{\Delta, \frac{1}{2}\rho_0(\underline{X}), \frac{1}{2}\rho_1(\underline{X})\}.$$

Let $X \in B[\underline{X}, \varepsilon(\underline{X})] \cap \mathbb{R}_{\leq r}^{m \times n}$ and $Y \in \text{ERFDR}(X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$. Let us first consider the case where rank $X = r$. Then, by Proposition 2.2,

$$0 < \sigma_r(X) = \sigma_r(X) - \sigma_r(\underline{X}) \leq \|X - \underline{X}\| \leq \varepsilon(\underline{X}) \leq \Delta.$$

Thus, there exist $\hat{X} \in P_{\mathbb{R}_{r-1}^{m \times n}}(X)$ and $\tilde{X}^R \in \text{ERFD}(\hat{X}; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$ such that $f(Y) \leq f(\tilde{X}^R)$. Moreover, $\hat{X} \in B[\underline{X}, 2\varepsilon(\underline{X})]$ since

$$\|\hat{X} - \underline{X}\| \leq \|\hat{X} - X\| + \|X - \underline{X}\| \leq \sigma_r(X) + \varepsilon(\underline{X}) \leq 2\varepsilon(\underline{X}) \leq \min\{\rho_0(\underline{X}), \rho_1(\underline{X})\}.$$

As $X, \hat{X} \in B[\underline{X}, \rho_0(\underline{X})]$, it holds that

$$(4.5) \qquad f(\hat{X}) \leq f(X) + 2\delta(\underline{X}).$$

As $X, \hat{X} \in B[\underline{X}, \rho_1(\underline{X})] \cap \mathbb{R}_{\leq r}^{m \times n}$, it holds that

$$
\begin{aligned}
f(Y) &\leq f(\tilde{X}^R) \\
&\leq f(\hat{X}) - c \kappa_1 \alpha_*(\underline{X}) s(\hat{X}; f, \mathbb{R}_{\leq r}^{m \times n})^2 \\
&\leq f(\hat{X}) - c \kappa_1 \alpha_*(\underline{X}) \frac{\|\nabla f(\hat{X})\|^2}{\min\{m, n\} - r + 1} \\
&\leq f(\hat{X}) - 3\delta(\underline{X}) \\
&\leq f(X) - \delta(\underline{X}),
\end{aligned}
$$

where the second inequality follows from (4.3), the third from the second inequality of (2.17) since rank $\hat{X} = r - 1$, the fourth from (4.2) and (4.4), and the fifth from (4.5). Let us now consider the case where rank $X < r$. There exists $\tilde{X} \in \text{ERFD}(X; f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2)$ such that $f(Y) \leq f(\tilde{X})$. Therefore,

$$
\begin{aligned}
f(Y) &\leq f(\tilde{X}) \\
&\leq f(X) - c \kappa_1 \alpha_*(\underline{X}) s(X; f, \mathbb{R}_{\leq r}^{m \times n})^2 \\
&\leq f(X) - c \kappa_1 \alpha_*(\underline{X}) \frac{r - \text{rank } X}{\min\{m, n\} - \text{rank } X} \|\nabla f(X)\|^2 \\
&\leq f(X) - c \kappa_1 \alpha_*(\underline{X}) \frac{\|\nabla f(X)\|^2}{\min\{m, n\} - r + 1} \\
&\leq f(X) - 3\delta(\underline{X}) \\
&\leq f(X) - \delta(\underline{X}),
\end{aligned}
$$
where the second inequality follows from (4.3), the third from the second inequality of (2.17), and the fifth from (4.2) and (4.4). □

**THEOREM 4.2.** Consider a sequence generated by ERFDR (Algorithm 4.2). If this sequence is finite, then its last element is B-stationary for (1.1) in the sense of Definition 2.3. If it is infinite, then all of its accumulation points, if any, are B-stationary for (1.1).

*Proof.* This follows from [15, Proposition 3.2] and Lemma 4.1. □

Theorem 4.3 offers a lower bound on the rate at which $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ converges to zero along all bounded subsequences of every sequence generated by ERFDR. Importantly, Theorem 4.2 is not a consequence of Theorem 4.3 since, as indicated in Section 2.2, the function $s(\cdot; f, \mathbb{R}_{\le r}^{m \times n})$ can fail to be lower semicontinuous at every point of $\mathbb{R}_{\le r}^{m \times n}$. The methods from [16] enjoy the same lower bound, but are not guaranteed to accumulate at B-stationary points of (1.1). Riemannian gradient descent [2, §2] also enjoys this lower bound, but this fact does not imply Theorem 4.3: $\mathbb{R}_{\le r}^{m \times n}$ is not a manifold and, while $\mathbb{R}_{r}^{m \times n}$ is a manifold, it is such that [2, Theorem 2.11] is vacuous due to $\rho = 0$.

**THEOREM 4.3.** Let $(X_i)_{i \in \mathbb{N}}$ be a sequence generated by ERFDR (Algorithm 4.2). If a subsequence $(X_{ik})_{k \in \mathbb{N}}$ is bounded, then, for all $k \in \mathbb{N}$,

$$ (4.6) \qquad \sum_{l=0}^{k} s(X_{il}; f, \mathbb{R}_{\le r}^{m \times n})^2 < \frac{f(X_0) - \inf_{l \in \mathbb{N}} f(X_{il})}{c \kappa_1 \min \left\{ \underline{\alpha}, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0, \rho]}(\nabla f)} \right\}}, $$

where

$$ (4.7) \qquad \rho := \sup_{l \in \mathbb{N}} \left( \|X_{il} - X_0\| + \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X_{il})\| \right) < \infty, $$

thus $\lim_{l \to \infty} s(X_{il}; f, \mathbb{R}_{\le r}^{m \times n}) = 0$ and

$$ (4.8) \qquad \min_{l \in \{0, \dots, k\}} s(X_{il}; f, \mathbb{R}_{\le r}^{m \times n}) < \frac{1}{\sqrt{k+1}} \sqrt{\frac{f(X_0) - \inf_{l \in \mathbb{N}} f(X_{il})}{c \kappa_1 \min \left\{ \underline{\alpha}, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0, \rho]}(\nabla f)} \right\}}}. $$

If, moreover, $(X_{ik})_{k \in \mathbb{N}}$ converges to $X \in \mathbb{R}_{\le r}^{m \times n}$, then $\inf_{l \in \mathbb{N}} f(X_{il}) = f(X)$. If $(X_i)_{i \in \mathbb{N}}$ is bounded, which is the case if the sublevel set $\{X \in \mathbb{R}_{\le r}^{m \times n} | f(X) \le f(X_0)\}$ is bounded, then all accumulation points have the same image by $f$ and, for all $\varepsilon \in (0, \infty)$,

$$ (4.9) \qquad i_{\varepsilon} := \min\{i \in \mathbb{N} \mid s(X_i; f, \mathbb{R}_{\le r}^{m \times n}) \le \varepsilon\} \le \left\lfloor \frac{f(X_0) - \inf_{j \in \mathbb{N}} f(X_j)}{\varepsilon^2 c \kappa_1 \min \left\{ \underline{\alpha}, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0, \rho]}(\nabla f)} \right\}} \right\rfloor - 1. $$

*Proof.* The statement about the image of the accumulation points is established in the proof of [15, Corollary 6.3]. The proof of the other statements follows that of [12, (1.2.22)]. Observe that $\|\nabla f(X_i)\| > 0$ for all $i \in \mathbb{N}$. Assume that a subsequence $(X_{ik})_{k \in \mathbb{N}}$ is bounded. Let $\rho$ be as in (4.7). Then, for all $l \in \mathbb{N}$, it holds that $B[X_{il}, \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X_{il})\|] \subseteq B[X_0, \rho]$; indeed, for all $X \in B[X_{il}, \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X_{il})\|]$,

$$ \|X - X_0\| \le \|X - X_{il}\| + \|X_{il} - X_0\| \le \frac{\bar{\alpha}}{\kappa_2} \|\nabla f(X_{il})\| + \|X_{il} - X_0\| \le \rho. $$
Thus, for all $l \in \mathbb{N}$,

$$ 
\begin{aligned}
f(X_{i_{l+1}}) &\le f(X_{i_l+1}) \\
&\le f(\tilde{X}_{i_l}) \\
&\le f(X_{i_l}) - c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\} s(X_{i_l}; f, \mathbb{R}_{\le r}^{m \times n})^2,
\end{aligned}
$$

where the last inequality follows from (3.6), and hence

$$ s(X_{i_l}; f, \mathbb{R}_{\le r}^{m \times n})^2 \le \frac{f(X_{i_l}) - f(X_{i_{l+1}})}{c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}}. $$

For all $k \in \mathbb{N}$, summing the preceding inequality over $l \in \{0, \dots, k\}$ yields

$$ 
\begin{aligned}
(k+1) \min_{l \in \{0, \dots, k\}} s(X_{i_l}; f, \mathbb{R}_{\le r}^{m \times n})^2 &\le \sum_{l=0}^k s(X_{i_l}; f, \mathbb{R}_{\le r}^{m \times n})^2 \\
&\le \frac{f(X_{i_0}) - f(X_{i_{k+1}})}{c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}} \\
&< \frac{f(X_0) - \inf_{l \in \mathbb{N}} f(X_{i_l})}{c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}},
\end{aligned}
$$

and (4.6) and (4.8) follow. The “moreover” statement is clear. Assume now that $(X_i)_{i \in \mathbb{N}}$ is bounded. By (4.8), for all $\varepsilon \in (0, \infty)$ and $i \in \mathbb{N}$, if

$$ \frac{1}{\sqrt{i+1}} \sqrt{\frac{f(X_0) - \inf_{j \in \mathbb{N}} f(X_j)}{c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}}} \le \varepsilon, $$

i.e.,

$$ i \ge \frac{f(X_0) - \inf_{j \in \mathbb{N}} f(X_j)}{\varepsilon^2 c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}} - 1, $$

then there is $j \in \{0, \dots, i\}$ such that $s(X_j; f, \mathbb{R}_{\le r}^{m \times n}) \le \varepsilon$, thus

$$ i_{\varepsilon} \le j \le \left[ \frac{f(X_0) - \inf_{j \in \mathbb{N}} f(X_j)}{\varepsilon^2 c \kappa_1 \min \left\{ \alpha, \frac{2\beta\kappa_2(1-c)}{\mathrm{Lip}_{B[X_0,\rho]}(\nabla f)} \right\}} \right] - 1, $$

and (4.9) is proven. $\square$

The analysis conducted in Sections 3 and 4.1 can be extended straightforwardly to the case where $f$ is only defined on an open subset of $\mathbb{R}^{m \times n}$ containing $\mathbb{R}_{\le r}^{m \times n}$.

**4.2. On the choice of $\Delta$.** Theorem 4.2 is valid for every sequence $(\Delta_i)_{i \in \mathbb{N}}$ bounded away from zero. However, $(\Delta_i)_{i \in \mathbb{N}}$ influences the sequence generated by ERFDR since it governs the sensitivity of the rank reduction mechanism. Every action of the rank reduction mechanism increases both the exploration of the feasible set and the computational cost. The parameter $\Delta_i$ enables to tune the tradeoff between exploration and low computational cost at iteration $i$: the smaller $\Delta_i$ the less likely the rank reduction mechanism takes action.
**5. A rank-increasing algorithm.** As mentioned in Section 1, optimization problems on the determinantal variety $\mathbb{R}_{\le r}^{m \times n}$ appear in several applications. In practice, the parameter $r$ influences both the computational work required by an optimization algorithm to produce a solution and the quality of the solution. However, the most suitable $r$, or even a suitable $r$, may not be known a priori. Rank-increasing and rank-adaptive algorithms aim at overcoming this difficulty. For example, the rank-increasing method proposed in [23, Algorithm 1] starts with a low value of $r$, which is increased progressively by a given constant. This allows the algorithm to avoid considering unnecessarily large ranks. Rank-adaptive algorithms are more sophisticated. For example, the Riemannian rank-adaptive method defined in [25, Algorithm 3] increases or decreases the rank by an adaptively chosen amount as the iteration proceeds, offering a tunable tradeoff between the computational cost of producing a solution and the quality of the solution. $\mathbb{P}^2\text{GDR}$ [15, Algorithm 6.2] and ERFDR (Algorithm 4.2) can be used to design rank-increasing schemes. An example based on ERFDR is given as Algorithm 5.1.

<caption>**Algorithm 5.1 A rank-increasing algorithm based on ERFDR**</caption>

**Require:** $(f, r, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta, \tau, \varepsilon)$ where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $0 < \underline{\alpha} \le \bar{\alpha} < \infty$, $\beta, c, \tau \in (0, 1)$, $\kappa_1 \in (0, \frac{1}{2}]$, $\kappa_2 \in (0, 1]$, and $\Delta, \varepsilon \in (0, \infty)$.
**Input:** $(X_0, r_0)$ such that $X_0 \in \mathbb{R}_{\le r_0}^{m \times n}$, $r_0 \in \{1, \dots, r\}$, and $\{X \in \mathbb{R}_{\le r}^{m \times n} | f(X) \le f(X_0)\}$ is bounded.
**Output:** $((X_i)_{i=0}^{i=i_*}, (r_i)_{i=0}^{i=i_*})$ such that $i_* \in \mathbb{N} \cup \{\infty\}$ and, for all $i \in \{1, \dots, i_*\}$, $X_i \in \mathbb{R}_{\le r_{i-1}}^{m \times n}$, $r_i \in \{r_{i-1}, \dots, r\}$, and $s(X_i; f, \mathbb{R}_{\le r_{i-1}}^{m \times n}) \le \tau^{i-1}\varepsilon$.
1: $i \leftarrow 0$;
2: **while** $s(X_i; f, \mathbb{R}_{\le r_i}^{m \times n}) > 0$ **do**
3: &nbsp;&nbsp;&nbsp;&nbsp;Iterate ERFDR on $(X_i; f, r_i, \underline{\alpha}, \bar{\alpha}, \beta, c, \kappa_1, \kappa_2, \Delta)$ at least once to compute $X_{i+1} \in \mathbb{R}_{\le r_i}^{m \times n}$ such that $s(X_{i+1}; f, \mathbb{R}_{\le r_i}^{m \times n}) \le \tau^i \varepsilon$;
4: &nbsp;&nbsp;&nbsp;&nbsp;Choose $r_{i+1} \in \{r_i, \dots, r\}$;
5: &nbsp;&nbsp;&nbsp;&nbsp;$i \leftarrow i + 1$;
6: **end while**
7: $i_* \leftarrow i$;

By Theorems 4.2 and 4.3, line 3 terminates; (4.9) even provides an upper bound on the number of ERFDR iterations required. There is no constraint on the choice to be made in line 4; the choice can be made, e.g., based on information depending on the application or by using a rank-increasing mechanism such as that in [25, Algorithm 3].

If $i_* < \infty$, then $s(X_{i_*}; f, \mathbb{R}_{\le r_{i_*}}^{m \times n}) = 0$. Otherwise, since $(r_i)_{i \in \mathbb{N}}$ is in $\mathbb{N}$, monotonically nondecreasing, and upper bounded by $r$, there exists $\underline{r} \in \{r_0, \dots, r\}$ such that $r_i = \underline{r}$ for all $i \in \mathbb{N}$ large enough. Thus, Corollary 5.1 readily follows from Theorems 4.2 and 4.3.

**COROLLARY 5.1.** Let $((X_i)_{i=0}^{i=i_*}, (r_i)_{i=0}^{i=i_*})$ be generated by Algorithm 5.1. If $i_* < \infty$, then $X_{i_*}$ is B-stationary on $\mathbb{R}_{\le r_{i_*}}^{m \times n}$, i.e., $s(X_{i_*}; f, \mathbb{R}_{\le r_{i_*}}^{m \times n}) = 0$. Otherwise, letting $\underline{r}$ denote the limit of $(r_i)_{i \in \mathbb{N}}$:

1. each of the accumulation points of $(X_i)_{i \in \mathbb{N}}$, of which there exists at least one, is B-stationary on $\mathbb{R}_{\le r}^{m \times n}$, i.e., is a zero of $s(\cdot; f, \mathbb{R}_{\le \underline{r}}^{m \times n})$;

2. $\lim_{i \to \infty} s(X_i; f, \mathbb{R}_{\le \underline{r}}^{m \times n}) = 0$;

3. all accumulation points of $(X_i)_{i \in \mathbb{N}}$ have the same image by $f$.
Corollary 5.1 is stronger than [25, Theorem 2]. Furthermore, the latter relies on [25, Assumption 6], which can fail to be satisfied even by polynomial functions [14, Proposition 7.21].

ERFDR can be replaced with $P^2$GDR in Algorithm 5.1. By [15, Theorem 6.2 and Corollary 6.3], a result analogous to Corollary 5.1 holds.

**6. The CRFD map and the CRFDR algorithm.** The CRFD map is introduced in Definition 6.3 as a subclass of the ERFD map (Algorithm 3.1) based on Propositions 6.1 and 6.2. It exploits the idea raised at the end of Section 2.2 of finding a computationally cheaper surrogate for (2.15) when the rank of the input is smaller than $r$. The CRFDR map, which is the iteration map of CRFDR and uses the CRFD map as a subroutine, is also introduced in Definition 6.3.

**PROPOSITION 6.1.** For every closed cone $C \subseteq \mathbb{R}^{m \times n}$,

$$ \inf_{X \in \mathbb{R}^{m \times n} \setminus \{0_{m \times n}\}} \frac{\|P_C(X)\|}{\|X\|} = \min_{X \in \partial B(0_{m \times n}, 1)} \|P_C(X)\|, $$

and this quantity is positive if and only if $C^* = \{0_{m \times n}\}$.

*Proof.* Let $C \subseteq \mathbb{R}^{m \times n}$ be a closed cone. For all $X \in \mathbb{R}^{m \times n} \setminus \{0_{m \times n}\}$ and $\lambda \in (0, \infty)$,

$$ d(\lambda X, C) = \inf_{Y \in C} \|\lambda X - Y\| = \lambda \inf_{Y \in C} \|X - \frac{Y}{\lambda}\| = \lambda \inf_{Y \in C} \|X - Y\| = \lambda d(X, C). $$

Thus, by Proposition 2.1, for all $X \in \mathbb{R}^{m \times n} \setminus \{0_{m \times n}\}$,

$$ \begin{aligned} \frac{\|P_C(X)\|}{\|X\|} &= \frac{\sqrt{\|X\|^2 - d(X, C)^2}}{\|X\|} \\ &= \sqrt{1 - \left(\frac{d(X, C)}{\|X\|}\right)^2} \\ &= \sqrt{1 - d\left(\frac{X}{\|X\|}, C\right)^2} \\ &= \|P_C\left(\frac{X}{\|X\|}\right)\|. \end{aligned} $$

Hence,

$$ \inf_{X \in \mathbb{R}^{m \times n} \setminus \{0_{m \times n}\}} \frac{\|P_C(X)\|}{\|X\|} = \inf_{X \in \partial B(0_{m \times n}, 1)} \|P_C(X)\|. $$

The equality follows from the extreme value theorem. The “if and only if” statement follows from Proposition 2.1. □

**PROPOSITION 6.2.** Let $X \in \mathbb{R}^{m \times n}$ and $\tau := \text{rank} X$. Let $C \subseteq \mathbb{R}^{m \times n}$ be a closed cone such that $C^* = \{0_{m \times n}\}$. Then, every $G \in P_C(-\nabla f(X))$ satisfies (3.1) with $\kappa_1 = \min_{Y \in \partial B(0_{m \times n}, 1)} \|P_C(Y)\|^2$ and $\kappa_2 = 1$ and $X + \alpha G \in \mathbb{R}^{m \times n}$ for all $\alpha \in (0, \infty)$.

*Proof.* Let $Z := -\nabla f(X)$ and $G \in P_C(Z)$. By Propositions 2.1 and 6.1 and the
first inequality of (2.17),

$$
\begin{align*}
\langle Z, G \rangle &= \|G\|^2 \\
&= \|P_C(Z)\|^2 \\
&\geq \min_{Y \in \partial B(0_{m \times n}, 1)} \|P_C(Y)\|^2 \|Z\|^2 \\
&\geq \min_{Y \in \partial B(0_{m \times n}, 1)} \|P_C(Y)\|^2 s(X; f, \mathbb{R}_{\leq r}^{m \times n})^2,
\end{align*}
$$

which establishes the first statement. The second statement holds by subadditivity
of the rank.

<figure><img src="image_3.png" /></figure>

DEFINITION 6.3. The ERFD map (Algorithm 3.1) is called the CRFD map if, given an input $X \in \mathbb{R}_{\leq r}^{m \times n}$ of rank denoted by $\underline{r}$, the element of $\mathbb{R}^{m \times n}$ to be chosen in line 1 is selected in $P_{\underline{T}_{\mathbb{R}_{\leq r}^{m \times n}}(X)}(-\nabla f(X))$ if $\underline{r} = r$ and in $P_C(-\nabla f(X))$ if $\underline{r} < r$, where $C \subseteq \mathbb{R}_{\leq r-\underline{r}}^{m \times n}$ is a closed cone satisfying the following properties:

1. $\min_{Y \in \partial B(0_{m \times n}, 1)} \|P_C(Y)\|^2 \ge \kappa_1$;

2. computing a projection onto $C$ and an SVD of this projection is at most as
expensive as computing the Frobenius norm of an element of $\mathbb{R}^{m \times n}$.

The ERFDR map is called the CRFDR map if it uses the CRFD map in lines 1 and 4.

Examples of a closed cone $C \subseteq \mathbb{R}_{\le 1}^{m \times n}$ satisfying the requirements of Definition 6.3 for all $X \in \mathbb{R}_{<r}^{m \times n}$ are given in Table 6.1.

<table><caption>TABLE 6.1</caption>
  <thead>
    <tr>
      <th>C</th>
      <th>min<br>X∈∂B(0<sub>m×n</sub>,1) ||P<sub>C</sub>(X)||<sup>2</sup></th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <td>all elements of ℝ<sup>m×n</sup> with at most one nonzero entry</td>
      <td>1/mn</td>
    </tr>
    <tr>
      <td>all elements of ℝ<sup>m×n</sup> with at most one nonzero row</td>
      <td>1/m</td>
    </tr>
    <tr>
      <td>all elements of ℝ<sup>m×n</sup> with at most one nonzero column</td>
      <td>1/n</td>
    </tr>
  </tbody>
</table>

Examples of a closed cone $C \subseteq \mathbb{R}_{\le 1}^{m \times n}$ satisfying the requirements of Definition 6.3 for all $X \in \mathbb{R}_{<r}^{m \times n}$.

Proposition 6.2 still holds if “$P_C(-\nabla f(X))$” and “$\kappa_2 = 1$” are replaced with “$P_{\tilde{T}_{\mathbb{R}^{m \times n}}(X)}(-\nabla f(X)) + P_C(-\nabla f(X))$” and “$\kappa_2 = \frac{1}{2}$”, respectively. This defines a potentially interesting alternative to the CRFD map.

**7. Practical implementation and computational cost of the CRFDR map.** Following [13, §7], this section compares the computational cost of the CRFDR map (Definition 6.3) with that of the RFDR map [13, Algorithm 2] (Section 7.2) and that of the RFD map [13, Algorithm 1] (Section 7.3). The comparison is based on detailed implementations of these algorithms involving only evaluations of $f$ and $\nabla f$, a projection onto a closed cone $C$ as in Definition 6.3, an SVD of this projection, and some operations from linear algebra:

1. matrix multiplication requiring at most 2mnr flops;

2. QR factorization with column pivoting [5, Algorithm 5.4.1] of a matrix with $m$ or $n$ rows and at most $r$ columns;
3. small-scale SVD, i.e., the matrix to decompose is m-by-r, r-by-n, or its dimensions are at most r;

4. large-scale SVD, i.e., truncated SVD of rank at most $r - \underline{z}$ of an m-by-n matrix whose rank can be as large as $\min\{m, n\} - \underline{z}$, with $\underline{z} \in \{0, \dots, r-1\}$.

The SVD terminology is that from Section 2.1. In this list, only the (truncated) SVD relies on a convergent algorithm rather than an algorithm with finite complexity such as those for QR factorization. Furthermore, if $C$ is chosen among the examples given in Table 6.1, then projecting onto $C$ amounts to find, in an $m$-by-$n$ matrix, the entry of maximal absolute value or the row or column of maximal Frobenius norm, and an SVD of the projection is readily available.

**7.1. Detailed implementation of the CRFDR map.** Detailed implementations of the RFDR and CRFDR maps are given in [13, Algorithms 8] and Algorithm 7.2, respectively.<fnref n="1" /> Algorithm 7.2 uses as a subroutine Algorithm 7.1, which is a detailed implementation of the CRFD map. Those algorithms work with factorizations of the involved matrices as much as possible.

Algorithm 7.1 involves one evaluation of $\nabla f$ (in line 1), at most

$$ (7.1) \qquad 1 + \max \left\{ 0, \left\lfloor \ln \left( \frac{2(1-c)}{\alpha \mathrm{Lip}_{B[X,\alpha||\nabla f(X)||]}(\nabla f)} \right) / \ln(\beta) \right\rfloor \right\} $$

evaluations of $f$ (in the while loop that is executed), at most one projection onto $C$ and an SVD of this projection (in line 21), zero or two QR factorization(s) with column pivoting of a matrix with $m$ or $n$ rows and at most $r$ columns (in line 23), matrix multiplications requiring at most $2mnr$ flops [5, Table 1.1.2], and one small-scale SVD (just after the while loop that is executed). The upper bound (7.1) follows from (3.4).

If the input is $0_{m \times n}$, then the QR factorizations in line 23 and the small-scale SVD in line 27 are not needed.

The input and output of Algorithm 7.1 are SVDs because it is a subroutine of Algorithm 7.2, which requires an SVD as input.

<footnote n="1">¹Matlab implementations of RFDR and CRFDR based on these detailed implementations are available at https://github.com/golikier/BouligandStationarityLowRankOptimization.</footnote>
<caption>**Algorithm 7.1 Detailed CRFD map via SVDs**</caption>

**Require:** ($f, r, \alpha, \beta, c, \kappa_1$) where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $\alpha \in (0, \infty)$, $\beta, c \in (0, 1)$, and $\kappa_1 \in (0, \frac{1}{2}]$.

**Input:** $(U, \Sigma, V)$ where $U\Sigma V^\top \in \mathbb{R}_\ell^{m \times n}$ is an SVD and $\ell \in \{0, \dots, r\}$.

**Output:** $(\tilde{U}, \tilde{\Sigma}, \tilde{V})$ where $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \mathbb{R}_{\tilde{r}}^{m \times n}$ is an SVD, $\tilde{r} \in \{0, \dots, r\}$, and $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \text{ERFD}(U\Sigma V^\top; f, r, \alpha, \alpha, \beta, c, \kappa_1, 1)$.

1: $G \leftarrow -\nabla f(U\Sigma V^\top)$;

2: **if** $\ell = r$ **then**

3: $G_1 \leftarrow U^\top G$; $G_2 \leftarrow GV$; $s_1 \leftarrow \|G_1\|^2$; $s_2 \leftarrow \|G_2\|^2$;

4: **if** $s_1 \ge s_2$ **then**

5: $X_2 \leftarrow \Sigma V^\top$;

6: **while** $f(U(X_2 + \alpha G_1)) > f(U\Sigma V^\top) - c\alpha s_1$ **do** ▷
$UG_1 \in P_{\tilde{T}_{\mathbb{R}^{m \times n}(U\Sigma V^\top)}}(G)$.

7: $\alpha \leftarrow \alpha\beta$;

8: **end while**

9: Compute an SVD $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \mathbb{R}_{\tilde{r}}^{r \times n}$ of $X_2 + \alpha G_1$;

10: $\tilde{U} \leftarrow U\tilde{U}$;

11: **else**

12: $X_1 \leftarrow U\Sigma$;

13: **while** $f((X_1 + \alpha G_2)V^\top) > f(U\Sigma V^\top) - c\alpha s_2$ **do** ▷
$G_2V^\top \in P_{\tilde{T}_{\mathbb{R}^{m \times n}(U\Sigma V^\top)}}(G)$.

14: $\alpha \leftarrow \alpha\beta$;

15: **end while**

16: Compute an SVD $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \mathbb{R}_{\tilde{r}}^{m \times r}$ of $X_1 + \alpha G_2$;

17: $\tilde{V} \leftarrow V\tilde{V}$;

18: **end if**

19: **else**

20: Choose, e.g., in Table 6.1, a closed cone $C \subseteq \mathbb{R}_{\le r-\ell}^{m \times n}$ satisfying the requirements of Definition 6.3;

21: Choose $\bar{G} \in P_C(G)$ and write it via SVD as $\bar{G} = \overline{U\Sigma V}^\top \in \mathbb{R}_{\bar{r}}^{m \times n}$; ▷ Recall that $1 \le \bar{r} \le r - \ell$.

22: $s \leftarrow \|\bar{\Sigma}\|^2$;

23: Compute QR factorizations with column pivoting $[U \bar{U}] = \hat{U}R_1$ and $[V \bar{V}] = \hat{V}R_2$ where $\hat{U} \in \text{St}(r_1, m)$, $\hat{V} \in \text{St}(r_2, n)$, and $r_1, r_2 \in \{\max\{\ell, \bar{r}\}, \dots, \ell + \bar{r}\}$;

24: **while** $f(\hat{U}R_1 \text{diag}(\Sigma, \alpha\bar{\Sigma})R_2^\top \hat{V}^\top) > f(U\Sigma V^\top) - c\alpha s$ **do**

25: $\alpha \leftarrow \alpha\beta$;

26: **end while**

27: Compute an SVD $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \mathbb{R}_{\tilde{r}}^{r_1 \times r_2}$ of $R_1 \text{diag}(\Sigma, \alpha\bar{\Sigma})R_2^\top$;

28: $\tilde{U} \leftarrow \hat{U}\tilde{U}$; $\tilde{V} \leftarrow \hat{V}\tilde{V}$;

29: **end if**

30: Return $(\tilde{U}, \tilde{\Sigma}, \tilde{V})$.

In the worst case, i.e., if the input has rank $r$ and its smallest singular value is smaller than or equal to $\Delta$, then Algorithm 7.2 calls Algorithm 7.1 twice. In the first call, applied to the input, lines 3 to 18 are executed. In the second call, applied to a projection of the input onto $\mathbb{R}_{r-1}^{m \times n}$, it holds that $\ell = r - 1$, hence lines 20 to 28
are executed. If $r > 1$, then, besides matrix multiplications, the two calls require two evaluations of $\nabla f$, at most two times (7.1) evaluations of $f$, one projection onto the closed cone $C$, an SVD of this projection, two QR factorization(s) with column pivoting of a matrix with $m$ or $n$ rows and $r$ columns, and two small-scale SVDs.

<caption>**Algorithm 7.2 Detailed CRFDR map**</caption>

**Require:** ($f, r, \alpha, \beta, c, \kappa_1, \Delta$) where $f: \mathbb{R}^{m \times n} \to \mathbb{R}$ is differentiable with $\nabla f$ locally Lipschitz continuous, $r < \min\{m, n\}$ is a positive integer, $\alpha \in (0, \infty)$, $\beta, c \in (0, 1)$, $\kappa_1 \in (0, \frac{1}{2}]$, and $\Delta \in (0, \infty)$.

**Input:** ($U, \tilde{\Sigma}, V$) where $U\Sigma V^\top \in \mathbb{R}_{\mathcal{L}}^{m \times n}$ is an SVD and $\mathcal{L} \in \{0, \dots, r\}$.

**Output:** ($\tilde{U}, \tilde{\Sigma}, \tilde{V}$) where $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \mathbb{R}_{\tilde{r}}^{m \times n}$ is an SVD, $\tilde{r} \in \{0, \dots, r\}$, and $\tilde{U}\tilde{\Sigma}\tilde{V}^\top \in \text{ERFDR}(U\Sigma V^\top; f, r, \alpha, \alpha, \beta, c, \kappa_1, \Delta)$.

1: ($\tilde{U}, \tilde{\Sigma}, \tilde{V}$) ← Algorithm 7.1($U, \Sigma, V$; $f, r, \alpha, \beta, c, \kappa_1$);

2: **if** $\mathcal{L} = r$ and $\Sigma(r, r) \le \Delta$ **then**

3: ($\tilde{U}^R, \tilde{\Sigma}^R, \tilde{V}^R$) ← Algorithm 7.1($U(\cdot, 1:r-1), \Sigma(1:r-1, 1:r-1), V(\cdot, 1:r-1)$; $f, r, \alpha, \beta, c, \kappa_1$);

4: **if** $f(\tilde{U}^R\tilde{\Sigma}^R(\tilde{V}^R)^\top) < f(\tilde{U}\tilde{\Sigma}\tilde{V}^\top)$ **then**

5: ($\tilde{U}, \tilde{\Sigma}, \tilde{V}$) ← ($\tilde{U}^R, \tilde{\Sigma}^R, \tilde{V}^R$);

6: **end if**

7: **end if**

8: **Return** ($\tilde{U}, \tilde{\Sigma}, \tilde{V}$).

**7.2. Comparison with the RFDR map.** Table 7.1 summarizes the operations required by [13, Algorithm 8] and Algorithm 7.2, matrix multiplication excluded, in the case where $r > 1$, the input has rank $r$, and its smallest singular value is smaller than or equal to $\Delta$. The only difference is that, where [13, Algorithm 8] requires a large-scale SVD, Algorithm 7.2 merely requires a projection onto $C$, an SVD of this projection, and two QR factorizations with column pivoting of a matrix with $m$ or $n$ rows and $r$ columns.

<table><caption>TABLE 7.1</caption><thead><tr><th>Operation</th><th>[13, Algorithm 8] (RFDR)</th><th>Algorithm 7.2 (CRFDR)</th></tr></thead><tbody><tr><td>evaluation of f</td><td>at most 2 · (7.1)</td><td>at most 2 · (7.1)</td></tr><tr><td>evaluation of ∇f</td><td>2</td><td>2</td></tr><tr><td>QR</td><td>0</td><td>2</td></tr><tr><td>small-scale SVD</td><td>2</td><td>2</td></tr><tr><td>large-scale SVD</td><td>1</td><td>0</td></tr><tr><td>SVD-projection onto C</td><td>0</td><td>1</td></tr></tbody></table>

Operations required by [13, Algorithm 8] and Algorithm 7.2, matrix multiplication excluded, in the case where $r > 1$, the input has rank $r$, and its smallest singular value is smaller than or equal to $\Delta$. “QR” means QR factorization with column pivoting of a matrix with $m$ or $n$ rows and $r$ columns. “SVD-projection onto $C$” means computing a projection onto $C$ and writing it as an SVD, which is straightforward if $C$ is chosen from Table 6.1.

**7.3. Comparison with the RFD map.** RFD [21, Algorithm 4] does not satisfy the property that accumulation points are B-stationary for (1.1) [13, §8] whereas, as shown above, CRFDR does. This comes at a computational cost which, however, is the least amongst all methods that satisfy the property. In the typical case where the sequence generated by RFD is contained in $\mathbb{R}_r^{m \times n}$, this computational overhead
is twofold. First, the iterates of CRFDR are stored as SVDs, while those of RFD
merely need to be stored in a format that reveals the rank and orthonormal bases of
the row and column spaces. Second, given an input $X \in \mathbb{R}_r^{m \times n}$ such that $\sigma_r(X) \le \Delta$, the CRFDR map applies the CRFD map to $\tilde{X} \in P_{\mathbb{R}_{r-1}^{m \times n}}(X)$; $\tilde{X}$ is readily available since the iterates are stored as SVDs. This involves the following: (i) computing an arbitrary projection of $-\nabla f(\tilde{X})$ onto a closed cone as in Definition 6.3 and writing it as an SVD, which requires no computational overhead beyond evaluating $-\nabla f(\tilde{X})$ if $C$ is the first example given in Table 6.1; (ii) at most (7.1) evaluations of $f$; (iii) two QR factorizations with column pivoting of a matrix with $m$ or $n$ rows and $r$ columns; (iv) one SVD of a matrix whose dimensions are at most $r$.

**8. Conclusion.** PGD, P²GDR, RFDR, HRTR, and some of their hybridizations are the only algorithms in the literature guaranteed to generate a sequence in $\mathbb{R}_{\le r}^{m \times n}$ whose accumulation points are B-stationary for (1.1) in the sense of Definition 2.3. All these algorithms can require SVDs or eigenvalue decompositions that are computationally prohibitive in the typical case where $r \ll \min\{m, n\}$ if $\nabla f$ does not have low rank. Among them, RFDR is the most parsimonious with these computationally expensive operations.

The main contribution of this paper is CRFDR (Definition 6.3), a modification of RFDR that generates a sequence in $\mathbb{R}_{\le r}^{m \times n}$ whose accumulation points are B-stationary for (1.1), while requiring none of the computationally expensive operations mentioned in the preceding paragraph (Table 7.1). In the class of algorithms generating a sequence in $\mathbb{R}_{\le r}^{m \times n}$ whose accumulation points are provably B-stationary for (1.1), CRFDR is that with the smallest computational overhead compared with RFD [21, Algorithm 4], which is not in that class [13, §8]; see Section 7.3. The measure of B-stationarity defined in (2.1) converges to zero along bounded subsequences at a rate at least $O(1/\sqrt{i+1})$, where $i$ is the iteration counter. A side contribution of this paper is a rank-increasing scheme (Algorithm 5.1), which can be of interest if the parameter $r$ in (1.1) is potentially overestimated. A promising perspective is to use CRFDR to design hybrid algorithms based on the framework presented in [15, §3].

REFERENCES

[1] P.-A. ABSIL, R. MAHONY, AND R. SEPULCHRE, *Optimization Algorithms on Matrix Manifolds*, Princeton University Press, Princeton, NJ, USA, 2008, https://doi.org/10.1515/9781400830244.

[2] N. BOUMAL, P.-A. ABSIL, AND C. CARTIS, *Global rates of convergence for nonconvex optimization on manifolds*, IMA Journal of Numerical Analysis, 39 (2019), pp. 1–33, https://doi.org/10.1093/imanum/drx080.

[3] C. ECKART AND G. YOUNG, *The approximation of one matrix by another of lower rank*, Psychometrika, 1 (1936), pp. 211–218, https://doi.org/10.1007/BF02288367.

[4] N. GILLIS AND F. GLINEUR, *Low-rank matrix approximation with weights or missing data is NP-hard*, SIAM Journal on Matrix Analysis and Applications, 32 (2011), pp. 1149–1165, https://doi.org/10.1137/110820361.

[5] G. H. GOLUB AND C. F. VAN LOAN, *Matrix Computations*, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, USA, 4th ed., 2013, https://doi.org/10.56021/9781421407944.

[6] L. GRIPPO, F. LAMPARIELLO, AND S. LUCIDI, *A nonmonotone line search technique for Newton's method*, SIAM Journal on Numerical Analysis, 23 (1986), pp. 707–716, https://doi.org/10.1137/0723046.

[7] W. HA, H. LIU, AND R. F. BARBER, *An equivalence between critical points for rank constraints versus low-rank factorizations*, SIAM Journal on Optimization, 30 (2020), pp. 2927–2955, https://doi.org/10.1137/18M1231675.

[8] U. HELMKE AND M. A. SHAYMAN, *Critical points of matrix least squares distance func-
tions, Liner Algebra and its Applications, 215 (1995), pp. 1–19, https://doi.org/10.1016/
0024-3795(93)00070-G.

[9] E. LEVIN, J. KILEEL, AND N. BOUMAL, *Finding stationary points on bounded-rank matrices: a geometric hurdle and a smooth remedy*, Mathematical Programming, 199 (2023), pp. 831–864, https://doi.org/10.1007/s10107-022-01851-2.

[10] E. LEVIN, J. KILEEL, AND N. BOUMAL, *The effect of smooth parametrizations on nonconvex optimization landscapes*, Mathematical Programming, (2024), https://doi.org/10.1007/s10107-024-02058-3.

[11] X. LI AND Z. LUO, *Normal cones intersection rule and optimality analysis for low-rank matrix optimization with affine manifolds*, SIAM Journal on Optimization, 33 (2023), pp. 1333–1360, https://doi.org/10.1137/22M147863X.

[12] Y. NESTEROV, *Lectures on Convex Optimization*, vol. 137 of Springer Optimization and Its Applications, Springer, Cham, 2nd ed., 2018, https://doi.org/10.1007/978-3-319-91578-4.

[13] G. OLIKIER AND P.-A. ABSIL, *An apocalypse-free first-order low-rank optimization algorithm with at most one rank reduction attempt per iteration*, SIAM Journal on Matrix Analysis and Applications, 44 (2023), pp. 1421–1435, https://doi.org/10.1137/22M1518256.

[14] G. OLIKIER, K. A. GALLIVAN, AND P.-A. ABSIL, *First-order optimization on stratified sets*, (2023), https://arxiv.org/abs/2303.16040.

[15] G. OLIKIER, K. A. GALLIVAN, AND P.-A. ABSIL, *Low-rank optimization methods based on projected-projected gradient descent that accumulate at Bouligand stationary points*, (2024), https://arxiv.org/abs/2201.03962v2.

[16] G. OLIKIER, A. USCHMAJEW, AND B. VANDEREYCKEN, *Gauss-Southwell type descent methods for low-rank matrix optimization*, (2023), https://arxiv.org/abs/2306.00897v2.

[17] G. OLIKIER AND I. WALDSPURGER, *Projected gradient descent accumulates at Bouligand stationary points*, (2024), https://arxiv.org/abs/2403.02530.

[18] E. PAUWELS, *Generic Fréchet stationarity in constrained optimization*, (2024), https://arxiv.org/abs/2402.09831.

[19] Q. REBJOCK AND N. BOUMAL, *Optimization over bounded-rank matrices through a desingularization enables joint global and local guarantees*, (2024), https://arxiv.org/abs/2406.14211.

[20] R. T. ROCKAFELLAR AND R. J.-B. WETS, *Variational Analysis*, vol. 317 of Grundlehren der mathematischen Wissenschaften, Springer-Verlag Berlin Heidelberg, 1998, https://doi.org/10.1007/978-3-642-02431-3. Corrected 3rd printing 2009.

[21] R. SCHNEIDER AND A. USCHMAJEW, *Convergence results for projected line-search methods on varieties of low-rank matrices via Lojasiewicz inequality*, SIAM Journal on Optimization, 25 (2015), pp. 622–646, https://doi.org/10.1137/140957822.

[22] A. THEMELIS, L. STELLA, AND P. PATRINOS, *Forward-backward envelope for the sum of two nonconvex functions: Further properties and nonmonotone linesearch algorithms*, SIAM Journal on Optimization, 28 (2018), pp. 2274–2303, https://doi.org/10.1137/16M1080240.

[23] A. USCHMAJEW AND B. VANDEREYCKEN, *Line-search methods and rank increase on low-rank matrix varieties*, in Proceedings of the 2014 International Symposium on Nonlinear Theory and its Applications, 2014, pp. 52–55, https://doi.org/10.34385/proc.46.A1L-C4.

[24] A. USCHMAJEW AND B. VANDEREYCKEN, *On critical points of quadratic low-rank matrix optimization problems*, IMA Journal of Numerical Analysis, 40 (2020), pp. 2626–2651, https://doi.org/10.1093/imanum/drz061.

[25] G. ZHOU, W. HUANG, K. A. GALLIVAN, P. VAN DOOREN, AND P.-A. ABSIL, *A Riemannian rank-adaptive method for low-rank optimization*, Neurocomputing, 192 (2016), pp. 72–80, https://doi.org/10.1016/j.neucom.2016.02.030.