In this paper, we aim to provide a systematic study of the relationship between Chernoff information and topological, as well as algebraic properties of the corresponding Gaussian tree graphs for the underlying graphical testing problems. We first show the relationship between Chernoff information and generalized eigenvalues of the associated covariance matrices. It is then proved that Chernoff information between two Gaussian trees sharing certain local subtree structures can be transformed into that of two smaller trees. Under our proposed grafting operations, bottleneck Gaussian trees, namely, Gaussian trees connected by one such operation, can thus be simplified into two 3-node Gaussian trees, whose topologies and edge weights are subject to the specifics of the operation. Thereafter, we provide a thorough study about how Chernoff information changes when small differences are accumulated into bigger ones via concatenated grafting operations. It is shown that the two Gaussian trees connected by more than one grafting operation may not have bigger Chernoff information than that of one grafting operation unless these grafting operations are separate and independent. At the end, we propose an optimal linear dimensional reduction method related to generalized eigenvalues.
In this paper, we are particularly interested in finding out the determining factors of Chernoff information in distinguishing Gaussian trees with the same amount of randomness, i.e. sharing the same determinant of their covariance matrices and normalized variances. The assumptions are for the ease of analysis and providing insights, as shown later in our results. Generalized eigenvalues of covariance matrices @math and @math are often considered when judging the difference between two Gaussian graphs @cite_13 @cite_15 . We tie the Chernoff information to generalized eigenvalues, which are further shown to be determined by local structure and topological differences between two graphs.
@cite_15 @cite_13
1716904016 2963754333 2079985400 2962826552
The Gaussian graphical model, a popular paradigm for studying relationship among variables in a wide range of applications, has attracted great attention in recent years. This paper considers a fundamental question: When is it possible to estimate low-dimensional parameters at parametric square-root rate in a large Gaussian graphical model? A novel regression approach is proposed to obtain asymptotically efficient estimation of each entry of a precision matrix under a sparseness condition relative to the sample size. When the precision matrix is not sufficiently sparse, or equivalently the sample size is not sufficiently large, a lower bound is established to show that it is no longer possible to achieve the parametric rate in the estimation of each entry. This lower bound result, which provides an answer to the delicate sample size question, is established with a novel construction of a subset of sparse precision matrices in an application of Le Cam's lemma. Moreover, the proposed estimator is proven to have optimal convergence rate when the parametric rate cannot be achieved, under a minimal sample requirement. The proposed estimator is applied to test the presence of an edge in the Gaussian graphical model or to recover the support of the entire model, to obtain adaptive rate-optimal estimation of the entire precision matrix as measured by the matrix @math operator norm and to make inference in latent variables in the graphical model. All of this is achieved under a sparsity condition on the precision matrix and a side condition on the range of its spectrum. This significantly relaxes the commonly imposed uniform signal strength condition on the precision matrix, irrepresentability condition on the Hessian tensor operator of the covariance matrix or the @math constraint on the precision matrix. Numerical results confirm our theoretical findings. The ROC curve of the proposed algorithm, Asymptotic Normal Thresholding (ANT), for support recovery significantly outperforms that of the popular GLasso algorithm. A number of problems in probability and statistics can be addressed using the multivariate normal (Gaussian) distribution. In the one-dimensional case, computing the probability for a given mean and variance simply requires the evaluation of the corresponding Gaussian density. In the @math -dimensional setting, however, it requires the inversion of an @math covariance matrix, @math , as well as the evaluation of its determinant, @math . In many cases, such as regression using Gaussian processes, the covariance matrix is of the form @math , where @math is computed using a specified covariance kernel which depends on the data and additional parameters (hyperparameters). The matrix @math is typically dense, causing standard direct methods for inversion and determinant evaluation to require @math work. This cost is prohibitive for large-scale modeling. Here, we show that for the most commonly used covariance functions, the matrix @math can be hierarchically factored into a product of block low-rank updates of the identity matrix, yielding an @math algorithm for inversion. More importantly, we show that this factorization enables the evaluation of the determinant @math , permitting the direct calculation of probabilities in high dimensions under fairly broad assumptions on the kernel defining @math . Our fast algorithm brings many problems in marginalization and the adaptation of hyperparameters within practical reach using a single CPU core. The combination of nearly optimal scaling in terms of problem size with high-performance computing resources will permit the modeling of previously intractable problems. We illustrate the performance of the scheme on standard covariance kernels. We consider the asymptotic fluctuation behavior of the largest eigenvalue of certain sample covariance matrices in the asymptotic regime where both dimensions of the corresponding data matrix go to infinity. More precisely, let X be an n x p matrix, and let its rows be i.i.d. complex normal vectors with mean 0 and covariance Σ p . We show that for a large class of covariance matrices £ p, the largest eigenvalue of X*X is asymptotically distributed (after recentering and rescaling) as the Tracy-Widom distribution that appears in the study of the Gaussian unitary ensemble. We give explicit formulas for the centering and scaling sequences that are easy to implement and involve only the spectral distribution of the population covariance, n and p. The main theorem applies to a number of covariance models found in applications. For example, well-behaved Toeplitz matrices as well as covariance matrices whose spectral distribution is a sum of atoms (under some conditions on the mass of the atoms) are among the models the theorem can handle. Generalizations of the theorem to certain spiked versions of our models and a.s. results about the largest eigenvalue are given. We also discuss a simple corollary that does not require normality of the entries of the data matrix and some consequences for applications in multivariate statistics. Gaussian graphical models are of great interest in statistical learning. Because the conditional independencies between different nodes correspond to zero entries in the inverse covariance matrix of the Gaussian distribution, one can learn the structure of the graph by estimating a sparse inverse covariance matrix from sample data, by solving a convex maximum likelihood problem with an l1-regularization term. In this paper, we propose a first-order method based on an alternating linearization technique that exploits the problem's special structure; in particular, the subproblems solved in each iteration have closed-form solutions. Moreover, our algorithm obtains an e-optimal solution in O(1 e) iterations. Numerical experiments on both synthetic and real data from gene association networks show that a practical version of this algorithm outperforms other competitive algorithms.