An official website of the United States government
The cumulative empirical spectral measure (CESM) $$\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$$ of a $$n\times n$$ symmetric matrix $$\mathbf{A}$$ is defined as the fraction of eigenvalues of $$\mathbf{A}$$ less than a given threshold, i.e., $$\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$$. Spectral sums $$\operatorname{tr}(f[\mathbf{A}])$$ can be computed as the Riemann–Stieltjes integral of $$f$$ against $$\Phi[\mathbf{A}]$$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $$t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$$ with probability at least $$1-\eta$$, by applying the Lanczos algorithm for $$\lceil 12 t^{-1} + \frac{1}{2} \rceil$$ iterations to $$\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments.
more »
« less
Long-term accuracy of numerical approximations of SPDEs with the stochastic Navier–Stokes equations as a paradigm
Abstract This work introduces a general framework for establishing the long time accuracy for approximations of Markovian dynamical systems on separable Banach spaces. Our results illuminate the role that a certain uniformity in Wasserstein contraction rates for the approximating dynamics bears on long time accuracy estimates. In particular, our approach yields weak consistency bounds on $${\mathbb{R}}^{+}$$ while providing a means to sidestepping a commonly occurring situation where certain higher order moment bounds are unavailable for the approximating dynamics. Additionally, to facilitate the analytical core of our approach, we develop a refinement of certain ‘weak Harris theorems’. This extension expands the scope of applicability of such Wasserstein contraction estimates to a variety of interesting stochastic partial differential equation examples involving weaker dissipation or stronger nonlinearity than would be covered by the existing literature. As a guiding and paradigmatic example, we apply our formalism to the stochastic 2D Navier–Stokes equations and to a semi-implicit in time and spectral Galerkin in space numerical approximation of this system. In the case of a numerical approximation, we establish quantitative estimates on the approximation of invariant measures as well as prove weak consistency on $${\mathbb{R}}^{+}$$. To develop these numerical analysis results, we provide a refinement of $$L^{2}_{x}$$ accuracy bounds in comparison to the existing literature, which are results of independent interest.
more »
« less
- PAR ID:
- 10531808
- Publisher / Repository:
- IMAJNA
- Date Published:
- Journal Name:
- IMA Journal of Numerical Analysis
- ISSN:
- 0272-4979
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We present a mixed finite element method for approximating a fourth-order elliptic partial differential equation (PDE), the Kirchhoff plate equation, on a surface embedded in $${\mathbb {R}}^{3}$$, with or without boundary. Error estimates are given in mesh-dependent norms that account for the surface approximation and the approximation of the surface PDE. The method is built on the classic Hellan–Herrmann–Johnson method (for flat domains), and convergence is established for $$C^{k+1}$$ surfaces, with degree $$k$$ (Lagrangian, parametrically curved) approximation of the surface, for any $$k \geqslant 1$$. Mixed boundary conditions are allowed, including clamped, simply-supported and free conditions; if free conditions are present then the surface must be at least $$C^{2,1}$$. The framework uses tools from differential geometry and is directly related to the seminal work of Dziuk, G. (1988) Finite elements for the Beltrami operator on arbitrary surfaces. Partial Differential Equations and Calculus of Variations, vol. 1357 (S. Hildebrandt & R. Leis eds). Berlin, Heidelberg: Springer, pp. 142–155. for approximating the Laplace–Beltrami equation. The analysis here is the first to handle the full surface Hessian operator directly. Numerical examples are given on nontrivial surfaces that demonstrate our convergence estimates. In addition, we show how the surface biharmonic equation can be solved with this method.more » « less
-
We study lower bounds for the problem of approximating a one dimensional distribution given (noisy) measurements of its moments. We show that there are distributions on $[-1,1]$ that cannot be approximated to accuracy $$\epsilon$$ in Wasserstein-1 distance even if we know \emph{all} of their moments to multiplicative accuracy $$(1\pm2^{-\Omega(1/\epsilon)})$$; this result matches an upper bound of Kong and Valiant [Annals of Statistics, 2017]. To obtain our result, we provide a hard instance involving distributions induced by the eigenvalue spectra of carefully constructed graph adjacency matrices. Efficiently approximating such spectra in Wasserstein-1 distance is a well-studied algorithmic problem, and a recent result of Cohen-Steiner et al. [KDD 2018] gives a method based on accurately approximating spectral moments using $$2^{O(1/\epsilon)}$$ random walks initiated at uniformly random nodes in the graph.As a strengthening of our main result, we show that improving the dependence on $$1/\epsilon$$ in this result would require a new algorithmic approach. Specifically, no algorithm can compute an $$\epsilon$$-accurate approximation to the spectrum of a normalized graph adjacency matrix with constant probability, even when given the transcript of $$2^{\Omega(1/\epsilon)}$$ random walks of length $$2^{\Omega(1/\epsilon)}$$ started at random nodes.more » « less
-
Abstract When implementing Markov Chain Monte Carlo (MCMC) algorithms, perturbation caused by numerical errors is sometimes inevitable. This paper studies how the perturbation of MCMC affects the convergence speed and approximation accuracy. Our results show that when the original Markov chain converges to stationarity fast enough and the perturbed transition kernel is a good approximation to the original transition kernel, the corresponding perturbed sampler has fast convergence speed and high approximation accuracy as well. Our convergence analysis is conducted under either the Wasserstein metric or the$$\chi^2$$metric, both are widely used in the literature. The results can be extended to obtain non-asymptotic error bounds for MCMC estimators. We demonstrate how to apply our convergence and approximation results to the analysis of specific sampling algorithms, including Random walk Metropolis, Metropolis adjusted Langevin algorithm with perturbed target densities, and parallel tempering Monte Carlo with perturbed densities. Finally, we present some simple numerical examples to verify our theoretical claims.more » « less
-
In this paper, we present a sharper version of the results in the paper Dimension independent bounds for general shallow networks; Neural Networks, \textbf{123} (2020), 142-152. Let $$\mathbb{X}$$ and $$\mathbb{Y}$$ be compact metric spaces. We consider approximation of functions of the form $$ x\mapsto\int_{\mathbb{Y}} G( x, y)d\tau( y)$$, $$ x\in\mathbb{X}$$, by $$G$$-networks of the form $$ x\mapsto \sum_{k=1}^n a_kG( x, y_k)$$, $$ y_1,\cdots, y_n\in\mathbb{Y}$$, $$a_1,\cdots, a_n\in\mathbb{R}$$. Defining the dimensions of $$\mathbb{X}$$ and $$\mathbb{Y}$$ in terms of covering numbers, we obtain dimension independent bounds on the degree of approximation in terms of $$n$$, where also the constants involved are all dependent at most polynomially on the dimensions. Applications include approximation by power rectified linear unit networks, zonal function networks, certain radial basis function networks as well as the important problem of function extension to higher dimensional spaces.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imanum/drae043
