  Approximate Simultaneous Diagonalization (ASD) is a problem to find a common
similarity transformation which approximately diagonalizes a given
square-matrix tuple. Many data science problems have been reduced into ASD
through ingenious modelling. For ASD, the so-called Jacobi-like methods have
been extensively used. However, the methods have no guarantee to suppress the
magnitude of off-diagonal entries of the transformed tuple even if the given
tuple has a common exact diagonalizer, i.e., the given tuple is simultaneously
diagonalizable. In this paper, to establish an alternative powerful strategy
for ASD, we present a novel two-step strategy, called
Approximate-Then-Diagonalize-Simultaneously (ATDS) algorithm. The ATDS
algorithm decomposes ASD into (Step 1) finding a simultaneously diagonalizable
tuple near the given one; and (Step 2) finding a common similarity
transformation which diagonalizes exactly the tuple obtained in Step 1. The
proposed approach to Step 1 is realized by solving a Structured Low-Rank
Approximation (SLRA) with Cadzow's algorithm. In Step 2, by exploiting the idea
in the constructive proof regarding the conditions for the exact simultaneous
diagonalizability, we obtain a common exact diagonalizer of the obtained tuple
in Step 1 as a solution for the original ASD. Unlike the Jacobi-like methods,
the ATDS algorithm has a guarantee to find a common exact diagonalizer if the
given tuple happens to be simultaneously diagonalizable. Numerical experiments
show that the ATDS algorithm achieves better performance than the Jacobi-like
methods.
