Trace minimization with column norm constraint

233 Views Asked by At

For a symmetric and negative semidefinite matrix $Q\in\mathbb{R}^{n \times n}$, how can one solve the following QCQP 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 [r]\end{array}$$

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

1

There are 1 best solutions below

3
On BEST ANSWER

Note that this trace is simply equal to $\sum_{i}x_i^TQx_i$. Thus, it suffices to separately minimize $x_i^TQx_i$ over the columns of $x_i$. By the Rayleigh-Ritz theorem, this minimum is attained if and only if $x_i$ is a unit eigenvector associated with the smallest (i.e. largest in absolute value) eigenvalue of $Q$.