Generalized left-localized Cayley parametrization for optimization with orthogonality constraints

Abstract

We present a reformulation of optimization problems over the Stiefel manifold by using a Cayley-type transform, named the generalized left-localized Cayley transform, for the Stiefel manifold. The reformulated optimization problem is defined over a vector space, whereby we can apply directly powerful computational arts designed for optimization over a vector space. The proposed Cayley-type transform enjoys several key properties which are useful to (i) study relations between the original problem and the proposed problem; (ii) check the conditions to guarantee the global convergence of optimization algorithms. Numerical experiments demonstrate that the proposed algorithm outperforms the standard algorithms designed with a retraction on the Stiefel manifold.

Keywords:

• Stiefel manifold
• Cayley transform
• Cayley parametrization
• orthogonality constraint
• non-convex optimization

Disclosure statement

No potential conflict of interest was reported by the author(s).

Notes

1 ${\phi }^{-1}$ is well-defined over $Q_{N,N}$ because all eigenvalues of $\mathit{V}\in Q_{N,N}$ are pure imaginary. For the second expression in (4(4) ${\phi }^{-1}:Q_{N,N}\to \mathrm{SO}(N)\setminus E_{N,N}:\mathit{V}\mapsto (\mathit{I}-\mathit{V})(\mathit{I}+\mathit{V}{)}^{-1}=2(\mathit{I}+\mathit{V}{)}^{-1}-\mathit{I}$(4) ), see the beginning of Appendix 3.

2 The closure of $\mathrm{SO}(N)\setminus E_{N,N}$ is equal to $\mathrm{SO}(N)$. For every $\mathit{U}\in \mathrm{SO}(N)$, we can approximate it by some sequence $({\mathit{U}}_n{)}_{n=1}^{\mathrm{\infty }}$ of $\mathrm{SO}(N)\setminus E_{N,N}$ with any accuracy, i.e. $\underset{n\to \mathrm{\infty }}{lim}{\mathit{U}}_n=\mathit{U}$.

3 The domain of ${\phi }_{\mathit{S}}$ with $\mathit{S}\in \mathrm{SO}(N)$ is a subset $\mathrm{O}(N)\setminus E_{N,N}(\mathit{S})=\mathrm{SO}(N)\setminus E_{N,N}(\mathit{S})$ of $\mathrm{SO}(N)$.

4 As in (9(9) $Q_{N,p}(\mathit{S}):=Q_{N,p}:=\left\{\left[\begin{array}{cc}\mathit{A}& -{\mathit{B}}^{\mathsf{T}}\\ \mathit{B}& \mathbf{0}\end{array}\right]|\begin{array}{c}-{\mathit{A}}^{\mathsf{T}}=\mathit{A}\in {\mathbb{R}}^{p\times p},\\ \mathit{B}\in {\mathbb{R}}^{(N-p)\times p}\end{array}\right\}\subset Q_{N,N}.$(9) ), $Q_{N,p}(\mathit{S})$ is the common set $Q_{N,p}$ for every $\mathit{S}\in \mathrm{O}(N)$. However, we distinguish $Q_{N,p}(\mathit{S})$ for each $\mathit{S}\in \mathrm{O}(N)$ as a parametrization of the particular subset $\mathrm{St}(p,N)\setminus E_{N,p}(\mathit{S})$ of $\mathrm{St}(p,N)$ (see also Remark 1.3(b)).

5 Algorithm 1 can serve as a central building block in our further advanced Cayley parametrization strategies, reported partially in [38–40].

6 The local diffeomorphism of $R_{\mathit{U}}$ around $\mathbf{0}\in T_{\mathit{U}}\mathrm{St}(p,N)$ can be verified with the inverse function theorem and the condition (ii) in Definition B.1.

7 Let ${\mathit{I}}_p+[[\mathit{V}]{]}_{21}^{\mathsf{T}}[[\mathit{V}]{]}_{21}=\mathit{Q}({\mathit{I}}_p+\mathbf{\Sigma }){\mathit{Q}}^{\mathsf{T}}$ be the eigenvalue decomposition with $\mathit{Q}\in \mathrm{O}(N)$ and a nonnegative-valued diagonal matrix $\mathbf{\Sigma }\in {\mathbb{R}}^{p\times p}$. From (I2) in Appendix 9, we have $\Vert {\mathit{M}}^{-1}{\Vert }_2\le \Vert ({\mathit{I}}_p+\mathbf{\Sigma }{)}^{-1}{\Vert }_F=(1+{\sigma }_{min}^2([[\mathit{V}]{]}_{21}){)}^{-1}\le 1$. Thus, we have $\kappa (\mathit{M})\le \Vert \mathit{M}{\Vert }_2\le 1+\Vert [[\mathit{V}]{]}_{11}{\Vert }_2+\Vert [[\mathit{V}]{]}_{21}{\Vert }_2^2$.

