0
$\begingroup$

Suppose $A$ and $B$ are known matrices, and we are to find matrix $X$ that minimizes the following function,

$$\frac{1}{2}||X||^2+\frac{1}{2}||X^TAX-B||^2$$

Taking the relevant derivative w.r.t $X$ gives us, $$ X +(X^TAX-B)(A+A^T)X$$

I couldn't reduce the derivative further as $A$ is not necessarily a square matrix; so, $(A+A^T)$ would be invalid. I am using the formula in slide 17, Matrix Calculus to differentiate $X^TAX$ to $(A+A^T)X$

Is there a way to circumvent this issue?

Thank you.

$\endgroup$
3
  • 1
    $\begingroup$ For the product $X^TAX$ to be defined, $A$ must be square. W.l.o.g. you can assume that $A$ is symmetric or replace it by its symmetrized version. I'm not sure that there is an easy solution. Try to find something usable in the case that $A$ is symmetric and $B$ is upper triangular. $\endgroup$ Mar 13 '14 at 11:26
  • $\begingroup$ Yes, ofcourse. $A$ must be a square matrix, thanks. Now that this is out of the way, is it easy to solve for $X$ when equating the derivative to zero? thanks $\endgroup$ Mar 13 '14 at 12:22
  • 1
    $\begingroup$ No, not really. You can not even assume that one of the factors is zero, since there are non-zero matrices with product zero. -- If $A$ were positive definite, you could take a square root of it, a real square root, not just a Cholesky factor, and express the equation in terms of the matrix $Y=A^{1/2}XA^{1/2}$ as $$[I+2(Y^TY+A^{1/2}BA^{1/2})]Y=0.$$ But is the derivative correct? Replace in the original objective function $X$ by $X+tH$ and compute the linear terms, I think $(A+A^T)X$ should come before $(X^TAX−B)$. $\endgroup$ Mar 13 '14 at 13:47
1
$\begingroup$

By the AGM inequality, $\frac{1}{2}(||X||^2 + ||X^TAX - B||^2) \geq ||X||||X^TAX - B||$ with equality if $||X|| = ||X^TAX - B||$. So the minimum occurs when $X = X^TAX - B$.

$\endgroup$
4
  • $\begingroup$ Thanks, but then how would we solve for $X$ here. $X=X^TAX-B$ => $B=X^TAX-X$ => $B=(X^TA-I)X$ => ?? $\endgroup$ Mar 13 '14 at 7:56
  • $\begingroup$ Does the matrix $X$ have any special structure. For example, is it self-adjoint, unitary, or invertible? $\endgroup$ Mar 13 '14 at 8:05
  • $\begingroup$ No, the structure of $X$ is completely arbitrary, but its numbers are Real. $\endgroup$ Mar 13 '14 at 8:19
  • 1
    $\begingroup$ Mustafa, you are clearly wrong because when the required minimum is reached for a matrix $X$, there's no reason so that your AGM inequality becomes an equality. $\endgroup$
    – user91684
    Mar 15 '14 at 11:18
1
$\begingroup$

Replace $X$ by $X+εH$ and disregard all terms that are $O(ε^2)$. Then, assuming the matrix norm is the Frobenius norm (?) \begin{align} &\tfrac12\|X+εH\|^2+\tfrac12\|(X+εH)^TA(X+εH)-B\|^2\\[1em] &=\tfrac12\|X\|^2+ε\,Tr(X^TH)\\[0.2em] &\qquad+\;\tfrac12\|X^TAX-B\|^2+ε\,Tr((X^TAX-B)^TH^TAX)+ε\,Tr((X^TAX-B)^TX^TAH)\\[1em] &=\tfrac12\|X\|^2+\tfrac12\|X^TAX-B\|^2\\[0.2em] &\qquad+ε\,Tr\Bigl(\Bigl[X^T+(X^TA^TX-B^T)X^TA+(X^TAX-B)X^TA^T\Bigr]H\Bigr) \end{align}

So the correct derivative is $$ X^T+(X^TA^TX-B^T)X^TA+(X^TAX-B)X^TA^T $$ or transposed as gradient $$ X+A^TX(X^TAX-B)+AX(X^TA^TX-B^T) $$ which has no easy further simplifications.

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