Physical constraints and manifold-valued inversion

Let $X$ and $Y$ be real vector spaces, let $U\subseteq X$ be nonempty, and let $A:X\to Y$ be linear. Supply metrics $d_X$ on $X$ and $d_Y$ on $Y$; for a purely algebraic instance with no specified metrics, use the discrete metrics $d_X(x,x^{\mathrm{\prime }})=0$ if $x=x^{\mathrm{\prime }}$ and $1$ otherwise, and likewise on $Y$. These metrics require no compatibility with the vector operations, and no continuity of $A$ is assumed. The discrete triangle inequality holds because, if two endpoints differ, at least one of the two successive pairs differs. Give $U$ and its subsets their restricted metrics. Thus every pair of real vector spaces still admits this convention. The corresponding metric-space inverse-problem model has admissible truths $U$ and forward map $A{\mathrm{\mid }}_U$. An admissible constraint class is a nonempty subset $C\subseteq U$; its constrained forward map is the restriction $A{\mathrm{\mid }}_C:C\to Y$. The class $C$ is identifiable for $A$ if $A{\mathrm{\mid }}_C$ is injective, meaning $Ax=A{x}^{\mathrm{\prime }}$ for $x,x^{\mathrm{\prime }}\in C$ implies $x=x^{\mathrm{\prime }}$. Define the difference set and kernel by

$C-C:=\{x-x^{\mathrm{\prime }}:x,x^{\mathrm{\prime }}\in C\},\ker A:=\{x\in X:Ax=0_Y\}\mathrm{.}$

Forward maps and admissible truth classes

Linear maps between vector spaces

Kernel of a linear map

Christian Clason, Regularization of Inverse Problems, Chapter 3 §§3.1–3.2

Tristan van Leeuwen and Christoph Brune, 10 Lectures on Inverse Problems and Imaging, Lecture 1 §1.2

Let $X$ and $Y$ be real vector spaces, let $A:X\to Y$ be linear, and let $C\subseteq X$ be nonempty. The restriction $A{\mathrm{\mid }}_C:C\to Y$ is injective if and only if

$(C-C)\cap \ker A=\{0\}\mathrm{.}$

This condition characterizes exact uniqueness on $C$; it gives no stability bound for perturbed data.

Admissible constraint classes and restricted identifiability

Linearity of the forward map

Kernel of the forward map

Christian Clason, Regularization of Inverse Problems, Chapter 3 §§3.1–3.2

Tristan van Leeuwen and Christoph Brune, 10 Lectures on Inverse Problems and Imaging, Lecture 1 §1.2

For integers $1\le p\le n$, define the real Stiefel constraint set

$\mathrm{St}(n,p):=\{X\in {\mathbb{R}}^{n\times p}:X^{\mathsf{T}}X=I_p\}\mathrm{.}$

Equip ${\mathbb{R}}^{n\times p}$ with the Frobenius inner product $⟨U,V{⟩}_F=\mathrm{tr}(U^{\mathsf{T}}V)$ and norm $\mathrm{\parallel }U{\mathrm{\parallel }}_F=\sqrt{⟨U,U{⟩}_F}$. Let $H={\mathbb{R}}^{n\times p}$, let $Y$ be a real Hilbert space, let $U\subseteq H$ be open and contain $\mathrm{St}(n,p)$, and let $F:U\to Y$ be continuously Fréchet differentiable. Given data $y\in Y$, a reference matrix $X_{\mathrm{r}\mathrm{e}\mathrm{f}}\in H$, and $\lambda \ge 0$, define the residual and regularized objective by

$r(X):=\mathrm{\parallel }F(X)-y{\mathrm{\parallel }}_Y,\mathrm{\Phi }(X):=\frac{1}{2}\mathrm{\parallel }F(X)-y{\mathrm{\parallel }}_Y^2+\frac{\lambda }{2}\mathrm{\parallel }X-X_{\mathrm{r}\mathrm{e}\mathrm{f}}{\mathrm{\parallel }}_F^2\mathrm{.}$

