An official website of the United States government
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $$n^{1.5}$$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $$(1 \pm \delta)$$ approximation to the determinant of any SDDM matrix with constant probability in about $$n^2 \delta^{-2}$$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $$n^2 \delta^{-2}$$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $$\delta$$ from the $$w$$-uniform distribution .
more »
« less
The Sixth Moment of Random Determinants
We determine the sixth moment of the determinant of an asymmetric n×n random matrix where the entries are drawn independently from an arbitrary distribution Ω over R with mean 0. Furthermore, we derive the asymptotic behavior of the sixth moment of the determinant as the size of the matrix tends to infinity.
more »
« less
- Award ID(s):
- 2008920
- PAR ID:
- 10483219
- Publisher / Repository:
- University of Waterloo
- Date Published:
- Journal Name:
- Journal of integer sequences
- ISSN:
- 1530-7638
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
The natural determinant reference (NDR) or principal natural determinant is the Slater determinant comprised of the N most strongly occupied natural orbitals of an N-electron state of interest. Unlike the Kohn–Sham (KS) determinant, which yields the exact ground-state density, the NDR only yields the best idempotent approximation to the interacting one-particle reduced density matrix, but it is well-defined in common atom-centered basis sets and is representation-invariant. We show that the under-determination problem of prior attempts to define a ground-state energy functional of the NDR is overcome in a grand-canonical ensemble framework at the zero-temperature limit. The resulting grand potential functional of the NDR ensemble affords the variational determination of the ground state energy, its NDR (ensemble), and select ionization potentials and electron affinities. The NDR functional theory can be viewed as an “exactification” of orbital optimization and empirical generalized KS methods. NDR functionals depending on the noninteracting Hamiltonian do not require troublesome KS-inversion or optimized effective potentials.more » « less
-
Metal-fullerene compounds are characterized by significant electron transfer to the fullerene cage, giving rise to an electric dipole moment. We use the method of electrostatic beam deflection to verify whether such reactions take place within superfluid helium nanodroplets between an embedded C 60 molecule and either alkali (heliophobic) or rare-earth (heliophilic) atoms. The two cases lead to distinctly different outcomes: C 60 Na n ( n = 1–4) display no discernable dipole moment, while C 60 Yb is strongly polar. This suggests that the fullerene and small alkali clusters fail to form a charge-transfer bond in the helium matrix despite their strong van der Waals attraction. The C 60 Yb dipole moment, on the other hand, is in agreement with the value expected for an ionic complex.more » « less
-
We study algorithms for approximating the spectral density (i.e., the eigenvalue distribution) of a symmetric matrix A ∈ ℝn×n that is accessed through matrix-vector product queries. Recent work has analyzed popular Krylov subspace methods for this problem, showing that they output an ∈ · || A||2 error approximation to the spectral density in the Wasserstein-1 metric using O (1/∈ ) matrix-vector products. By combining a previously studied Chebyshev polynomial moment matching method with a deflation step that approximately projects off the largest magnitude eigendirections of A before estimating the spectral density, we give an improved error bound of ∈ · σℓ (A) using O (ℓ log n + 1/∈ ) matrix-vector products, where σℓ (A) is the ℓth largest singular value of A. In the common case when A exhibits fast singular value decay and so σℓ (A) « ||A||2, our bound can be much stronger than prior work. We also show that it is nearly tight: any algorithm giving error ∈ · σℓ (A) must use Ω(ℓ + 1/∈ ) matrix-vector products. We further show that the popular Stochastic Lanczos Quadrature (SLQ) method essentially matches the above bound for any choice of parameter ℓ, even though SLQ itself is parameter-free and performs no explicit deflation. Our bound helps to explain the strong practical performance and observed ‘spectrum adaptive’ nature of SLQ, and motivates a simple variant of the method that achieves an even tighter error bound. Technically, our results require a careful analysis of how eigenvalues and eigenvectors are approximated by (block) Krylov subspace methods, which may be of independent interest. Our error bound for SLQ leverages an analysis of the method that views it as an implicit polynomial moment matching method, along with recent results on low-rank approximation with single-vector Krylov methods. We use these results to show that the method can perform ‘implicit deflation’ as part of moment matching.more » « less
-
We formulate Wyner's common information for random vectors x ϵ R n with joint Gaussian density. We show that finding the common information of Gaussian vectors is equivalent to maximizing a log-determinant of the additive Gaussian noise covariance matrix. We coin such optimization problem as a constrained minimum determinant factor analysis (CMDFA) problem. The convexity of such problem with necessary and sufficient conditions on CMDFA solution is shown. We study the algebraic properties of CMDFA solution space, through which we study two sparse Gaussian graphical models, namely, latent Gaussian stars, and explicit Gaussian chains. Interestingly, we show that depending on pairwise covariance values in a Gaussian graphical structure, one may not always end up with the same parameters and structure for CMDFA solution as those found via graphical learning algorithms. In addition, our results suggest that Gaussian chains have little room left for dimension reduction in terms of the number of latent variables required in their CMDFA solutions.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
