skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Explore Research Products in the PAR
It may take a few hours for recently added research products to appear in PAR search results.


Title: Topological and Algebraic Properties of Chernoff Information between Gaussian Graphs
In this paper, we want to find out the determining factors of Chernoff information in distinguishing a set of Gaussian graphs. We find that Chernoff information of two Gaussian graphs can be determined by the generalized eigenvalues of their covariance matrices. We find that the unit generalized eigenvalues do not affect Chernoff information and their corresponding dimensions do not provide information for classification purpose. In addition, we can provide a partial ordering using Chernoff information between a series of Gaussian trees connected by independent grafting operations. By exploiting relationship between generalized eigenvalues and Chernoff information, we can do optimal classification linear dimension reduction with least loss of information for classification.  more » « less
Award ID(s):
1642991
PAR ID:
10125859
Author(s) / Creator(s):
; ; ;
Date Published:
Journal Name:
2018 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton)
Page Range / eLocation ID:
670 to 675
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; (, Journal of Fourier Analysis and Applications)
    null (Ed.)
    Abstract We introduce a set of novel multiscale basis transforms for signals on graphs that utilize their “dual” domains by incorporating the “natural” distances between graph Laplacian eigenvectors, rather than simply using the eigenvalue ordering. These basis dictionaries can be seen as generalizations of the classical Shannon wavelet packet dictionary to arbitrary graphs, and do not rely on the frequency interpretation of Laplacian eigenvalues. We describe the algorithms (involving either vector rotations or orthogonalizations) to construct these basis dictionaries, use them to efficiently approximate graph signals through the best basis search, and demonstrate the strengths of these basis dictionaries for graph signals measured on sunflower graphs and street networks. 
    more » « less
  2. ; ; (, Numerical Linear Algebra with Applications)
    Abstract The QZ algorithm computes the generalized Schur form of a matrix pencil. It is an iterative algorithm and, at some point, it must decide when to deflate, that is when a generalized eigenvalue has converged and to move on to another one. Choosing a deflation criterion that makes this decision is nontrivial. If it is too strict, the algorithm might waste iterations on already converged eigenvalues. If it is not strict enough, the computed eigenvalues might not have full accuracy. Additionally, the criterion should not be computationally expensive to evaluate. There are two commonly used criteria: theelementwisecriterion and thenormwisecriterion. This paper introduces a new deflation criterion based on the size of and the gap between the eigenvalues. We call this new deflation criterion thestrictcriterion. This new criterion for QZ is analogous to the criterion derived by Ahues and Tisseur for the QR algorithm. Theoretical arguments and numerical experiments suggest that the strict criterion outperforms the normwise and elementwise criteria in terms of accuracy. We also provide an example where the accuracy of the generalized eigenvalues using the elementwise or the normwise criteria is less than two digits whereas the strict criterion leads to generalized eigenvalues which are almost accurate to the working precision. Additionally, this paper evaluates some commonly used criteria for infinite eigenvalues. 
    more » « less
  3. ; ; ; (, Monthly Notices of the Royal Astronomical Society)
    ABSTRACT The future detection of gravitational waves (GWs) from a Galactic core-collapse supernova will provide information on the physics inside protoneutron stars (PNS). In this work, we apply three different classification methods for the PNS non-radial oscillation modes: Cowling classification, Generalized Cowling Nomenclature (GCN), and a classification based on modal properties (CBMP). Using PNS models from 3D simulations of core-collapse supernovae, we find that in the early stages of the PNS evolution, typically 0.4 s after the bounce, the Cowling classification is inconsistent, but the GCN and the CBMP provide complementary information that helps to understand the evolution of the modes. In the GCN, we note several avoided crossings as the mode frequencies evolve at early times, while the CBMP tracks the modes across the avoided crossings. We verify that the strongest emission of GWs by the PNS corresponds to the f mode in the GCN, indicating that the mode trapping region alternates between the core and the envelope at each avoided crossing. At later times, approximately 0.4 s after the bounce, the three classification methods present a similar description of the mode spectrum. We use our results to test universal relations for the PNS modes according to their classification and find that the behaviour of the universal relations for f and p modes is remarkably simple in the CBMP. 
    more » « less
  4. ; ; (, Information Processing Letters)
    In this paper, we derive parameterized Chernoff bounds and show their applications for simplifying the analysis of some well-known probabilistic algorithms and data structures. The parameterized Chernoff bounds we provide give probability bounds that are powers of two, with a clean formulation of the relation between the constant in the exponent and the relative distance from the mean. In addition, we provide new simplified analyses with these bounds for hash tables, randomized routing, and a simplified, non-recursive adaptation of the Floyd-Rivest selection algorithm. 
    more » « less
  5. ; (, SPAA 2020)
    null (Ed.)
    We consider the problem of finding lower bounds on the I/O complexity of arbitrary computations in a two level memory hierarchy. Executions of complex computations can be formalized as an evaluation order over the underlying computation graph. However, prior methods for finding I/O lower bounds leverage the graph structures for specific problems (e.g matrix multiplication) which cannot be applied to arbitrary graphs. In this paper, we first present a novel method to bound the I/O of any computation graph using the first few eigenvalues of the graph’s Laplacian. We further extend this bound to the parallel setting. This spectral bound is not only efficiently computable by power iteration, but can also be computed in closed form for graphs with known spectra. We apply our spectral method to compute closed-form analytical bounds on two computation graphs (the Bellman-Held-Karp algorithm for the traveling salesman problem and the Fast Fourier Transform), as well as provide a probabilistic bound for random Erdős Rényi graphs. We empirically validate our bound on four computation graphs, and find that our method provides tighter bounds than current empirical methods and behaves similarly to previously published I/O bounds. 
    more » « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email