A Bregman extension of quasi-Newton updates I: an information geometrical framework

References

• Amari , S. 1995 . Information geometry of the EM and em algorithms for neural networks . Neural Networks , 8 ( 9 ) : 1379 – 1408 .
   Web of Science ®Google Scholar
• Amari , S. and Nagaoka , H. 2000 . “ Methods of Information Geometry ” . In Translations of Mathematical Monographs , Vol. 191 , Oxford : Oxford University Press .
   Google Scholar
• Banerjee , A. , Merugu , S. , Dhillon , I. and Ghosh , J. 2005 . Clustering with Bregman divergences . Journal of Machine Learning Research , 6 : 1705 – 1749 .
   Web of Science ®Google Scholar
• Basu , A. , Harris , I. R. , Hjort , N. L. and Jones , M. C. 1998 . Robust and efficient estimation by minimising a density power divergence . Biometrika , 85 ( 3 ) : 549 – 559 .
   Web of Science ®Google Scholar
• Bauschke , H. H. and Borwein , J. M. 1997 . Legendre functions and the method of random Bregman projections . Journal of Convex Analysis , 4 ( 1 ) : 27 – 67 .
   Google Scholar
• Bauschke , H. H. and Combettes , P. L. 2002 . Iterating Bregman retractions . SIAM Journal of Optimization , 13 ( 4 ) : 1159 – 1173 .
   Web of Science ®Google Scholar
• Bregman , L. M. 1967 . The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming . USSR Computational Mathematics and Mathematical Physics , 7 : 200 – 217 .
   Google Scholar
• Broyden , C. G. 1967 . Quasi-newton methods and their application to function minimisation . Mathematics of Computation , 21 ( 99 ) : 368 – 381 .
   Web of Science ®Google Scholar
• Cowell , R. G. , Dawid , A. P. , Lauritzen , S. L. and Spiegelhalter , D. J. 2007 . Probabilistic Networks and Expert Systems: Exact Computational Methods for Bayesian Networks , New York : Springer Publishing Company .
   Google Scholar
• Davidon , W. C. 1959 . “ Variable metric method for minimization ” . A.E.C. Research and Development Report, ANL-5990
   Google Scholar
• Dempster , A. P. 1972 . Covariance selection . Biometrics , 28 : 157 – 175 .
   Web of Science ®Google Scholar
• Dempster , A. P. , Laird , N. M. and Rubin , D. B. 1977 . Maximum likelihood from incomplete data via the em algorithm . Journal of the Royal Statistical Society B , 39 : 1 – 38 .
   Google Scholar
• Dhillon , I. S. and Tropp , J. A. 2007 . Matrix nearness problems with Bregman divergences . SIAM Journal on Matrix Analysis and Applications , 29 ( 4 ) : 1120 – 1146 .
   Web of Science ®Google Scholar
• Fletcher , R. 1991 . A new variational result for quasi-Newton formulae . SIAM Journal on Optimization , 1 : 18 – 21 .
   Google Scholar
• Fletcher , R. 1995 . An optimal positive definite update for sparse hessian matrices . SIAM Journal on Optimization , 5 : 192 – 218 .
   Web of Science ®Google Scholar
• Freund , Y. and Schapire , R. E. 1997 . A decision-theoretic generalization of on-line learning and an application to boosting . Journal of Computer and System Sciences , 55 ( 1 ) : 119 – 139 .
   Web of Science ®Google Scholar
• Fukuda , M. , Kojima , M. , Murota , K. and Nakata , K. 2000 . Exploiting sparsity in semidefinite programming via matrix completion I: General framework . SIAM Journal on Optimization , 11 ( 3 ) : 647 – 674 .
   Web of Science ®Google Scholar
• Gill , P. E. and Murray , W. 1972 . Quasi-Newton methods for unconstrained optimization . Journal of the Institute of Mathematics and its Applications , 9 : 91 – 108 .
   Google Scholar
• Golub , G. H. and Van Loan , C. F. 1996 . Matrix Computations , Baltimore, MD : Johns Hopkins University Press .
   Google Scholar
• Golumbic , M. C. 2004 . Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics, Vol. 57) , Amsterdam , , The Netherlands : North-Holland Publishing Co .
   Google Scholar
