Solving the Generalized Sylvester Equation
Common Sylvester Equations
The Sylvester equation
$$ \mathbf{AX}+\mathbf{XD} = \mathbf{E} $$The generalized Sylvester equation
$$ \mathbf{AXB}+\mathbf{CXD} = \mathbf{E} $$where $\mathbf{X}\in \mathbb{R}^{n\times r}$, $\mathbf{A}\in \mathbb{R}^{m\times n}$, $\mathbf{B}\in \mathbb{R}^{r\times p}$, $\mathbf{C}\in \mathbb{R}^{m\times n}$, $\mathbf{D}\in \mathbb{R}^{r\times p}$, $\mathbf{E}\in \mathbb{R}^{m\times p}$.
The Stein matrix equation
$$ \mathbf{AXB}+\mathbf{X} = \mathbf{E} $$The Lyapunov matrix equation
$$ \mathbf{AX}+\mathbf{XA^T}=\mathbf{E} $$Solving the Generalized Sylvester Equation
- Use a closed-form solution
- Use Newton’s method or the conjugate gradient method
Solving the Generalized Sylvester Equation with ADMM
$$ \begin{cases} \mathbf{AXB}+\mathbf{CXD}=\mathbf{E} \\ \mathbf{AXB}+\mathbf{CXD}=\mathbf{E} \end{cases} $$Move terms across to construct an equivalent system:
$$ \begin{cases} \mathbf{AXB}=\mathbf{E}-\mathbf{CXD} \\ \mathbf{CXD}=\mathbf{E}-\mathbf{AXB} \end{cases} $$Set
$$ \begin{cases} \mathbf{E}_1=\mathbf{E}-\mathbf{CXD} \\ \mathbf{E}_2=\mathbf{E}-\mathbf{AXB} \end{cases} $$This gives
$$ \begin{cases} \mathbf{AXB}=\mathbf{E}_1 \\ \mathbf{CXD}=\mathbf{E}_2 \end{cases} $$The two systems above are equivalent, so the two copies of $\mathbf{X}$ have the same solution. They can therefore be written as
$$ \begin{cases} \mathbf{AX_1B}=\mathbf{E}_1 \\ \mathbf{CX_2D}=\mathbf{E}_2 \end{cases} $$First solve $\mathbf{AX_1B}=\mathbf{E}_1$:
$$ \begin{equation} \begin{aligned} \min_{\mathbf{X}_1,\mathbf{Z}_1}&~~\frac{1}{2}\|\mathbf{Z_1B-E_1} \|_F^2\\ \text{s.t.}&~~\mathbf{Z}_1=\mathbf{AX}_1 \end{aligned} \end{equation} $$Applying ADMM yields
$$ \begin{equation} \begin{aligned} \mathbf{Z}_1 &= ((\mathbf{E-CX_2D})\mathbf{B}^T+\eta\mathbf{AX_1-Q_1})(\mathbf{BB}^T+\eta\mathbf{I})^{-1}\\ \mathbf{X}_1 &=(\eta\mathbf{A^TA})^{-1}(\mathbf{A^TQ_1}+\eta\mathbf{A^TZ_1})\\ \mathbf{Q_1} &=\mathbf{Q_1}+\eta(\mathbf{Z}_1-\mathbf{AX_1}) \end{aligned} \end{equation} $$Likewise, solving $\mathbf{CX_2D}=\mathbf{E}_2$ by ADMM gives
$$ \begin{equation} \begin{aligned} \min_{\mathbf{X}_2,\mathbf{Z}_2}&~~\frac{1}{2}\|\mathbf{Z_2D-E_2} \|_F^2\\ \text{s.t.}&~~\mathbf{Z}_2=\mathbf{CX}_2 \end{aligned} \end{equation} $$Applying ADMM yields
$$ \begin{equation} \begin{aligned} \mathbf{Z}_2 &= ((\mathbf{E-AX_1B})\mathbf{D}^T+\eta\mathbf{CX_2-Q_2})(\mathbf{DD}^T+\eta\mathbf{I})^{-1}\\ \mathbf{X}_2 &=(\eta\mathbf{C^TC})^{-1}(\mathbf{C^TQ_2}+\eta\mathbf{C^TZ_2})\\ \mathbf{Q_2} &=\mathbf{Q_2}+\eta(\mathbf{Z}_2-\mathbf{CX_2}) \end{aligned} \end{equation} $$Iterating equation (2) and equation (4) in turn yields the final $\mathbf{X}_1$ and $\mathbf{X}_2$. Finally,
$$ \mathbf{X} = \eta\mathbf{X}_1+(1-\eta)\mathbf{X}_2 $$where $\eta>0$.
