A low discrepancy sequence on graphs
From MaRDI portal
Abstract: Many applications such as election forecasting, environmental monitoring, health policy, and graph based machine learning require taking expectation of functions defined on the vertices of a graph. We describe a construction of a sampling scheme analogous to the so called Leja points in complex potential theory that can be proved to give low discrepancy estimates for the approximation of the expected value by the impirical expected value based on these points. In contrast to classical potential theory where the kernel is fixed and the equilibrium distribution depends upon the kernel, we fix a probability distribution and construct a kernel (which represents the graph structure) for which the equilibrium distribution is the given probability distribution. Our estimates do not depend upon the size of the graph.
Recommendations
Cites work
- scientific article; zbMATH DE number 1716483 (Why is no real title available?)
- scientific article; zbMATH DE number 5797591 (Why is no real title available?)
- scientific article; zbMATH DE number 3174696 (Why is no real title available?)
- scientific article; zbMATH DE number 3906565 (Why is no real title available?)
- scientific article; zbMATH DE number 1971048 (Why is no real title available?)
- scientific article; zbMATH DE number 3399629 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A general discrepancy theorem
- Collective dynamics of `small-world' networks
- Concerning nonnegative matrices and doubly stochastic matrices
- Discrete Signal Processing on Graphs: Sampling Theory
- Doubly stochastic normalization of the Gaussian kernel is robust to heteroskedastic noise
- Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
- Eigendecomposition-Free Sampling Set Selection for Graph Signals
- Equidistribution of points via energy
- Generalized designs on graphs: Sampling, spectra, symmetries
- Manifold learning with bi-stochastic kernels
- Multiscale data sampling and function extension
- Numerical integration on graphs: Where to sample and how to weigh
- On Leja sequences: some results and applications
- On the distribution of simple zeros of polynomials
- On the theory of potentials in locally compact spaces
- On the tractability of multivariate integration and approximation by neural networks
- People mover's distance: class level geometry using fast pairwise data adaptive transportation costs
- Quadrature points via heat kernel repulsion
- Random sampling of bandlimited signals on graphs
- Randomized Halton sequences
- Sampling in Paley-Wiener spaces on combinatorial graphs
- Sequences of well-distributed vertices on graphs and spectral bounds on optimal transport
- Sur certaines suites liées aux ensembles plans et leur application à la représentation conforme
- The DAD Theorem for Arbitrary Row Sums
- The Sinkhorn–Knopp Algorithm: Convergence and Applications
- Weighted polynomials, radial basis functions and potentials on locally compact spaces
Cited in
(2)
This page was built for publication: A low discrepancy sequence on graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1982596)
