Nearest matrix orthogonally similar to a given matrix

Question

Given $A,B\in\Bbb R^{n\times n}$ is there technique find $$\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_F\mbox{ or }\min_{ T\in O(n,\Bbb R)}\|A-TBT^{-1}\|_2$$ within additive approximation error in $\epsilon>0$ in $O\big(\big(\frac{n\cdot\log(\|A\|_2\|B\|_2)}\epsilon\big)^c\big)$ time at fixed $c>0$?

Answer 1

Not a full answer, but some pointers on how to get a numerical method: If $\|\cdot\|_2$ denotes the spectral norm, then, by unitary invariance, your problem is equal to $$ \min_{T\in O(n)}\|AT-TB\|_2. $$ As such, the objective is the concatenation of the linear map $T\mapsto AT-TB$ and the norm and hence, convex. Subgradients of the objective can be computed with the help of

Watson, G. Alistair. "Characterization of the subdifferential of some matrix norms." Linear algebra and its applications 170 (1992): 33-45. https://doi.org/10.1016/0024-3795(92)90407-2

and the subgradient chain rule.

To deal with the constraint the $T$ is orthogonal seems possible, e.g. there is

Abrudan, Traian E., Jan Eriksson, and Visa Koivunen. "Steepest descent algorithms for optimization under unitary matrix constraint." IEEE Transactions on Signal Processing 56.3 (2008): 1134-1147. http://dx.doi.org/10.1109/TSP.2007.908999

I did not check how the optimality conditions arising from the respective Lagrangian $$ L(T,\Lambda) = \|AT-TB\|_2 + \langle \Lambda,T^T T - I\rangle $$ look like, though…

Note that the Frobenius norm is also unitarily invariant, so you can do the same in this case and minimize $\|AT-TB\|_F^2$ instead, which is also a convex function in $T$. While these reformulations are equivalent, it does not mean that the objective functions are the same: they only coincide on the constraint set.

$\newcommand{\tr}{\operatorname{tr}}$ Here is the optimality system in the case of the Frobenius norm: We use the formulation $$ \min_T \tfrac12\|AT-TB\|_F^2\ \text{ s.t. }\ T^TT-I=0 $$ and form the Lagrangian (using Igor's derivation) $$ L(T,\Lambda) = \tfrac12\|A\|_F^2 + \tfrac12\|B\|_F^2 - \tr(ATB^T T^T) - \tr(\Lambda^T(T^T T-I)). $$ Using the identities $$ \partial_X(\tr(AXBX^TC)) = A^TC^TXB + CAXB $$ and $$ \partial_X(\tr(XX^TB)) = \partial_X(\tr(X^TBX)) = BX+B^TX $$ from the Matrix Cookbook we get the optimality conditions $$ \begin{split} \partial_\Lambda L & = T^T T-I = 0\\ \partial_T L & = -2(A^T TB^T + ATB) + \Lambda T + \Lambda^T T = 0. \end{split} $$ Any idea, how to solve this?

Answer 2

Depends what you mean by "technique". Your problem is a quadratically constrained quadratic program. To be precise, the objective function is

$$\mbox{tr} (A-TBT^t)(A^t - TB^t T^t) = \mbox{tr} ( AA^t + TBB^tT^t - A TB^t T^t - TBT^t A^t) =\\ = \|A\|_F^2 + \|B\|_F^2 - 2 \mbox{tr} (ATB^t T^t),$$

so you are trying to maximize the trace of $ATB^t T^t$ under the constraints $TT^t = I.$ Neither the objective nor the constraints are convex, so I would not be too hopeful.

Answer 3

This is really just a very long comment.

First, if you haven't run across the Orthogonal Procrustes Problem before, you may find it interesting. (It's very similar, and has an efficient algorithm.)

Second, a little observation. As Igor Rivin points out, this problem is equivalent to maximizing $$\max_{ T\in O(n,\Bbb R)} \mathrm{Tr}[TB^{t}T^{t}A]$$

