Pipeline-generated

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Riemannian optimization on stiefel and grassmann manifolds

1 · Prerequisites

2 · Summary

This page develops first-order geometry and optimization for real orthonormal frames and their Grassmann quotient, plus the complex Grassmann geometry needed for Hermitian projector models. It fixes the real Frobenius metric on complex coordinates, proves tangent and projected-gradient formulas, and gives exact-domain real QR and polar retractions, a complex polar retraction, and projected real Stiefel/Grassmann vector transport. The algorithm entries define finite-budget retraction Armijo and an OPT3-matched real or complex Grassmann trust-region method. The complexity results prove Armijo and trust-region first-order $O (ε^{- 2})$ bounds under their stated pullback regularity and subproblem conditions; the trust-region count includes accepted and rejected outer trials.

Grassmann objectives must be invariant under changes of orthonormal frame. Finite search or subproblem budgets can return failure and carry no unconditional success guarantee. The trust-region result is first-order; no second-order complexity claim is made here. The complex model treats complex matrix spaces as real vector spaces with metric $Re tr (U^{*} V)$ .

3 · Logical flowchart

4 · Definitions, theorems and proofs

DefinitionDefinition: Literature-sourcedProof: AI-generatedOpen item page →

Real Stiefel and Grassmann optimization conventions

Definition

For integers $1 \leq r \leq n$ , the real Stiefel manifold is $St (n, r) : = {X \in R^{n \times r} : X^{T} X = I_{r}} .$ The real Grassmannian $Gr (r, n)$ is the set of $r$ -dimensional linear subspaces of $R^{n}$ , identified with the quotient of $St (n, r)$ by the right action $X \mapsto X Q$ of $O (r)$ . A frame $X$ represents the subspace $[X] = range (X)$ .

On matrix spaces use the Frobenius inner product $⟨ U, V ⟩_{F} = tr (U^{T} V)$ . Give Stiefel its induced metric. On the Grassmann quotient use the quotient metric: identify a tangent vector at $[X]$ with its unique horizontal representative $Z$ satisfying $X^{T} Z = 0$ , and pair horizontal representatives by the Frobenius inner product. A Grassmann formula written with a frame representative must be unchanged under $(X, Z) \mapsto (X Q, Z Q)$ for $Q \in O (r)$ .

For a square real matrix $M$ , set $sym (M) = (M + M^{T}) / 2$ .

Facts & Assumptions

Given: Integers $1 \leq r \leq n$ and the real matrix spaces with their Euclidean topology.

[F1]

The right action of $O (r)$ on orthonormal frames changes frame but not the represented subspace, and its quotient is the Grassmannian (Stiefel spaces, Grassmannians, and tautological bundles).

[F2]

A Riemannian metric is a smooth symmetric positive-definite bilinear form on each tangent space (Riemannian metric and riemannian manifold).

[F3]

The Euclidean inner product on a finite real coordinate space is the sum of coordinatewise products (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F4]

A Grassmannian point is an $r$ -dimensional subspace of the ambient vector space (The Grassmannian of r-dimensional subspaces of a finite-dimensional vector space).

Proof

technique · direct verification of the metric convention

1.1givenF2F3algebra

For any real matrix $U$ , $⟨ U, U ⟩_{F} = \sum_{i, j} U_{i j}^{2}$ , so this pairing is symmetric bilinear and positive for every nonzero $U$ by [F3]. Its restriction to each tangent or horizontal subspace is therefore a positive-definite inner product, as required by [F2].

1.2F1givenalgebra

In a local Grassmann graph chart, choose a smooth orthonormal frame section $X (u)$ from the local frame-bundle trivialization in [F1], and set $P (u) = X (u) X (u)^{T}$ . For a chart tangent $v$ , differentiating $X (u)^{T} X (u) = I$ gives $A = X (u)^{T} D X_{u} [v]$ skew-symmetric. The first term $X (u) A$ is vertical: for every skew-symmetric $A$ , the Cayley curve $Q (t) = (I_{r} - \frac{t}{2} A)^{- 1} (I_{r} + \frac{t}{2} A)$ satisfies $Q (t)^{T} Q (t) = I_{r}$ near zero and $Q (t) = I_{r} + t A + O (t^{2})$ . Thus $Z = (I - X (u) X (u)^{T}) D X_{u} [v]$ is the unique horizontal representative of $v$ . Then $D P_{u} [v] = Z X (u)^{T} + X (u) Z^{T}$ . For horizontal $Z, W$ , direct expansion gives $\frac{1}{2} ⟨ Z X^{T} + X Z^{T}, W X^{T} + X W^{T} ⟩_{F} = ⟨ Z, W ⟩_{F}$ . Thus the quotient pairing has smooth coefficients in every graph chart. In a local product chart of the frame bundle, matrix entries vary smoothly, so the ambient Frobenius pairing has smooth coefficients on Stiefel as well.

2.1F1F4givenalgebra∎

By [F4], each frame represents an $r$ -dimensional subspace, and [F1] identifies frames representing the same subspace by the right orthogonal action. For $Q^{T} Q = I_{r}$ , cyclicity of trace gives $⟨ U Q, V Q ⟩_{F} = tr (Q^{T} U^{T} V Q) = tr (U^{T} V)$ . Thus the action is isometric and the horizontal pairing is independent of the chosen orthonormal frame.

DefinitionDefinition: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Complex Stiefel and Grassmann optimization conventions

Definition

For $1 \leq r \leq n$ , set ${St}_{C} (n, r) = {X \in C^{n \times r} : X^{*} X = I_{r}}$ and ${Gr}_{C} (r, n) = {St}_{C} (n, r) / U (r)$ . The class $[X]$ represents the complex column space of $X$ ; two orthonormal frames represent the same space exactly when they differ by right multiplication by a unitary $r \times r$ matrix. Regard each complex matrix space as a real vector space and use the real Frobenius inner product $⟨ U, V ⟩_{R} : = Re tr (U^{*} V) .$ Give the complex Stiefel manifold its induced metric. On the complex Grassmann quotient, represent tangent vectors horizontally by matrices $Z$ with $X^{*} Z = 0$ and pair these representatives by $⟨ \cdot, \cdot ⟩_{R}$ . For $A = A_{0} + i A_{1} \in C^{n \times r}$ , write $ρ (A) : = (\begin{array}{cc} A_{0} & - A_{1} \\ A_{1} & A_{0} \end{array}) \in R^{2 n \times 2 r}$ for its realification, the real matrix acting on real/imaginary coordinates as $A$ acts on complex coordinates. Write $Herm (A) = (A + A^{*}) / 2$ .

Facts & Assumptions

Given: Integers $1 \leq r \leq n$ and complex matrix spaces with their usual real-coordinate topology.

[F1]

A Riemannian metric is a smooth positive-definite real bilinear pairing on each tangent space (Riemannian metric and riemannian manifold).

[F2]

