Grassmannian optimization is NP-hard

Zehua Lai, Lek-Heng Lim, Ke Ye

We show that unconstrained quadratic optimization over a Grassmannian $\mathrm{Gr}(k,n)$ is NP-hard. Our results cover all scenarios: (i) when $k$ and $n$ are both allowed to…