Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Differentiation of matrix functionals using triangular factorization

Authors: F. R. de Hoog, R. S. Anderssen and M. A. Lukas
Journal: Math. Comp. 80 (2011), 1585-1600
MSC (2010): Primary 15A24; Secondary 15A15, 40C05, 65F30
Published electronically: January 6, 2011
MathSciNet review: 2785469
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: In various applications, it is necessary to differentiate a matrix functional $ w({\bf A}({\bf x}))$, where $ {\bf A}({\bf x})$ is a matrix depending on a parameter vector $ {\bf x}$. Usually, the functional itself can be readily computed from a triangular factorization of $ {\bf A}({\bf x})$. This paper develops several methods that also use the triangular factorization to efficiently evaluate the first and second derivatives of the functional. Both the full and sparse matrix situations are considered. There are similarities between these methods and algorithmic differentiation. However, the methodology developed here is explicit, leading to new algorithms. It is shown how the methods apply to several applications where the functional is a log determinant, including spline smoothing, covariance selection and restricted maximum likelihood.

References [Enhancements On Off] (What's this?)

  • 1. R. P. Barry and R. K. Pace.
    Monte Carlo estimates of the log determinant of large sparse matrices.
    J. Linear Algebra Appl., 28:41-54, 1999. MR 1670972
  • 2. R. A. Berk.
    Statistical Learning from a Regression Perspective.
    Springer-Verlag, New York, 2008.
  • 3. A. Dempster.
    Covariance selection.
    Biometrics, 28:57-175, 1972.
  • 4. J. J. Dongarra, I. S. Duff, D. C. Sorensen, and H. A. van der Vorst.
    Numerical Linear Algebra for High-Performance Computers.
    SIAM Press, Philidelphia, 1998. MR 1654239 (2000a:65002)
  • 5. A. M. Erisman and W. F. Tinney.
    On computing certain elements of the inverse of a sparse matrix.
    Communications ACM, 18:177-179, 1975. MR 0378372 (51:14540)
  • 6. A. George and J. Li.
    The evolution of the minimum degree ordering algorithm.
    SIAM Review, 31:1-19, 1989. MR 986480 (90g:65033)
  • 7. G. H. Golub and R. H. Plemmons.
    Large-scale geodetic least-squares adjustment by dissection and orthogonal decomposition.
    Lin. Algebra Appl., 34:3-27, 1980. MR 591422 (81k:86010)
  • 8. A. Griewank.
    Evaluating Derivatives.
    SIAM, Philadelphia, 2000. MR 1753583 (2001b:65003)
  • 9. D. A. Harville.
    Matrix Algebra from a Statistician's Perspective.
    Springer, New York, 1997. MR 1467237 (98k:15001)
  • 10. T. J. Hastie and R. J. Tibshirani.
    Generalized Additive Models.
    Chapman and Hall, London, 1990. MR 1082147 (92e:62117)
  • 11. M. F. Hutchinson and F. R. de Hoog.
    Smoothing noisy data with spline functions.
    Numer. Math., 47:99-106, 1985. MR 797880 (86j:65020)
  • 12. K. Kubota.
    Matrix inversion algorithms by means of automatic differentiation.
    Appl. Math. Lett., 7:19-22, 1994. MR 1350388
  • 13. S. L. Lauritzen.
    Graphical Models.
    Oxford University Press, New York, 1996. MR 1419991 (98g:62001)
  • 14. M. A. Lukas.
    Robust generalized cross-validation for choosing the regularization parameter.
    Inverse Problems, 22:1883-1902, 2006. MR 2261272 (2007j:62051)
  • 15. M. A. Lukas, F. R. de Hoog, and R. S. Anderssen.
    Efficient algorithms for robust generalized cross-validation spline smoothing, J. Comput. Appl. Math., 235:102-107, 2010. MR 2671036
  • 16. H. M. Markowitz.
    The elimination form of the inverse and its application to linear programming.
    Management Sci., 3:255-269, 1957. MR 0112244 (22:3098)
  • 17. S. G. Nash.
    A survey of truncated-Newton methods.
    J. Comp. Appl. Math., 124:45-59, 2000. MR 1803293
  • 18. H. Niessner and K. Reichert.
    On computing the inverse of a sparse matrix.
    Inter. J. Numer. Methods Eng., 19:1513-1526, 1983.
  • 19. P. Ravikumar, M. J. Wainwright, G. Raskutti, and B. Yu.
    High-dimensional covariance estimation by minimizing $ \ell_1$-penalized log-determinant divergence.
    IEEE, 2008.
  • 20. S. D. Silvey.
    Optimal Design.
    Chapman and Hall, London, 1980. MR 606742 (82d:62123)
  • 21. S. P. Smith.
    Differentiation of the Cholesky algorithm.
    J. Comp. Graph. Stat., 4:134-147, 1995.
  • 22. K. Takahashi, J. Fagan, and M. S. Chin.
    Formation of a sparse bus impedance matrix and its application to short circuit study.
    Power Industry Computer Applications Conf. Proc. Minneapolis, Minn., 8:63-69, June 4-6, 1973.
  • 23. G. Wahba.
    Bayesian confidence intervals for the cross-validated smoothing spline.
    J.R. Stat. Soc., Ser. B, 45:133-150, 1983. MR 701084 (84k:62054)
  • 24. F. V. Waugh and P. S. Dwyer.
    Compact computation of the inverse of a matrix.
    Annals Math. Stat., 16:259-271, 1945. MR 0013919 (7:218d)
  • 25. J. Whittaker.
    Graphical Models in Applied Multivariate Statistics.
    Wiley, Chichester, 1990. MR 1112133 (93f:62002)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 15A24, 15A15, 40C05, 65F30

Retrieve articles in all journals with MSC (2010): 15A24, 15A15, 40C05, 65F30

Additional Information

F. R. de Hoog
Affiliation: CSIRO Mathematics, Informatics and Statistics, GPO Box 664, Canberra, ACT 2601, Australia

R. S. Anderssen
Affiliation: CSIRO Mathematics, Informatics and Statistics, GPO Box 664, Canberra, ACT 2601, Australia

M. A. Lukas
Affiliation: Mathematics and Statistics, Murdoch University, South Street, Murdoch WA 6150, Australia

Keywords: Differentiation matrix functionals, triangular factorization, algorithmic differentiation, log-det relationships, robust generalized cross validation, smoothing splines, REML, covariance selection
Received by editor(s): May 5, 2009
Published electronically: January 6, 2011
Article copyright: © Copyright 2011 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society