PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal low-rank approximations of Bayesian linear inverse problems

Alessio Spantini, Antti Solonen, Tiangang Cui, James Martin, Luis Tenorio, Youssef Marzouk

arXiv:1407.3463v2math.NAstat.COstat.ME

TL;DR

High-dimensional Bayesian inverse problems often contain a low-dimensional data-informed subspace, but approximations must preserve posterior covariance and mean structure. The paper derives optimal low-rank covariance updates and posterior-mean approximations using generalized eigendirections and weighted Bayes risk. These methods provide data-independent offline computations and fast repeated evaluations, with extensions bounded by the finite-dimensional linear-Gaussian setting.

  • Problem

    The paper addresses how to approximate Gaussian posterior covariance and mean efficiently when Bayesian inverse problems are high-dimensional but data are informative mainly on a low-dimensional subspace.

  • Method

    It uses low-rank negative updates of the prior covariance based on leading generalized eigenvectors of (H, Γ^-1_pr), plus two posterior-mean approximations optimized under posterior-precision-weighted squared-error Bayes risk.

  • Results

    The covariance updates are optimal for a broad loss class, including the Förstner metric and corresponding Hellinger and Kullback-Leibler criteria, while the mean approximations support fast repeated data evaluations.

  • Takeaways & Limitations

    The approach exploits intrinsic low-dimensional inference structure to reduce computational demands while preserving posterior approximations, especially in many-query settings.

  • Takeaways & Limitations

    The analysis is developed for finite-dimensional Bayesian linear inverse problems with Gaussian priors and measurements, with infinite-dimensional and nonlinear extensions left as future work.

Abstract

from arXiv · show

In the Bayesian approach to inverse problems, data are often informative, relative to the prior, only on a low-dimensional subspace of the parameter space. Significant computational savings can be achieved by using this subspace to characterize and approximate the posterior distribution of the parameters. We first investigate approximation of the posterior covariance matrix as a low-rank update of the prior covariance matrix. We prove optimality of a particular update, based on the leading eigendirections of the matrix pencil defined by the Hessian of the negative log-likelihood and the prior precision, for a broad class of loss functions. This class includes the Förstner metric for symmetric positive definite matrices, as well as the Kullback-Leibler divergence and the Hellinger distance between the associated distributions. We also propose two fast approximations of the posterior mean and prove their optimality with respect to a weighted Bayes risk under squared-error loss. These approximations are deployed in an offline-online manner, where a more costly but data-independent offline calculation is followed by fast online evaluations. As a result, these approximations are particularly useful when repeated posterior mean evaluations are required for multiple data sets. We demonstrate our theoretical results with several numerical examples, including high-dimensional X-ray tomography and an inverse heat conduction problem. In both of these examples, the intrinsic low-dimensional structure of the inference problem can be exploited while producing results that are essentially indistinguishable from solutions computed in the full space.

1. Introduction.

The paper develops optimal, structure-exploiting approximations for Gaussian Bayesian linear inverse problems, targeting posterior covariance and mean computations in high-dimensional settings. Its low-rank methods reduce storage and computation while supporting repeated posterior evaluations.

  • Problem: The paper studies finite-dimensional Bayesian linear inverse problems with Gaussian priors and measurements, whose Gaussian posterior is determined by its mean and covariance.The approximations target posterior characteristics rather than the full distribution directly.
  • Covariance approximation: Posterior covariance is approximated by a low-rank negative update of the prior covariance, with optimality defined through loss functions emphasizing relative covariance differences.The approach exploits the prior-to-posterior update structure and includes the Förstner metric.
  • Covariance approximation: The optimal covariance update uses leading generalized eigenvectors of the negative log-likelihood Hessian and prior precision pencil.This eigendirection choice establishes optimality for a broad class of covariance losses and related distributional criteria.
  • Posterior mean approximation: Two posterior-mean approximations support repeated evaluations across datasets by using low-rank affine data maps or low-rank prior-covariance updates.Both are optimized under a posterior-precision-weighted squared-error Bayes risk.
  • Connections: The methods extend Gaussian posterior approximations used in nonlinear inverse-problem algorithms, including stochastic Newton MCMC and Laplace-based approaches.These connections position the linear theory as a building block for broader nonlinear methods.
  • Related approaches: Earlier prior-based dimension reduction can collapse neglected directions and require strong prior smoothness, motivating methods that preserve posterior structure more directly.The paper instead exploits data-informed low-dimensional structure relative to the prior.

