# Symmetric linear least-squares solution

Given tall matrices $$A$$ and $$Y$$ and the following overdetermined linear system in square matrix $$X$$

$$AX=Y$$

is there an explicit formula for the least-squares solution if $$X$$ is constrained to be symmetric?

• Presumably, given symmetry constraint, $X$ and $Y$ are square matrices, in which case $X=A^+Y$ is not the least squares solution (of vec'd problem, or equivalently, minimizing Frobenius norm of $X - Y$). Please clarify. – Mark L. Stone Sep 4 '19 at 22:44
• @MarkL.Stone $X$ is square but $A$ and $Y$ are tall. – Museful Sep 4 '19 at 22:53
• Sorry, I shouldn't have said $Y$ square. But my point about $X=A^+Y$ not being the solution in the absence of symmetry requirement still stands. That formula assumes $X$ and $Y$ are column vectors. – Mark L. Stone Sep 4 '19 at 23:17
• @MarkL.Stone I see. That part isn't essential to the question so I just removed it. – Museful Sep 4 '19 at 23:39
• I don't know of any explicit formula (but not saying it doesn't exist). But it can be readily formulated and numerically solved as a convex Quadratic Programming (QP) or Second Order Cone Problem (SOCP). – Mark L. Stone Sep 4 '19 at 23:48

I assume that $$A$$ is onto, so that $$H:=A^TA$$ is positive definite. Minimizing $$\|AX-Y\|_F^2$$ in Frobenius norm (the least square) among symmetric matrices $$X$$ yields the optimality condition that $$\langle AS,AX-Y\rangle=0$$ for every symmetric $$S$$. This amounts to saying that $$A^T(AX-Y)$$ is skew-symmetric. In other words, $$X$$ is the solution of the Lyapunov equation $$HX+XH=A^TY+Y^TA=:K.$$ The explicit formula is $$X=\int_0^\infty e^{-tH}Ke^{-tH}dt.$$

• Is (numerical) evaluation of that integral more difficult than numerically solving the convex Quadratic Programming (QP) or Second Order Cone Problem (SOCP) of minimizing Frobenius norm (or its square) subject to constraint $X = X^T$? – Mark L. Stone Sep 7 '19 at 13:05
• @MarkL.Stone Why compute the integral? Isn't the Lyapunov equation a system of linear equations? Why not use Gaussian elimination? – Rodrigo de Azevedo Sep 7 '19 at 14:18
• Prof. Serre, is it still a Lyapunov equation without information on the positive definiteness of (symmetric) matrix $K$? – Rodrigo de Azevedo Sep 7 '19 at 14:22
• @Rodrigo de Azevedo My bad. You are correct. – Mark L. Stone Sep 7 '19 at 15:12
• @RodrigodeAzevedo. $K$ does not need to be positive, but $H$ needs to. Actually, the semi-definite case (for $H$) reduces to the positive definite one, by using the orthogonal projection $\Pi$ onto the subspace $(\ker A)^\bot$. Then you must replace $Y$ by $\Pi Y$. – Denis Serre Sep 7 '19 at 16:31

Complementing Denis Serre's answer and rephrasing the original problem slightly, given tall matrices $$\rm A$$ and $$\rm B$$, we have the following quadratic program in square matrix $$\rm X$$

$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm X - \mathrm B \|_{\text F}^2\\ \text{subject to} & \mathrm X = \mathrm X^\top\end{array}$$

We define the Lagrangian

$$\mathcal L (\mathrm X, \Lambda) := \| \mathrm A \mathrm X - \mathrm B \|_{\text F}^2 + \langle \Lambda, \mathrm X - \mathrm X^\top \rangle$$

Differentiating the Lagrangian with respect to $$\mathrm X$$ and $$\Lambda$$ and finding where the derivatives vanish, we obtain the following system of linear matrix equations

\begin{aligned} 2 \mathrm A^\top \left( \mathrm A \mathrm X - \mathrm B \right) + \Lambda - \Lambda^\top &= \mathrm O\\ \mathrm X - \mathrm X^\top &= \mathrm O \end{aligned}

which can be rewritten as follows

\begin{aligned} \mathrm A^\top \left( \mathrm A \mathrm X - \mathrm B \right) &= -\frac12 \left( \Lambda - \Lambda^\top \right)\\ \mathrm X &= \mathrm X^\top\end{aligned}

From the 1st matrix equation, we conclude that matrix $$\mathrm A^\top \left( \mathrm A \mathrm X - \mathrm B \right)$$ is skew-symmetric, i.e.,

$$\left( \mathrm A^\top \left( \mathrm A \mathrm X - \mathrm B \right) \right)^\top = -\mathrm A^\top \left( \mathrm A \mathrm X - \mathrm B \right)$$

which can be rewritten as the following Lyapunov-like linear matrix equation in symmetric matrix $$\rm X$$

$$\boxed{ \mathrm X \left( \mathrm A^\top \mathrm A \right) + \left( \mathrm A^\top \mathrm A \right) \mathrm X = \mathrm A^\top \mathrm B + \mathrm B^\top \mathrm A }$$

Half-vectorizing both sides of the matrix equation above, we obtain a system of linear equations in the entries of $$\rm X$$ not in the lower triangular

$$\left( \mathrm A^\top \mathrm A \oplus \mathrm A^\top \mathrm A \right) \mathrm D \, \mbox{vech} (\mathrm X) = \mathrm D \, \mbox{vech} \left( \mathrm A^\top \mathrm B + \mathrm B^\top \mathrm A \right)$$

where $$\oplus$$ denotes the Kronecker sum and $$\rm D$$ is a (tall) duplication matrix. Assuming invertibility, the least-squares solution could be written as follows

$$\hat{\mathrm X} := \mbox{vech}^{-1} \left( \mathrm L \left( \mathrm A^\top \mathrm A \oplus \mathrm A^\top \mathrm A \right)^{-1} \mathrm D \, \mbox{vech} \left( \mathrm A^\top \mathrm B + \mathrm B^\top \mathrm A \right) \right)$$

where $$\rm L$$ is a (fat) elimination matrix.