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)

 
 

 

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?)

  • [1] Peter J. Bickel and Elizaveta Levina, Covariance regularization by thresholding, Ann. Statist. 36 (2008), no. 6, 2577-2604. MR 2485008 (2010b:62197), https://doi.org/10.1214/08-AOS600
  • [2] Jens Peter Reus Christensen and Paul Ressel, Functions operating on positive definite matrices and a theorem of Schoenberg, Trans. Amer. Math. Soc. 243 (1978), 89-95. MR 502895 (81f:15031), https://doi.org/10.2307/1997755
  • [3] Dominique Guillot and Bala Rajaratnam, Retaining positive definiteness in thresholded matrices, Linear Algebra Appl. 436 (2012), no. 11, 4143-4160. MR 2915274, https://doi.org/10.1016/j.laa.2012.01.013
  • [4] Alfred Hero and Bala Rajaratnam, Large-scale correlation screening, J. Amer. Statist. Assoc. 106 (2011), no. 496, 1540-1552. MR 2896855, https://doi.org/10.1198/jasa.2011.tm11015
  • [5] Alfred Hero and Bala Rajaratnam, Hub discovery in partial correlation graphs, IEEE Trans. Inform. Theory 58 (2012), no. 9, 6064-6078. MR 2966078, https://doi.org/10.1109/TIT.2012.2200825
  • [6] Carl S. Herz, Fonctions opérant sur les fonctions définies-positives, Ann. Inst. Fourier (Grenoble) 13 (1963), 161-180 (French). MR 0152832 (27 #2806)
  • [7] Fumio Hiai, Monotonicity for entrywise functions of matrices, Linear Algebra Appl. 431 (2009), no. 8, 1125-1146. MR 2547900 (2010h:15011), https://doi.org/10.1016/j.laa.2009.04.001
  • [8] Roger A. Horn, The theory of infinitely divisible matrices and kernels, Trans. Amer. Math. Soc. 136 (1969), 269-286. MR 0264736 (41 #9327)
  • [9] Ai Li and Steve Horvath, Network neighborhood analysis with the multi-node topological overlap measure, Bioinformatics 23 (2007), no. 2, 222-231.
  • [10] G. G. Lorentz, Bernstein polynomials, 2nd ed., Chelsea Publishing Co., New York, 1986. MR 864976 (88a:41006)
  • [11] Walter Rudin, Positive definite sequences and absolutely monotonic functions, Duke Math. J 26 (1959), 617-622. MR 0109204 (22 #91)
  • [12] I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96-108. MR 0005922 (3,232c)
  • [13] J. Schur, Bemerkungen zur Theorie der beschränkten Bilinearformen mit unendlich vielen Veränderlichen, Journal für die reine und angewandte Mathematik 140 (1911), 1-28.
  • [14] Harkrishan Vasudeva, Positive definite matrices and absolutely monotonic functions, Indian J. Pure Appl. Math. 10 (1979), no. 7, 854-858. MR 537245 (81a:26007)
  • [15] Bin Zhang and Steve Horvath, A general framework for weighted gene co-expression network analysis, Stat. Appl. Genet. Mol. Biol. 4 (2005), Art. 17, 45 pp. (electronic). MR 2170433, https://doi.org/10.2202/1544-6115.1128

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.

American Mathematical Society