2. Optimal approximation of the posterior covariance matrix.

The paper formulates posterior covariance approximation as a low-rank negative update of the prior covariance and identifies an optimal update through generalized eigenpairs. The resulting method is compatible with invariant covariance losses and can be computed using matrix-free eigensolvers.

  • Bayesian linear model: The Gaussian posterior has mean and covariance determined by the linear forward model, prior, and observation covariance; its covariance is independent of the observed data.This makes data-independent covariance approximation possible.
  • Approximation class: The posterior covariance naturally takes the form of a negative semidefinite, often low-rank update of the prior covariance because data reduce variance only in informative directions.The low-rank structure lies in the update, not necessarily in the posterior covariance itself.
  • Loss functions: The loss class includes the Förstner metric and is defined through generalized eigenvalues of the compared symmetric positive definite matrices.These losses emphasize relative rather than purely absolute covariance differences.
  • Distributional interpretation: With the posterior mean held fixed, covariance optimality is equivalent to optimality in Hellinger distance and Kullback-Leibler divergence between the associated Gaussian distributions.The equivalence applies to the loss class defined in the paper.
  • Optimality theorem: For any loss in the specified class, the optimal rank-r covariance update is obtained from the leading generalized eigenpairs of the pencil (H, Γ^-1_pr).The minimizer is unique when the first r generalized eigenvalues are distinct.
  • Computation: The minimum loss depends on the generalized eigenvalues, providing a stopping criterion after computing eigenpairs in decreasing order.Standard or generalized Hermitian Lanczos methods can exploit prior square-root factors or prior-precision solves.

3. Properties of the optimal covariance approximation.

The optimal covariance approximation selects directions where posterior variance is smallest relative to prior variance and induces a data-informed reduced model. This interaction-based construction is generally superior to reductions based only on the Hessian or prior.

  • Precision interpretation: The optimal posterior precision approximation is the inverse of the optimal covariance approximation and uses the same generalized eigendirections.The corresponding eigenvectors are generalized eigenvectors of the posterior-prior covariance pencil.
  • Informative directions: The optimal generalized eigenvectors identify directions that minimize the posterior-to-prior variance ratio and therefore maximize relative variance reduction.These are the parameter-space directions where the data are most informative relative to the prior.
  • Reduced model: An oblique projector onto the data-informed subspace produces a reduced forward model whose posterior covariance equals the optimal covariance approximation.This connects covariance approximation with intrinsic dimensionality reduction.
  • Broader use: The projected model can also support nonlinear approximations by evaluating the likelihood on the projected parameters while retaining the prior density.Its posterior mean minimizes weighted squared-error Bayes risk among low-rank linear functions of the data.
  • Frobenius comparison: Frobenius-norm optimality selects directions maximizing absolute prior-posterior variance differences, unlike the relative differences selected by the Förstner-based approach.The Frobenius-based eigenproblem is also more expensive and does not provide the same distributional optimality statement.
  • Alternative reductions: Hessian-only and prior-only reductions are suboptimal because they ignore interactions between likelihood curvature, prior covariance, and their relative importance.The optimal projector can differ from the leading Hessian eigenspace.

4. Optimal approximation of the posterior mean.

The paper derives optimal low-rank posterior mean approximations for repeated Bayesian inverse-problem evaluations, using Bayes risk under a posterior-precision-weighted squared-error loss. The resulting approximations exploit low-dimensional structure and support fast online application after an offline calculation.

  • Motivation: The method targets repeated posterior mean evaluations for different data sets, not replacing efficient single-realization solvers.The approximation is designed for online inference contexts where solving a linear system for every data set is costly.
  • Objective: Posterior mean approximation errors are measured with a Mahalanobis squared-error loss that penalizes errors more strongly in directions of lower posterior variance.This weighting discourages approximate means from leaving the bulk of the posterior probability distribution.
  • Approximation classes: The paper considers two approximation classes: low-rank matrices and matrices obtained by replacing the posterior covariance with a low-rank negative semidefinite update of the prior covariance.Both classes seek an approximation matrix that minimizes the corresponding Bayes risk.
  • Optimality results: Theorem 4.1 gives an analytically optimal low-rank posterior mean approximation whose structure follows the optimal posterior covariance approximation.The solution is characterized using generalized eigenvectors and associated eigenvalue ordering.
  • Online evaluation: The rank-r approximation coincides with the posterior mean of a projected linear Gaussian model, so new data realizations require only a low-rank matrix-vector product.This yields the intended offline-online computational pattern.
  • Low-rank update approximation: Theorem 4.2 provides a second optimal estimator based on a low-rank update of the prior covariance, with online cost dominated by adjoint and prior solves.Combining this estimator with the optimal covariance approximation gives a complete approximate Gaussian posterior.
  • Estimator comparison: When fewer than r generalized eigenvalues exceed one, the optimal low-rank update estimator outperforms the optimal low-rank estimator; otherwise, the low-rank estimator is more accurate and less expensive under under-resolved approximations.The choice between estimators therefore depends on the number of informative eigendirections relative to the selected rank.