Supply an ambient gradient oracle $G:U\to H$ satisfying $D\mathrm{\Phi }(X)[Z]=⟨G(X),Z{⟩}_F$ for every $X\in U$ and $Z\in H$, an initial frame $X_0\in \mathrm{St}(n,p)$, a residual tolerance $\tau \ge 0$, a finite integer budget $K\ge 0$, and a step schedule ${\alpha }_0,\dots ,{\alpha }_{K-1}$ with every ${\alpha }_k>0$. For a square matrix $M$, put $\mathrm{sym}(M):=(M+M^{\mathsf{T}})\mathrm{/}2$. The tangent-projection and metric-dual calculation for this $C^1$ objective, well-definedness of every tangent polar call, and finite-budget feasibility are justified by the finite-budget return and feasibility lemma. No smoothness beyond $C^1$ is required. The procedure is:

1. Set the current frame to $X_0$ and the schedule index to $k=0$. If $r(X)\le \tau$, return $(X,r(X),\mathtt{\text{target-met}})$.

2. While $k<K$, compute $G(X)$ and the Stiefel gradient $g:=G(X)-X\mathrm{sym}(X^{\mathsf{T}}G(X))$. If $g=0$, return $(X,r(X),\mathtt{\text{stationary}})$.

3. Set $\eta :=-{\alpha }_{k}g$ and form the polar-retracted candidate

   $X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}}:=(X+\eta )((X+\eta {)}^{\mathsf{T}}(X+\eta ){)}^{-1\mathrm{/}2}\mathrm{.}$

4. Evaluate $\mathrm{\Phi }(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})$ and $r(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})$. If $\mathrm{\Phi }(X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}})>\mathrm{\Phi }(X)$, return $(X,r(X),\mathtt{\text{objective-rejected}})$. Otherwise accept $X_{\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{a}\mathrm{l}}$ as the current frame. If its residual is at most $\tau$, return $(X,r(X),\mathtt{\text{target-met}})$; otherwise increment $k$ by one and repeat the loop.

5. When $k=K$, return $(X,r(X),\mathtt{\text{budget-exhausted}})$.

This procedure is restricted to the stated finite-dimensional real Stiefel constraint and the displayed polar retraction. It gives no convergence, global-optimality, or noisy-data stability guarantee, and it makes no finite-precision claim. It does not apply to positivity constraints or other nonlinear manifolds without a separately specified compatible retraction and proof.

Finite-budget return, tangent metric-dual formula, and feasibility ↗

Nonlinear forward maps on real Hilbert spaces

Real Stiefel and Grassmann metric conventions

Stiefel tangent space and orthogonal projection

Polar retraction formula and domain

The polar map is a Stiefel retraction

Absil, Mahony, and Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 3, Example 3.6.2

Absil, Mahony, and Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 4, Example 4.1.3

Nicolas Boumal, An Introduction to Optimization on Smooth Manifolds, §§3.8 and 7.3

For the supplied $C^1$ objective and ambient gradient oracle, the displayed projected vector is the Frobenius metric-dual gradient of the restricted objective, and every polar trial is defined. For every input satisfying the finite-budget Stiefel gradient procedure, it returns after at most $K$ trial evaluations with an output frame $X_{\mathrm{o}\mathrm{u}\mathrm{t}}\in \mathrm{St}(n,p)$. Every accepted update has nonincreasing objective value, and the returned status is target-met exactly when $r(X_{\mathrm{o}\mathrm{u}\mathrm{t}})\le \tau$; every other returned status has $r(X_{\mathrm{o}\mathrm{u}\mathrm{t}})>\tau$.

Finite-budget Stiefel gradient procedure

Stiefel tangent-space formula

Polar retraction formula

Stiefel-valued polar retraction

Absil, Mahony, and Sepulchre, Optimization Algorithms on Matrix Manifolds, Chapter 4, Example 4.1.3

Nicolas Boumal, An Introduction to Optimization on Smooth Manifolds, §7.3