optimization on set of semi-orthogonal matrices

Question

Let Q be a diagonal $n\times n-$matrix with entries are non-negative and $<1$.

Im trying to find X a semi-orthogonal $d\times n-$matrix ($XX^T=I_{id}$) that minimize $$\Vert XQX^T\Vert$$ where $d<n$ and $\Vert A\Vert=\sup(\Vert Ax\Vert_1 \ x\in\mathbb{R^d}, \Vert x\Vert_1=1)$ and $\Vert.\Vert_1$ is the euclidean norm

Answer 1

Let us note $\lambda_0,...,\lambda_{n-1}$ the eigenvalues of $Q$. Without loss of generality, suppose $\lambda_0 >= \lambda_1 >= ... >= \lambda_{n-1}$. Let us also note $x_0, ...,x_{n-1}$ the corresponding eigen vectors.

To start you off you can first show that $\dim(Im(X^T)) = d$.

Then you can show that $\|XQX^T\| = min_{\mathbb{R}x_{i} \subset Im(X^T)} \lambda_{i}$. (The smallest eigen value such that the corresponding eigen space is included in the image of $X^T$).

This should give you a clearer idea of what a solution X looks like.

Answer 2

Here is another way to look at it.

Let ${\cal X} = \{ X :\mathbb{R}^n \to \mathbb{R}^d| X X^T = I \}$, and ${\cal V} = \{ V \subset \mathbb{R}^n| \dim V = d \}$, the $d$ dimensional subspaces.

We replace the minimisation over ${\cal X}$ by a minimisation over ${\cal V}$, and use the subspace characterisation of singular values to get a solution.

Also note that since $Q$ is symmetric, we have $\|XQX^T\| = \max_{\|x\| \le 1} |x^T XQX^T x|$. Furthermore, it is straightforward to check that $\|x\| = \|X^T x\|$ for any $x$. Also note that since $Q \ge 0$ it has a square root.

We have \begin{eqnarray} \min_{X \in {\cal X}} \|XQX^T\| &=& \min_{X \in {\cal X}} \max_{\|x\| \le 1} |x^T XQ X^Tx| \\ &=& \min_{X \in {\cal X}} \max_{z \in {\cal R} X^T, \|z\| \le 1} |z^T Q z| \\ &=& \min_{X \in {\cal X}} \max_{z \in {\cal R} X^T, \|z\| \le 1} \|\sqrt{Q}z\|^2 \\ &=& \min_{X \in {\cal X}, V={\cal R}X^T} \max_{z \in V, \|z\| \le 1} \|\sqrt{Q}z\|^2 \\ &=& \min_{V \in {\cal V}} \max_{z \in V, \|z\| \le 1} \|\sqrt{Q}z\|^2 \\ &=& \sigma_{n-d+1}(\sqrt{Q})^2 \\ &=& \sigma_{n-d+1}(Q) \end{eqnarray} Note that a minimising $X$ can be found by computing the singular value decomposition of $Q$ (which is trivial in this case) and letting $X^T = \begin{bmatrix} v_{n-d+1}, ..., v_n \end{bmatrix}$, where $v_{n-d+1}, ..., v_n$ are the left singular vectors of $Q$, in this case, if we assume that the entries of $Q$ are ordered in non decreasing fashion we have $X^T = \begin{bmatrix} 0 \\ I \end{bmatrix}$.