Approximate Joint Matrix Triangularization
  We consider the problem of approximate joint triangularization of a set of
noisy jointly diagonalizable real matrices. Approximate joint triangularizers
are commonly used in the estimation of the joint eigenstructure of a set of
matrices, with applications in signal processing, linear algebra, and tensor
decomposition. By assuming the input matrices to be perturbations of
noise-free, simultaneously diagonalizable ground-truth matrices, the
approximate joint triangularizers are expected to be perturbations of the exact
joint triangularizers of the ground-truth matrices. We provide a priori and a
posteriori perturbation bounds on the `distance' between an approximate joint
triangularizer and its exact counterpart. The a priori bounds are theoretical
inequalities that involve functions of the ground-truth matrices and noise
matrices, whereas the a posteriori bounds are given in terms of observable
quantities that can be computed from the input matrices. From a practical
perspective, the problem of finding the best approximate joint triangularizer
of a set of noisy matrices amounts to solving a nonconvex optimization problem.
We show that, under a condition on the noise level of the input matrices, it is
possible to find a good initial triangularizer such that the solution obtained
by any local descent-type algorithm has certain global guarantees. Finally, we
discuss the application of approximate joint matrix triangularization to
canonical tensor decomposition and we derive novel estimation error bounds.
