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$)?
1 Answer
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)$.
-
$\begingroup$ 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? $\endgroup$– TuckerOct 7, 2020 at 0:52
-
$\begingroup$ @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)$. $\endgroup$– user1551Oct 10, 2020 at 10:18
-
$\begingroup$ $+\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)$$ $\endgroup$– gregMar 2 at 2:53