5. Numerical examples.

The numerical examples show that posterior covariance and mean approximations exploit an intrinsically low-dimensional informed subspace, with performance governed by the relative spectra of the prior and Hessian. Across tomography and heat-equation problems, the optimal approximations achieve accurate results at substantially reduced ranks and costs, while their relative advantage depends on the forward model and preconditioning.

  • Controlled spectra: When prior variances are constant, prior-based reduction is as effective as generalized reduction; when noise variances are constant, Hessian-based reduction is equally effective.For general spectra, the important directions depend on both prior and noise information, which the generalized reduction combines naturally.
  • Controlled spectra: As data become less informative across the controlled-spectrum configurations, the BFGS update remains effective but is clearly suboptimal to generalized reduction.The comparison uses Förstner distance between the posterior covariance and its low-rank approximation.
  • X-ray tomography: In the 16384-dimensional tomography problem, a rank 200 covariance update accurately approximates posterior variance, while rank 100 already reproduces small-scale sample features.The approximation uses the exact posterior mean, so observed sample differences reflect covariance approximation alone.
  • X-ray tomography: Tomography posterior-mean errors decrease with rank, but low-rank approximations outperform low-rank updates at smaller ranks until generalized eigenvalues below one are included.The crossover is predicted by the generalized eigenvalues of the pencil (H, Γ−1_pr).
  • X-ray tomography: At approximately r = 200, accurate tomography posterior means require relative CPU times of 7.3 for µ^(r)_pos(y) and 29.0 for bµ^(r)_pos(y), limiting speedups for cheap sparse forward operators.The reported costs are comparable to the number of iterative-solver steps affordable at equivalent computational cost.
  • X-ray tomography: Full-angle tomography requires higher-rank covariance updates than limited-angle tomography for a given error because its generalized eigenvalues decay more slowly.The relative posterior-mean CPU times are reported as similar to the limited-angle case.
  • Heat equation: In the heat-equation example, visually indistinguishable posterior means at r = 200 require relative CPU time 0.001 for the low-rank approximation.The numerical results follow the same error trends and crossover behavior as tomography, while computational costs differ substantially.

6. Conclusions.

The paper establishes optimal low-rank approximations for posterior covariance and mean in finite-dimensional Gaussian linear inverse problems, exploiting directions where data most reduce posterior variance. These approximations support distributional optimality guarantees and efficient repeated posterior-mean evaluations.

  • Posterior covariance approximation: The posterior covariance is optimally approximated by a rank-r negative semidefinite update of the prior, using generalized eigendirections of the likelihood Hessian and prior precision.The result applies to a broad class of covariance losses, including the Förstner metric, and identifies directions with the greatest relative posterior-variance reduction.
  • Posterior covariance approximation: The covariance approximation also yields optimal Gaussian posterior approximations under Hellinger distance and Kullback-Leibler divergence when the posterior mean is known exactly.This follows because the relevant covariance-loss class includes the functions associated with both distributional criteria.
  • Posterior mean approximation: The paper develops fast posterior-mean approximations that minimize Bayes risk for squared-error loss weighted by posterior precision.The most efficient form expresses the posterior mean as the product of a single low-rank matrix with the data, making it suitable for repeated data realizations.
  • Scope and extensions: The current theory is finite-dimensional and Gaussian, with extensions proposed for infinite-dimensional priors, infinite-dimensional data, nonlinear forward models, and sequential inference.These are identified as directions for future work rather than results established by the present analysis.
  • Optimality characterization: The optimal low-rank update selects the leading eigenvalues of the relevant matrix pencil, with uniqueness when the first r eigenvalues are distinct.The auxiliary optimization reduces to selecting the leading components of the diagonal matrix D, and monotonicity establishes the minimizing subsequence.
Loading 1407.3463v2…