2
$\begingroup$

I would like to minimize the following quantity:

$Q = \left\lVert{X - C}\right\rVert^2_F + a\left\lVert{X - I}\right\rVert^2_F$

Where $X\in\mathbb R^{n\times n}$ is unknown, $C\in\mathbb R^{n\times n}$ is a known positive semi-definite and symmetric matrix, $I$ is the identity matrix, $a\in\mathbb R^+$ and $\left\lVert\cdot\right\rVert_F$ is the Frobenius norm. There is also some constraint on $X$, but for simplicity let's assume that it is only needed to be positive semi-definite. If I could somehow complete the squares on $Q$ then I could you use this answer to solve my problem.

Any help would be much appreciated. Thanks in advance.

$\endgroup$
2
$\begingroup$

Addendum to user1551

Find the gradient and set it to zero, i.e., \begin{align} \frac{\partial Q}{\partial X} = 2(X - C) + a 2(X - I) = 0 \Longrightarrow X = \frac{C + a I}{a+1}. \end{align} The solution is exactly the same as user1551's solution.


p.s.: there are several posts that explain how to compute gradient of Frobenius norm. For instance, say $f:= \|X\|_F^2 = \operatorname{tr}(X^T X)\equiv X:X$ (double colon to denote Frobenius product). Then, compute differential followed by the gradient. So, $df = dX:X + X:dX = 2X:dX \Longrightarrow \frac{\partial f}{\partial X} = 2X$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. While it explains more clearly than user1551's answer how to find the global minimiser it doesn't provide a formula suitable for working with constraints so I am a bit hesitant to accept it. $\endgroup$ – cgss Jul 30 '20 at 9:48
  • $\begingroup$ @cgss If you solve a problem, and the unconstrained solution satisfies your constraints, then you have also solved the constrained problem. This is often the quickest way to solve a constrained problem, since unconstrained techniques are simple and direct. $\endgroup$ – greg Jul 31 '20 at 3:43
  • $\begingroup$ @greg I agree with that. The thing is that as I said in the question, the constraint was simplified. The actual constraint is that X minus a diagonal matrix is positive semidefinite. So I need something of the form of user1551's answer to manipulate my constraints. $\endgroup$ – cgss Jul 31 '20 at 9:41
1
$\begingroup$

The objective function is equal to $(a+1)\left\|X-\frac{C+aI}{a+1}\right\|_F^2+\text{constant}$. Hence the unique global minimiser is $X=\frac{C+aI}{a+1}$. As $C\succeq0$ and $a\ge0$, $X$ is positive semidefinite.

$\endgroup$
1
  • $\begingroup$ Could you please explain it with more details? $\endgroup$ – cgss Jul 27 '20 at 16:06

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.