Fundamental Linear Algebra Problem of Gaussian Inference
- URL: http://arxiv.org/abs/2010.08022v1
- Date: Thu, 15 Oct 2020 21:09:17 GMT
- Title: Fundamental Linear Algebra Problem of Gaussian Inference
- Authors: Timothy D Barfoot
- Abstract summary: We state the Fundamental Linear Algebra Problem of Gaussian Inference (FLAPOGI)
We provide a global solution and then a local version that can be implemented using local message passing amongst agents calculating in parallel.
Contrary to belief propagation, our local scheme is guaranteed to converge in both the mean and desired covariance quantities.
- Score: 14.670851095242451
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Underlying many Bayesian inference techniques that seek to approximate the
posterior as a Gaussian distribution is a fundamental linear algebra problem
that must be solved for both the mean and key entries of the covariance. Even
when the true posterior is not Gaussian (e.g., in the case of nonlinear
measurement functions) we can use variational schemes that repeatedly solve
this linear algebra problem at each iteration. In most cases, the question is
not whether a solution to this problem exists, but rather how we can exploit
problem-specific structure to find it efficiently. Our contribution is to
clearly state the Fundamental Linear Algebra Problem of Gaussian Inference
(FLAPOGI) and to provide a novel presentation (using Kronecker algebra) of the
not-so-well-known result of Takahashi et al. (1973) that makes it possible to
solve for key entries of the covariance matrix. We first provide a global
solution and then a local version that can be implemented using local message
passing amongst a collection of agents calculating in parallel. Contrary to
belief propagation, our local scheme is guaranteed to converge in both the mean
and desired covariance quantities to the global solution even when the
underlying factor graph is loopy; in the case of synchronous updates, we
provide a bound on the number of iterations required for convergence. Compared
to belief propagation, this guaranteed convergence comes at the cost of
additional storage, calculations, and communication links in the case of loops;
however, we show how these can be automatically constructed on the fly using
only local information.
Related papers
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
Learning disentangled representations from unlabelled data is a fundamental challenge in machine learning.
We introduce a novel approach to disentangled representation learning based on quadratic optimal transport.
We demonstrate the effectiveness of our approach for quantifying disentanglement across four standard benchmarks.
arXiv Detail & Related papers (2024-07-10T16:51:32Z) - Stability of a Generalized Debiased Lasso with Applications to Resampling-Based Variable Selection [11.490578151974285]
We propose an approximate formula for updating a debiased Lasso coefficient.
As applications, we show that the approximate formula allows us to reduce the complexity of variable selection algorithms.
arXiv Detail & Related papers (2024-05-05T22:05:02Z) - Approximating a RUM from Distributions on k-Slates [88.32814292632675]
We find a generalization-time algorithm that finds the RUM that best approximates the given distribution on average.
Our theoretical result can also be made practical: we obtain a that is effective and scales to real-world datasets.
arXiv Detail & Related papers (2023-05-22T17:43:34Z) - Equivariant Disentangled Transformation for Domain Generalization under
Combination Shift [91.38796390449504]
Combinations of domains and labels are not observed during training but appear in the test environment.
We provide a unique formulation of the combination shift problem based on the concepts of homomorphism, equivariance, and a refined definition of disentanglement.
arXiv Detail & Related papers (2022-08-03T12:31:31Z) - Equivariance Discovery by Learned Parameter-Sharing [153.41877129746223]
We study how to discover interpretable equivariances from data.
Specifically, we formulate this discovery process as an optimization problem over a model's parameter-sharing schemes.
Also, we theoretically analyze the method for Gaussian data and provide a bound on the mean squared gap between the studied discovery scheme and the oracle scheme.
arXiv Detail & Related papers (2022-04-07T17:59:19Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
We address the non- optimisation problem of finding a matrix on the Stiefel manifold that maximises a quadratic objective function.
We propose a simple yet effective sparsity-promoting algorithm for finding the dominant eigenspace matrix.
arXiv Detail & Related papers (2021-09-30T19:17:35Z) - Linear regression with partially mismatched data: local search with
theoretical guarantees [9.398989897176953]
We study an important variant of linear regression in which the predictor-response pairs are partially mismatched.
We use an optimization formulation to simultaneously learn the underlying regression coefficients and the permutation corresponding to the mismatches.
We prove that our local search algorithm converges to a nearly-optimal solution at a linear rate.
arXiv Detail & Related papers (2021-06-03T23:32:12Z) - Provably Convergent Working Set Algorithm for Non-Convex Regularized
Regression [0.0]
This paper proposes a working set algorithm for non-regular regularizers with convergence guarantees.
Our results demonstrate high gain compared to the full problem solver for both block-coordinates or a gradient solver.
arXiv Detail & Related papers (2020-06-24T07:40:31Z) - Approximation Schemes for ReLU Regression [80.33702497406632]
We consider the fundamental problem of ReLU regression.
The goal is to output the best fitting ReLU with respect to square loss given to draws from some unknown distribution.
arXiv Detail & Related papers (2020-05-26T16:26:17Z) - Sub-Gaussian Matrices on Sets: Optimal Tail Dependence and Applications [6.034622792544481]
We study when a sub-Gaussian matrix can become a near isometry on a set.
We show that previous best known dependence on the sub-Gaussian norm was sub-optimal.
We also develop a new Bernstein type inequality for sub-exponential random variables, and a new Hanson-Wright inequality for quadratic forms of sub-Gaussian random variables.
arXiv Detail & Related papers (2020-01-28T23:06:20Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.