Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

Request Permissions   Purchase Content 
 

 

Functions preserving positive definiteness for sparse matrices


Authors: Dominique Guillot and Bala Rajaratnam
Journal: Trans. Amer. Math. Soc. 367 (2015), 627-649
MSC (2010): Primary 15B48, 26A48, 05C50, 15A42
DOI: https://doi.org/10.1090/S0002-9947-2014-06183-7
Published electronically: July 17, 2014
MathSciNet review: 3271272
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the problem of characterizing entrywise functions that preserve the cone of positive definite matrices when applied to every off-diagonal element. Our results extend theorems of Schoenberg [Duke Math. J., 9], Rudin [Duke Math. J., 26], Christensen and Ressel [Trans. Amer. Math. Soc., 243], and others, where similar problems were studied when the function is applied to all elements, including the diagonal ones. It is shown that functions that are guaranteed to preserve positive definiteness cannot at the same time induce sparsity, i.e., set elements to zero. These results have important implications for the regularization of positive definite matrices, where functions are often applied to only the off-diagonal elements to obtain sparse matrices with better properties (e.g., Markov random field/graphical model structure, better condition number). As a particular case, it is shown that soft-thresholding, a commonly used operation in modern high-dimensional probability and statistics, is not guaranteed to maintain positive definiteness, even if the original matrix is sparse. This result has a deep connection to graphs, and in particular, to the class of trees. We then proceed to fully characterize functions which do preserve positive definiteness. This characterization is in terms of absolutely monotonic functions and turns out to be quite different from the case when the function is also applied to diagonal elements. We conclude by giving bounds on the condition number of a matrix which guarantee that the regularized matrix is positive definite.


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


Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 15B48, 26A48, 05C50, 15A42

Retrieve articles in all journals with MSC (2010): 15B48, 26A48, 05C50, 15A42


Additional Information

Dominique Guillot
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305

Bala Rajaratnam
Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305

DOI: https://doi.org/10.1090/S0002-9947-2014-06183-7
Keywords: Positive definiteness, entrywise matrix functions, absolutely monotonic functions, hard-thresholding, soft-thresholding, sparse matrices, graphs, trees
Received by editor(s): October 1, 2012
Received by editor(s) in revised form: May 12, 2013
Published electronically: July 17, 2014
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.