Search

This paper studies the estimation of large precision matrices and Cholesky factors obtained by observing a Gaussian process at many locations. Under general assumptions on the precision and the observations, we show that the sample complexity scales poly-logarithmically with the size of the precision matrix and its Cholesky factor. The key challenge in these estimation tasks is the polynomial growth of the condition number of the target matrices with their size. For precision estimation, our theory hinges on an intuitive local regression technique on the lattice graph which exploits the approximate sparsity implied by the screening effect. For Cholesky factor estimation, we leverage a block-Cholesky decomposition recently used to establish complexity bounds for sparse Cholesky factorization., Comment: 28 pages

The aim of these notes is to demonstrate the potential for ideas in machine learning to impact on the fields of inverse problems and data assimilation. The perspective is one that is primarily aimed at researchers from inverse problems and/or data assimilation who wish to see a mathematical presentation of machine learning as it pertains to their fields. As a by-product, we include a succinct mathematical treatment of various topics in machine learning., Comment: 254 pages

This paper establishes optimal convergence rates for estimation of structured covariance operators of Gaussian processes. We study banded operators with kernels that decay rapidly off-the-diagonal and $L^q$-sparse operators with an unordered sparsity pattern. For these classes of operators, we find the minimax optimal rate of estimation in operator norm, identifying the fundamental dimension-free quantities that determine the sample complexity. In addition, we prove that tapering and thresholding estimators attain the optimal rate. The proof of the upper bound for tapering estimators requires novel techniques to circumvent the issue that discretization of a banded operator does not result, in general, in a banded covariance matrix. To derive lower bounds for banded and $L^q$-sparse classes, we introduce a general framework to lift theory from high-dimensional matrix estimation to the operator setting. Our work contributes to the growing literature on operator estimation and learning, building on ideas from high-dimensional statistics while also addressing new challenges that emerge in infinite dimension., Comment: 38 pages, 3 figures

This paper studies sparse covariance operator estimation for nonstationary Gaussian processes with sharply varying marginal variance and small correlation lengthscale. We introduce a covariance operator estimator that adaptively thresholds the sample covariance function using an estimate of the variance components. Building on recent results from empirical process theory, we derive an operator norm bound on the estimation error in terms of the sparsity level of the covariance and the expected supremum of the normalized process. Our theory and numerical simulations demonstrate the advantage of adaptive threshold estimators over universal threshold and sample covariance estimators in nonstationary settings., Comment: 38 pages, 5 figures

This is a concise mathematical introduction to Monte Carlo methods, a rich family of algorithms with far-reaching applications in science and engineering. Monte Carlo methods are an exciting subject for mathematical statisticians and computational and applied mathematicians: the design and analysis of modern algorithms are rooted in a broad mathematical toolbox that includes ergodic theory of Markov chains, Hamiltonian dynamical systems, transport maps, stochastic differential equations, information theory, optimization, Riemannian geometry, and gradient flows, among many others. These lecture notes celebrate the breadth of mathematical ideas that have led to tangible advancements in Monte Carlo methods and their applications. To accommodate a diverse audience, the level of mathematical rigor varies from chapter to chapter, giving only an intuitive treatment to the most technically demanding subjects. The aim is not to be comprehensive or encyclopedic, but rather to illustrate some key principles in the design and analysis of Monte Carlo methods through a carefully-crafted choice of topics that emphasizes timeless over timely ideas. Algorithms are presented in a way that is conducive to conceptual understanding and mathematical analysis -- clarity and intuition are favored over state-of-the-art implementations that are harder to comprehend or rely on ad-hoc heuristics. To help readers navigate the expansive landscape of Monte Carlo methods, each algorithm is accompanied by a summary of its pros and cons, and by a discussion of the type of problems for which they are most useful. The presentation is self-contained, and therefore adequate for self-guided learning or as a teaching resource. Each chapter contains a section with bibliographic remarks that will be useful for those interested in conducting research on Monte Carlo methods and their applications., Comment: 150 pages, 21 figures

Modern data-driven surrogate models for weather forecasting provide accurate short-term predictions but inaccurate and nonphysical long-term forecasts. This paper investigates online weather prediction using machine learning surrogates supplemented with partial and noisy observations. We empirically demonstrate and theoretically justify that, despite the long-time instability of the surrogates and the sparsity of the observations, filtering estimates can remain accurate in the long-time horizon. As a case study, we integrate FourCastNet, a state-of-the-art weather surrogate model, within a variational data assimilation framework using partial, noisy ERA5 data. Our results show that filtering estimates remain accurate over a year-long assimilation window and provide effective initial conditions for forecasting tasks, including extreme event prediction.

