Some of the most common Riemannian manifolds in geometry, including many that are important in engineering applications, may be represented as matrix manifolds, i.e., submanifolds or quotient manifolds of \(\mathbb {R}^{m \times n}\) endowed with various Riemannian metrics.

We consider four of the best known ones: The Cartan manifold of ellipsoids in \(\mathbb {R}^n\) may be modeled as the set of positive definite matrices

\begin{equation} \label {eq:El} \El (\mathbb {R}^n) \cong \{ A \in \mathbb {R}^{n \times n} : A^\tp = A, \; x^\tp A x > 0 \text { for all } x \ne 0 \}. \end{equation}

The compact Stiefel manifold of orthogonal \(k\)-frames in \(\mathbb {R}^n\) may be modeled as the set of \(n \times k\) orthonormal matrices

\begin{equation} \label {eq:V} \V _k(\mathbb {R}^n) \cong \{Y \in \mathbb {R}^{n \times k} : Y^\tp Y = I \} \end{equation}

The noncompact Stiefel manifold of \(k\)-frames in \(\mathbb {R}^n\) may be modeled as the set of \(n \times k\) full-rank matrices

\begin{equation} \label {eq:St} \St _k(\mathbb {R}^n) \cong \{ S \in \mathbb {R}^{n \times k} : \rank (S) = k\} \end{equation}

The Grassmannian of \(k\)-planes in \(\mathbb {R}^n\) may be modeled either as projection matrices, involution matrices, or, more generally, quadratic matrices with appropriate trace values:

\begin{align} \Gr _k(\mathbb {R}^n) &\cong \{P \in \mathbb {R}^{n \times n}: P^2 = P = P^\tp ,\; \tr (P) = k\} \label {eq:P} \\ &\cong \{Q \in \mathbb {R}^{n \times n} : Q^\tp Q =I,\; Q^\tp = Q, \; \tr (Q)=2k - n\} \nonumber \\ &\cong \{ W \in \mathbb {R}^{n \times n}: W^\tp = W, \; (W - a I)(W- bI) = 0, \; \tr (W) = ka + (n-k)b \}. \nonumber \end{align} Further examples may be obtained from these four basic cases as product, quotient, or submanifolds.

We will show that unconstrained quadratic optimization over any of these models of Grassmannian is NP-hard. Our results cover all scenarios: (i) when \(k\) and \(n\) are both allowed to grow; (ii) when \(k\) is arbitrary but fixed; (iii) when \(k\) is fixed at its lowest possible value of \(1\).

For example, the clique decision problem, i.e., deciding if a clique of size \(k\) exists in a graph \(G = (V, E)\), may be formulated as the maximization problem

\begin{equation} \label {eq:func} \max _{P\in \Gr (k, n)} \biggl [ \sum _{(i, j) \in E}e_i^\tp P e_i e_j^\tp P e_j + \sum _{i \in V} e_i^\tp P e_i e_i^\tp P e_i \biggr ], \end{equation}

where \(\Gr (k,n)\) is the projection model of Grassmannian in (4) and \(e_1, \dots , e_n \in \mathbb {R}^n\) the standard basis. This establishes NP-hardness of (i) for the projection model but we will extend it to other models and also to (ii) and (iii).

We will establish similar NP-hardness results for unconstrained quadratic optimization over the Cartan manifold in (1), as well as unconstrained cubic optimization over the compact and noncompact Stiefel manifolds in (2) and (3).

In all cases, we will rule out the existence of \(\mathrm {FPTAS}\) and show that these hardness results hold regardless of the choice of Riemannian metrics one puts on these manifolds. If time permits, we will also discuss the NP-hardness of optimizing over various representations of these manifolds as quotient matrix manifolds, including

\begin{alignat*} {3} \Gr _k(\mathbb {R}^n) &\cong \Or (n)/(\Or (k)\times \Or (n-k)), \qquad &\V _k(\mathbb {R}^n) &\cong \Or (n)/\Or (n-k),\\ \St _k(\mathbb {R}^n) &\cong \GL (n)/\Pa _1(k,n), &\El (\mathbb {R}^n) &\cong \GL (n)/\Or (n). \end{alignat*}

References

• [1]  Z. Lai, L.-H. Lim, and K. Ye, “Grassmannian optimization is NP-hard,” arXiv:2406.19377, 2024.