# 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)$$.
• 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? Oct 7, 2020 at 0:52
• @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)$. Oct 10, 2020 at 10:18
• $+\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)$$