• Grone , R. , Johnson , C. R. , Sá , E. M. and Wolkowicz , H. 1984 . Positive definite completions of partial hermitian matrices . Linear Algebra and its Applications , 58 : 109 – 124 .
   Web of Science ®Google Scholar
• Güler , O. , Gürtuna , F. and Shevchenko , O. 2009 . Duality in quasi-Newton methods and new variational characterizations of the DFP and BFGS updates . Optimization Methods and Software , 24 ( 1 ) : 45 – 62 .
   Web of Science ®Google Scholar
• Kakihara , S. , Ohara , A. and Tsuchiya , T. “ Information geometry and primal–dual interior-point algorithms ” . Optimization Online, 2010, submitted for publication
   Google Scholar
• T. Kanamori and A. Ohara, A Bregman extension of quasi-Newton updates II: Convergence and robustness properties, arXiv:1010.2847v1, 2010
   Google Scholar
• Kobayashi , S. and Nomizu , K. 1996 . Foundations of Differential Geometry , New York : Wiley-Interscience .
   Google Scholar
• Kullback , S. and Leibler , R. A. 1951 . On information and sufficiency . The Annals of Mathematical Statistics , 22 ( 1 ) : 79 – 86 .
   Google Scholar
• Luenberger , D. and Ye , Y. 2008 . Linear and Nonlinear Programming , New York : Springer .
   Google Scholar
• McLachlan , G. J. and Krishnam , T. 2008 . The EM Algorithm and Extensions , 2 , New York : Wiley .
   Google Scholar
• Minami , M. and Eguchi , S. 2002 . Robust blind source separation by beta-divergence . Neural Computation , 14 ( 8 ) : 1859 – 1886 .
   Web of Science ®Google Scholar
• Murata , N. , Takenouchi , T. , Kanamori , T. and Eguchi , S. 2004 . Information geometry of U-boost and Bregman divergence . Neural Computation , 16 ( 7 ) : 1437 – 1481 .
   Web of Science ®Google Scholar
• Nocedal , J. 1980 . Updating quasi-newton matrices with limited storage . Mathematics of Computation , 35 ( 151 ) : 773 – 782 .
   Web of Science ®Google Scholar
• Nocedal , J. 1992 . Theory of algorithms for unconstrained optimization . Acta Numerica , 1 : 199 – 242 .
   Google Scholar
• Nocedal , J. and Wright , S. 1999 . Numerical Optimization , New York : Springer .
   Google Scholar
• Nocedal , J. and Yuan , Y.-X. 1993 . Analysis of a self-scaling quasi-Newton method . Mathematical Programming , 61 : 19 – 37 .
   Web of Science ®Google Scholar
• Ohara , A. 1999 . “ Information geometric analysis of an interior point method for semidefinite programming ” . In Geometry in Present Day Science , Edited by: Barndorff-Nielsen , O. E. and Vedel Jensen , E. B. 49 – 74 . Singapore : World Scientific .
   Google Scholar
• Ohara , A. and Eguchi , S. “ Geometry on positive definite matrices and V-potential function ” . Technical report, ISM Research Memo, 2005
   Google Scholar
• Oren , S. S. and Luenberger , D. G. 1974 . Self-scaling variable metric (ssvm) algorithms, part i. Criteria and sufficient conditions for scaling a class of algorithms . Management Science , 20 : 845 – 862 .
   Web of Science ®Google Scholar
• Rockafellar , R. T. 1970 . Convex Analysis , Princeton : Princeton University Press . Technical report, ISM Research Memo, 2005
   Google Scholar
• Sorensen , D. C. 1982 . Collinear scaling and sequential estimation in sparse optimization algorithm . Mathematical Programming Studies , 18 : 135 – 159 .
   Web of Science ®Google Scholar
• Toint , P. L. 1977 . On sparse and symmetric matrix updating subject to a linear equation . Mathematics of Computation , 31 : 954 – 961 .
   Web of Science ®Google Scholar
• Yamashita , N. 2008 . Sparse quasi-Newton updates with positive definite matrix completion . Mathematical Programming , 115 ( 1 ) : 1 – 30 .
   Web of Science ®Google Scholar