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

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.