3
$\begingroup$

Given a square matrix $A \in \mathbb{R}^{n \times n}$, I need to compute $$ \min_{X \in \Omega} \lVert A - X\rVert^2$$ where $\Omega = \{X \in \mathbb{R}^{n \times n} |\, {\rm tr}(X) = 1, X \text{ is symmetric, }X \geq 0 \}$, namely I want the projection of a given matrix on the set $\Omega$.

But I also neec to compute it fast. I tried using cvx_solver but it's way too slow computing it directly. is there a better way to write this problem? Or is there a known closed formula or quick algorithm for finding such projection?

$\endgroup$
2
  • 1
    $\begingroup$ Which norm are you using? $\endgroup$ Commented Apr 14, 2015 at 1:20
  • $\begingroup$ For the solver I tried using norm 2 and Frobenius norm. But both take a bit long $\endgroup$
    – karlabos
    Commented Apr 14, 2015 at 12:42

1 Answer 1

3
$\begingroup$

Using Lagrange multipliers for the conditions $X-X^T=0$ and ${\rm tr}(X)=1$ and for the objective function the Frobenius norm, you get the Lagrange functional $$ L(X,U,v)=\frac12\|A-X\|_F^2+{\rm tr}(U^T(X-X^T))+v(1-{\rm tr}(X)) $$ and from the condition $\frac{∂L}{∂X}=0$ the general form $$ X=A+(U-U^T)+vI $$ To get trace $1$, you need $1={\rm tr}(A)+n·v$, the condition for $U$ is not that uniquely determined, only $2(U-U^T)=A^T-A$ has to be satisfied -- which is sufficient to uniquely determine $X$. The simple solution for that is $U=A^T$. Thus $$ X=\frac12(A+A^T)+\frac1n(1-{\rm tr}(A))·I $$

$\endgroup$
4
  • $\begingroup$ Could you explain in detail how you derived $X=A+(U-U^T)+vI$ and $2(U-U^T)=A^T-A$? Thank you! $\endgroup$ Commented Apr 14, 2015 at 11:55
  • $\begingroup$ Now it is crystal clear! $\endgroup$ Commented Apr 14, 2015 at 12:40
  • $\begingroup$ I see. But that doesn't take care of the positive definite part... $\endgroup$
    – karlabos
    Commented Apr 14, 2015 at 12:43
  • 1
    $\begingroup$ Ok, for that you need something like the polar decomposition, either per SVD or per the dedicated iteration.. However, I do not see how that meshes with the trace condition. First projecting on a superset of the final set need not be the same as direct projection. Where here the superset it the set of sym.pos.def. matrices, and the subset those that have trace 1. $\endgroup$ Commented Apr 14, 2015 at 13:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .