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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityGiven 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?
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.$$
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.