# Grassmannian optimization is NP-hard

arXiv: https://arxiv.org/abs/2406.19377 · HTML: https://mlsanity.com/paper/2406.19377/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Jun 2024.

## Built on by (most cited first, 1 of 1)

- [Deflation-Free Optimal Scoring](https://mlsanity.com/paper/2604.25664/) (2026)

## Abstract (arXiv)

We show that unconstrained quadratic optimization over a Grassmannian operatornameGr(k,n) 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 1. We then deduce the NP-hardness of unconstrained cubic optimization over the Stiefel manifold operatornameV(k,n) and the orthogonal group operatornameO(n). As an addendum we demonstrate the NP-hardness of unconstrained quadratic optimization over the Cartan manifold, i.e., the positive definite cone mathbbSnscriptscriptstyle++ regarded as a Riemannian manifold, another popular example in manifold optimization. We will also establish the nonexistence of FPTAS in all cases.