---
abstract: 'We introduce *extended Gaussian distributions* as a precise and principled way of combining Gaussian probability uninformative priors, which indicate complete absence of information. To give an extended Gaussian distribution on a finite-dimensional vector space $X$ is to give a subspace $D$, along which no information is known, together with a Gaussian distribution on the quotient $X/D$. We show that the class of extended Gaussians remains closed under taking conditional distributions. We then introduce *decorated linear maps and relations* as a general framework to combine probability with nondeterminism on vector spaces, which includes extended Gaussians as a special case. This enables us to apply methods from categorical logic to probability, and make connections to the semantics of probabilistic programs with exact conditioning.'
address: 'iHub, Radboud University Nijmegen, The Netherlands'
author:
- Dario Stein
bibliography:
- 'main.bib'
title: 'Decorated Linear Relations: Extending Gaussian Probability with Uninformative Priors'
---

probabilistic programming, probability theory, Bayesian inference, category theory, Markov categories

Introduction
============

Gaussian (multivariate normal) distributions are a small but expressive family of probability distributions with a variety of applications, from ridge regression over Kálmán filters to Gaussian process regression. An important feature is that Gaussians are self-conjugate, that is conditional distributions of Gaussians are themselves Gaussian. For example, in a regression problem, we may put Gaussian priors on the regression coefficients $a_i \sim \mathcal N(0,\sigma)$[^1] and let $y = a_ix_i + \ldots + a_bx_n$. We can then make noisy or exact observations for datapoints $(\vec x_i, y_i)_{i=1,\ldots,n}$ and obtain Gaussian posteriors over both the regression coefficients and the predicted value.

An important question is then how to model complete *absence of information* in such a setting, say over coefficients or data. Conditioning on such absent information should have no effect. However, no Gaussian distribution ${\mathcal N}(\mu,\sigma)$ is ever completely uninformative, because it is integrable and introduces a bias towards its mean. Intuitively, the uninformative prior over the real line should be the limit of $\mathcal N(\mu,\sigma)$ for $\sigma \to \infty$. However, this limit cannot be taken in any ordinary sense because it assigns measure $0$ to every bounded set (it converges weakly to the zero measure, which is not a probability measure). The Lebesgue measure $\lambda$ is another candidate, however it is not a probability measure because it fails to be normalized. Nonetheless, so called *improper priors* like the Lebesgue measure are frequently used in density computations, because *after conditioning*, they may result in a well-defined and normalized posterior (e.g. @gelman). We prefer to give a formal account of this phenomenon which completely avoids non-normalization:

In , we present a theory of *extended Gaussian distributions*, which faithfully include ordinary Gaussian distributions while adding in uninformative priors. Extended Gaussian variables can be added, scaled and conditioned just like ordinary Gaussians. We generalize the natural duality between precision and covariance for ordinary Gaussians to the extended case ().

In , we generalize extended Gaussian distributions to a category ${{\mathsf}{GaussEx}}$ of *extended Gaussian maps* between vector spaces. ${{\mathsf}{GaussEx}}$ combines features from Gaussian probability as well as nondeterminism, which is modelled by linear relations. This is surprising because probability and nondeterminism are difficult to combine in general @nogo. We show that ${{\mathsf}{GaussEx}}$ is an instance of a general construction: For a suitable type of 'decoration' $S$, we define the categories ${\mathsf{Lin}_{S}}$ of *decorated linear maps* and ${{\mathsf}{LinRel}}_S$ of *decorated linear relations*, of which linear relations, affine relations, ordinary Gaussians and extended Gaussians are obtained for different choices of $S$. This joint formalism lets us elegantly establish relationships between those categories, such as the support of a Gaussian, which is an affine subspace ().

Because extended Gaussians are inherently not measure-theoretic, we will use the language of categorical probability theory @cho_jacobs [@fritz] to talk about random variables, distributions and conditioning in an abstract and unified way. In technical terms, our main theorem is that ${{\mathsf}{GaussEx}}$ is a Markov category which has all conditionals (Theorem \[thm:cond\]).

Recent applications of categorical probability theory include @bart:licsmultisets [@jacobs:hypergeo]. The categorical framework has a canonical counterpart in the compositional semantics of probabilistic programs @staton:commutative_semantics [@dariothesis]. In @2021compositional, we treat *exact conditioning* of Gaussian random variables from a programming-languages viewpoint. The study of uninformative priors is very natural in this context, because it asks for a unit for the conditioning operation. We will discuss this more in but take care to keep the developments of self-contained and avoid categorical language there.