The accurate characterisation of energy exchanges between nanoscale quantum systems and their environments is of paramount importance for quantum technologies, and central to quantum thermodynamics. Here, we show that, in order to accurately approximate steady-state heat currents via perturbative master equations, the coupling-induced reorganisation correction to the system's energy must be carefully taken into account. Not doing so, may yield sizeable errors, especially at low, or even moderate temperatures. In particular, we show how a 'reorganised master equation' can produce very accurate estimates for the heat currents when the reorganisation energy is weak and one works with environments with a broad spectrum. Notably, such master equation outperforms its 'non-reorganised' counterpart in the calculation of heat currents, at modelling dynamics, and at correctly capturing equilibration. This is so even if both types of equation are derived to the same order of perturbation theory. Most importantly, working with reorganised master equations does not involve additional complications when compared with alternative approaches. Also, invoking the secular approximation to secure thermodynamic consistency does not compromise their precision., Comment: 8 pages, 3 figures; comments welcome

This paper proposes novel noise-free Bayesian optimization strategies that rely on a random exploration step to enhance the accuracy of Gaussian process surrogate models. The new algorithms retain the ease of implementation of the classical GP-UCB algorithm, but the additional random exploration step accelerates their convergence, nearly achieving the optimal convergence rate. Furthermore, to facilitate Bayesian inference with an intractable likelihood, we propose to utilize optimization iterates for maximum a posteriori estimation to build a Gaussian process surrogate model for the unnormalized log-posterior density. We provide bounds for the Hellinger distance between the true and the approximate posterior distributions in terms of the number of design points. We demonstrate the effectiveness of our Bayesian optimization algorithms in non-convex benchmark objective functions, in a machine learning hyperparameter tuning problem, and in a black-box engineering design problem. The effectiveness of our posterior approximation approach is demonstrated in two Bayesian inference problems for parameters of dynamical systems.

This paper analyzes hierarchical Bayesian inverse problems using techniques from high-dimensional statistics. Our analysis leverages a property of hierarchical Bayesian regularizers that we call approximate decomposability to obtain non-asymptotic bounds on the reconstruction error attained by maximum a posteriori estimators. The new theory explains how hierarchical Bayesian models that exploit sparsity, group sparsity, and sparse representations of the unknown parameter can achieve accurate reconstructions in high-dimensional settings.

