Hi Here is my question:
Suppose there is an $n \times n$ real symmetric matrix $X$. It is easy to project it onto the positive semidefinite cone $\mathcal{S}_n^+$. We can just apply the the eigenvalue decomposition to obtain $X = U S U^T$, where $S$ is the eigenvalue matrix, then we can project $S$ onto $S_+$ by changing all the negative eigenvalues in $S$ to be zeros. Then the projected matrix $\bar X $ equals to $US_+U^T$. $\bar X$ is the "closest" matrix to $X$ such that $\bar X \succeq 0$. ($\bar X \in \mathcal{S}_n^+$)
Now I want to project it to a more complicated cone, i.e., a face of cone. Let's denote the cone by $\mathcal{K}$, suppose $V$ is given, then $\mathcal{K} = \{Z \in \mathcal{S}_n, Z = V P V^T, P \in \mathcal{S}_d^+, n > d\}$, where $\mathcal{S}_n$ means the cone of $n \times n$ real symmetric matrices, $\mathcal{S}_d^+$ denotes the cone of $d \times d$ real symmetric positive semidefinite matrices, and $V$ is an $n \times d$ matrix. Therefore $Z$ will not be full rank, i.e., $Z$ is on the boundary (face) of the positive semidefinite cone. I would like to project $X$ to the cone $\mathcal{K}$ so the projected $\bar X$ is the "closest" one to $X$.
I am not sure how to do this projection similar to the first paragraph. Does there exist a formula or algorithm for doing this? I know I can use the matlab toolbox but that is an iterative algorithm which is not exact and also costly. Any ideas or suggestions would be greatly appreciated. Thanks a lot!
Best Answer
Without loss of generality, $V^TV=I_d$ (if not do $QR$ decomposition or similar to get an orthonormal basis for the span of $V$). Note that by changing basis $\mathcal{K}$ is equivalent to the intersection of the positive semidefinite cone with block diagonal matrices. $$ Z \in \mathcal{K} \Leftrightarrow QZQ^T = \begin{pmatrix} A &0\\0 &0 \end{pmatrix}, A \in S_d^+ $$
So to project onto $\mathcal{K}$, first we calculate $V^TZV$ (equivalent to extracting out the $d \times d$ submatrix), project it onto $S_d^+$, then expand back onto $S_n$. That is, denoting projecting onto $C$ by $\Pi_C$:
$$ \Pi_\mathcal{K}(Z) = V[\Pi_\mathcal{S_d^+}(V^TZV)]V^T\\ $$