3
$\begingroup$

My question is the following:

Suppose $M$ is an $n \times n$ symmetric real matrix. I want to find an $n \times n$ symmetric real matrix X such that $|| X -M||_F$ is minimized with the constraint that $U^T X U \succeq 0$ (positive semidefinite), where $U$ is an $n \times d$ matrix, $U^TU = I_d$ and $n > d$. $|| \cdot ||_F$ is the frobenius norm of matrix. In short: \begin{equation} X^* = \displaystyle \text{argmin}_{X:U^TXU\succeq 0}||X-M ||_F, X, M \in \mathcal{S_n} \end{equation}

Some useful information may be: $U$ can be obtained from eigenvalue decomposition of $BB^T$ or QR decomposition of $B$ in the sense that there exists $Q = [U,V]$ such that $Q^TQ = QQ^T = I_n, U^TB = 0$.

I would like to find a formula or construction based on eigenvalue decomposition or singular value decomposition for M. For example, if the constraint is $X \succeq 0$ instead of $U^T X U \succeq 0$, we can first apply eigenvalue decomposition to $M$ such that $M = Q \text{diag}(\lambda_1,\cdots, \lambda_n) Q^T$, then $X^* =Q \text{diag}(\max\{\lambda_1,0\},\cdots, \max\{\lambda_n,0\}) Q^T $ would minimize $|| X-M ||_F$.

I used CVX package to compute $X^*$ for some examples and I found some interesting facts: $ (X^*-M) B = 0$ where $U^TB=0$ and $X^* -M$ is always positive semidefinite while $M$ and $X^*$ may not be positive semidefinite. Any help or suggestion of what method or tools I should use for these kind of problems would be much appreciated! Thanks~

$\endgroup$
3
$\begingroup$

Consider $Q$ as you defined it. Let $Y = Q^TXQ$ and $N = Q^TMQ$. Let $$ E = \pmatrix{I_d\\0} $$ We can rewrite your optimization problem as $X^* = Q^TY^*Q$, where $$ Y^* = \arg\min_{Y:E^TYE \geq 0} \| Y - N\|_F $$ Note, however, that $E^TYE$ is simply the upper-left $d \times d$ principle submatrix of $Y$. Denote this submatrix as $\tilde Y$. Let $\tilde N$ denote the corresponding submatrix of $N$.

It therefore suffices to set all other entries of $Y$ to those of $N$ and setting $\tilde Y$ to solve $$ \tilde Y = \arg\min_{Z \geq 0} \|Z - \tilde N\|_F $$ Now, find an orthogonal $W$ such that $W^T\tilde N W$ is diagonal. Make the substitution $\tilde A = W^T \tilde Y W$. We then find $$ \tilde A = \arg\min_{A \geq 0} \|A - D\|_F $$ This has an obvious and unique solution: take $\tilde A$ to be diagonal matrix. Set $a_{ii} = \max\{d_{ii},0\}$.

With that, we have enough information to get the unique solution $X$.

$\endgroup$

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.