A posteriori error bounds for joint matrix decomposition problems

Nicolò Colombo, Nikos Vlassis

Research output: Contribution to journalConference articlepeer-review

Abstract

Joint matrix triangularization is often used for estimating the joint eigenstructure of a set M of matrices, with applications in signal processing and machine learning. We consider the problem of approximate joint matrix triangularization when the matrices in M are jointly diagonalizable and real, but we only observe a set M′ of noise perturbed versions of the matrices in M. Our main result is a first-order upper bound on the distance between any approximate joint triangularizer of the matrices in M′ and any exact joint triangularizer of the matrices in M. The bound depends only on the observable matrices in M′ and the noise level. In particular, it does not depend on optimization specific properties of the triangularizer, such as its proximity to critical points, that are typical of existing bounds in the literature. To our knowledge, this is the first a posteriori bound for joint matrix decomposition. We demonstrate the bound on synthetic data for which the ground truth is known.

Original languageEnglish
Pages (from-to)4950-4957
Number of pages8
JournalADVANCES IN NEURAL INFORMATION PROCESSING SYSTEMS
Publication statusPublished - Dec 2016
Event30th Annual Conference on Neural Information Processing Systems, NIPS 2016 - Barcelona, Spain
Duration: 5 Dec 201610 Dec 2016

Cite this