Suppose we have the singular value decompositions: $$ A = U_1 \Sigma_1 V_1 $$ $$ B = U_2 \Sigma_2 V_2 $$ Then $$ TB^{t}T^{-1}A = T V_2^{t}\Sigma_2 U_2^{t}T^{t} U_1 \Sigma_1 V_1 $$ If we set $T=U_1U_2^t$, then $$ TB^{t}T^{-1}A = T V_2^{t}\Sigma_2\Sigma_1 V_1 $$ I suspect that aligning the singular values this way (i.e., in the $\Sigma_2\Sigma_1$ term, we multiply together the two largest singular values, etc) ought to maximize the trace.

Answer 4

Regardless of the objective function, the constraints are non-convex, so the overall optimization problem is non-convex.

Solve it using numerical optimization on matrix manifolds, specifically, the Grassmann manifold to handle the orthonormal constraint. See "Optimization Algorithms on Matrix Manifolds", P.-A. Absil, Robert Mahony, Rodolphe Sepulchre, Princeton University Press, 2007, full text freely available online at https://press.princeton.edu/absil .

The numerical optimization on matrix manifold can be performed using Manopt http://www.manopt.org/tutorial.html#costdescription using the "built-in" Grassmann manifold http://www.manopt.org/reference/manopt/manifolds/grassmann/grassmannfactory.html . You only need to provide objective function and (optionally) gradient calculation in Euclidean Space, i.e., ignoring the manifold constraint. You can not be assured to find a global minimum; at best, you will find a local minimum which may not be global.

Alternatively, you can solve with a general non-convex optimization solver, imposing the nonlinear equality constraints $T^TT = I$. This is better than directly numerically solving for derivative of Lagrangian = 0, because the numerical solver will be in effect doing this while (presuming trust region or line search method is used) rolling downhill, so to speak, and therefore more likely to get to at least a local minimum, rather than a local maximum, and if using a second order method, rather than a saddle point.

Answer 5

Using the spectral norm, we have the following optimization problem in matrix $\mathrm X \in \mathbb R^{n \times n}$

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

where matrices $\mathrm A, \mathrm B \in \mathbb R^{n \times n}$ are given. Introducing variable $t \in \mathbb R$ and rewriting in epigraph form,

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \| \mathrm A \mathrm X - \mathrm X \mathrm B \|_2 \leq t\\ & \mathrm X^\top \mathrm X = \mathrm I_n\end{array}$$

Note that $\| \mathrm A \mathrm X - \mathrm X \mathrm B \|_2 \leq t$ is equivalent to

$$t^2 \mathrm I_n - \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right)^\top \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right) \succeq \mathrm O_n$$

Dividing both sides by $t > 0$,

$$t \, \mathrm I_n - \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right)^\top \left( t \, \mathrm I_n \right)^{-1} \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right) \succeq \mathrm O_n$$

Using the Schur complement test for positive semidefiniteness, we obtain the following optimization problem in matrix $\mathrm X \in \mathbb R^{n \times n}$ and scalar $t > 0$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \begin{bmatrix} t \, \mathrm I_n & \mathrm A \mathrm X - \mathrm X \mathrm B\\ \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right)^\top & t \, \mathrm I_n\end{bmatrix} \succeq \mathrm O_{2n}\\ & \mathrm X^\top \mathrm X = \mathrm I_n\end{array}$$

Relaxing the equality constraint $\mathrm X^\top \mathrm X = \mathrm I_n$, we obtain $\mathrm X^\top \mathrm X \preceq \mathrm I_n$, a linear matrix inequality (LMI) that can be rewritten as follows

$$\begin{bmatrix} \mathrm I_n & \mathrm X\\ \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{2n}$$

Thus, the relaxation of the original optimization problem is a (convex) semidefinite program (SDP) in matrix $\mathrm X \in \mathbb R^{n \times n}$ and scalar $t > 0$

$$\begin{array}{ll} \text{minimize} & t\\ \text{subject to} & \begin{bmatrix} t \, \mathrm I_n & \mathrm A \mathrm X - \mathrm X \mathrm B & & \\ \left( \mathrm A \mathrm X - \mathrm X \mathrm B \right)^\top & t \, \mathrm I_n & & \\ & & \mathrm I_n & \mathrm X\\ & & \mathrm X^\top & \mathrm I_n\end{bmatrix} \succeq \mathrm O_{4n}\end{array}$$

It remains to be determined whether this relaxation is actually useful.