Matrix Nearness Problems with Bregman Divergences
Authors:
- Inderjit S. DhillonIDInderjit S. Dhillon
- Joel A. TroppJTJoel A. Tropp
Top Cited Papers
- 1 January 2008
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Matrix Analysis and Applications
- Vol. 29 (4) , 1120-1146
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.Keywords
This publication has 23 references indexed in Scilit:
- Efficient rank reduction of correlation matricesLinear Algebra and its Applications, 2007
- Least-Squares Covariance Matrix AdjustmentSIAM Journal on Matrix Analysis and Applications, 2005
- Iterating Bregman RetractionsSIAM Journal on Optimization, 2003
- Computing the nearest correlation matrix--a problem from financeIMA Journal of Numerical Analysis, 2002
- Dykstras algorithm with bregman projections: A convergence proofOptimization, 2000
- A successive projection methodMathematical Programming, 1988
- An Algorithm for Restricted Least Squares RegressionJournal of the American Statistical Association, 1983
- $I$-Divergence Geometry of Probability Distributions and Minimization ProblemsThe Annals of Probability, 1975
- The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programmingUSSR Computational Mathematics and Mathematical Physics, 1967
- On a Least Squares Adjustment of a Sampled Frequency Table When the Expected Marginal Totals are KnownThe Annals of Mathematical Statistics, 1940