Trace minimization with row norm constraint

116 Views Asked by At

For a symmetric and negative semidefinite matrix $Q\in\mathbb{R}^{n \times n}$, how can one solve the following optimization problem in tall matrix $X \in \mathbb{R}^{n \times r}$

$$\begin{array}{ll} \text{minimize} & \text{Trace}(X^\top Q X)\\ \text{subject to} & \left\| x_i \right\|_2^2 \leq 1, \quad \forall i \in [n]\end{array}$$

where $x_i$ is the $i$-th row of $X$? Generally, $n \gg r$.


If the norm constraint is on the columns of $X$, the solution is quite straight-forward. But with a constraint on the rows the problems looks much more tricky.