Extended Gaussian Distributions {#sec:dist}
===============================

We begin with an informal introduction to extended Gaussians, before defining them formally in . In a nutshell, an extended Gaussian on a vector space $X$ is a Gaussian distribution on a quotient $X/D$. For an overview of linear algebra terminology, see .\
**Representations:** A *Gaussian distribution* on ${\mathbb R}^n$ can be written uniquely as ${\mathcal N}(\mu, \Sigma)$ where $\mu \in {\mathbb R}^n$ is its *mean* and $\Sigma \in {\mathbb R}^{n \times n}$ is a symmetric positive-semidefinite matrix called its *covariance matrix*. The *support* of ${\mathcal N}(\mu,\Sigma)$ is the affine subspace $\mu + {\mathsf{col}}(\Sigma)$ where ${\mathsf{col}}(\Sigma)$ is the column space (image) of $\Sigma$. Gaussian distributions transform as follows under linear maps: If $A \in {\mathbb R}^{m \times n}$, then $$A_*{\mathcal N}(\mu, \Sigma) = {\mathcal N}(A\mu, A\Sigma A^T)$$ is its pushforward Gaussian distribution on ${\mathbb R}^m$. For an introduction to Gaussian probability see e.g. @alexthesis.\
We now wish to add certain forms of limits to Gaussian distributions, which allow us to express ignorance along a certain subspace $D$. An *extended Gaussian distribution on ${\mathbb R}^n$* is an entity which can be written as $${\mathcal N}(\mu, \Sigma) + D \label{repr_gaussex}$$ where $D \subseteq {\mathbb R}^n$ is a vector subspace called *locus of nondeterminism*. Extended Gaussian distributions transform as $A_*({\mathcal N}(\mu, \Sigma) + D) = {\mathcal N}(A\mu, A\Sigma A^T) + A[D]$ where $A[D] = \{ Ax : x \in D \}$ is the image subspace. The intuition is that nondeterministic (uninformative) noise is present in the distribution along the subspace $D$. For example, the extended Gaussian distribution ${\mathcal N}(0,0) + {\mathbb R}$ (which we'll simply write as ${\mathbb R}$) expresses a 'uniform distribution' over the real line; it is the distribution of a point about which we have no information.\
**Translation invariance and non-uniqueness:** An important consequence of the uninformativeness is that the representation can no longer be unique. For example, the uniform distribution on ${\mathbb R}$ should be translation invariant, because adding a constant to an unknown point results in an unknown point. We can thus, for example, expect the following three representations of extended Gaussians to denote the same distribution: $${\mathcal N}(10,0) + {\mathbb R}= {\mathbb R}= {\mathcal N}(0,10) + {\mathbb R}$$

Let us consider a more complex example involving two correlated random variables:

\[ex:extendedexample\] Let $X_1,X_2$ be independent normal variables, to which we add some uniform noise along the diagonal $D = \{ (y,y) : y \in {\mathbb R}\}$; that is we let $Y \sim {\mathbb R}$ and define $$Z_1 = X_1 + Y,\quad Z_2 = X_2 + Y$$ The extended Gaussian vector $(Z_1,Z_2)$ can be decomposed into a sum (see ) $$\begin{aligned}
    (Z_1,Z_2) &= \underbrace{(X_1+Y,X_1+Y)}_{\in D} + (0,X_2-X_1)
    \end{aligned}$$ where the first summand lies in $D$ and the second one takes values in the complement $0 \times {\mathbb R}$. By translation invariance, the first contribution gets absorbed by $D$. The remaining contribution $(0,X_2-X_1)$ has variance $2$ in the second coordinate. We can therefore conclude that following are both valid representations of the joint distribution of $(Z_1,Z_2)$: $${\mathcal N}\left(\begin{pmatrix} 0 \\ 0 \end{pmatrix},\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\right) + D = {\mathcal N}\left(\begin{pmatrix} 0 \\ 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix}\right) \label{eq:extended_nonuniqueness}$$

<span>r</span><span>0.3</span> ![image](example.pdf){width="30.00000%"}

**Conditionals:** Unlike $X_1,X_2$, the variables $Z_1, Z_2$ in Example \[ex:extendedexample\] are no longer independent, because they are coupled via $Y$. In fact, one can show that $Z_2$ given $Z_1$ has the conditional distribution $$Z_2|Z_1 \sim {\mathcal N}(Z_1,2)$$ The expression $Z_1 \mapsto {\mathcal N}(Z_1,2)$ appearing in the conditional is an example of an *extended Gaussian map*, which we consider systematically in . In Theorem \[thm:cond\], we prove that that conditional distributions of extended Gaussians are again extended Gaussian. We now proceed to define extended Gaussians formally.

Definition of Extended Gaussians {#sec:defn}
--------------------------------

For a first definition of extended Gaussians, we start from the representatives in and quotient by an equivalence relation for when they shall denote the same distribution:

\[Preliminary Definition\]\[def:firstdef\] An extended Gaussian distribution on ${\mathbb R}^n$ is an equivalence class of pairs $(D, \psi)$ where $D \subseteq {\mathbb R}^n$ is a vector subspace and $\psi$ is a Gaussian distribution on ${\mathbb R}^n$. We identify two such pairs $(D,\psi), (D',\psi')$ if and only if $D=D'$ and the pushforward distributions $(p_K)_*\psi$ and $(p_K)_*\psi'$ agree for some (equivalently any) direct sum decomposition $D \oplus K = {\mathbb R}^n$, where $p_K$ is the projection endomorphism onto $K$.

In Example \[ex:extendedexample\], we considered the particular complement $K = 0 \times {\mathbb R}$ of $D$. The projection onto $K$ is given by the matrix $$A = \begin{pmatrix}
    0 & 0 \\
    -1 & 1
    \end{pmatrix}$$ From this we obtain the desired equality by verifying that $$A_*\left[{\mathcal N}\left(\begin{pmatrix} 0 \\ 0 \end{pmatrix},\begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}\right)\right]
    = {\mathcal N}\left(\begin{pmatrix} 0 \\ 0 \end{pmatrix},\begin{pmatrix} 0 & 0 \\ 0 & 2 \end{pmatrix}\right)$$

The choice of complement is in no way canonical. A cleaner, high-level definition goes as follows: *An extended Gaussian distribution on $X$ with locus of nondeterminism $D$ is an ordinary Gaussian distribution on the quotient space $X/D$* (Definition \[def:gaussex\]). The preliminary definition \[def:firstdef\] is then obtained by identifying ${\mathbb R}^n/D$ with the complement $K$. However, because the choice of complement is non-canonical, it is preferable to work with the quotient directly. However, the abstract definition makes it necessary to re-introduce Gaussian distributions on more general vector spaces than just ${\mathbb R}^n$ in a coordinate-free way. This development is well-known, and we refer to e.g. @alexthesis [Section 1] for an overview:

All vector spaces $X$ are henceforth assumed finite-dimensional. We write $X^*$ for the dual space of $X$, consisting of all linear maps $X \to {\mathbb R}$. By a *form* on $X$, we mean a *symmetric bilinear map* $\Omega : X \times X \to {\mathbb R}$. The kernel of $\Omega$ is the set $$\ker(\Omega) {\stackrel{\text{def}}=}\{ x \in X : \Omega(x,-) = 0 \} = \{ y \in X : \Omega(-,y) = 0 \}$$ We call $\Omega$ *nondegenerate* if $\ker(\Omega) = 0$. Note that $\Omega$ can be curried as $\omega: X \to X^*$ with $\omega(x) = \Omega(x,-)$. The notation is consistent in that $\ker(\Omega) = \ker(\omega)$, and $\Omega$ is nondegenerate if and only if $\omega : X \to X^*$ is an isomorphism. If $\Omega$ has kernel $K$, then the quotient form $\widetilde \Omega : (X/K) \times (X/K) \to {\mathbb R}$ is well-defined and nondegenerate.

A form $\Omega : X \times X \to {\mathbb R}$ is called *positive semidefinite* if $\Omega(x,x) \geq 0$ for all $x \in X$, and *positive definite* if $\Omega(x,x)>0$ for all $x \neq 0$. A positive semidefinite form is positive definite if and only if it is nondegenerate.

The correct coordinate-free version of the covariance matrix is that of a covariance form $\Sigma : X^* \times X^* \to {\mathbb R}$ on the dual space. Given a random variable $U$ on the space $X$, and linear functions $f, g : X \to {\mathbb R}$, we compute the covariance $$\Sigma(f,g) {\stackrel{\text{def}}=}\mathbb E[f(U)g(U)]-\mathbb E[f(U)]\mathbb E[g(U)]$$ This expression is symmetric, bilinear and positive semidefinite. A Gaussian distribution is fully determined by its mean and covariance form, which motivates the following definition:

A Gaussian distribution on a vector space $X$ is a pair written ${\mathcal N}(\mu,\Sigma)$ of a mean $\mu \in X$ and a positive semidefinite form $\Sigma : X^* \times X^* \to {\mathbb R}$. If $f : X \to Y$ is a linear map, the Gaussian distribution pushes forward to ${\mathcal N}(f(\mu), f_*\Sigma)$ where $(f_*\Sigma)(g,h) = \Sigma(gf,hf)$.

We can now give the following concise definition of extended Gaussians.

\[def:gaussex\] An extended Gaussian distribution on a vector space $X$ is a pair $(D,\psi)$ where $D \subseteq X$ is a vector subspace and $\psi$ is a Gaussian distribution on $X/D$.

Every linear map $f : X \to Y$ induces a linear map $f_D : X/D \to Y/f[D]$, and we take the pushforward of $(D,\psi)$ to be $(f[D], (f_D)_*\psi)$.

Precision and Duality {#sec:duality}
---------------------

We will show that our definition of extended Gaussians fits into an elegant duality between forms on a space and its dual. This lets us convert between two equivalent representations, using a *covariance form* or a *precision form*, which are convenient for different purposes:\
Probability distributions and probability densities are dual to each other. Distributions naturally push forward, and consequently the covariance form must be defined on the *dual space* $X^*$. On the other hand, *density functions* pull back. If the covariance matrix $\Sigma$ is nonsingular, the Gaussian distribution ${\mathcal N}(\mu,\Sigma)$ has a Lebesgue density $$f(x) \propto \exp\left(-\frac 1 2 (x-\mu)^T \Omega (x-\mu) \right) \label{eq:density}$$ where $\Omega = \Sigma^{-1}$ is called the *precision matrix*. If $\Sigma$ is singular, $\mathcal N(\mu,\Sigma)$ will only admit a density on its support $S$, and the precision is only defined on that subspace. The coordinate-free formulation of the precision-covariance correspondence is given by the following duality statement (where for simplicity we assume centered distributions, that is mean zero):

\[plainduality\] The following pieces of data are equivalent for every vector space $X$

1.  a form $\Sigma : X^* \times X^* \to {\mathbb R}$

2.  a subspace $S \subseteq X$ and a nondegenerate form $\Omega : S \times S \to {\mathbb R}$

Recall that the evaluation pairing $X^* \times X \to {\mathbb R}$ induces a duality between the subspaces of $X$ and $X^*$ called *annihilators*, which we here denote $(-)^\bot$. For subspaces $D \subseteq X$ and $F \subseteq X^*$, the subspaces $D^\bot \subseteq X^*, F^\bot \subseteq X$ are defined as $$\begin{aligned}
D^\bot {\stackrel{\text{def}}=}\{ f \in X^* : f|_D = 0 \}, \qquad
F^\bot {\stackrel{\text{def}}=}\{ x \in X : \forall f \in F, f(x) = 0 \}\end{aligned}$$ Taking annihilators is order-reversing and involutive; we list further properties under Proposition \[prop:annih\].

In Theorem \[plainduality\], the subspace $S$ is taken to be annihilator of the kernel $K=\ker(\Sigma)$, that is $S=\{ x : \forall f \in K, f(x)= 0\}$. This recovers the familiar support $S={\mathsf{col}}(\Sigma)$ for covariance matrices. We may think of the form $\Omega$ as taking the value infinity outside of $S$ (which corresponds to vanishing a density under ).\
Extended Gaussians admit a generalized and in fact more symmetric version of this correspondence:

\[exduality\] The following pieces of data are equivalent for every vector space $X$

1.  pairs $\langle S,\Omega \rangle$ of a subspace $S \subseteq X$ and $\Omega : S \times S \to {\mathbb R}$

2.  pairs $\langle F, \Sigma \rangle$ of a subspace $F \subseteq X^*$ and $\Sigma : F \times F \to {\mathbb R}$

<!-- -->

1.  Given $\langle S,\Omega \rangle$, let $D = \ker(\Omega) \subseteq S$ and define $F=D^\bot$ and $K=S^\bot$.

    Form the nondegenerate quotient form $\widetilde \Omega : (S/D) \times (S/D) \to {\mathbb R}$. Its currying $\widetilde \omega : (S/D) \to (S/D)^*$ is an isomorphism. Making use of the canonical isomorphisms described in Proposition \[prop:annih\], $$\begin{tikzcd}
            {(S/D)^*} && {S/D} \\
            {D^\bot/S^\bot} && {K^ \bot/F^\bot} \\
            {F/K} && {(F/K)^*}
            \arrow["{\widetilde \omega^{-1}}", from=1-1, to=1-3]
            \arrow["\sim", from=2-1, to=1-1]
            \arrow[no head, from=3-1, to=2-1]
            \arrow[shift left=1, no head, from=2-1, to=3-1]
            \arrow[no head, from=2-3, to=1-3]
            \arrow[shift right=1, no head, from=2-3, to=1-3]
            \arrow["\sim", from=2-3, to=3-3]
            \arrow["{\widetilde \sigma}", from=3-1, to=3-3]
            \end{tikzcd} \label{duality}$$ we obtain an iso $\widetilde \sigma : (F/K) \to (F/K)^*$, which is the same thing as a bilinear form $\Sigma : F \times F \to {\mathbb R}$ with kernel $K$.

2.  Conversely, given $\langle F, \Sigma\rangle$, let $K=\ker(\Sigma)$ and define $D = F^\bot$ and $S = K^\bot$. Turn $\Sigma$ into an iso $\widetilde \sigma : (F/K) \to (F/K)^*$, then reading the diagram backwards uniquely defines the iso $\widetilde \omega$ and hence the form $\Omega$ with kernel $D$.

The constructions are clearly inverses to each other. It is furthermore easy to see that the correspondence takes positive semidefinite forms to positive semidefinite forms.

A (centered) extended Gaussian thus has a *covariance representation* which is a pair $\langle F,\Sigma \rangle$ with $F \subseteq X^*$ and $\Sigma$ a positive semidefinite form on $F$, and a *precision representation* $\langle S,\Omega \rangle$ with $S \subseteq X$ and $\Omega$ positive semidefinite on $S$. The covariance representation is convenient for computing pushforwards, while the precision representation generalizes density functions and is useful for conditioning. Note that the locus of nondeterminism of an extended Gaussian is $D=\ker(\Omega)$, that is, unlike for ordinary Gaussians, vanishing precision is now allowed! The proof of Theorem \[exduality\] is reminiscent of the construction of the Moore-Penrose pseudoinverse, whose relevance to Gaussian probability is well-known (e.g. @lauritzen).

\[def:uniform\] We define the *uniform distribution* $u_X$ on $X$ to be the unique extended Gaussian distribution whose locus of nondeterminism is all of $X$. Its precision representation is the zero form $X \times X \to {\mathbb R}$; its covariance representation is the zero form on the trivial subspace $0 \subseteq X^*$.

A Category of Extended Gaussian maps {#sec:maps}
====================================

It is convenient to generalize Gaussian distributions on $X$ to *Gaussian maps* $X \to Y$, which are linear functions with Gaussian noise, informally written $x \mapsto f(x) + \psi$, where $f : X \to Y$ is linear and $\psi$ is a Gaussian distribution on $Y$ (independent of $x$). This allows us to discuss distributions, linear maps and conditionals within a single formalism.

Gaussian maps can be composed in sequence and in parallel, where the noise is pushed forward and accumulated appropriately. Formally, we defines a symmetric monoidal category ${{\mathsf}{Gauss}}$ (due to @fritz [Ch. 6]) as follows: Objects are vector spaces $X$, and morphisms are Gaussian maps $(f + \psi)$ between them. On objects, the tensor is cartesian product, $X \otimes Y = X \times Y$, and the categorical structure is given by $$\begin{aligned}
(f+\psi) \circ (g+\varphi) = fg + \psi + f_*\varphi \qquad (f+\psi) \otimes (f' + \psi') = f \times f' + \psi \otimes \psi'\end{aligned}$$ where $\psi \otimes \psi'$ denotes the product distribution of Gaussians. Furthermore, we can copy and discard information using the linear maps $\mathsf{cpy}_X : X \to X \times X, x \mapsto (x,x)$ and $\mathsf{del}_X : X \to 0$. This gives ${{\mathsf}{Gauss}}$ the structure of a *Markov category* @fritz, that is a categorical model of probability theory. We can recover Gaussian distributions as Gaussian maps $0 \to X$ out of the trivial vector space.

In this section, we show that the construction of ${{\mathsf}{Gauss}}$ arises as an instance of a general notion of *decorated linear map* $x \mapsto f(x)+s$. We then give a recipe to combine decorated linear maps with nondeterminism to obtain *decorated linear relations*. This subsumes our earlier construction of extended Gaussian distributions, as well as serving as a definition for *extended Gaussian maps* (Definition \[def:gaussexmor\]).

In , we use the generality of this construction to establish the following diagram of identity-on-objects functors between Markov categories, where the bottom row consists of decorated linear maps and the top row of decorated linear relations: $$\begin{tikzcd}
{{{\mathsf}{LinRel}}^+} && {{{\mathsf}{AffRel}}^+} && {{\mathsf}{GaussEx}}\\
\\
{\mathsf{Vec}}&& {{\mathsf}{Aff}}&& {{\mathsf}{Gauss}}\arrow[from=3-1, to=1-1]
\arrow[from=3-3, to=1-3]
\arrow[from=3-5, to=1-5]
\arrow[from=3-1, to=3-3]
\arrow[from=3-3, to=3-5]
\arrow[from=1-1, to=1-3]
\arrow[from=1-3, to=1-5]
\arrow["{\mathsf{supp}}"', from=3-5, to=1-3]
\end{tikzcd} \label{eq:thediagram}$$ In all categories of this diagram, the objects are finite-dimensional vector spaces $X$. Recall that a *linear relation* between vector spaces is a relation $R \subseteq X \times Y$ that is also a vector subspace; an *affine relation* is a relation that is also an affine subspace (see ). The remaining Markov categories in the diagram are defined as

-   ${\mathsf{Vec}}$: vector spaces and linear functions

-   ${{\mathsf}{Aff}}$: vector spaces and affine-linear functions

-   ${{\mathsf}{LinRel}}^+$: vector spaces and left-total linear relations

-   ${{\mathsf}{AffRel}}^+$: vector spaces and left-total affine relations

The functor ${\mathsf{supp}}$ collapses an Gaussian distributions to their supports, which are affine subspaces.

Decorated Linear Maps
---------------------

Let $S : {\mathsf{Vec}}\to {\mathsf{CMon}}$ be a functor from the category of vector spaces into the category of commutative monoids and monoid homomorphisms. We think of elements $s \in S(Y)$ as "decorations" for linear maps into $Y$, and thus call $S$ a decoration functor.

We define a category ${\mathsf{Lin}_{S}}$ of $S$-decorated linear maps as follows:

1.  Objects are vector spaces $X$

2.  Morphisms are pairs $(f,s)$ where $f : X \to Y$ is a linear map and $s \in S(Y)$

3.  Composition is defined as follows: if $g : X \to Y, f : Y \to Z$, define $$(f,t) \circ (g,s) = (fg,t + S(f)(s))$$ Note that addition takes place in the commutative monoid $S(Z)$.

There is a faithful inclusion $J : {\mathsf{Vec}}\to {\mathsf{Lin}_{S}}$ sending $f$ to $(f,0)$. The functor $U : {\mathsf{Lin}_{S}} \to {\mathsf{Vec}}$ which forgets the decoration is an opfibration; a decorated map $(f,s) : X \to Y$ is opcartesian if and only if $s$ is a unit in the monoid $S(Y)$. In fact, ${\mathsf{Lin}_{S}}$ is precisely the (op-)Grothendieck construction for $S$ seen as a functor ${\mathsf{Vec}}\to \mathsf{Cat}$.

We argue that ${\mathsf{Lin}_{S}}$ has the structure of a symmetric monoidal category with the tensor $X \otimes Y = X \times Y$ on objects. For this, we first observe that $S$ is automatically lax monoidal; for this we define natural maps $\oplus : S(X) \times S(Y) \to S(X \times Y)$ given as follows: For $(s,t) \in S(X) \times S(Y)$, let $s \oplus t = S(i_X)(s) + S(i_Y)(t)$ where $i_X : X \to X \times Y, i_Y : Y \to X \times Y$ are the biproduct inclusions. We can now define the tensor of decorated map as $(f,s) \otimes (g,t) = (f \times g, s \oplus t)$. The monoidal category ${\mathsf{Lin}_{S}}$ is in general not cartesian; it does however inherit copy and delete maps from ${\mathsf{Vec}}$. The category ${\mathsf{Lin}_{S}}$ is a Markov category if and only if deleting is natural, i.e. $S(0) \cong 0$.

\[ex:bottomrow\] We reconstruct the bottom row of for the following decoration functors:

1.  For $S(X)=0$, ${\mathsf{Lin}_{S}}$ is equivalent to ${\mathsf{Vec}}$.

2.  For $S(X)=X$, ${\mathsf{Lin}_{S}}$ is equivalent to ${{\mathsf}{Aff}}$. A map $X \to Y$ consists of a pair $(f,y)$ with $f : X \to Y$ linear and $y \in Y$.

3.  Define ${\mathsf{Cov}}(X) = \{ \sigma : X^* \times X^* \to {\mathbb R}\text{ positive semidefinite form} \}$ to be the set of covariance forms. This is a commutative monoid under pointwise addition, and is functorial via ${\mathsf{Cov}}(f)(\sigma)(g,h) = \sigma(gf,hf)$. Let $S(X) = X \times {\mathsf{Cov}}(X)$, then ${\mathsf{Lin}_{S}}$ is precisely ${{\mathsf}{Gauss}}$.

Decorated Linear Relations
--------------------------

Given a decoration functor $S : {\mathsf{Vec}}\to {\mathsf{CMon}}$, we define $S$-decorated linear relations by maintaining a locus of nondeterminism $D$ similar to Definition \[def:gaussex\].

\[def:rel\] We define a category ${\mathsf{LinRel}_{S}}$ as follows:

1.  objects are vector spaces $X$

2.  morphisms in ${\mathsf{LinRel}_{S}}(X,Y)$ are triples $(D,f,s)$ where $D \subseteq Y$ is a vector subspace, $f : X \to Y/D$ is a linear map and $s \in S(Y/D)$.

Intuitively, the subspace $D$ represents the direction of complete ignorance, so we only decorate the quotient.

Composition of $(D,g,s) : X \to Y$ and $(E,f,t) : Y \to Z$ is slightly more involved: We first define the composite subspace $F$ as $E + f[D]$, which is well-defined. The composite $Y \xrightarrow{f} Z/E \to Z/F$ vanishes on $D$ and so descends to $\tilde f : Y/D \to Z/F$. We define the composite as $$(E,f,t) \circ (D,g,s) = (F,\tilde f g, S(\tilde f)(s) + S(Z/E \to Z/F)(t))$$

To understand the name 'decorated linear relation', we consider the case $S=0$ where we obtain that ${\mathsf{LinRel}_{S}}$ is equivalent to ${{\mathsf}{LinRel}}^+$. The key observation is the following:

To give a left-total linear relation $R \subseteq X \times Y$ is to give subspace $D \subseteq Y$ and a linear function $f : X \to Y/D$ to the quotient.

The correspondence is fully spelled out in Proposition \[prop:linrel\_characterization\]. This means we can think of a left-total relation $R$ as a linear function with nondeterministic noise $x \mapsto f(x) + D$ along some subspace $D$. This is similar to a decorated linear map, however the choice of the linear map $f$ is no longer unique, so further quotienting is required, as we discuss now:\
**As a quotient:** We can demystify the composition of ${\mathsf{LinRel}_{S}}$ by first constructing an auxiliary category and then quotienting it by a congruence. We first consider the decoration functor ${\mathsf{Sub}}: {\mathsf{Vec}}\to {\mathsf{CMon}}$ defined by ${\mathsf{Sub}}(X) = \{ D \subseteq X \text{ vector subspace } \}$. Each ${\mathsf{Sub}}(X)$ is a commutative monoid under Minkowski addition $D + E$, and the functorial action for $f : X \to Y$ is direct image $D \mapsto f[D]$, which is a monoid homomorphism. Now we consider the category ${\mathsf{Lin}_{S \times {\mathsf{Sub}}}}$ where morphisms $X \to Y$ are by definition triples $(f,s,D)$ with $s \in S(Y)$ and $D \subseteq Y$, and composition is $(f,t,E) \circ (g,s,D) = (fg, t + S(f)(s), E + f[D])$. This has all the data for ${\mathsf{LinRel}_{S}}$ and explains why the composite subspace is formed the way it is.

However some pieces of data need to be identified if they agree on the quotient by $D$: We define an equivalence relation $(f_1,s_1,D_1) \approx (f_2,s_2,D_2)$ if $D_1=D_2$ are the same subspace $D$, and $\pi_{Y/D}f_1 = \pi_{Y/D}f_2$ and $S(\pi_{Y/D})(s_1) = S(\pi_{Y/D})(s_2) \in S(Y/V)$ where $\pi_{Y/D} : Y \to Y/D$ is the quotient map.

The relation $\approx$ is a congruence relation, and ${\mathsf{LinRel}_{S}}$ is the quotient of ${\mathsf{Lin}_{S \times {\mathsf{Sub}}}}$ under $\approx$. ${\mathsf{LinRel}_{S}}$ is symmetric monoidal and inherits the copy and delete maps from ${\mathsf{Vec}}$. It is a Markov category if $S(0) \cong 0$.

See Appendix ().

\[def:gaussexmor\] We define the Markov category ${{\mathsf}{GaussEx}}$ to be ${\mathsf{LinRel}_{X \times {\mathsf{Cov}}}}$.

In the style of Proposition \[prop:linrel\_characterization\], we can show that ${\mathsf{LinRel}_{X}} \cong {{\mathsf}{AffRel}}^+$. This way the ${\mathsf{LinRel}_{}}$ construction applied to Example \[ex:bottomrow\] gives rise to the top row of .

Relationships between the Constructions {#sec:relationships}
---------------------------------------

The constructions ${\mathsf{Lin}_{}}$ and ${\mathsf{LinRel}_{}}$ are themselves functorial:

Let $S,T : {\mathsf{Vec}}\to {\mathsf{CMon}}$ be decoration functors and $\alpha : S \to T$ a natural transformation. Then we have induced monoidal identity-on-objects functors $$\begin{aligned}
    F_\alpha &: {\mathsf{Lin}_{S}} \to {\mathsf{Lin}_{T}}, (f,s) \mapsto (f,\alpha(s)) \\
    G_\alpha &: {\mathsf{LinRel}_{S}} \to {\mathsf{LinRel}_{T}}, (D,f,s) \mapsto (D,f,\alpha(s)) 
    \end{aligned}$$ which preserve copy and delete structure.

This proposition accounts for all functors in the diagram except for ${\mathsf{supp}}$. For every decoration functor $S$, we obtain an inclusion functor ${\mathsf{Lin}_{S}} \to {\mathsf{LinRel}_{S}}$ by choosing locus of nondeterminism $D=0$, that is forming the composite $$\begin{tikzcd}
{{\mathsf{Lin}_{S}}} && {{\mathsf{Lin}_{S \times {\mathsf{Sub}}}}} && {{\mathsf{LinRel}_{S}}}
\arrow["{F_{{\mathsf{id}}\times 0}}", from=1-1, to=1-3]
\arrow[two heads, from=1-3, to=1-5]
\end{tikzcd}$$

From a decorated linear relation, we can extract its locus of nondeterminism by forgetting the decoration via the following composite: $$\begin{tikzcd}
{{\mathsf{LinRel}_{S}}} && {{\mathsf{LinRel}_{0}} \cong {{\mathsf}{LinRel}}^+}
\arrow["{G_0}", from=1-1, to=1-3]
\end{tikzcd}$$ Recall that the support of a Gaussian distribution $\mathcal N(\mu,\Sigma)$ on ${\mathbb R}^n$ is the affine space $\mu + {\mathsf{col}}(\Sigma)$. This construction can be extended functorially to ${{\mathsf}{Gauss}}$ as follows:

We have a functor ${\mathsf{supp}}: {{\mathsf}{Gauss}}\to {{\mathsf}{AffRel}}^+$ which takes the Gaussian noise to its support. Concretely on ${\mathbb R}^n$, ${\mathsf{supp}}(x \mapsto Ax + \mathcal N(\mu, \Sigma)) = (x \mapsto Ax + \mu + {\mathsf{col}}(\Sigma))$.

We construct ${\mathsf{supp}}$ as the composite $$\begin{tikzcd}
    {{\mathsf{Lin}_{X \times {\mathsf{Cov}}}}} && {{\mathsf{Lin}_{X \times {\mathsf{Sub}}}}} && {{\mathsf{LinRel}_{X}} \cong {{\mathsf}{AffRel}}^+}
    \arrow["{F_{{\mathsf{id}}_X \times \alpha}}", from=1-1, to=1-3]
    \arrow[two heads, from=1-3, to=1-5]
    \end{tikzcd}$$ where $\alpha_X : {\mathsf{Cov}}(X) \to {\mathsf{Sub}}(X)$ is takes the covariance form $\sigma$ to the annihilator of its kernel. Naturality is nontrivial and can be shown using the Cholesky composition, which makes use of the positive semidefiniteness of $\sigma$.

Conditioning
------------

Our presentation of extended Gaussians is not measure-theoretic. Categorical probability theory @fritz [@cho_jacobs; @dariothesis] is a general language of probability which allows one to precisely state concepts such as determinism, independence and support in an abstract way without relying on a measure-theoretic formalism. An important notion is that of a *conditional distribution* @fritz [Section 11], which means we can break the sampling of a joint distribution $(X,Y) \sim \psi$ into two parts: We first sample $X \sim \psi_X$ from the marginal, and then sample $Y$ dependently on $X$, $Y \sim \psi_{|X}(X)$. Conditional distributions are extended to *conditionals* of arbitrary morphisms $f : A \to X \otimes Y$ in @fritz [Definition 11.5], which is a morphism $f_{|X} : X \otimes A \to Y$ satisfying the equation $f(x,y|a) = f_{|X}(y|x,a)f_X(y|a)$ in the appropriate categorical sense.\
Conditionals in ${{\mathsf}{Gauss}}$ exist and are given by the usual conditional distributions @fritz [11.8]. ${{\mathsf}{LinRel}}^+$ also has conditionals, which are essentially given by re-ordering a relation $R \subseteq A \times (X \times Y)$ to a relation $R_{|X} \subseteq (X \times A) \times Y$. This $R_{|X}$ may not be left-total yet, but any linear relation can be extended to a left-total one outside of its domain.\
We will now show that extended Gaussians have conditionals too: We proceed by picking a convenient complement to the locus of nondeterminism $D$, which lets reduce the proof to the existence of conditionals in ${{\mathsf}{Gauss}}$ and ${{\mathsf}{LinRel}}^+$ separately. In fact, this strategy works for general decorated linear relations:

\[thm:cond\] If ${\mathsf{Lin}_{S}}$ has conditionals, so does ${\mathsf{LinRel}_{S}}$.

Let $\varphi \in {\mathsf{LinRel}_{S}}(A, X \times Y)$ be represented modulo $\approx$ by $(f,\mu,D)$ with $\mu \in S(X \times Y)$. By Lemma \[lemma:nicecomplement\], there exists a complement $K \subseteq X \times Y$ of $D$ such that $K_X$ is a complement of $D_X$ in $X$. We then take $P_K,P_D : X \times Y \to X \times Y$ to be the projection endomorphisms, and replace the representative $\mu$ by $S(P_K)(\mu)$ and $f$ by $P_Kf$ without affecting $\varphi$.

Now we consider $(f,\mu) \in {\mathsf{Lin}_{S}}(A, X \times Y)$ and find a conditional $(g,\psi) \in {\mathsf{Lin}_{S}}(X \times A, Y)$. This means we can obtain $(X_1,Y_1) \sim f(a) + \mu$ as $$\begin{aligned}
    X_1 &\sim f_X(a) + \mu_X \\
    Y_1 &\sim g(x,a) + \psi 
    \end{aligned}$$ Similarly we can use conditionals in ${{\mathsf}{LinRel}}^+$ to find a linear function $h : X \to Y$ and a subspace $H \subseteq Y$ such that $(X_2,Y_2) \sim D$ can be obtained as $$\begin{aligned}
    X_2 &\sim D_X \\
    Y_2 &\sim h(X_2) + H
    \end{aligned}$$ Thus a joint sample $(X,Y) \sim \varphi(a)$ can be obtained as follows $$\begin{aligned}
    X_1 &\sim f_X(a) + \mu_X \\
    X_2 &\sim D_X \\
    X &= X_1 + X_2 \\
    Y_1 &\sim g(X_1,a) + \psi \\
    Y_2 &\sim h(X_2) + H \\
    Y &= Y_1 + Y_2
    \end{aligned}$$ Because we have chosen $K$ such that $K_X \oplus D_X = X$, we can extract the values of $X_1,X_2$ from $X$ via the projections $P_{K_X}, P_{D_X} : X \to X$ as $X_1 = P_{K_X}(X)$ and $X_2 = P_{D_X}(X)$. We can thus read off a conditional for $\varphi$ by combining the two individual conditionals, namely $$\varphi|_X(x,a) = g(P_{K_X}(x),a) + h(P_{D_X}(x)) + \psi + H$$

\[coro:cond\] ${{\mathsf}{GaussEx}}$ has all conditionals.

For example, the procedure of Theorem \[thm:cond\] recovers Example \[ex:extendedexample\] systematically: In order to find a conditional distribution for the joint distribution $(Z_1,Z_2) \sim {\mathcal N}(0,I_2) + \{ (x,x) : x \in {\mathbb R}\}$ on ${\mathbb R}\times {\mathbb R}$, we choose the particular complement $K=0 \times {\mathbb R}$ of the diagonal and obtain desired decomposition $$\begin{aligned}
    Z_1 &\sim {\mathbb R}\\
    Z_2 &\sim Z_1 + {\mathcal N}(0,2)
    \end{aligned}$$

**Conditioning on equality:** In the context of Gaussian probability, we can condition two random variables $U,V$ to be *exactly equal* @2021compositional by introducing an auxiliary variable $Z = U-V$ for their difference, and computing the conditional distribution $(U,V)|Z=0$. For example, if $U,V \sim N(0,1)$ are independent standard normal variables, then the conditional distribution $U|Z=0$ is ${\mathcal N}(0,0.5)$. Note that the variance of $U$ has shrunk after conditioning, because $V$ is itself concentrated around $0$ and thus induces a stronger concentration in $U$.

We can now formally show that our uniform extended Gaussians $u_X$ (Definition \[def:uniform\]) are really uninformative in the sense that conditioning on equality with a uniform variable does not change the prior:

\[prop:uninformative\] For every extended Gaussian prior $\psi$ on $X$, if $U \sim \psi$ and $V \sim u_X$, then $U|(U=V)$ still has distribution $\psi$.

We introduce an auxiliary random variable $Z = U-V$ and show that the following two joint distributions over $(U,V,Z)$ are equal: $$\begin{Bmatrix}
    U \sim \psi \\
    V \sim u_X \\
    Z = U - V
    \end{Bmatrix} =
    \begin{Bmatrix}
    Z \sim u_X \\
    U \sim \psi \\
    V = U - Z 
    \end{Bmatrix}$$ The right-hand side lets us read off the conditional on $Z$ immediately. Conditioning on equality now means setting $Z=0$, after which we obtain $U \sim \psi, V = U$.

Outlook and Discussion {#sec:discussion}
======================

We have defined a sound mathematical model for reasoning about Gaussian distributions together with uninformative priors, and gained a new and generalized perspective on linear relations. We gave a construction to combine probability and nondeterminism on vector spaces, which is generally not possible in a seamless way @weakdist [@nogo].

The original motivation for this work comes from programming language theory and the semantics of probabilistic programming @2021compositional. While in statistics literature, noisy observations are seen as the primary operation of interest, our focus on singular covariances is natural from a logical or programming perspective: Copying and conditioning are fundamental operations, however they do lead to highly singular distributions. In @gaussianinfer, we defined a programming language for Gaussian probability with a first-class exact conditioning construct. In this setting, the existence of a uniform distribution is simply asking for a unit for the conditioning operation. Further connections between probability and logic arise both through the analogy with unification in logic programming @staton:predicate_logic and the relationship to linear relations (). Linear relations have have been used in graphical reasoning and signal-flow diagrams @bsz [@baez:props; @baez:control].

We believe that ${{\mathsf}{GaussEx}}$ solves the outstanding characterization of ${{\mathsf}{Cond}}({{\mathsf}{Gauss}})$ in @2021compositional. The category ${{\mathsf}{Cond}}({{\mathsf}{GaussEx}})$ can express both logical (solving linear equations) and probabilistic computation (conditioning Gaussians). We believe that it is a hypergraph category @hypergraphcats, with conditioning as multiplication and uniform distributions as units. @coecke:inference have suggested hypergraph categories as the right setting for inference, and celebrated algorithms such as message-passing inference can be formulated fully abstractly there @morton:inference. We believe that categorical probability theory is a compelling language to go beyond measure-theoretic foundations and talking about statistical models and conditioning in a high-level way. The systematic connection with probabilistic programming languages is elaborated in @dariothesis.

We hope that extended Gaussians will also be useful outside of theoretical computer science. Here we have introduced them primarily from an algebraic and category-theoretic viewpoint and shown a duality theorem (Theorem \[exduality\]) linking them to certain types of quadratic forms. We would like to explore further connections to statistics @quotients and functional analysis: An important step is to topologize the homsets of ${{\mathsf}{GaussEx}}$ and characterize which in which ways Gaussian distributions can converge to extended Gaussians. Ideally this would exhibit the construction of extended Gaussians as a form of topological completion. The aspect of considering improper priors as limits of normalized ones is treated in @akaike [@approximations].

It also seems interesting to consider extended Gaussians under the 'principle of transformation groups' (e.g. @jaynes:priors). In @2021compositional [VI], we remark that ${{\mathsf}{Gauss}}$ is essentially presented as a PROP by the invariance of the standard normal distribution under the orthogonal group $O(n)$. We expect the uniform distributions to be presented by invariance under all of $\mathsf{GL}(n)$.

Acknowledgements
================

It has been useful to discuss this work with many people. Particular thanks go to Tobias Fritz, Bart Jacobs, Dusko Pavlovic, Sam Staton and Alexander Terenin.

Appendix
========

Glossary: Linear Algebra {#sec:glossary}
------------------------

All vector spaces are assumed finite dimensional. For vector subspaces $U,V \subseteq X$, their *Minkowski sum* is the subspace $U+V = \{ u + v : u \in U, v \in V \}$. If furthermore $U \cap V = 0$, we call their sum a *direct sum* and write $U \oplus V$. A *complement* of $U$ is a subspace $V$ such that $U\oplus V = X$. An *affine subspace* $W \subseteq X$ is a subset of the form $x + U$ for some $x \in X$ and a (unique) vector subspace $U \subseteq X$. The space $W$ is called a *coset* of $U$ and the cosets of $U$ organize into the quotient vector space $X/U = \{ x + U : x \in X \}$.\
An affine-linear map $f : X \to Y$ between vector spaces is a map of the form $f(x) = g(x) + y$ for some linear function $g : X \to Y$ and $y \in Y$. Vector spaces and affine-linear maps form a category ${{\mathsf}{Aff}}$.\
A *linear relation* $R \subseteq X \times Y$ is a relation which is also a vector subspace of $X \times Y$. An *affine relation* $R \subseteq X \times Y$ is a relation which is also an affine subspace of $X \times Y$. We write $R(x) {\stackrel{\text{def}}=}\{ y \in Y : (x,y) \in R \}$. A relation $R \subseteq X \times Y$ is *left-total* if $R(x) \neq \emptyset$ for all $x \in X$.\
Linear relations, affine relations and left-total relations are closed under the usual composition of relations. We denote by ${{\mathsf}{LinRel}}^+$ and ${{\mathsf}{AffRel}}^+$ the categories whose objects are vector spaces, and morphisms are left-total linear and affine relations respectively. Those categories are Markov categories (left-totality must be assumed for discarding to be natural).\
The following characterization underlies Definition \[def:rel\]: Every left-total linear relation can be written as a 'linear map with nondeterministic noise' $x \mapsto f(x) + D$.

\[prop:linrel\_characterization\] Let $R \subseteq X \times Y$ be a left-total linear relation. Then

1.  \[it:r0\] $R(0)$ is a vector subspace of $Y$

2.  \[it:coset\] $R(x)$ is a coset of $R(0)$ for every $x \in X$

3.  \[it:lin\] the assignment $x \mapsto R(x)$ is a well-defined linear map $X \to Y/R(0)$

4.  \[it:bij\] every linear map $X \to Y/D$ is of that form for a unique left-total linear relation

For \[it:r0\], consider $y,y' \in R(0)$ (by assumption nonempty), then by linearity of $R$ $$(0,y) \in R, (0,y') \in R \Rightarrow (0,\alpha y + \beta y') \in R$$ so $R(0)$ is a vector subspace. For \[it:coset\], we can find some $w \in R(x)$ and wish to show that $R(x) = w + R(0)$. Indeed if $y \in R(x)$ then $(x,y) - (x,w) = (0,y-w) \in R$ so $y-w \in R(0)$, hence $y \in w+R(0)$. Conversely for all $z \in R(0)$ we have $(x,w+z) = (x,w)+(0,z) \in R$ so $w+z \in R(x)$. This completes the proof that $R(x)$ is a coset. For \[it:lin\], the previous point shows that the map $\rho : x \mapsto R(x)$ is a well-defined map $X \to Y/R(0)$. It remains to show it is linear. That is, if $w \in R(x)$ and $z \in R(y)$ then $\alpha w + \beta z \in R(\alpha x + \beta y)$. This follows immediately from the linearity of $R$. For the last point \[it:bij\], given a linear map $f : X \to Y/V$ we construct the relation $$(x,y) \in R \Leftrightarrow y \in f(x)$$ which is left-total because $f(x) \neq \emptyset$. To see that $R$ is linear, let $(x,y) \in R, (x',y') \in R$ meaning $y - z \in V$ and $y' - z \in V$ for representatives $z,z'$ of $f(x),f(x')$. Linearity of $f$ means that $\alpha z + \beta z'$ is a representative of $f(\alpha x + \beta x')$. Thus $$\alpha y + \beta y' - (\alpha z + \beta z') = \alpha(y-z) + \beta (y'-z') \in V$$

#### Annihilators

\[prop:annih\]

1.  Taking annihilators is order-reversing and involutive

2.  If $D \subseteq S \subseteq X$, then $S^\bot \subseteq D^\bot \subseteq X^*$ and we have a canonical isomorphism $$(S/D)^* \cong D^\bot/S^\bot \label{iso1}$$ and similarly for $K \subseteq F \subseteq X^*$, we have $$(F/K)^* \cong K^\bot/F^\bot \label{iso2}$$

3.  We have $$(V + W)^\bot = V^\bot \cap W^\bot$$ $$(F \cap W)^\bot = F^\bot + G^\bot$$ If $D \subseteq X$ and $f : X \to Y$, then $$(f[D])^\bot = \{ g \in Y^* : gf \in D^\bot \}$$ If $U \subseteq X, V \subseteq Y$, we have a canonical isomorphism $$(U \times V)^\bot \cong U^\bot \times V^\bot$$

Standard. An explicit description of the canonical iso is given as follows.

1.  We define $\alpha : D^\bot/S^\bot \to (S/D)^*$ as follows. If $f \in D^\bot$, then $f$ is a function $X \to {\mathbb R}$ such that $f|_D = 0$. The restriction $f|_S : S \to {\mathbb R}$ thus descends to the quotient $S/D \to {\mathbb R}$, and we let $\widetilde \alpha(f) = f|_S$. To check this is well-defined, notice that the kernel of $\widetilde \alpha$ consists of those $f \in X^*$ such that $f|_S=0$, that is $S^\bot$.

2.  We define $\alpha^{-1} : (S/D)^* \to D^\bot/S^\bot$ as follows. An element $f \in (S/D)^*$ is a function $f : S \to {\mathbb R}$ with $S|_D = 0$. Find any extension of $f$ to a linear function $\bar f : X \to {\mathbb R}$ (such an extension exists because $S$ is a retract of $X$). Then still $\bar f|_D = 0$, so $\bar f \in D^\bot$. It remains to show that the choice of extension does not matter in the quotient $D^\bot/S^\bot$. Indeed if $\bar f_2$ is another extension, then $(\bar f - \bar f_2)|_S = f - f = 0$, hence $(\bar f - \bar f_2) \in S^\bot$.

Conditioning {#sec:cond_appendix}
------------

The proof of the existence of conditionals in ${\mathsf{LinRel}_{S}}$ proceeds by picking a good complement to the locus of nondeterminism $D \subseteq X \times Y$ as follows:

\[lemma:nicecomplement\] Let $V \subseteq X \times Y$ be a vector subspace, and let $V_X \subseteq X$ be its projection. Then there exists a complement $K \subseteq X \times Y$ of $V$ such that $K_X$ is a complement of $V_X$.

We give an explicit construction, where in fact we can choose $K$ to be a cartesian product of subspaces $U \times W$. Define $$V_X = \{ x : (x,y) \in V \} \qquad H = \{ y : (0,y) \in V \}$$ We argue that if $U \oplus V_X = X$ and $W \oplus H = Y$, then $(U \times W) \oplus V = X \times Y$. First we prove that $(U \times W) \cap V = 0$: Indeed, if $(u,w) \in V$ for $u \in U, w \in W$, then $u \in V_X$, but that implies $u=0$. So we know $(0,w) \in V$, i.e. $w \in H$. Thus $w=0$.

It remains to show that we can write every $(x,y)$ as $(u+v_1,w+v_2)$ with $u \in U, w \in W$ and $(v_1,v_2) \in V$.

1.  We can write $x = u+v_1$ with $u \in U$ and $v_1 \in V_X$.

2.  We claim that there exists a $b \in W$ such that $(v_1,b) \in V$. Because $v_1 \in V_X$, there exists some $b' \in Y$ such that $(v_1,b') \in V$. We now decompose $b' = b + h$ for $b \in W, h \in H$. By definition of $H$, we have $(0,h) \in V$, so $(v_1,b)=(v_1,b')-(0,h) \in V$.

3.  Write $y = w' + h$ with $w' \in W, h \in H$ and define $w = w' - b$ and $v_2 = h + b$. Then we have $w \in W$ and $(v_1,v_2) = (v_1,b)+(0,h) \in V$, and as desired $$(u,w) + (v_1,v_2) = (x, w' - b + h + b) = (x,w' + h) = (x,y).$$

Composition and Congruence {#sec:welldef}
--------------------------

For the construction of ${\mathsf{LinRel}_{S}}$, it remains to check that the relation $\approx$ is a monoidal congruence on ${\mathsf{Lin}_{S \times {\mathsf{Sub}}}}$. Recall that $(f,s,U) \approx (g,t,U)$ if and only if $\pi f = \pi g$ and $S(\pi)(s) = S(\pi)(t)$ where $\pi = \pi_{Y/U} : Y \to Y/U$ is the quotient map.\
**Transitivity:** Let $(f, r, V) \approx (g, s, V) \approx (h, t, V)$ meaning $\pi f = \pi g = \pi h$ and $S(\pi)(r) = S(\pi)(s) = S(\pi)(t)$. Then clearly also $(f, r, V) \approx (h, t, V)$.\
**Congruence:** Let $f_i : Y \to Z$, $g_i : X \to Y$ and $U \subseteq Y, V \subseteq Z$ be given for $i=1,2$, and assume that $(f_1, r_1, V) \approx (f_2, r_2, V)$ and $(g_1, s_1, U) \approx (g_2,s_2,U)$. We need to show that $(f_1g_1, r_1 + S(f_1)(s_1), V+f_1[U]) \approx (f_2g_2, r_2 + S(f_2)(s_2), V+f_2[U])$.\
Firstly, we need that $W = V+f_1[U] = V+f_2[U]$ is well-defined. Let $\pi = \pi_{Y/V}$ then by assumption $\pi f_1 = \pi f_2$, so $f_1(y) - f_2(y) \in V$ for all $y \in Y$. Hence $f_1[U] + V = f_2[U] + V$.\
Now, we need to show that $f_1g_1(x) - f_2g_2(x) \in W$. We know that $f_1(x) - f_2(x) \in V$ and $g_1(y) - g_2(y) \in U$, hence $$\begin{aligned}
f_2(g_2(x)) - f_1(g_1(x)) = \underbrace{f_1(g_2(x) - g_1(x))}_{\in f_1[U]} + \underbrace{(f_2(g_2(x)) - f_1(g_2(x)))}_{\in V} \in W\end{aligned}$$ For the decorations, we know by assumption that $S(\pi_{Y/U})(s_1) = S(\pi_{Y/U})(s_2)$ and $S(\pi_{Z/V})(r_1) = S(\pi_{Z/V})(r_2)$. We need to show that $S(\pi_{Z/W})(r_1 + S(f_1)(s_1)) = S(\pi_{Z/W})(r_2 + S(f_2)(s_2))$.

The composites $Y \xrightarrow{f_i} Z \xrightarrow{\pi_{Z/W}} Z/W$ are equal for $i=1,2$ and vanish on $U$, thus descending to a map $\tilde f : Y/U \to Z/W$, and we obtain $$\begin{aligned}
S(\pi_{Z/W})(S(f_1)(s_1)) &= S(\pi_{Z/W}f_1)(s_1) \\
&= S(\tilde f\pi_{Y/U})(s_1) \\
&= S(\tilde f)(S(\pi_{Y/U})(s_1)) \\
&= S(\tilde f)(S(\pi_{Y/U})(s_2)) \\
&= S(\tilde f\pi_{Y/U})(s_2) \\
&= S(\pi_{Z/W}f_2)(s_2) \\
&= S(\pi_{Z/W})(S(f_2)(s_2)) \end{aligned}$$ The desired proposition now follows easily from the additivity of $S(\pi_{Z/W})(-)$.\
**Tensor:** Let $f_i : X' \to X$, $g_i : Y' \to Y$ and $U \subseteq X, V \subseteq Y$ be given for $i=1,2$ and assume $(f_1,s_1,U) \approx (f_2,s_2,U)$ and $(g_1,t_1,V) \approx (g_2,t_2,V)$. We need to show that $(f_1 \times g_1, s_1 \oplus t_1, U \times V) \approx (f_2 \times g_2, s_2 \oplus t_2, U \times V)$.\
It is immediate that $(f_1(x),g_1(y)) - (f_2(x),g_2(x)) \in U \times V$ for all $x \in X', y \in Y'$. For the sum of decorations, we chase them around the diagram $$\begin{tikzcd}
X & {X \times Y} & {(X \times Y)/(U \times V)} & {X \times Y} & Y \\
\\
{X/U} && {(X/U)\times(Y/V)} && {Y/V}
\arrow["{\pi_{X/U}}"', from=1-1, to=3-1]
\arrow["{i_1}"', from=3-1, to=3-3]
\arrow["{i_2}", from=3-5, to=3-3]
\arrow["{\pi_{Y/V}}", from=1-5, to=3-5]
\arrow["{i_X}", from=1-1, to=1-2]
\arrow["\pi", from=1-2, to=1-3]
\arrow["\pi"', from=1-4, to=1-3]
\arrow["{i_Y}"', from=1-5, to=1-4]
\arrow["\cong"{marking}, from=3-3, to=1-3]
\end{tikzcd}$$ to notice that $S(\pi)(S(i_X)(s_i))$ depends only on $S(\pi_{X/U})(s_i)$.

[^1]: throughout, $\sigma$ denotes the *variance* (and not standard deviation) for consistency with the covariance matrices $\Sigma$ in the multivariate case. We make no further mentions of standard deviations.

{'source': 'arXiv_out/2204'}