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

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