Functions preserving positive definiteness for sparse matrices
HTML articles powered by AMS MathViewer
- by Dominique Guillot and Bala Rajaratnam PDF
- Trans. Amer. Math. Soc. 367 (2015), 627-649 Request permission
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
- Peter J. Bickel and Elizaveta Levina, Covariance regularization by thresholding, Ann. Statist. 36 (2008), no. 6, 2577–2604. MR 2485008, DOI 10.1214/08-AOS600
- 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, DOI 10.1090/S0002-9947-1978-0502895-2
- Dominique Guillot and Bala Rajaratnam, Retaining positive definiteness in thresholded matrices, Linear Algebra Appl. 436 (2012), no. 11, 4143–4160. MR 2915274, DOI 10.1016/j.laa.2012.01.013
- Alfred Hero and Bala Rajaratnam, Large-scale correlation screening, J. Amer. Statist. Assoc. 106 (2011), no. 496, 1540–1552. MR 2896855, DOI 10.1198/jasa.2011.tm11015
- Alfred Hero and Bala Rajaratnam, Hub discovery in partial correlation graphs, IEEE Trans. Inform. Theory 58 (2012), no. 9, 6064–6078. MR 2966078, DOI 10.1109/TIT.2012.2200825
- Carl S. Herz, Fonctions opérant sur les fonctions définies-positives, Ann. Inst. Fourier (Grenoble) 13 (1963), 161–180 (French). MR 152832, DOI 10.5802/aif.137
- Fumio Hiai, Monotonicity for entrywise functions of matrices, Linear Algebra Appl. 431 (2009), no. 8, 1125–1146. MR 2547900, DOI 10.1016/j.laa.2009.04.001
- Roger A. Horn, The theory of infinitely divisible matrices and kernels, Trans. Amer. Math. Soc. 136 (1969), 269–286. MR 264736, DOI 10.1090/S0002-9947-1969-0264736-5
- Ai Li and Steve Horvath, Network neighborhood analysis with the multi-node topological overlap measure, Bioinformatics 23 (2007), no. 2, 222–231.
- G. G. Lorentz, Bernstein polynomials, 2nd ed., Chelsea Publishing Co., New York, 1986. MR 864976
- Walter Rudin, Positive definite sequences and absolutely monotonic functions, Duke Math. J. 26 (1959), 617–622. MR 109204
- I. J. Schoenberg, Positive definite functions on spheres, Duke Math. J. 9 (1942), 96–108. MR 5922, DOI 10.1215/S0012-7094-42-00908-6
- 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.
- Harkrishan Vasudeva, Positive definite matrices and absolutely monotonic functions, Indian J. Pure Appl. Math. 10 (1979), no. 7, 854–858. MR 537245
- 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. MR 2170433, DOI 10.2202/1544-6115.1128
Additional Information
- Dominique Guillot
- Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
- MR Author ID: 772714
- Bala Rajaratnam
- Affiliation: Department of Mathematics, Stanford University, Stanford, California 94305
- MR Author ID: 861028
- Received by editor(s): October 1, 2012
- Received by editor(s) in revised form: May 12, 2013
- Published electronically: July 17, 2014
- © Copyright 2014
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication. - 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
- MathSciNet review: 3271272