Symmetric linear least squares solution 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$)?
 A: 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)$.
