Minimum-norm solution of $A = X B + B^T X^T$

Question

Let $A, B, X$ be invertible square matrices, and let $A$ additionally be symmetric. I'd like to solve the following minimization problem:

$$\text{argmin}_X |\!| X |\!|_F \ \ \ \ \text{s.t.} \ \ \ \ A = X B + B^\top X^\top.$$

Are there any clever tricks for doing so? I see that since the RHS is linear in the elements of $X$, one could simply vectorize $X$ and solve the resulting linear equation, but this seems like a poor solution to me -- I'd like to either have a solution that uses the matrix structure of $A, B$ or know that no such solution exists.

Partial solution. It's clear that $X = \frac{1}{2} A B^{-1}$ satisfies the constraint. The rest of the solutions are of the form $X = \frac{1}{2} C B^{-1}$, where $\frac{1}{2}(C + C^\top) = A$. I just don't know how to minimize $|\!| X |\!|_F$ over this set.

Answer 1

I'll assume all matrices are real. The equation is equivalent to $$ V^TAV = V^TXUU^TBV + V^TB^TUU^TX^TV $$ for every orthogonal $U,V$. In particular, you can take an SVD of $B$, so that $U^TBV=S$ is diagonal. After setting $M=V^TAV$ and $Y=V^TXU$, with $\|Y\|=\|X\|$, the equation reads $$ M = YS + SY^T. $$ This is now easy to solve entrywise: $$ m_{ij} = y_{ij}s_j + s_iy_{ji} \quad \forall i,j. $$ We can consider only the equations with $i \leq j$, since both sides are symmetric, and solve these equations in the least-squares sense for each pair $(i,j)$ separately, since they are independent. Each is a $1\times 1$ or $2\times 1$ least-squares problem, which is easy to solve.

This idea should work also when $S$ and/or $A$ are singular, and produce a backward stable numerical method.

Answer 2

We assume that all the matrices are real.

$\textbf{Part 1}$. The general solution of the considered equation is $X=\dfrac{1}{2}(A+K)B^{-1}$ where $K$ is skew-symmetric. It remains to find a convenient $K$.

Let $f:K\in Skew\mapsto tr(XX^T)=\dfrac{1}{4}tr((A+K)B^{-1}B^{-T}(A-K))\in\mathbb{R}^+$.

$f(K)=\dfrac{1}{4}tr((A-K)(A+K)Z)$, where $Z=B^{-1}B^{-T}\in Sym^+$.

The tangent space to Skew in $K$ is Skew; then

$Df_K:S\in Skew\mapsto \dfrac{1}{4}tr((-SA+AS-SK-KS)Z)$ or

$-2Df_K(S)=tr(S(AZ+KZ))$. Assume that $f$ admits a local extremum in $X$.

Then, for every $S\in Skew$, $tr(S(AZ+KZ))=0$, that is, $AZ+KZ\in Sym$.

Thus (2) $KZ+ZK=-AZ+ZA$, where $Z$ is positive definite and $-AZ+ZA\in Skew$.

$\textbf{Part 2.}$ The equation (2) is solved -by me- here

Efficiently solve the Sylvester equation $AX+XA = C$ where $X$ is skew-symmetric

I show that (2) admits a unique skew-symmetric solution (here $X_0$) and that $X_0$ can be calculated using the spectral decomposition of $Z$.

$\textbf{Conclusion.}$ Note that $-2D^2f_K:(S,T)\in Skew^2\mapsto tr(STZ)$ and $-2D^2f_K(S,S)=tr(S^2Z)<0$, except when $S=0$ (because $S^2\in Sym^-$).

Thus $f(X_0)$ is a strict minimum of $f$. Since there is only one local extremum, we are done. $\square$