2
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Is the situation exactly as stated? So $V$ is given and $\mathcal{K}$ depends on $V$? Or is $\mathcal{K}$ the set of positive semidefinite matrices with rank $\le d$? $\endgroup$ – gerw Dec 18 '15 at 21:48
  • $\begingroup$ Yes, $\mathcal{K}$ depends on $V$, $\mathcal{K}$ is the set of positive semidefinite matrices such that the matrices of has null space $B$ since we require $V^T B = 0$. If $\mathcal{K}$ is the set of psd matrices with rank $ k \leq d$ then we can just select the $d$ greatest eigenvalues to do the projection $\endgroup$ – Pew Dec 19 '15 at 0:47
2
$\begingroup$

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\\ $$

$\endgroup$
  • $\begingroup$ Thanks. I think that is the answer! $\endgroup$ – Pew Dec 20 '15 at 23:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.