Matrix Nearness Problems with Bregman Divergences

Inderjit Dhillon, Joel Tropp

Abstract:   This paper discusses a new class of matrix nearness problems that measure approximation error using a directed distance measure called a Bregman divergence. Bregman divergences offer an important generalization of the squared Frobenius norm and relative entropy, and they all share fundamental geometric properties. In addition, these divergences are intimately connected with exponential families of probability distributions. Therefore, it is natural to study matrix approximation problems with respect to Bregman divergences. This article proposes a framework for studying these problems, discusses some specific matrix nearness problems, and provides algorithms for solving them numerically. These algorithms apply to many classical and novel problems, and they admit a striking geometric interpretation.

Download: pdf


  • Matrix Nearness Problems with Bregman Divergences (pdf, software)
    I. Dhillon, J. Tropp.
    SIAM Journal of Matrix Analysis and Applications (SIMAX) 29(4), pp. 1120-1146, November 2007.