8 From the relation $\underset{\mathit{U}\in \mathrm{St}(p,N)}{min}f(\mathit{U})=\underset{\mathit{V}\in Q_{N,p}(\mathit{S})}{inf}f\circ {\mathrm{\Phi }}_{\mathit{S}}^{-1}(\mathit{V})$ in Lemma 2.6, ${\mathrm{\Phi }}_{\mathit{S}}^{-1}({\mathit{V}}^{\star })\in \mathrm{St}(p,N)$ is also a global minimizer of f over $\mathrm{St}(p,N)$.

9 We note that this early stopping of GDM+CP-retraction can be caused by the instability [22] of the Sherman-Morrison-Woodbury formula used in $R_{{\mathit{U}}_0}^{\mathrm{Cay}}$ and $\mathrm{\nabla }(f\circ R_{{\mathit{U}}_0}^{\mathrm{Cay}})$.

10 The subspace $W_1:=\{\mathit{U}\mathbf{\Omega }\in {\mathbb{R}}^{N\times p}\mid {\mathbf{\Omega }}^{\mathsf{T}}=-\mathbf{\Omega }\in {\mathbb{R}}^{p\times p}\}\subset {\mathbb{R}}^{N\times p}$ is an orthogonal complement to the subspace $W_2:=\{{\mathit{U}}_{\perp }\mathit{K}\in {\mathbb{R}}^{N\times p}\mid \mathit{K}\in {\mathbb{R}}^{(N-p)\times p}\}\subset {\mathbb{R}}^{N\times p}$ with the inner product $⟨\mathit{X},\mathit{Y}⟩=\mathrm{Tr}({\mathit{X}}^{\mathsf{T}}\mathit{Y})(\mathit{X},\mathit{Y}\in {\mathbb{R}}^{N\times p})$. The tangent space $T_{\mathit{U}}\mathrm{St}(p,N)$ can be decomposed as $W_1\oplus W_2$ with the direct sum ⊕. In view of the orthogonal decomposition, the first term and the second term in the right-hand side of (A1(A1) $\begin{array}{rl}(\mathit{X}\in {\mathbb{R}}^{N\times p}){\mathcal{P}}_{T_{\mathit{U}}\mathrm{St}(p,N)}(\mathit{X})& :=\underset{\mathit{Z}\in T_{\mathit{U}}\mathrm{St}(p,N)}{\mathrm{argmin}}\Vert \mathit{X}-\mathit{Z}{\Vert }_F\\ & =\frac{1}{2}\mathit{U}({\mathit{U}}^{\mathsf{T}}\mathit{X}-{\mathit{X}}^{\mathsf{T}}\mathit{U})+(\mathit{I}-\mathit{U}{\mathit{U}}^{\mathsf{T}})\mathit{X}.\end{array}$(A1) ) can be regarded respectively as the orthogonal projection of $\mathit{X}$ onto $W_1$ and $W_2$.

11 The exponential mapping ${\mathrm{Exp}}_{\mathit{U}}:T_{\mathit{U}}\mathrm{St}(p,N)\to \mathrm{St}(p,N)$ at $\mathit{U}\in \mathrm{St}(p,N)$ is defined as a mapping that assigns a given direction $\mathcal{D}\in T_{\mathit{U}}\mathrm{St}(p,N)$ to a point on the geodesic of $\mathrm{St}(p,N)$ with the initial velocity $\mathcal{D}$. The exponential mapping is also a special instance of retractions of $\mathrm{St}(p,N)$. However, due to its high computational complexity, computationally simpler retractions have been used extensively for Problem 1.1 [1].

Additional information

Funding

This work was supported by JSPS [grants-in-aid19H04134] partially, by JSPS [grants-in-aid 21J21353] and by JST SICORP [grant number JPMJSC20C6].