Gaussian process regression is a classical kernel method for function estimation and data interpolation. In large data applications, computational costs can be reduced using low-rank or sparse approximations of the kernel. This paper investigates the effect of such kernel approximations on the interpolation error. We introduce a unified framework to analyze Gaussian process regression under important classes of computational misspecification: Karhunen-Lo\`eve expansions that result in low-rank kernel approximations, multiscale wavelet expansions that induce sparsity in the covariance matrix, and finite element representations that induce sparsity in the precision matrix. Our theory also accounts for epistemic misspecification in the choice of kernel parameters.

This paper investigates covariance operator estimation via thresholding. For Gaussian random fields with approximately sparse covariance operators, we establish non-asymptotic bounds on the estimation error in terms of the sparsity level of the covariance and the expected supremum of the field. We prove that thresholded estimators enjoy an exponential improvement in sample complexity compared with the standard sample covariance estimator if the field has a small correlation lengthscale. As an application of the theory, we study thresholded estimation of covariance operators within ensemble Kalman filters., Comment: 29 pages, 2 figures

Filtering is concerned with online estimation of the state of a dynamical system from partial and noisy observations. In applications where the state of the system is high dimensional, ensemble Kalman filters are often the method of choice. These algorithms rely on an ensemble of interacting particles to sequentially estimate the state as new observations become available. Despite the practical success of ensemble Kalman filters, theoretical understanding is hindered by the intricate dependence structure of the interacting particles. This paper investigates ensemble Kalman filters that incorporate an additional resampling step to break the dependency between particles. The new algorithm is amenable to a theoretical analysis that extends and improves upon those available for filters without resampling, while also performing well in numerical examples., Comment: 32 pages, 5 figures

This paper analyzes a popular computational framework to solve infinite-dimensional Bayesian inverse problems, discretizing the prior and the forward model in a finite-dimensional weighted inner product space. We demonstrate the benefit of working on a weighted space by establishing operator-norm bounds for finite element and graph-based discretizations of Mat\'ern-type priors and deconvolution forward models. For linear-Gaussian inverse problems, we develop a general theory to characterize the error in the approximation to the posterior. We also embed the computational framework into ensemble Kalman methods and MAP estimators for nonlinear inverse problems. Our operator-norm bounds for prior discretizations guarantee the scalability and accuracy of these algorithms under mesh refinement., Comment: 39 pages, 0 figures

This paper introduces a computational framework to reconstruct and forecast a partially observed state that evolves according to an unknown or expensive-to-simulate dynamical system. Our reduced-order autodifferentiable ensemble Kalman filters (ROAD-EnKFs) learn a latent low-dimensional surrogate model for the dynamics and a decoder that maps from the latent space to the state space. The learned dynamics and decoder are then used within an ensemble Kalman filter to reconstruct and forecast the state. Numerical experiments show that if the state dynamics exhibit a hidden low-dimensional structure, ROAD-EnKFs achieve higher accuracy at lower computational cost compared to existing methods. If such structure is not expressed in the latent state dynamics, ROAD-EnKFs achieve similar accuracy at lower cost, making them a promising approach for surrogate state reconstruction and forecasting.

We study a Jarzysnki type equality for work in systems that are monitored using non-projective unsharp measurements. The information acquired by the observer from the outcome $f$ of an energy measurement, and the subsequent conditioned normalized state $\hat \rho(t,f)$ evolved up to a final time $t$ are used to define work, as the difference between the final expectation value of the energy and the result $f$ of the measurement. The Jarzynski equality obtained depends on the coherences that the state develops during the process, the characteristics of the meter used to measure the energy, and the noise it induces into the system. We analyze those contributions in some detail to unveil their role. We show that in very particular cases, but not in general, the effect of such noise gives a factor multiplying the result that would be obtained if projective measurements were used instead of non-projective ones. The unsharp character of the measurements used to monitor the energy of the system, which defines the resolution of the meter, leads to different scenarios of interest. In particular, if the distance between neighboring elements in the energy spectrum is much larger than the resolution of the meter, then a similar result to the projective measurement case is obtained, up to a multiplicative factor that depends on the meter. A more subtle situation arises in the opposite case in which measurements may be non-informative, i.e. they may not contribute to update the information about the system. In this case, a correction to the relation obtained in the non-overlapping case appears. We analyze the conditions in which such a correction becomes negligible. We also study the coherences, in terms of the relative entropy of coherence developed by the evolved post-measurement state. We illustrate the results by analyzing a two-level system monitored by a simple meter., Comment: 14 pages, 3 figures

During the last decades the industry has seen the number of Earth orbiting satellites rise, mostly due to the need to monitor Earth as well as to establish global communication networks. Nano, micro, and small satellites have been a prime tool for answering these needs, with large and mega constellations planned, leading to a potential launch gap. An effective and commercially appealing solution is the development of small launchers, as these can complement the current available launch opportunity offer, serving a large pool of different types of clients, with a flexible and custom service that large conventional launchers cannot adequately assure. Rocket Factory Augsburg has partnered with CEiiA for the development of several structures for the RFA One rocket. The objective has been the design of solutions that are low-cost, light, and custom-made, applying design and manufacturing concepts as well as technologies from other industries, like the aeronautical and automotive, to the aerospace one. This allows for the implementation of a New Space approach to the launcher segment, while also building a supply chain and a set of solutions that enables the industrialisation of such structures for this and future small launchers. The two main systems under development have been a versatile Kick-Stage, for payload carrying and orbit insertion, and a sturdy Payload Fairing. Even though the use of components off-the-shelf have been widely accepted in the space industry for satellites, these two systems pose different challenges as they must be: highly reliable during the most extreme conditions imposed by the launch, so that they can be considered safe to launch all types of payloads. This paper thus dives deep on the solutions developed in the last few years, presenting also lessons learned during the manufacturing and testing of these structures., Comment: 10 pages, 13 figures, Manuscript presented at the 73rd International Astronautical Congress, IAC 2022, Paris, France, 18 - 22 September 2022

This paper integrates manifold learning techniques within a \emph{Gaussian process upper confidence bound} algorithm to optimize an objective function on a manifold. Our approach is motivated by applications where a full representation of the manifold is not available and querying the objective is expensive. We rely on a point cloud of manifold samples to define a graph Gaussian process surrogate model for the objective. Query points are sequentially chosen using the posterior distribution of the surrogate model given all previous queries. We establish regret bounds in terms of the number of queries and the size of the point cloud. Several numerical examples complement the theory and illustrate the performance of our method.

Many modern algorithms for inverse problems and data assimilation rely on ensemble Kalman updates to blend prior predictions with observed data. Ensemble Kalman methods often perform well with a small ensemble size, which is essential in applications where generating each particle is costly. This paper develops a non-asymptotic analysis of ensemble Kalman updates that rigorously explains why a small ensemble size suffices if the prior covariance has moderate effective dimension due to fast spectrum decay or approximate sparsity. We present our theory in a unified framework, comparing several implementations of ensemble Kalman updates that use perturbed observations, square root filtering, and localization. As part of our analysis, we develop new dimension-free covariance estimation bounds for approximately sparse matrices that may be of independent interest.

In recent decades, science and engineering have been revolutionized by a momentous growth in the amount of available data. However, despite the unprecedented ease with which data are now collected and stored, labeling data by supplementing each feature with an informative tag remains to be challenging. Illustrative tasks where the labeling process requires expert knowledge or is tedious and time-consuming include labeling X-rays with a diagnosis, protein sequences with a protein type, texts by their topic, tweets by their sentiment, or videos by their genre. In these and numerous other examples, only a few features may be manually labeled due to cost and time constraints. How can we best propagate label information from a small number of expensive labeled features to a vast number of unlabeled ones? This is the question addressed by semi-supervised learning (SSL). This article overviews recent foundational developments on graph-based Bayesian SSL, a probabilistic framework for label propagation using similarities between features. SSL is an active research area and a thorough review of the extant literature is beyond the scope of this article. Our focus will be on topics drawn from our own research that illustrate the wide range of mathematical tools and ideas that underlie the rigorous study of the statistical accuracy and computational efficiency of graph-based Bayesian SSL., Comment: To appear in Notices of the AMS

This paper introduces a computational framework to incorporate flexible regularization techniques in ensemble Kalman methods for nonlinear inverse problems. The proposed methodology approximates the maximum a posteriori (MAP) estimate of a hierarchical Bayesian model characterized by a conditionally Gaussian prior and generalized gamma hyperpriors. Suitable choices of hyperparameters yield sparsity-promoting regularization. We propose an iterative algorithm for MAP estimation, which alternates between updating the unknown with an ensemble Kalman method and updating the hyperparameters in the regularization to promote sparsity. The effectiveness of our methodology is demonstrated in several computed examples, including compressed sensing and subsurface flow inverse problems.

Hierarchical models with gamma hyperpriors provide a flexible, sparse-promoting framework to bridge $L^1$ and $L^2$ regularizations in Bayesian formulations to inverse problems. Despite the Bayesian motivation for these models, existing methodologies are limited to \textit{maximum a posteriori} estimation. The potential to perform uncertainty quantification has not yet been realized. This paper introduces a variational iterative alternating scheme for hierarchical inverse problems with gamma hyperpriors. The proposed variational inference approach yields accurate reconstruction, provides meaningful uncertainty quantification, and is easy to implement. In addition, it lends itself naturally to conduct model selection for the choice of hyperparameters. We illustrate the performance of our methodology in several computed examples, including a deconvolution problem and sparse identification of dynamical systems from time series data.

The classical spin-vector Monte Carlo (SVMC) model is a reference benchmark for the performance of a quantum annealer. Yet, as a Monte Carlo method, SVMC is unsuited for an accurate description of the annealing dynamics in real-time.We introduce the spin-vector Langevin (SVL) model as an alternative benchmark in which the time evolution is described by Langevin dynamics. The SVL model is shown to provide a more stringent test than the SVMC model for the identification of quantum signatures in the performance of quantum annealing devices, as we illustrate by describing the Kibble-Zurek scaling associated with the dynamics of symmetry breaking in the transverse field Ising model, recently probed using D-Wave machines. Specifically, we show that D-Wave data are reproduced by the SVL model., Comment: Main text: 10 pages, 5 Figures, and SM: Fortran Code SVLdynamics.f

The stochastic partial differential equation approach to Gaussian processes (GPs) represents Mat\'ern GP priors in terms of $n$ finite element basis functions and Gaussian coefficients with sparse precision matrix. Such representations enhance the scalability of GP regression and classification to datasets of large size $N$ by setting $n\approx N$ and exploiting sparsity. In this paper we reconsider the standard choice $n \approx N$ through an analysis of the estimation performance. Our theory implies that, under certain smoothness assumptions, one can reduce the computation and memory cost without hindering the estimation accuracy by setting $n \ll N$ in the large $N$ asymptotics. Numerical experiments illustrate the applicability of our theory and the effect of the prior lengthscale in the pre-asymptotic regime.

Data assimilation is concerned with sequentially estimating a temporally-evolving state. This task, which arises in a wide range of scientific and engineering applications, is particularly challenging when the state is high-dimensional and the state-space dynamics are unknown. This paper introduces a machine learning framework for learning dynamical systems in data assimilation. Our auto-differentiable ensemble Kalman filters (AD-EnKFs) blend ensemble Kalman filters for state recovery with machine learning tools for learning the dynamics. In doing so, AD-EnKFs leverage the ability of ensemble Kalman filters to scale to high-dimensional states and the power of automatic differentiation to train high-dimensional surrogate models for the dynamics. Numerical results using the Lorenz-96 model show that AD-EnKFs outperform existing methods that use expectation-maximization or particle filters to merge data assimilation and machine learning. In addition, AD-EnKFs are easy to implement and require minimal tuning.

This paper develops manifold learning techniques for the numerical solution of PDE-constrained Bayesian inverse problems on manifolds with boundaries. We introduce graphical Mat\'ern-type Gaussian field priors that enable flexible modeling near the boundaries, representing boundary values by superposition of harmonic functions with appropriate Dirichlet boundary conditions. We also investigate the graph-based approximation of forward models from PDE parameters to observed quantities. In the construction of graph-based prior and forward models, we leverage the ghost point diffusion map algorithm to approximate second-order elliptic operators with classical boundary conditions. Numerical results validate our graph-based approach and demonstrate the need to design prior covariance models that account for boundary conditions.

In deep metric learning (DML), high-level input data are represented in a lower-level representation (embedding) space, such that samples from the same class are mapped close together, while samples from disparate classes are mapped further apart. In this lower-level representation, only a single inference sample from each known class is required to discriminate between classes accurately. The features a DML model uses to discriminate between classes and the importance of each feature in the training process are unknown. To investigate this, this study takes embeddings trained to discriminate faces (identities) and uses unsupervised clustering to identify the features involved in facial identity discrimination by examining their representation within the embedded space. This study is split into two cases; intra class sub-discrimination, where attributes that differ between a single identity are considered; such as beards and emotions; and extra class sub-discrimination, where attributes which differ between different identities/people, are considered; such as gender, skin tone and age. In the intra class scenario, the inference process distinguishes common attributes between single identities, achieving 90.0\% and 76.0\% accuracy for beards and glasses, respectively. The system can also perform extra class sub-discrimination with a high accuracy rate, notably 99.3\%, 99.3\% and 94.1\% for gender, skin tone, and age, respectively.

This paper provides a unified perspective of iterative ensemble Kalman methods, a family of derivative-free algorithms for parameter reconstruction and other related tasks. We identify, compare and develop three subfamilies of ensemble methods that differ in the objective they seek to minimize and the derivative-based optimization scheme they approximate through the ensemble. Our work emphasizes two principles for the derivation and analysis of iterative ensemble Kalman methods: statistical linearization and continuum limits. Following these guiding principles, we introduce new iterative ensemble Kalman methods that show promising numerical performance in Bayesian inverse problems, data assimilation and machine learning tasks.

Importance sampling is used to approximate Bayes' rule in many computational approaches to Bayesian inverse problems, data assimilation and machine learning. This paper reviews and further investigates the required sample size for importance sampling in terms of the $\chi^2$-divergence between target and proposal. We develop general abstract theory and illustrate through numerous examples the roles that dimension, noise-level and other model parameters play in approximating the Bayesian update with importance sampling. Our examples also facilitate a new direct comparison of standard and optimal proposals for particle filtering.

In this paper we analyze the graph-based approach to semi-supervised learning under a manifold assumption. We adopt a Bayesian perspective and demonstrate that, for a suitable choice of prior constructed with sufficiently many unlabeled data, the posterior contracts around the truth at a rate that is minimax optimal up to a logarithmic factor. Our theory covers both regression and classification.

This paper investigates Gaussian Markov random field approximations to nonstationary Gaussian fields using graph representations of stochastic partial differential equations. We establish approximation error guarantees building on the theory of spectral convergence of graph Laplacians. The proposed graph representations provide a generalization of the Mat\'ern model to unstructured point clouds, and facilitate inference and sampling using linear algebra methods for sparse matrices. In addition, they bridge and unify several models in Bayesian inverse problems, spatial statistics and graph-based machine learning. We demonstrate through examples in these three disciplines that the unity revealed by graph representations facilitates the exchange of ideas across them.