2
$\begingroup$

Given an overdetermined linear system $AX=Y$ with known $A$ and $Y$, how would I go about finding the least squares solution $X$ under the constraint that it is symmetric ($X=X^T$)?

$\endgroup$

1 Answer 1

4
$\begingroup$

Let $P=A^TA$ and $S=A^TY+Y^TA$. When $X$ is symmetric, $$ \|AX-Y\|_F^2=\operatorname{tr}(XPX-SX+Y^TY).\tag{1} $$ Since the set of all symmetric matrices form a closed linear subspace, there is always a global minimiser and any such global minimiser must be a critical point of $(1)$. However, as $P$ is positive semidefinite, the converse is also true, i.e. each critical point of $(1)$ is a global minimum.

At each critical point $X$, we have $$ 0=\operatorname{tr}\left((\Delta X)PX+XP(\Delta X)-S(\Delta X)\right) =2\operatorname{tr}\left((PX+XP-S)(\Delta X)\right) $$ for any symmetric matrix $\Delta X$. In particular, the trace is zero if we put $\Delta X=PX+XP-S$. But then $\operatorname{tr}((PX+XP-S)^2)=0$, meaning that $$ PX+XP-S=0.\tag{2} $$ Thus the global minimisers of $(1)$ are the symmetric solutions to $(2)$.

When $A$ has full column rank, $P=A^TA$ is positive definite. Therefore the above equation (known as Lyapunov equation) has a unique solution, which can be expressed as $$ \operatorname{vec}(X)=(I\otimes P+P\otimes I)^{-1}\operatorname{vec}(S) $$ or $$ X=\int_0^\infty e^{-tP}Se^{-tP}dt. $$ When $A$ has deficient column rank, we may solve $(2)$ without the symmetry constraint first, and then obtain a global minimiser by symmetrising the solution to $(2)$. More specifically, let $M = I\otimes P+P\otimes I$. Then the general solution to $(2)$ is given by $$ \operatorname{vec}(X_0)=M^+\operatorname{vec}(S) + (I-M^+M)\operatorname{vec}(T) $$ where $T$ is any matrix with the same size as $S$. The general symmetric solution to $(2)$ is therefore given by $X=\frac12(X_0+X_0^T)$.

$\endgroup$
3
  • $\begingroup$ Can you help provide some clarification. I understand that for square matrices $|| A ||_{F}^{2}= \text{tr}\left(A^{\top}A\right)$. Using this and a little algebraic expansion one has $||A X - Y ||_{F}^{2}=\text{tr}\left(X^{\top}A^{\top}AX-Y^{\top}AX-X^{\top}A^{\top}Y+Y^{\top}Y\right)$. The thing I don't understand is how $Y^{\top}AX+X^{\top}A^{\top}Y$ can reduce to $SX$ even when $X$ is symmetric. Have you also assumed that $A$ and $Y$ are also symmetric? $\endgroup$
    – Tucker
    Oct 7, 2020 at 0:52
  • $\begingroup$ @Tucker Every square matrix has the same trace as its transpose. Thus $\operatorname{tr}(X^\top A^\top Y)$ can be rewritten as $\operatorname{tr}(Y^\top AX)$. $\endgroup$
    – user1551
    Oct 10, 2020 at 10:18
  • $\begingroup$ $+\tt1\,$ By introducing the Duplication matrix $D$ and its pseudoinverse $D^+$ $${\rm vec}(X) = D\;{\rm vech}(X) \;\iff\; {\rm vech}(X) = D^+\,{\rm vec}(X)$$ The vectorized equation can be directly solved for the symmetric solution $${\rm vec}(X) = D(D^+MD)^{-1}D^+{\rm vec}(S)$$ $\endgroup$
    – greg
    Mar 2 at 2:53

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.