Functions preserving positive definiteness for sparse matrices

DOI10.1090/S0002-9947-2014-06183-7zbMATH Open1305.15075arXiv1210.3894MaRDI QIDQ5496595FDOQ5496595

Authors: Dominique Guillot, Bala Rajaratnam 

Publication date: 2 February 2015

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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 emph{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.

Full work available at URL: https://arxiv.org/abs/1210.3894

Recommendations

• Preserving positivity for matrices with sparsity constraints
• Retaining positive definiteness in thresholded matrices
• Preserving positivity for rank-constrained matrices
• Sparse matrix decompositions and graph characterizations
• A panorama of positivity. I: Dimension free

zbMATH Keywords

graphssparse matricestreespositive definitenessabsolutely monotonic functionshard-thresholdingsoft-thresholdingentrywise matrix functions

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational methods for sparse matrices (65F50) Inequalities involving eigenvalues and eigenvectors (15A42) Positive matrices and their generalizations; cones of matrices (15B48) Monotonic functions, generalizations (26A48)

Cites Work

• Title not available (Why is that?)
• Covariance regularization by thresholding
• Positive definite functions on spheres
• Fonctions opérant sur les fonctions définies-positives
• Hub Discovery in Partial Correlation Graphs
• Large-Scale Correlation Screening
• Retaining positive definiteness in thresholded matrices
• Functions Operating on Positive Definite Matrices and a Theorem of Schoenberg
• The Theory of Infinitely Divisible Matrices and Kernels
• A General Framework for Weighted Gene Co-Expression Network Analysis
• Positive definite sequences and absolutely monotonic functions
• Monotonicity for entrywise functions of matrices
• Positive definite matrices and absolutely monotonic functions

Cited In (16)

• Positivity preservers forbidden to operate on diagonal blocks
• A sharp lower-tail bound for Gaussian maxima with application to bootstrap methods in high dimensions
• An inequality for tensor product of positive operators and its applications
• Continuity of positive nonlinear maps between $C^*$-algebras
• The critical exponent: a novel graph invariant
• A panorama of positivity. II: Fixed dimension
• Matrix positivity preservers in fixed dimension. I
• Moment-sequence transforms
• Inequalities for generalized matrix function and inner product
• Complete characterization of Hadamard powers preserving Loewner positivity, monotonicity, and convexity
• Schur polynomials and matrix positivity preservers
• Positive definite Hankel matrix completions and Hamburger moment completions
• Critical exponents of graphs
• Preserving positivity for rank-constrained matrices
• Matrix positivity preservers in fixed dimension
• Preserving positivity for matrices with sparsity constraints

This page was built for publication: Functions preserving positive definiteness for sparse matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496595)