Symmetric linear least squares solution

Question

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$)?

Answer 1

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