The coordinatewise product on a finite real coordinate space is its Euclidean inner product (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

[F3]

Complex Stiefel frames are quotiented by the right unitary action, and graph charts give the Grassmannian's local coordinates (Stiefel spaces, Grassmannians, and tautological bundles).

Proof

technique · identify complex matrices with pairs of real matrices and verify the quotient pairing

1.1F1F2givenalgebra

Write $U = A + i B$ and $V = C + i D$ with real matrices. For $z = x + i y$ , $ρ (U) (x, y) = (A x - B y, B x + A y)$ , the real and imaginary parts of $U z$ ; hence $ρ (U V) = ρ (U) ρ (V)$ , $ρ (U)^{T} = ρ (U^{*})$ , and, when $U$ is invertible, $ρ (U^{- 1}) = ρ (U)^{- 1}$ . Also $⟨ U, V ⟩_{R} = tr (A^{T} C + B^{T} D)$ , the ordinary Euclidean inner product on the real and imaginary coordinates. It is real bilinear, symmetric, and positive on nonzero matrices by [F2]; its restriction to each real tangent space is positive definite, as required by [F1].

1.2F1F2F3givenalgebra

In a local complex Grassmann graph chart, choose a smooth orthonormal frame section $X (u)$ from the frame-bundle trivialization in [F3], and set $P (u) = X (u) X (u)^{*}$ . For a chart tangent $v$ , differentiating $X (u)^{*} X (u) = I$ makes $A = X (u)^{*} D X_{u} [v]$ skew-Hermitian. The first term $X (u) A$ is vertical: for every skew-Hermitian $A$ , the Cayley curve $Q (t) = (I_{r} - \frac{t}{2} A)^{- 1} (I_{r} + \frac{t}{2} A)$ satisfies $Q (t)^{*} Q (t) = I_{r}$ near zero and $Q (t) = I_{r} + t A + O (t^{2})$ . Thus the horizontal component $Z = (I - X (u) X (u)^{*}) D X_{u} [v]$ is the unique representative of $v$ . Then $D P_{u} [v] = Z X (u)^{*} + X (u) Z^{*}$ . For horizontal $Z, W$ , direct expansion gives $\frac{1}{2} Re tr ((Z X^{*} + X Z^{*})^{*} (W X^{*} + X W^{*})) = Re tr (Z^{*} W)$ . Hence the quotient pairing has smooth coefficients in every graph chart. In a local product chart of the frame bundle, matrix entries vary smoothly, so the ambient real Frobenius pairing has smooth coefficients on the complex Stiefel space as well.

2.1F3givenstep 1.1algebra∎

The complex frame quotient and its local graph charts are those of [F3]. For unitary $Q$ , cyclicity of trace and $Q Q^{*} = I$ give $⟨ U Q, V Q ⟩_{R} = Re tr (Q^{*} U^{*} V Q) = Re tr (U^{*} V)$ . Thus the right unitary action is isometric, and the Frobenius pairing of horizontal representatives is independent of the chosen orthonormal frame.

PropositionStatement: Literature-sourcedProof: AI-generatedOpen item page →

Finite-dimensional Stiefel and Grassmann manifolds are compact

Statement

For $1 \leq r \leq n$ , $St (n, r)$ is a nonempty closed bounded subset of $R^{n \times r}$ , and $Gr (r, n)$ is compact as its continuous quotient image. Hence both spaces are compact.

Facts & Assumptions

Given: Integers $1 \leq r \leq n$ and the Stiefel and quotient definitions of Real Stiefel and Grassmann optimization conventions.

[F1]

A subset of finite-dimensional Euclidean space is compact if it is closed and bounded (For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent).

[F2]

The quotient map $q : X \mapsto [X]$ is continuous for the quotient topology and is surjective by the quotient definition in the real conventions.

Proof

technique · Heine–Borel followed by the open-cover definition of quotient compactness

1.1givenF1algebra

The equations $X^{T} X = I_{r}$ are polynomial equations in the entries, so their common zero set is closed. Also $∥ X ∥_{F}^{2} = tr (X^{T} X) = r$ , so the set is bounded. The matrix with columns $e_{1}, \dots, e_{r}$ belongs to it, so it is nonempty.

2.1F1F2step 1.1choose

Let $U$ be any open cover of $Gr (r, n)$ . By [F2], the sets $q^{- 1} (U)$ for $U \in U$ are open in $St (n, r)$ and cover it. Compactness from step 1.1 gives $U_{1}, \dots, U_{k} \in U$ whose preimages cover $St (n, r)$ . Since $q$ is surjective, $U_{1}, \dots, U_{k}$ cover $Gr (r, n)$ . Thus the quotient is compact directly from the open-cover definition.

3.1step 1.1step 2.1∎

Step 1.1 proves compactness of $St (n, r)$ and step 2.1 proves compactness of $Gr (r, n)$ , as claimed.

PropositionStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Finite-dimensional complex Stiefel and Grassmann manifolds are compact

Statement

For $1 \leq r \leq n$ , ${St}_{C} (n, r)$ is a nonempty closed bounded subset of the real coordinate space $R^{2 n r}$ , and ${Gr}_{C} (r, n)$ is its continuous quotient image. Both spaces are compact.

Facts & Assumptions

Given: $1 \leq r \leq n$ and the complex Stiefel and quotient definitions of Complex Stiefel and Grassmann optimization conventions.

[F1]

Complex matrix entries are real and imaginary coordinates in a finite-dimensional real Euclidean space (Complex Stiefel and Grassmann optimization conventions).

[F2]

Closed bounded subsets of finite-dimensional Euclidean space are compact (For a nonempty subset of $R^{n}$ with $n \geq 1$ , compactness, closedness and boundedness, pseudocompactness, and attainment of extrema by every continuous real-valued function are equivalent).

[F3]

The quotient map $q : X \mapsto [X]$ is continuous for the quotient topology and is surjective by the complex quotient definition.

Proof

technique · apply Heine–Borel to the frame constraint and pull back arbitrary open covers along the quotient map

1.1F1givenalgebra

The map $X \mapsto X^{*} X$ is continuous in the real and imaginary coordinates, so its inverse image of the closed singleton ${I_{r}}$ is closed. Also $∥ X ∥_{F}^{2} = tr (X^{*} X) = r$ on this set, so it is bounded. The frame $[e_{1} \dots e_{r}]$ shows it is nonempty.

2.1F1F2F3givenstep 1.1choose

Let $U$ be any open cover of ${Gr}_{C} (r, n)$ . By [F3], the sets $q^{- 1} (U)$ for $U \in U$ are open in ${St}_{C} (n, r)$ and cover it. Compactness from step 1.1 gives $U_{1}, \dots, U_{k} \in U$ whose preimages cover ${St}_{C} (n, r)$ . Surjectivity of $q$ then makes $U_{1}, \dots, U_{k}$ a cover of ${Gr}_{C} (r, n)$ . Thus the quotient is compact directly from the open-cover definition.

3.1F1F2F3step 1.1step 2.1∎

Step 1.1 proves compactness of ${St}_{C} (n, r)$ and step 2.1 proves compactness of ${Gr}_{C} (r, n)$ , as claimed.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Tangent spaces and Frobenius projections on Stiefel and Grassmann

Statement

For $X \in St (n, r)$ , the tangent space and its Frobenius orthogonal projection are $T_{X} St (n, r) = {Z : X^{T} Z + Z^{T} X = 0}, Π_{X}^{S t} (G) = G - X sym (X^{T} G) .$ For $[X] \in Gr (r, n)$ , its tangent vectors have unique horizontal representatives $Z$ with $X^{T} Z = 0$ , and the quotient-metric projection of an ambient $G$ to this horizontal space is $Π_{X}^{G r} (G) = (I - X X^{T}) G .$

Facts & Assumptions

Given: $1 \leq r \leq n$ , $X^{T} X = I_{r}$ , and the Frobenius metrics of Real Stiefel and Grassmann optimization conventions.

[F1]

The Stiefel constraint map is $F (X) = X^{T} X - I_{r}$ , and the Grassmannian is the quotient of orthonormal frames by the right orthogonal action (Stiefel spaces, Grassmannians, and tautological bundles).

[F2]

At a regular level, the tangent space is the kernel of the differential (The tangent space of a regular level set is the kernel).

Proof

technique · differentiate the Stiefel constraint and orthogonally decompose matrices

1.1F1F2givenalgebra

The derivative of $F$ at $X$ is $D F_{X} [Z] = X^{T} Z + Z^{T} X$ . It is onto the symmetric matrices because for any symmetric $H$ , the choice $Z = X H / 2$ gives $D F_{X} [Z] = H$ . Thus $0$ is a regular value; [F2] identifies the tangent space with the displayed kernel.

2.1givenstep 1.1algebra

Write $S = sym (X^{T} G)$ . Then $X^{T} (G - X S) + (G - X S)^{T} X = 0$ , so $G - X S$ is tangent. For every symmetric $H$ and tangent $Z$ , $⟨ X H, Z ⟩_{F} = tr (H X^{T} Z) = 0$ because $X^{T} Z$ is skew-symmetric. Hence $X S$ is normal and $G - X S$ is the orthogonal projection.

2.2F1givenstep 1.1algebra

A curve $Q (t)$ in $O (r)$ through $I_{r}$ has $Ω = Q^{'} (0)$ skew-symmetric by differentiating $Q (t)^{T} Q (t) = I_{r}$ . Conversely, for any skew-symmetric $Ω$ , the Cayley curve $Q (t) = (I_{r} - \frac{t}{2} Ω)^{- 1} (I_{r} + \frac{t}{2} Ω)$ is defined near zero, satisfies $Q (t)^{T} Q (t) = I_{r}$ , and has $Q (t) = I_{r} + t Ω + O (t^{2})$ ; hence the vertical tangent directions are exactly $X Ω$ . Every Stiefel tangent $Z$ decomposes as $Z = X Ω + (I - X X^{T}) Z$ , where $Ω = X^{T} Z$ is skew and the second term is horizontal. These summands are orthogonal, so the quotient tangent is represented uniquely by the horizontal summand.

3.1F1givenstep 2.2algebra∎

The matrix $(I - X X^{T}) G$ is horizontal. For every horizontal $Z$ , $⟨ G - (I - X X^{T}) G, Z ⟩_{F} = ⟨ X X^{T} G, Z ⟩_{F} = 0$ , since $X^{T} Z = 0$ . Therefore it is the quotient-metric projection. Under $X \mapsto X Q$ and $G \mapsto G Q$ it becomes $(I - X X^{T}) G Q$ , the same tangent vector in the changed representative.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Complex Stiefel and Grassmann tangent projections

Statement

For $X \in {St}_{C} (n, r)$ , as a real manifold, $T_{X} {St}_{C} (n, r) = {Z : X^{*} Z + Z^{*} X = 0}$ and $Π_{X}^{S t} (G) = G - X Herm (X^{*} G)$ . The complex Grassmann tangent has the unique horizontal representative $X^{*} Z = 0$ , and its quotient-metric projection is $Π_{X}^{G r} (G) = (I - X X^{*}) G$ .

Facts & Assumptions

Given: $1 \leq r \leq n$ , $X^{*} X = I_{r}$ , and the real Frobenius metrics of Complex Stiefel and Grassmann optimization conventions.

[F1]

The Stiefel frame set is the level set of $X \mapsto X^{*} X - I_{r}$ , and the Grassmann space is its quotient by the right unitary action (Complex Stiefel and Grassmann optimization conventions).

[F2]

The tangent of a regular level set is the kernel of the level-map differential (The tangent space of a regular level set is the kernel).

[F3]

The complex Grassmann quotient has graph charts, and its frame bundle has right unitary fibers (Stiefel spaces, Grassmannians, and tautological bundles).

Proof

technique · differentiate the Hermitian constraint and orthogonally decompose into vertical, horizontal, and normal components

1.1F1F2givenalgebra

Regard the Hermitian $r \times r$ matrices as a real vector space. The derivative of $F (X) = X^{*} X - I_{r}$ is $D F_{X} [Z] = X^{*} Z + Z^{*} X$ . It is onto that space: for any Hermitian $H$ , $Z = X H / 2$ gives $D F_{X} [Z] = H$ . Hence the level is regular, and [F2] gives the displayed tangent kernel.

2.1givenstep 1.1algebra

Set $S = Herm (X^{*} G)$ . Then $X^{*} (G - X S) + (G - X S)^{*} X = 0$ , so $G - X S$ is tangent. For tangent $Z$ , put $K = X^{*} Z$ , which is skew-Hermitian. For Hermitian $S$ , $\overline{tr (S K)} = - tr (S K)$ by adjoint and cyclic-trace identities; thus $Re tr (S K) = 0$ . Therefore $X S$ is normal in the real Frobenius metric, and the stated formula is the Stiefel orthogonal projection.

2.2F1F3givenstep 1.1algebra

A curve $Q (t)$ in $U (r)$ through $I_{r}$ has $Ω = Q^{'} (0)$ skew-Hermitian by differentiating $Q (t)^{*} Q (t) = I_{r}$ . Conversely, for any skew-Hermitian $Ω$ , the Cayley curve $Q (t) = (I_{r} - \frac{t}{2} Ω)^{- 1} (I_{r} + \frac{t}{2} Ω)$ is defined near zero, satisfies $Q (t)^{*} Q (t) = I_{r}$ , and has $Q (t) = I_{r} + t Ω + O (t^{2})$ ; hence the vertical tangent directions are exactly $X Ω$ . Every Stiefel tangent decomposes as $Z = X Ω + (I - X X^{*}) Z$ with $Ω = X^{*} Z$ . The second summand is horizontal. For any vertical $X Ω$ and horizontal $W$ , $⟨ X Ω, W ⟩_{R} = Re tr (Ω^{*} X^{*} W) = 0$ , so the summands are orthogonal. The decomposition is unique, and the graph-chart quotient identifies its horizontal component with the quotient tangent.

3.1F1givenstep 2.2algebra∎

The matrix $(I - X X^{*}) G$ is horizontal. For every horizontal $Z$ , $⟨ G - (I - X X^{*}) G, Z ⟩_{R} = Re tr ((X X^{*} G)^{*} Z) = Re tr (G^{*} X X^{*} Z) = 0$ since $X^{*} Z = 0$ . Thus it is the horizontal orthogonal projection. Under $(X, G) \mapsto (X Q, G Q)$ for unitary $Q$ , it transforms to $(I - X X^{*}) G Q$ , the same tangent vector in the changed frame.

PropositionStatement: Literature-sourcedProof: AI-generatedOpen item page →

Projected Euclidean gradients are the Stiefel and Grassmann gradients

Statement

Let $F$ be smooth on an open neighborhood of $St (n, r)$ , and write $G = \nabla F (X)$ for its Euclidean gradient. Its restriction to Stiefel has Riemannian gradient $G - X sym (X^{T} G)$ . If $F (X Q) = F (X)$ for every $Q \in O (r)$ , it descends to a smooth Grassmann objective and its gradient has horizontal representative $(I - X X^{T}) G$ . In either metric, gradient zero is equivalent to a critical point of the restricted objective.

Facts & Assumptions

Given: $1 \leq r \leq n$ , a smooth ambient $F$ , $X \in St (n, r)$ , and, for the Grassmann conclusion, right-orthogonal invariance.

[F1]

The Frobenius projections to Stiefel and Grassmann tangent representatives are the formulas in Tangent spaces and Frobenius projections on Stiefel and Grassmann.

[F2]

A Riemannian gradient is the metric dual of the differential (The Riemannian gradient is the metric dual of the differential).

[F3]

Right multiplication by an orthogonal matrix changes the frame representative but not its subspace (Stiefel spaces, Grassmannians, and tautological bundles).

[F4]

The Jacobian definition gives the coordinate partial derivatives of $F$ as the entries of $G = \nabla F (X)$ (The Jacobian matrix of partial derivatives and the gradient in the scalar-valued case); for a smooth $F$ , its differential is linear and its value on a coordinate-basis matrix is the corresponding partial derivative.

[F5]

The Riemannian gradient vanishes exactly at critical points of a smooth function (The Riemannian gradient vanishes exactly at the critical points).

[F6]

The Frobenius pairing is the Euclidean coordinate inner product on matrix entries (The Euclidean inner product $⟨ x, y ⟩ = \sum_{k < n} x_{k} y_{k}$ on $R^{n}$ ).

Proof

technique · identify the metric dual by orthogonal projection

1.1F1F2F4F6givenalgebra

Let $E_{i j}$ be the coordinate-basis matrices. Smoothness of $F$ makes $d F_{X}$ linear, and by the definition in [F4], $d F_{X} [E_{i j}] = \partial_{i j} F (X) = G_{i j}$ . Expanding $Z = \sum_{i, j} Z_{i j} E_{i j}$ therefore gives $d F_{X} [Z] = \sum_{i, j} G_{i j} Z_{i j} = ⟨ G, Z ⟩_{F}$ . Restriction to Stiefel has this same differential on tangent vectors. By [F1], $Π_{X}^{S t} G$ is tangent and $G - Π_{X}^{S t} G$ is normal, hence $⟨ Π_{X}^{S t} G, Z ⟩_{F} = ⟨ G, Z ⟩_{F}$ . The metric-dual characterization [F2] proves the Stiefel formula.

1.2F3givenalgebra

Invariance and [F3] make $f ([X]) = F (X)$ well-defined. The graph charts for the quotient in [F3] provide smooth local frame sections; in each chart, $f$ is the composition of $F$ with such a section and is therefore smooth. For each skew-symmetric $Ω$ , the Cayley curve $Q (t) = (I_{r} - \frac{t}{2} Ω)^{- 1} (I_{r} + \frac{t}{2} Ω)$ satisfies $Q (t)^{T} Q (t) = I_{r}$ near zero by direct multiplication and has $Q (t) = I_{r} + t Ω + O (t^{2})$ . Invariance makes $F (X Q (t))$ constant, so $d F_{X} [X Ω] = 0$ for every vertical tangent; consequently the differential descends to horizontal representatives.

2.1F1F2F4F5F6givenstep 1.2∎

For a horizontal $Z$ , the descended differential is $⟨ G, Z ⟩_{F}$ by [F4] and [F6]. By [F1], $(I - X X^{T}) G$ is horizontal and its difference from $G$ is orthogonal to every horizontal $Z$ , so it is the metric dual on the quotient. [F5] gives the asserted equivalence between a zero gradient and criticality on each manifold.

DefinitionDefinition: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Polar retraction on the complex Grassmannian

Definition

For $X \in {St}_{C} (n, r)$ and horizontal $η \in T_{[X]} {Gr}_{C} (r, n)$ , so $X^{*} η = 0$ , define $R_{X}^{p o l} (η) = (X + η) ((X + η)^{*} (X + η))^{- 1 / 2}$ and $R_{[X]}^{p o l} (η) = range (R_{X}^{p o l} (η))$ . The inverse square root is the inverse of the unique positive-definite Hermitian square root. The horizontal condition gives $(X + η)^{*} (X + η) = I + η^{*} η ≻ 0$ , so this map is defined for every horizontal tangent vector, and its frame representative is unchanged as a Grassmann point when $(X, η)$ is replaced by $(X Q, η Q)$ with unitary $Q$ .

Facts & Assumptions

Given: $X \in {St}_{C} (n, r)$ and horizontal $η$ as in Complex Stiefel and Grassmann tangent projections.

[F1]

A horizontal representative satisfies $X^{*} η = 0$ (Complex Stiefel and Grassmann tangent projections).

[F2]

On a finite-dimensional real or complex inner-product space, a nonnegative operator has a unique nonnegative square root; for a positive-definite input its eigenvalues are the positive square roots of the input eigenvalues, so the root is positive definite and invertible (A non-negative operator has a unique non-negative square root).

[F3]

The complex Grassmannian is the quotient of complex orthonormal frames by right unitary changes of frame (Stiefel spaces, Grassmannians, and tautological bundles).

Proof

technique · verify full rank, orthonormality, and unitary equivariance of the polar formula

1.1F1F2givenalgebra

By [F1], $(X + η)^{*} (X + η) = I + η^{*} η$ . For every nonzero $v \in C^{r}$ , $v^{*} (I + η^{*} η) v = ∥ v ∥_{2}^{2} + ∥ η v ∥_{2}^{2} > 0$ , so the Gram matrix is Hermitian positive definite. Apply [F2] on $C^{r}$ : its unique nonnegative Hermitian square root has strictly positive eigenvalues and is invertible, which defines the inverse root in the formula.

2.1F2givenstep 1.1algebra

Write $C = (X + η)^{*} (X + η)$ and $Y = (X + η) C^{- 1 / 2}$ . Since $C^{- 1 / 2}$ is Hermitian and $C^{- 1 / 2} C C^{- 1 / 2} = I_{r}$ , we have $Y^{*} Y = I_{r}$ . Thus $Y$ is a complex orthonormal frame and its range is a point of the stated Grassmannian.

3.1F1F3step 2.1algebra∎

By the quotient convention [F3], frames related by a unitary matrix represent the same point. For unitary $Q$ , the Gram matrix of $(X Q, η Q)$ is $Q^{*} C Q$ . Uniqueness of the positive square root gives $(Q^{*} C Q)^{- 1 / 2} = Q^{*} C^{- 1 / 2} Q$ . Hence the resulting frame is $Y Q$ , with the same column space as $Y$ .

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The complex Grassmann polar map is a first-order retraction

Statement

The frame formula of Polar retraction on the complex Grassmannian is smooth on the horizontal tangent bundle, maps into ${St}_{C} (n, r)$ , fixes zero, and has frame differential $D R_{X}^{p o l} (0) [η] = η$ for horizontal $η$ . It is right-unitary equivariant, so its range map is representative-independent and has identity differential under the horizontal tangent identification. Thus it is a first-order retraction on ${Gr}_{C} (r, n)$ .

Facts & Assumptions

Given: $X \in {St}_{C} (n, r)$ and a horizontal tangent $η$ at $[X]$ .

[F1]

The polar frame and quotient maps are given by the Gram inverse-square-root formula (Polar retraction on the complex Grassmannian).

[F2]

The positive square root depends smoothly on real symmetric positive-definite matrices, by applying the real bundle theorem to the trivial Euclidean bundle over that open matrix domain (Positive-definite bundle endomorphisms have smooth positive square roots).

[F3]

Horizontal matrices are the representatives of the complex Grassmann tangent (Complex Stiefel and Grassmann tangent projections).

[F4]

The complex Grassmannian has local graph charts and frame fibers related by right unitary changes (Stiefel spaces, Grassmannians, and tautological bundles).

[F5]

The realification $ρ$ respects products and inverses, and matrix inversion preserves $C^{k}$ regularity on the nonvanishing-determinant domain (Complex Stiefel and Grassmann optimization conventions, Matrix inversion preserves $C^{k}$ regularity where the determinant is nonzero).

Proof

technique · differentiate the polar factor at zero and use unitary equivariance to descend to the quotient

1.1F1F2F5givenalgebra

The Gram matrix $C (X, η) = I + η^{*} η$ is Hermitian positive definite by [F1]. Its realification $ρ (C)$ is real symmetric because $ρ (C)^{T} = ρ (C^{*}) = ρ (C)$ , and positive definite because, for $z = x + i y$ , $(x, y)^{T} ρ (C) (x, y) = z^{*} C z > 0$ . The matrix $ρ (C^{1 / 2})$ is real symmetric by the same transpose identity, squares to $ρ (C)$ by [F5], and is positive definite by the same quadratic-form identity. Uniqueness of the positive square root and [F2] therefore make $C^{1 / 2}$ smooth in real coordinates. It stays invertible, so [F5] applied to its realification makes its inverse smooth for every finite $k$ , and that inverse is the realification of $C^{- 1 / 2}$ . The frame formula and its range are smooth.

1.2F1F2F3F5givenalgebra

Fix horizontal $η$ and set $Y (t) = (X + t η) (I + t^{2} η^{*} η)^{- 1 / 2}$ . The Gram factor has value $I$ at zero and derivative zero there because its argument is $I + t^{2} η^{*} η$ and the inverse-root map is smooth by [F2] and [F5]. The product rule gives $Y (0) = X$ and $Y^{'} (0) = η$ . By [F3], this is precisely identity on the quotient tangent.

2.1F1F3F4givenstep 1.2algebra∎

By [F4], the unitary-equivariant frame formula descends through the smooth Grassmann quotient. The definition's computation shows that replacing $(X, η)$ by $(X Q, η Q)$ changes $Y$ to $Y Q$ , leaving its range unchanged. Its identity differential from step 1.2 is therefore representative-independent.

PropositionStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Gradient of a unitary-invariant Hermitian projector energy

Statement

Let $1 \leq r \leq n$ , and let $E$ be real-valued and continuously differentiable on an open set of Hermitian $n \times n$ matrices containing the rank- $r$ orthogonal projectors. Suppose its real Frobenius gradient $K (P) = K (P)^{*}$ satisfies $D E (P) [H] = Re tr (K (P)^{*} H)$ for every Hermitian direction $H$ . Then $f ([X]) = E (X X^{*})$ is well-defined on ${Gr}_{C} (r, n)$ and has horizontal gradient $grad f ([X]) = 2 (I - X X^{*}) K (X X^{*}) X .$

Facts & Assumptions

Given: The real differentiable Hermitian-matrix functional and gradient in the Statement, and $X \in {St}_{C} (n, r)$ .

[F1]

The frame quotient is by the right unitary action, and complex matrix spaces use the real Frobenius pairing (Complex Stiefel and Grassmann optimization conventions).

[F2]

The horizontal tangent projection is $G \mapsto (I - X X^{*}) G$ (Complex Stiefel and Grassmann tangent projections).

[F3]

A Riemannian gradient is the metric dual of the differential (The Riemannian gradient is the metric dual of the differential).

[F4]

Complex Grassmann has local graph charts and frame representatives related by right unitary maps (Stiefel spaces, Grassmannians, and tautological bundles).

[F5]

The complex polar retraction has frame differential $D R_{X} (0) [Z] = Z$ for horizontal $Z$ (The complex Grassmann polar map is a first-order retraction).

Proof

technique · differentiate the projector map on horizontal directions, then project the ambient metric dual

1.1F1F4F5givenalgebra

For unitary $Q$ , $(X Q) (X Q)^{*} = X X^{*}$ , so $E (X X^{*})$ is independent of the representative. In the local graph charts [F4], it therefore defines a differentiable function $f$ on the quotient. Let $Y (t) = R_{X}^{p o l} (t Z)$ and $P (t) = Y (t) Y (t)^{*}$ . By [F5], $Y (0) = X$ and $Y^{'} (0) = Z$ , so differentiating gives $P (0) = P$ and $P^{'} (0) = Z X^{*} + X Z^{*}$ . Since $E$ is defined on an open neighborhood of $P$ , the chain rule gives the differential of $f$ along this Grassmann curve.

2.1F1F2F3givenstep 1.1algebra∎

Using $K = K^{*}$ , cyclicity of trace, and [F1], $d f_{[X]} [Z] = Re tr (K (Z X^{*} + X Z^{*})) = 2 Re tr ((K X)^{*} Z) = ⟨ 2 K X, Z ⟩_{R}$ . The horizontal metric dual is the projection of $2 K X$ . By [F2] it equals $2 (I - X X^{*}) K X$ , which is the claimed gradient by [F3].

DefinitionDefinition: Literature-sourcedProof: AI-generatedOpen item page →

QR and polar retractions on Stiefel and Grassmann

Definition

For $X \in St (n, r)$ and $η \in T_{X} St (n, r)$ , put $Y = X + η$ . On the domain where $Y$ has full column rank, let $qf (Y)$ be the $Q$ factor in the unique reduced QR factorization $Y = Q R$ with $R$ upper triangular and positive diagonal. Define the QR map by $R_{X}^{Q R} (η) = qf (X + η)$ . Define the polar map by $R_{X}^{p o l} (η) = (X + η) ((X + η)^{T} (X + η))^{- 1 / 2},$ where the exponent denotes the inverse of the unique positive-definite square root. For a Grassmann tangent at $[X]$ , use its unique horizontal representative $η$ satisfying $X^{T} η = 0$ and define the induced map by taking the output column space. Under $X \mapsto X Q$ , this representative changes to $η Q$ , so the input matrix changes to $(X + η) Q$ . The polar formula is right-equivariant: $R_{X Q}^{p o l} (η Q) = R_{X}^{p o l} (η) Q$ for every $Q \in O (r)$ .

These are defined only where the displayed input is full rank. In fact, for a Stiefel tangent $η$ , $X + η$ always has full column rank, since $∥ (X + η) v ∥_{2}^{2} = ∥ v ∥_{2}^{2} + ∥ η v ∥_{2}^{2}$ for every $v \in R^{r}$ .

Facts & Assumptions

Given: $X \in St (n, r)$ and $η \in T_{X} St (n, r)$ as in Tangent spaces and Frobenius projections on Stiefel and Grassmann.

[F1]

Gram–Schmidt orthonormalization gives an orthonormal basis from a linearly independent ordered family (Gram–Schmidt turns every finite independent list into an orthonormal list with the same successive spans).

[F2]

A real symmetric matrix has an orthonormal eigenbasis (Real spectral theorem: a self-adjoint endomorphism of a finite-dimensional real inner product space has an orthonormal eigenbasis).

[F3]

Every positive-definite self-adjoint bundle endomorphism has a unique smooth positive square root (Positive-definite bundle endomorphisms have smooth positive square roots).

[F4]

A reduced QR factorization writes a full-column-rank matrix as an orthonormal-column factor times an upper-triangular factor (Full, reduced, and column-pivoted computational QR factorisations).

[F5]

A tangent matrix satisfies $X^{T} η + η^{T} X = 0$ (Tangent spaces and Frobenius projections on Stiefel and Grassmann).

[F6]

A Grassmann tangent has a unique horizontal representative, and changing the frame from $X$ to $X Q$ changes it from $η$ to $η Q$ (Real Stiefel and Grassmann optimization conventions).

Proof

technique · verify the domains and orthonormality of both formulas

1.1F1F2F3F5givenalgebra

By [F5], tangency gives $X^{T} η + η^{T} X = 0$ . Therefore for $v \neq 0$ , $∥ (X + η) v ∥_{2}^{2} = ∥ v ∥_{2}^{2} + v^{T} (X^{T} η + η^{T} X) v + ∥ η v ∥_{2}^{2} = ∥ v ∥_{2}^{2} + ∥ η v ∥_{2}^{2} > 0.$ Thus $X + η$ has full column rank. More generally, for any full-rank $Y$ , $v^{T} Y^{T} Y v = ∥ Y v ∥_{2}^{2} > 0$ for $v \neq 0$ , so its Gram matrix is positive definite; [F1] supplies the QR factor, while [F2] diagonalizes the Gram matrix and [F3] supplies its positive square root and inverse.

2.1F1F2F3F4F6givenstep 1.1inductionalgebra∎

For full-column-rank $Y = [y_{1} \dots y_{r}]$ , its columns are linearly independent. Apply Gram–Schmidt [F1], writing $u_{j} = y_{j} - \sum_{i < j} (q_{i}^{T} y_{j}) q_{i}$ and $q_{j} = u_{j} / ∥ u_{j} ∥_{2}$ . The residuals are nonzero, so $Q = [q_{1} \dots q_{r}]$ has orthonormal columns. Set $R = Q^{T} Y$ . For $i > j$ , $q_{i}$ is orthogonal to $span (y_{1}, \dots, y_{j})$ , so $R_{i j} = 0$ ; and $R_{j j} = q_{j}^{T} y_{j} = ∥ u_{j} ∥_{2} > 0$ . Since each $y_{j}$ lies in $span (q_{1}, \dots, q_{j})$ , $Q R = Y$ . This constructs a reduced QR factorization with positive diagonal. To check uniqueness, if $Y = Q_{1} R_{1} = Q_{2} R_{2}$ are two such factorizations, then $Q_{2}^{T} Q_{1} = R_{2} R_{1}^{- 1}$ is orthogonal and upper triangular with positive diagonal. Its first column has only its first entry, which must be $1$ by unit norm and positivity; orthogonality zeros the rest of its first row. Induction on the remaining block makes it $I_{r}$ , so $Q_{1} = Q_{2}$ and $R_{1} = R_{2}$ . For the polar factor $U = Y (Y^{T} Y)^{- 1 / 2}$ , symmetry of the root and its defining square give $U^{T} U = (Y^{T} Y)^{- 1 / 2} (Y^{T} Y) (Y^{T} Y)^{- 1 / 2} = I_{r}$ . Hence both outputs have orthonormal columns. For a Grassmann input, [F6] says a frame change $X \mapsto X Q_{0}$ changes $η$ to $η Q_{0}$ , so the input $Y = X + η$ becomes $Y Q_{0}$ with the same column space; uniqueness of the positive root gives $(Q_{0}^{T} Y^{T} Y Q_{0})^{- 1 / 2} = Q_{0}^{T} (Y^{T} Y)^{- 1 / 2} Q_{0}$ , so the polar output is multiplied by $Q_{0}$ . Thus the Grassmann outputs are well-defined.

Remark

The formulas here are exact-arithmetic definitions. The finite-precision Householder QR supplier proves a backward-error statement under its operationwise assumptions and does not assert that a computed $Q$ is exactly orthogonal (The scaled Householder QR implementation is backward stable). No floating-point retraction guarantee is claimed by this page.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

The QR and polar maps are first-order Stiefel and Grassmann retractions

Statement

On the full-column-rank domains of QR and polar retractions on Stiefel and Grassmann, the positive-diagonal QR and polar maps are smooth, take values in $St (n, r)$ , fix $η = 0$ , and have differential $D R_{X} (0) [η] = η$ . Their induced Grassmann maps are independent of the representative and have identity differential under the horizontal tangent identification. Thus they are first-order retractions. This theorem makes no second-order claim; in particular, the QR map need not be second order.

Facts & Assumptions

Given: $X \in St (n, r)$ , the full-rank formulas of QR and polar retractions on Stiefel and Grassmann, and $η \in T_{X} St (n, r)$ .

[F1]

The retraction maps are the positive-diagonal QR factor and the polar factor of $X + η$ (QR and polar retractions on Stiefel and Grassmann).

[F2]

Tangency is characterized by $X^{T} η + η^{T} X = 0$ (Tangent spaces and Frobenius projections on Stiefel and Grassmann).

[F3]

Gram–Schmidt constructs an orthonormal basis on the full-rank domain (Gram–Schmidt turns every finite independent list into an orthonormal list with the same successive spans).

[F4]

The positive square root depends smoothly on a positive-definite matrix (Positive-definite bundle endomorphisms have smooth positive square roots).

[F5]

Matrix inversion preserves $C^{k}$ regularity on the nonvanishing-determinant domain (Matrix inversion preserves $C^{k}$ regularity where the determinant is nonzero).

Proof

technique · differentiate each matrix factorization at the zero tangent vector

1.1F1F3F4F5given

On the full-rank set, the Gram–Schmidt recurrences divide only by positive residual norms, so [F3] expresses the QR factors by smooth additions, products, divisions by nonzero functions, and positive square roots. The polar formula is smooth there by [F4], [F5] applied to its positive-definite Gram matrix, and smooth matrix multiplication. Both maps land in Stiefel by [F1]. At $η = 0$ , the factorizations are $X = X I_{r}$ , so each map returns $X$ .

1.2F1F2F4F5givenalgebra

For the polar map, $Y (t)^{T} Y (t) = I_{r} + t^{2} η^{T} η$ by [F2]. Its inverse square root equals $I_{r} + O (t^{2})$ by smoothness in [F4] and [F5] and its value $I_{r}$ at $I_{r}$ . Consequently $R_{X}^{p o l} (t η) = X + t η + O (t^{2})$ , so its derivative at zero is $η$ .

2.1F1F2step 1.1algebra

Set $Y (t) = X + t η$ and write its positive-diagonal QR factorization as $Y (t) = Q (t) R (t)$ . By step 1.1, $Q, R$ are differentiable near zero; $Q (0) = X$ , $R (0) = I_{r}$ . Put $W = Q^{'} (0)$ and $U = R^{'} (0)$ , so $η = W + X U$ and $U$ is upper triangular. Differentiating $Q (t)^{T} Q (t) = I_{r}$ shows $X^{T} W$ is skew-symmetric. By [F2], $X^{T} η$ is skew-symmetric; hence $U = X^{T} η - X^{T} W$ is skew-symmetric as well. A real matrix both upper triangular and skew-symmetric is zero, so $U = 0$ and $W = η$ .

3.1F1step 2.1step 1.2algebra∎

Under $(X, η) \mapsto (X Q_{0}, η Q_{0})$ , the inputs $X + η$ and $(X + η) Q_{0}$ have the same column space. Their QR outputs may differ as frames, but induce the same Grassmann point; the polar output transforms by $Q_{0}$ . Differentiating the induced maps therefore gives the same horizontal class of $η$ , which is the identity on the quotient tangent space.

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-budget retraction Armijo backtracking

Definition

Let $M$ be $St (n, r)$ or $Gr (r, n)$ , let $f : M \to R$ be smooth, and choose one retraction $R$ from QR and polar retractions on Stiefel and Grassmann. At $x \in M$ , let $g = grad f (x)$ . Fix $a \in (0, 1)$ , $β \in (0, 1)$ and an integer budget $J \geq 0$ .

If $g = 0$ , return (x, stationary). Otherwise test, in order, $t_{j} = β^{j}$ for $j = 0, \dots, J$ . At each trial form $y_{j} = R_{x} (- t_{j} g)$ ; if the chosen retraction's full-rank condition fails, reject that trial without evaluating $f (y_{j})$ . Otherwise accept and return $(y_{j}, t_{j})$ at the first index with $f (y_{j}) \leq f (x) - a t_{j} ∥ g ∥^{2} .$ If no trial passes, return (x, budget-exhausted).

AlgorithmAlgorithm: Literature-sourcedProof: Not applicableOpen item page →

Finite-budget Riemannian trust-region method

Definition

Let $1 \leq r \leq n$ . Let $M$ be a real Stiefel manifold $St (n, r)$ , a real Grassmannian $Gr (r, n)$ , or a complex Grassmannian ${Gr}_{C} (r, n)$ , with each tangent space regarded as a real inner-product space under the corresponding Frobenius metric. On a real Stiefel manifold or real Grassmannian choose the induced map of either the real QR or real polar formula from QR and polar retractions on Stiefel and Grassmann; on a complex Grassmannian choose the complex polar map from Polar retraction on the complex Grassmannian. Denote the chosen map by $R$ . Let $f : M \to R$ be of class $C^{2}$ and take an initial point $x_{0} \in M$ . For this regularity, $grad f (x)$ denotes the pointwise metric dual of $d f_{x}$ : in any orthonormal real basis $e_{i}$ of $T_{x} M$ , it is $\sum_{i} d f_{x} (e_{i}) e_{i}$ (the empty sum is zero). This convention agrees with The Riemannian gradient is the metric dual of the differential when $f$ is smooth; no infinitely differentiable gradient field is required.

Fix $0 < η_{1} < η_{2} < 1$ , $0 < γ_{d e c} < 1 < γ_{i n c}$ , $0 < θ_{C} \leq 1$ , a declared model-operator bound $M_{B} \geq 0$ , a maximum radius $Δ_{\max} > 0$ , an initial radius $0 < Δ_{0} \leq Δ_{\max}$ , target $ε \geq 0$ , and finite outer cap $N \in N_{0}$ . Supply as input a rule that evaluates a family $x \mapsto B_{x}$ of self-adjoint real-linear operators $B_{x} : T_{x} M \to T_{x} M$ at each visited point. On a Grassmannian, represent this intrinsic operator on the current horizontal space, consistently under changes of frame. Require $∥ B_{x} ∥_{o p} \leq M_{B}$ for every $x \in M$ , where $∥ B_{x} ∥_{o p} : = \sup_{s \neq 0} \frac{∥ B_{x} s ∥}{∥ s ∥},$ with $∥ B_{x} ∥_{o p} = 0$ when the tangent space is ${0}$ . Supply a subproblem routine $S$ with a finite operation cap $J_{S} \in N_{0}$ ; on input of the current model $m_{k}$ , radius $Δ_{k}$ , and tangent or horizontal space, it terminates within that cap and returns either a vector in that space or failure. No quality guarantee is required because the returned vector is checked below.

Starting with $x_{0}$ and $Δ_{0}$ , process $k = 0, \dots, N$ in order:

Set $g_{k} = grad f (x_{k})$ . Return $(x_{k}, stationary)$ if $g_{k} = 0$ , $(x_{k}, target-achieved)$ if $∥ g_{k} ∥ \leq ε$ , and $(x_{k}, outer-budget-exhausted)$ if $k = N$ .
Form the real pullback quadratic model $m_{k} (s) = f (x_{k}) + ⟨ g_{k}, s ⟩ + \frac{1}{2} ⟨ s, B_{x_{k}} s ⟩ .$ With $c_{k} = ⟨ g_{k}, B_{x_{k}} g_{k} ⟩$ , set $τ_{k} = {\begin{cases} Δ_{k} / ∥ g_{k} ∥, & c_{k} \leq 0, \\ \min {∥ g_{k} ∥^{2} / c_{k}, Δ_{k} / ∥ g_{k} ∥}, & c_{k} > 0, \end{cases} p_{C} = - τ_{k} g_{k},$ and set $P_{C} = m_{k} (0) - m_{k} (p_{C})$ .
Call $S$ on $(m_{k}, Δ_{k})$ in the current tangent or horizontal space. If it returned a vector $q$ with $∥ q ∥ \leq Δ_{k}$ and $m_{k} (0) - m_{k} (q) \geq θ_{C} P_{C}$ , set $p_{k} = q$ ; otherwise set $p_{k} = p_{C}$ . If $Δ_{k} \leq ∥ g_{k} ∥ / (2 M_{B})$ , replace the candidate by $p_{k} = p_{C}$ , interpreting that threshold as $+ \infty$ when $M_{B} = 0$ . Set $P_{k} = m_{k} (0) - m_{k} (p_{k})$ .
If $P_{k} \leq 0$ , return $(x_{k}, model-evaluation-failure)$ . Otherwise evaluate $y_{k} = R_{x_{k}} (p_{k})$ ; if the selected retraction is unavailable, return $(x_{k}, model-evaluation-failure)$ . If $f (y_{k})$ cannot be evaluated, return the same status. Otherwise set $ρ_{k} = (f (x_{k}) - f (y_{k})) / P_{k}$ .
If $ρ_{k} < η_{1}$ , reject and set $(x_{k + 1}, Δ_{k + 1}) = (x_{k}, γ_{d e c} Δ_{k})$ . Otherwise accept and set $x_{k + 1} = y_{k}$ . If also $ρ_{k} \geq η_{2}$ and $∥ p_{k} ∥ = Δ_{k}$ , set $Δ_{k + 1} = \min {γ_{i n c} Δ_{k}, Δ_{\max}}$ ; in every other accepted case set $Δ_{k + 1} = Δ_{k}$ .

Return the last accepted point with the corresponding stop status. A failed finite subproblem call, infeasible candidate, or candidate that misses the fraction-of-Cauchy test uses $p_{C}$ .

DefinitionDefinition: Literature-sourcedProof: AI-generatedOpen item page →

Projected vector transport on Stiefel and Grassmann

Definition

Let $X$ be a source frame, $η \in T_{X} St (n, r)$ , and $Z \in T_{X} St (n, r)$ . For Stiefel transport let $Y = R_{X} (η)$ be either the QR or polar endpoint. For Grassmann transport, require $η$ to be the unique horizontal representative at $[X]$ , so $X^{T} η = 0$ , and choose $Y = R_{X}^{p o l} (η)$ , the polar endpoint; the positive-diagonal QR frame is not used for this representative-based quotient transport. Define the projected Stiefel transport $T_{Y}^{S t} (Z) : = Z - Y sym (Y^{T} Z),$ and, for a horizontal source representative $Z$ , define the projected Grassmann transport representative $T_{Y}^{G r} (Z) : = (I - Y Y^{T}) Z .$ The Grassmann expression is interpreted as a tangent representative at $[Y]$ . The polar endpoint is right-equivariant, so the next proposition verifies representative independence, tangency, and identity at a zero step. These projection transports are not claimed to be Levi-Civita parallel transport.

Facts & Assumptions

Given: $X \in St (n, r)$ , a tangent step $η$ (horizontal in the Grassmann branch), its Stiefel endpoint $Y = R_{X} (η)$ or its Grassmann polar endpoint $Y = R_{X}^{p o l} (η)$ , and a source tangent (or horizontal) representative $Z$ .

[F1]

The Stiefel and horizontal projections at a frame $Y$ are the formulas in Tangent spaces and Frobenius projections on Stiefel and Grassmann.

[F2]

QR and polar endpoints are orthonormal frames, and the polar endpoint transforms as $R_{X Q}^{p o l} (η Q) = R_{X}^{p o l} (η) Q$ (QR and polar retractions on Stiefel and Grassmann).

[F3]

Both retractions fix the zero tangent vector (The QR and polar maps are first-order Stiefel and Grassmann retractions).

Proof

technique · identify each formula as the corresponding orthogonal projection

1.1F1F2given

The first displayed map is exactly the Stiefel tangent projection from [F1], and the second is exactly the horizontal Grassmann projection from [F1]. By [F2], the endpoint is a valid frame; each formula is linear in $Z$ and takes values in the stated destination tangent space.

2.1F1F2F3givenalgebra∎

Under a change $(X, η, Z) \mapsto (X Q, η Q, Z Q)$ , [F2] gives the polar endpoint $Y Q$ ; hence $I - (Y Q) (Y Q)^{T} = I - Y Y^{T}$ and the output changes to $V Q$ . This is exactly the changed horizontal representative, so the Grassmann tangent vector is independent of the frame. At $η = 0$ , [F3] gives $Y = X$ ; a Stiefel tangent has $sym (X^{T} Z) = 0$ , and a Grassmann horizontal representative has $X^{T} Z = 0$ , so both transports return $Z$ .

LemmaStatement: Literature-sourcedProof: AI-generatedOpen item page →

Retraction trust-region ratios are accurate at small radii

Statement

Let $M$ be a finite-dimensional real Stiefel or Grassmann manifold, or a complex Grassmannian, with its real Frobenius metric. Regard every tangent space as real, let $x \in M$ , and let $g = grad f (x) \neq 0$ . Choose a first-order retraction $R$ and write ${\hat{f}}_{x} (s) = f (R_{x} (s))$ on the tangent (or horizontal) space, equipped with its real Frobenius inner product. Suppose $\nabla {\hat{f}}_{x}$ is $L_{R}$ -Lipschitz on the ball $∥ s ∥ \leq Δ$ for $Δ > 0$ , and let $m_{x} (s) = f (x) + ⟨ g, s ⟩ + \frac{1}{2} ⟨ s, B_{x} s ⟩$ with $B_{x}$ self-adjoint and real-linear. Define its induced operator norm by $∥ B_{x} ∥_{o p} : = \sup_{s \neq 0} \frac{∥ B_{x} s ∥}{∥ s ∥},$ and assume $∥ B_{x} ∥_{o p} \leq M_{B}$ . Let $p_{C}$ be the negative-gradient Cauchy step, and let a feasible trial $p$ satisfy $m_{x} (0) - m_{x} (p) \geq θ_{C} [m_{x} (0) - m_{x} (p_{C})]$ for $0 < θ_{C} \leq 1$ . With a zero denominator interpreted as $+ \infty$ , if $Δ \leq ∥ g ∥ / (2 M_{B})$ , then its predicted decrease $P$ is positive and $∣ ρ - 1 ∣ \leq \frac{2 (L_{R} + M_{B}) Δ}{θ_{C} ∥ g ∥}, ρ = \frac{f (x) - f (R_{x} (p))}{P} .$ Consequently, for $0 < η_{2} < 1$ , if $Δ \leq \min {\frac{∥ g ∥}{2 M_{B}}, \frac{θ_{C} (1 - η_{2}) ∥ g ∥}{2 (L_{R} + M_{B})}},$ then $ρ \geq η_{2}$ . If $L_{R} + M_{B} = 0$ , the ratio equals $1$ .

Facts & Assumptions

Given: The $C^{2}$ pullback, gradient Lipschitz bound, self-adjoint model operator and norm bound, Cauchy-fraction condition, and small-radius safeguard in the Statement.

[F1]

A first-order real Stiefel/Grassmann or complex Grassmann retraction satisfies $D R_{x} (0) [s] = s$ (The QR and polar maps are first-order Stiefel and Grassmann retractions, The complex Grassmann polar map is a first-order retraction).

[F2]

The Riemannian trust-region step is feasible, has predicted decrease at least $θ_{C}$ times Cauchy decrease, and uses the Cauchy step when $Δ \leq ∥ g ∥ / (2 M_{B})$ (Finite-budget Riemannian trust-region method).

[F3]

The negative-gradient Cauchy step is the segment minimizer with the formula stated in The Cauchy step for a quadratic trust-region model.

[F4]

In orthonormal real coordinates on the finite-dimensional tangent or horizontal space, the operator $B_{x}$ has a symmetric matrix with Euclidean induced norm $∥ B_{x} ∥_{o p}$ , so the Cauchy decrease estimate gives at least $\frac{1}{2} ∥ g ∥ \min {Δ, ∥ g ∥ / ∥ B_{x} ∥_{o p}}$ , with the zero-operator convention (The Cauchy step gives a quantitative model decrease).

[F5]

The matrix norm is compatible with the vector norm and the Euclidean inner product satisfies Cauchy–Schwarz (Induced matrix norms are compatible with matrix-vector multiplication, submultiplicative, and satisfy ||I|| = 1, Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

[F6]

A scalar function continuous on a closed interval and differentiable in its interior has an interior point where its derivative is the endpoint slope (The mean value theorem, as the case $g (x) = x$ of Cauchy's: for $f$ continuous on $[a, b]$ with $a < b$ and differentiable on $(a, b)$ there is $c \in (a, b)$ with $f (b) - f (a) = f^{'} (c) (b - a)$ ).

Proof

technique · lower-bound the model decrease and compare pullback actual decrease with its quadratic model

1.1F3F5givencasesalgebra

Write $a = ∥ g ∥ > 0$ and $c = ⟨ g, B_{x} g ⟩$ . The operator norm bound and Cauchy–Schwarz in [F5] give $c \leq ∣ c ∣ \leq a ∥ B_{x} g ∥ \leq M_{B} a^{2}$ . If $c \leq 0$ , [F3] gives a boundary Cauchy step. If $c > 0$ , then $M_{B} > 0$ , the unconstrained segment minimizer has length $a^{3} / c \geq a / M_{B}$ , and $Δ \leq a / (2 M_{B})$ forces the constrained minimizer to the boundary. Thus $∥ p_{C} ∥ = Δ$ in both branches, including $M_{B} = 0$ .

2.1F2F4givenstep 1.1choosealgebra

Choose orthonormal real coordinates on the finite-dimensional tangent or horizontal space. In these coordinates [F4] applies, and $∥ B_{x} ∥_{2} = ∥ B_{x} ∥_{o p}$ . Since $∥ B_{x} ∥_{o p} \leq M_{B}$ and step 1.1 gives $∥ p_{C} ∥ = Δ$ , the Cauchy decrease is at least $\frac{1}{2} a Δ$ . The trial condition and [F2] therefore give $P = m_{x} (0) - m_{x} (p) \geq \frac{1}{2} θ_{C} a Δ > 0$ . This verifies that $ρ$ is defined.

3.1F1F2F5F6givenstep 2.1algebra∎

Put $ϕ (t) = {\hat{f}}_{x} (t p)$ and $h (t) = ϕ (t) - ϕ (0) - t ϕ^{'} (0)$ . By [F1], $ϕ^{'} (0) = ⟨ g, p ⟩$ . Lipschitz continuity and [F5] give $∣ h^{'} (t) ∣ \leq L_{R} t ∥ p ∥^{2} \leq L_{R} ∥ p ∥^{2}$ for $0 \leq t \leq 1$ . Apply [F6] on $[0, 1]$ to obtain $∣ h (1) ∣ \leq L_{R} ∥ p ∥^{2}$ . The quadratic model contributes at most $\frac{1}{2} M_{B} ∥ p ∥^{2}$ beyond the linear term, so $∣ f (x) - f (R_{x} (p)) - P ∣ \leq (L_{R} + M_{B}) ∥ p ∥^{2} .$ Since $∥ p ∥ \leq Δ$ , step 2.1 gives $∣ ρ - 1 ∣ \leq \frac{(L_{R} + M_{B}) Δ^{2}}{θ_{C} a Δ / 2} = \frac{2 (L_{R} + M_{B}) Δ}{θ_{C} a} .$ If $L_{R} + M_{B} = 0$ , the numerator error is zero and $ρ = 1$ . Otherwise the stated radius threshold makes $∣ ρ - 1 ∣ \leq 1 - η_{2}$ , hence $ρ \geq η_{2}$ .

PropositionStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Projected vector transports return tangent representatives

Statement

For every retraction step $η$ at $X$ , the maps Projected vector transport on Stiefel and Grassmann are smooth linear maps in the source tangent vector and take values in the endpoint tangent spaces; at $η = 0$ both return the input tangent representative. The Grassmann map is representative-independent under $(X, η, Z) \mapsto (X Q, η Q, Z Q)$ .

Facts & Assumptions

Given: A source frame $X$ , tangent step $η$ , its Stiefel endpoint or polar Grassmann endpoint $Y$ , and a source tangent or horizontal representative $Z$ .

[F1]

The projected transport formulas are those in Projected vector transport on Stiefel and Grassmann.

[F2]

The tangent spaces at $Y$ are characterized by the Stiefel and horizontal equations in Tangent spaces and Frobenius projections on Stiefel and Grassmann.

[F3]

The retraction maps fix the zero tangent vector (The QR and polar maps are first-order Stiefel and Grassmann retractions).

[F4]

QR and polar endpoints are frames, and the polar endpoint is right-equivariant (Projected vector transport on Stiefel and Grassmann).

Proof

technique · substitute the projected formulas into the tangent equations

1.1F1F2F3F4givenalgebra

Put $S = sym (Y^{T} Z)$ and $W = Z - Y S$ . Then $Y^{T} W = Y^{T} Z - S$ is skew-symmetric, so $Y^{T} W + W^{T} Y = 0$ . By [F2], $W$ is a Stiefel tangent. The projection formulas are linear in $Z$ and smooth in $Y$ ; [F3] makes their composition with the retraction smooth in $η$ .

1.2F1F2F4givenalgebra

The Grassmann output $V = (I - Y Y^{T}) Z$ satisfies $Y^{T} V = 0$ , so it is horizontal by [F2], and it depends linearly on $Z$ . Under $(X, η, Z) \mapsto (X Q, η Q, Z Q)$ , [F4] makes the polar endpoint $Y$ change to $Y Q$ . Then $I - (Y Q) (Y Q)^{T} = I - Y Y^{T}$ and the output changes to $V Q$ , exactly the changed horizontal representative. This proves independence of the represented tangent vector.

2.1F1F2F3givenalgebra∎

At $η = 0$ , [F3] gives $Y = X$ . If $Z$ is Stiefel tangent at $X$ , $X^{T} Z$ is skew-symmetric, so $sym (X^{T} Z) = 0$ and the Stiefel transport returns $Z$ . If $Z$ is horizontal, $X^{T} Z = 0$ and $(I - X X^{T}) Z = Z$ . Thus both transports are identity at the zero step, completing the vector-transport conditions.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Uniform pullback smoothness guarantees an Armijo step

Statement

Let $M = St (n, r)$ or $Gr (r, n)$ be compact, let $f : M \to R$ be smooth, and let $R$ be a QR or polar retraction with the first-order property of The QR and polar maps are first-order Stiefel and Grassmann retractions. Write ${\hat{f}}_{x} (η) = f (R_{x} (η))$ . Assume a uniform bound $∥ grad f (x) ∥ \leq G$ and a constant $L_{R} \geq 0$ such that, for every $x$ and $∥ η ∥ \leq 1$ , $∥ grad {\hat{f}}_{x} (η) - grad {\hat{f}}_{x} (0) ∥ \leq L_{R} ∥ η ∥ .$ For $a \in (0, 1)$ and a nonstationary iterate, set $δ = \min {1, (2 G)^{- 1}, 2 (1 - a) / L_{R}},$ where a reciprocal of zero is interpreted as $+ \infty$ . If the finite backtracking budget tests some $t_{j} = β^{j} \leq δ$ , then it accepts a step; the first accepted step obeys $t \geq β δ$ . For $0 < t \leq δ$ , the bound $t ∥ grad f (x) ∥ \leq 1 / 2$ keeps the pullback argument inside its assumed unit tangent ball; an earlier accepted trial may be larger.

Facts & Assumptions

Given: The compact manifold, smooth objective, first-order retraction, constants $G, L_{R}, a, β$ , and finite budget reaching $δ$ .

[F1]

The retraction pullback has derivative at zero equal to the original tangent direction (The QR and polar maps are first-order Stiefel and Grassmann retractions).

[F2]

The Riemannian gradient represents the differential in the chosen metric (The Riemannian gradient is the metric dual of the differential).

[F3]

The finite Armijo search tests $t_{j} = β^{j}$ and accepts only the sufficient-decrease inequality (Finite-budget retraction Armijo backtracking).

[F4]

The Euclidean inner product obeys Cauchy–Schwarz (Cauchy-Schwarz $∣ ⟨ x, y ⟩ ∣ \leq ∥ x ∥_{2} ∥ y ∥_{2}$ with its equality case, the triangle inequality for $∥ \cdot ∥_{2}$ , the parallelogram law and polarisation).

Proof

technique · integrate the Lipschitz pullback-gradient bound along the negative-gradient segment

1.1givenalgebra

Since $g \neq 0$ and $∥ g ∥ \leq G$ , we have $G > 0$ . For $0 < t \leq δ$ , $η = - t g$ has norm $t ∥ g ∥ \leq t G \leq 1 / 2$ , so the entire segment $s η$ , $0 \leq s \leq 1$ , lies in the unit ball.

2.1F1F2F3F4givenstep 1.1algebra

By [F1] and [F2], $D {\hat{f}}_{x} (0) [η] = ⟨ g, η ⟩ = - t ∥ g ∥^{2}$ . The fundamental theorem of calculus along $s \mapsto s η$ and the assumed Lipschitz bound give ${\hat{f}}_{x} (η) \leq f (x) - t ∥ g ∥^{2} + \int_{0}^{1} L_{R} s ∥ η ∥^{2} d s = f (x) - t ∥ g ∥^{2} + \frac{1}{2} L_{R} t^{2} ∥ g ∥^{2} .$ The integral bound uses [F4] to estimate the inner product of the gradient difference with $η$ . If $L_{R} = 0$ the last error is zero; otherwise $t \leq 2 (1 - a) / L_{R}$ makes the right side at most $f (x) - a t ∥ g ∥^{2}$ . Thus every tested $t \leq δ$ satisfies the Armijo test in [F3].

3.1F3givenstep 2.1algebra∎

Let $j$ be the first tested index with $β^{j} \leq δ$ . By step 2.1 this trial passes, so the algorithm stops no later than $j$ . If $j = 0$ , then $t = 1 \geq β δ$ because $δ \leq 1$ . If $j > 0$ , minimality gives $β^{j - 1} > δ$ , hence $β^{j} > β δ$ . Any earlier accepted grid point is larger still.

TheoremStatement: Literature-sourcedProof: AI-generatedjudge pass (gpt-6-luna)Open item page →

Retraction Armijo reaches an epsilon-gradient iterate in finite budget

Statement

Under the hypotheses of Uniform pullback smoothness guarantees an Armijo step, assume $f$ is bounded below by $f_{\inf}$ and every nonstationary call's finite budget reaches the stated $δ$ . For $N \geq 1$ accepted updates $x_{0}, \dots, x_{N}$ , $\min_{0 \leq k < N} ∥ grad f (x_{k}) ∥^{2} \leq \frac{f (x_{0}) - f_{\inf}}{a β δ N} .$ In particular, for every $ϵ > 0$ , after more than $(f (x_{0}) - f_{\inf}) / (a β δ ϵ^{2})$ accepted updates, some iterate among the pre-update points has gradient norm at most $ϵ$ . The order is $O (ϵ^{- 2})$ with the displayed constants fixed. This counts accepted updates; it does not assert an evaluation bound independent of the finite backtracking budgets.

Facts & Assumptions

Given: The Armijo acceptance and step bound, lower bound $f_{\inf}$ , constants $a, β, δ > 0$ , and $N$ accepted updates.

[F1]

Every nonstationary call accepts a step $t_{k} \geq β δ$ (Uniform pullback smoothness guarantees an Armijo step).

[F2]

An accepted Armijo update satisfies $f (x_{k + 1}) \leq f (x_{k}) - a t_{k} ∥ grad f (x_{k}) ∥^{2}$ (Finite-budget retraction Armijo backtracking).

Proof

technique · telescope the sufficient decreases

1.1F1F2givenalgebra

For every accepted update, [F1] and [F2] imply $f (x_{k}) - f (x_{k + 1}) \geq a β δ ∥ grad f (x_{k}) ∥^{2}$ . Summing for $k = 0, \dots, N - 1$ telescopes to $a β δ \sum_{k = 0}^{N - 1} ∥ grad f (x_{k}) ∥^{2} \leq f (x_{0}) - f (x_{N}) \leq f (x_{0}) - f_{\inf} .$ At least one of the $N$ nonnegative terms is no greater than their average, giving the stated bound.

2.1step 1.1givencontradiction∎

If every pre-update gradient norm were greater than $ϵ$ , the sum in step 1.1 would exceed $N ϵ^{2}$ . This contradicts its upper bound whenever $N > (f (x_{0}) - f_{\inf}) / (a β δ ϵ^{2})$ , proving the finite accepted-update claim.

TheoremStatement: Literature-sourcedProof: AI-generatedOpen item page →

Riemannian trust regions reach an epsilon-gradient iterate

Statement

Let $1 \leq r \leq n$ , and let $M$ be a compact real Stiefel manifold $St (n, r)$ , a compact real Grassmannian $Gr (r, n)$ , or a compact complex Grassmannian ${Gr}_{C} (r, n)$ . Let $f : M \to R$ be of class $C^{2}$ and take $x_{0} \in M$ ; set $f_{\inf} = \min_{M} f$ , whose existence is proved below. Equip each tangent or horizontal space with its real Frobenius inner product. For each self-adjoint real-linear model operator $B_{x}$ , define $∥ B_{x} ∥_{o p} : = \sup_{s \neq 0} \frac{∥ B_{x} s ∥}{∥ s ∥},$ with value $0$ on a zero tangent space, and assume $∥ B_{x} ∥_{o p} \leq M_{B}$ for some $M_{B} \geq 0$ . Assume the pullback gradients of the chosen first-order retraction are uniformly $L_{R}$ -Lipschitz on every trial ball of radius at most $Δ_{\max}$ , for some $L_{R} \geq 0$ . Run Finite-budget Riemannian trust-region method with fixed $0 < η_{1} < η_{2} < 1$ , $0 < γ_{d e c} < 1 < γ_{i n c}$ , $0 < θ_{C} \leq 1$ , $0 < Δ_{0} \leq Δ_{\max}$ , and target $0 < ε \leq 1$ . Assume every model and objective evaluation on a valid trial is available. The counts concern the uncapped trial sequence up to its first target iterate; for the finite-cap implementation, choose an outer cap at least the resulting total-trial bound.

Using $+ \infty$ for reciprocals of zero, define $c_{δ} = \min {\frac{1}{2 M_{B}}, \frac{θ_{C} (1 - η_{2})}{2 (L_{R} + M_{B})}}, c_{R} = \min {Δ_{0}, γ_{d e c} \min {c_{δ}, Δ_{\max}}},$ $c_{P} = \min {c_{R}, 1 / M_{B}}, c_{S} = \frac{1}{2} η_{1} θ_{C} c_{P} > 0, r_{ε} = \min {Δ_{0}, γ_{d e c} \min {c_{δ} ε, Δ_{\max}}} .$ Then the number $N_{s}$ of accepted steps and $N_{u}$ of rejected trials before the first iterate with $∥ grad f (x_{k}) ∥ \leq ε$ obey $N_{s} \leq \frac{f (x_{0}) - f_{\inf}}{c_{S} ε^{2}}, N_{u} \leq \frac{\log (Δ_{0} / r_{ε}) + N_{s} \log γ_{i n c}}{∣ \log γ_{d e c} ∣} .$ Consequently accepted steps and total trials $N_{s} + N_{u}$ are $O (ε^{- 2})$ as $ε ↓ 0$ , with all displayed constants fixed. Such a finite cap suffices to return either stationary or target-achieved status, in both cases with gradient norm at most $ε$ ; a smaller cap may return outer-budget-exhausted first. The constants and proof count accepted and rejected outer trials; they do not bound inner subproblem operations.

Facts & Assumptions

Given: Compact search manifold, $C^{2}$ objective with the pointwise gradient convention of Finite-budget Riemannian trust-region method, uniform pullback-gradient Lipschitz and self-adjoint real-linear model-operator bounds, and the trust-region parameter ranges and subproblem safeguards in the Statement.

[F1]

The finite-budget Riemannian method uses the $η_{1}, η_{2}$ ratio thresholds, $γ_{d e c}, γ_{i n c}$ radius branches, and the $θ_{C}$ Cauchy-decrease safeguard (Finite-budget Riemannian trust-region method).

[F2]

At sufficiently small radius, the pullback actual-to-predicted ratio is at least $η_{2}$ (Retraction trust-region ratios are accurate at small radii).

[F3]

In orthonormal real coordinates, the Cauchy step decrease is at least $\frac{1}{2} ∥ g ∥ \min {Δ, ∥ g ∥ / ∥ B_{x} ∥_{o p}}$ , with the zero-operator convention (The Cauchy step gives a quantitative model decrease).

[F4]

The real and complex Stiefel frame sets are nonempty compact metric subspaces of finite-dimensional real coordinate spaces, and the quotient maps to the Grassmannians are continuous and onto (Finite-dimensional Stiefel and Grassmann manifolds are compact, Finite-dimensional complex Stiefel and Grassmann manifolds are compact). A continuous real-valued function on a nonempty compact metric space attains its minimum (A continuous real-valued function on a nonempty compact metric space is bounded and attains a greatest and a least value).

[F5]

The natural logarithm is increasing and obeys product and quotient laws (The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm).

[F6]

For $y \geq 1$ , $0 \leq \log y \leq y$ (The natural logarithm is bounded above by its positive argument minus one).

[F7]

Every real number is exceeded by an integer (Every complete ordered field is Archimedean).

[F8]

If $0 < q < 1$ , then $q^{j} \to 0$ (For $∣ r ∣ < 1$ the sequence $r^{k}$ is null, and for $∣ r ∣ > 1$ the sequence $∣ r ∣^{k}$ diverges to $+ \infty$ ).

Proof

technique · establish an attained lower bound, derive a radius floor, then count accepted decreases and rejected contractions

1.1F4givencases

If $M = St (n, r)$ , the real-coordinate Stiefel set is a nonempty compact metric space by [F4], so [F4] gives an attained minimum of $f$ . If $M$ is either Grassmannian, let $q$ be its continuous surjective quotient map from the corresponding real or complex Stiefel set. Then $f \circ q$ is continuous on that nonempty compact metric frame set and attains its minimum by [F4]. Surjectivity makes this the minimum of $f$ on $M$ . Thus $f_{\inf}$ is finite and attained in every case.

1.2F1F2giveninductionalgebra

Fix $0 < ε \leq 1$ and write ${\overset{ˉ}{δ}}_{ε} = \min {c_{δ} ε, Δ_{\max}}$ . Whenever $∥ g_{k} ∥ > ε$ and $Δ_{k} \leq {\overset{ˉ}{δ}}_{ε}$ , the hypotheses of [F2] hold because $Δ_{k} \leq c_{δ} ∥ g_{k} ∥$ . Thus $ρ_{k} \geq η_{2} > η_{1}$ , and [F1] forbids rejection. Therefore every radius before target is at least $r_{ε} = \min {Δ_{0}, γ_{d e c} {\overset{ˉ}{δ}}_{ε}} > 0.$ Indeed the initial radius has this bound; an accepted update does not shrink it, and a rejected update starts above ${\overset{ˉ}{δ}}_{ε}$ and leaves a radius above $γ_{d e c} {\overset{ˉ}{δ}}_{ε}$ . Induction proves the claim.

2.1givenstep 1.1algebra

The pointwise gradient convention requires only differentiability. In an orthonormal real tangent basis $e_{i}$ , write $v = \sum_{i} v_{i} e_{i}$ and $G = \sum_{i} d f_{x} (e_{i}) e_{i}$ . Then $⟨ G, v ⟩ = \sum_{i} d f_{x} (e_{i}) v_{i} = d f_{x} (v)$ by linearity, and if $H$ has the same pairing with every $v$ , taking $v = G - H$ gives $∥ G - H ∥^{2} = 0$ , hence $G = H$ . The zero tangent space has $G = 0$ . Thus the gradient is well-defined for a $C^{2}$ objective. For the chosen first-order retraction, $D R_{x} (0) [v] = v$ ; the chain rule gives $D {\hat{f}}_{x} (0) [v] = d f_{x} [v] = ⟨ g, v ⟩$ , so the pullback gradient at zero is $g$ . All subsequent estimates require only the stated pullback Lipschitz bound and the continuity used in step 1.1.

2.2F1F3F7F8givenstep 1.1step 1.2chooseassume-contradischarge-contradictionalgebra

Choose orthonormal real coordinates on each finite-dimensional tangent or horizontal space. In those coordinates [F3] applies and the matrix norm of $B_{x}$ is $∥ B_{x} ∥_{o p}$ . If $∥ g_{k} ∥ > ε$ , then $r_{ε} \geq c_{R} ε, \min {Δ_{k}, ∥ g_{k} ∥ / ∥ B_{x_{k}} ∥_{o p}} \geq c_{P} ε,$ with the stated infinite-ratio convention when $M_{B} = 0$ . The first inequality follows from $ε \leq 1$ and the definitions of $r_{ε}, c_{R}$ ; the second follows from $Δ_{k} \geq r_{ε}$ , $∥ g_{k} ∥ > ε$ , and $∥ B_{x_{k}} ∥_{o p} \leq M_{B}$ . By [F1] and [F3], the selected step has predicted decrease at least the Cauchy fraction, hence at least $\frac{1}{2} θ_{C} c_{P} ε^{2}$ . Every accepted step has $ρ_{k} \geq η_{1}$ , so its actual decrease is at least $c_{S} ε^{2}$ . Run the update rule without applying the outer cap. If the target were never reached and only finitely many steps were accepted, the resulting infinite block of rejections would keep the point fixed and force its radius to zero by [F8], contradicting the radius floor in step 1.2. Thus the uncapped process must have infinitely many accepted steps unless it reaches the target. By [F7], choose an integer $m > (f (x_{0}) - f_{\inf}) / (c_{S} ε^{2})$ . After $m$ accepted steps the objective would be below $f_{\inf}$ , a contradiction. Thus the target is reached after finitely many accepted steps. Summing their decreases and using step 1.1 gives $N_{s} \leq \frac{f (x_{0}) - f_{\inf}}{c_{S} ε^{2}} .$

2.3F1F5givenstep 1.2algebra

If the initial point already meets the target, then $N_{s} = N_{u} = 0$ and the bounds hold. Otherwise let $Δ_{T}$ be the radius after the accepted step that first reaches the target. Each rejected trial multiplies the radius by $γ_{d e c}$ , and each accepted update multiplies it by a factor $q_{j} \in [1, γ_{i n c}]$ . Hence $Δ_{T} = Δ_{0} γ_{d e c}^{N_{u}} \prod_{j = 1}^{N_{s}} q_{j}, Δ_{T} \geq r_{ε}$ by step 1.2. Taking logarithms using [F5], then rearranging and using $\log q_{j} \leq \log γ_{i n c}$ , gives $N_{u} ∣ \log γ_{d e c} ∣ = \log (Δ_{0} / Δ_{T}) + \sum_{j = 1}^{N_{s}} \log q_{j} \leq \log (Δ_{0} / r_{ε}) + N_{s} \log γ_{i n c} .$ This is the asserted rejected-trial bound.

3.1F1F5F6givenstep 1.1step 1.2step 2.2step 2.3algebra∎

By step 1.1, $f_{\inf}$ is finite. The definitions give $r_{ε} \geq c_{R} ε$ , so [F5] gives $\log (Δ_{0} / r_{ε}) \leq \log (Δ_{0} / (c_{R} ε)) = \log (Δ_{0} / c_{R}) + \log (1 / ε) .$ By [F6], $\log (1 / ε) \leq 1 / ε \leq 1 / ε^{2}$ for $0 < ε \leq 1$ . Thus this radius term is $O (ε^{- 2})$ ; step 2.2 gives the same order for $N_{s}$ , and step 2.3 gives it for $N_{u}$ . A finite integer outer cap at least the resulting trial bound therefore suffices to return stationary or target-achieved. The algorithm tests zero gradient first, so stationary is possible; either return has gradient norm at most $ε$ .

5 · Examples, counterexamples and false statements

None yet.