Conservative Quantization of Covariance Matrices with Applications to Decentralized Information Fusion

Abstract

Information fusion in networked systems poses challenges with respect to both theory and implementation. Limited available bandwidth can become a bottleneck when high-dimensional estimates and associated error covariance matrices need to be transmitted. Compression of estimates and covariance matrices can endanger desirable properties like unbiasedness and may lead to unreliable fusion results. In this work, quantization methods for estimates and covariance matrices are presented and their usage with the optimal fusion formulas and covariance intersection is demonstrated. The proposed quantization methods significantly reduce the bandwidth required for data transmission while retaining unbiasedness and conservativeness of the considered fusion methods. Their performance is evaluated using simulations, showing their effectiveness even in the case of substantial data reduction.

1. Introduction

Interconnected sensor systems can gather more data, are more robust to faults and outliers, and can cover larger regions than a single sensor system. Such networked systems can also benefit from heterogeneous sensing modalities and parameterizations. Typical examples are wireless sensor networks which are used, for instance, in environmental monitoring [1,2,3], building automation [4,5], or moving object tracking [6,7]. A single node in a wireless sensor network often has limited energy, processing, and storage resources, and the wireless transmission of data is the most energy-intensive operation performed by the node while processing sensor data exhibits relatively low energy demands [8]. Even for networked systems that do not use wireless data transmission or that have sufficient energy resources, communication can be a limiting factor when nodes need to transmit large-scale estimates, which may occur in cooperative map building [9], cooperative localization [10,11], or multi-object tracking [12].

From the accruing sensor data, the interconnected devices can compute state estimates locally, e.g., by employing Kalman filter methods. Such estimates are typically supplied with error covariance matrices, which need to be transmitted and stored alongside the estimates, to be able to assess their uncertainty and combine them reliably. Therefore, reducing the amount of transmitted data through prior compression is key to meeting bandwidth limitations when high-dimensional state estimates are exchanged and to ensure long operating times of battery-driven sensor nodes when wireless data transmission is used. A comprehensive survey of lossless and lossy compression methods that are suitable for wireless sensor networks is given in [13]. The surveyed methods include multiple probabilistic quantization-based approaches [14,15,16,17] tailored to estimation problems. However, only scalar estimates are considered and their respective variances are assumed to be known to the receiver. Quantization as a means of data reduction has also been applied to Kalman filtering, a prominent example being the sign of innovations Kalman filter [18,19]. Again, the required covariance matrices are assumed to be known to the receiver. In contrast to the previous works, it is assumed in [20] that the receiver has no prior knowledge of the covariance matrices, which therefore need to be transmitted via the network. The authors develop data reduction methods for covariance matrices based on conservative diagonal approximations and, in [21], they investigate techniques to select subsets of the information to be transmitted. These methods assess how the selected information contributes to the receiver’s estimation quality.

In this paper, similarly to [20], we assume that the receiver has no knowledge about the covariance matrix at the transmitter. Hence, the sender has to prepare both its estimate and covariance matrix for transmission. In general, the covariance matrix will not be diagonal and dominates the amount of data that needs to be transmitted as its number of elements grows quadratically with the dimension of the estimate. The individual quantization of each coefficient constitutes a promising approach to reduce the data. However, such a quantized covariance matrix, in general, does not reliably account for the uncertainty of the estimate and can even violate the positive definiteness of the covariance matrix. For this reason, we study and compare two different approaches to compute a quantized covariance matrix that conservatively bounds the actual error covariance matrix. The first scheme employs a quantization based on diagonal dominance while the second scheme relies on a modified Cholesky decomposition. To further compress the data to be transmitted, we also investigate a quantization of the estimates. As typical fusion algorithms rely on unbiasedness, we employ a quantizer that preserves this property. The proposed quantization schemes yield conservative estimates that reliably assess the estimation error and can be further processed at the receiver.

At the receiver, the estimates are typically fed to a fusion algorithm to combine them with other estimates and to improve the estimation accuracy. Fusion algorithms that strive to minimize the error of the fusion result need access to the covariance matrices of the input estimates. Optimal fusion algorithms [22,23] can be designed if cross-correlations between the estimates are also known. They typically require the transmission of additional information [24] or specific communication strategies [25,26]. In the case where correlations are unknown, conservative fusion algorithms compute a bound on the actual but unknown error covariance matrix of the fusion results. Examples of such algorithms are covariance intersection (CI) [27], fast covariance intersection (FCI) [28,29], and inverse covariance intersection (ICI) [30,31], which are guaranteed to produce results with a conservative uncertainty quantification in the form of a covariance matrix. Other algorithms such as ellipsoidal intersection (EI) [32,33] provide no such guarantee but are typically less conservative. In this paper, we study how the proposed quantization schemes integrate with fusion algorithms and consider both optimal fusion and covariance intersection.

This paper is an extended version of [34], which proposed a quantization technique for covariance intersection. Here, we study the use of quantization in a broader sense to cover different fusion algorithms, and we propose an additional quantization scheme for covariance matrices that provides tighter bounds at the expense of higher computational demand. In total, this paper’s contributions address three different aspects:

• Estimate Quantization. We extend the probabilistic quantization method from [15,35] to vector-valued correlated random variables in order to generate unbiased quantized estimates [34] and conservative bounds on their error covariance matrices.

• Covariance Quantization. We propose two approaches to the conservative quantization of covariance matrices. The first scheme uses diagonal dominance [34]. As an alternative, we study a modified Cholesky decomposition and compare it to the first approach.

• Fusion of Estimates. We apply the quantization schemes to both an optimal fusion algorithm and covariance intersection in order to demonstrate that reliable estimates are attained.

Implementations of the proposed quantization schemes, written in Python, are provided as supplementary material, the link to which can be found at the end of the paper.

2. Notation

Lower case letters $x\in \mathbb{R}$ denote scalar quantities and additional underlining $\underline{x}\in {\mathbb{R}}^n$ indicates n-dimensional vector-valued quantities. The standard basis vectors of ${\mathbb{R}}^n$ are ${\underline{e}}_1,\dots ,{\underline{e}}_n$ and ${\underline{0}}_n$ denotes the n-dimensional zero vector. Bold uppercase letters indicate $n\times n$-matrices such as $\mathbf{X}\in {\mathbb{R}}^{n\times n}$. The ith coefficient of a vector and the $i,j$th coefficient of a matrix are ${\underline{x}}^i$ and ${\mathbf{X}}^{i,j}$, respectively. In addition, index ranges such as $i:j$, $i:$, and $:i$ are used to extract subvectors and submatrices. As an example, ${\underline{x}}^{i:j}$ is the subvector containing the ith to the jth coefficient of $\underline{x}$ and ${\mathbf{X}}^{:i,j}$ are the first i coefficients of the jth column of $\mathbf{X}$. The use of boldface as in $\mathrm{x}\in \mathbb{R}$ and $\underline{\mathrm{x}}\in {\mathbb{R}}^n$ indicates random scalars and random vectors, respectively. Uppercase calligraphic letters $\mathcal{A}$ indicate sets. In particular, ${\mathcal{S}}^n$ is used to denote the set of symmetric matrices in ${\mathbb{R}}^{n\times n}$ and ${\mathcal{S}}_{+}^n$ to denote the set of symmetric positive semi-definite (PSD) matrices in ${\mathbb{R}}^{n\times n}$. For $\mathbf{X}\in {\mathcal{S}}_{+}^n$ and $\mathbf{Y}\in {\mathcal{S}}_{+}^n$, the notation $\mathbf{X}⪯\mathbf{Y}$ signifies that $\mathbf{Y}-\mathbf{X}\in {\mathcal{S}}_{+}^n$. If $\mathbf{X}⪯\mathbf{Y}$ then $\mathbf{Y}\in {\mathcal{S}}_{+}^n$ is called an upper bound for $\mathbf{X}\in {\mathcal{S}}_{+}^n$. For (conditional) expectations the symbols $\mathbb{E}(·)$ and $\mathbb{E}(·|·)$ are used. The unconditional covariance between two random quantities is designated by $\mathbb{C}(·,·)$ or by $\mathbb{C}(·)$ if the arguments are identical. Similarly, the conditional covariance is denoted by $\mathbb{C}(·,·|·)$ or $\mathbb{C}(·|·)$.

3. Considered Problem

The process of quantization approximates a continuous quantity using a discrete one. In this work, we consider the quantization of covariance matrices and estimates with the goal of reducing the bandwidth and storage requirements on an interconnected sensor system. We demonstrate how optimal fusion and covariance intersection can be applied to quantized data while retaining some of their desirable properties.

For our purposes, a quantizer is a map $q:\mathcal{D}\to \mathcal{C}$, where the domain $\mathcal{D}$ is a closed, coefficient-wise bounded subset of either ${\mathbb{R}}^n$ or ${\mathbb{R}}^{n\times n}$, and the codomain $\mathcal{C}$, the so-called codebook, is a finite set. Quantizing covariance matrices for use in fusion methods is not straightforward. Naive coefficient-wise quantization of a covariance matrix can lead to a result that underestimates the uncertainty encoded in the original covariance matrix, or even worse, is not a valid covariance matrix anymore. This can cause divergence in certain estimation algorithms [27]. Ideally, the quantized covariance matrix $q\left(\mathbf{X}\right)$ should be an upper bound on a conservative estimate of the original matrix $\mathbf{X}$ in the sense that $q\left(\mathbf{X}\right)⪰\mathbf{X}$ holds. This averts divergence and guarantees that the confidence ellipsoid induced by $q\left(\mathbf{X}\right)$ contains the one induced by $\mathbf{X}$ [27]. The described situation is illustrated on the left side of Figure 1. Conservative quantization of covariance matrices can be achieved by enforcing certain conditions on the quantization error, as will be discussed in Section 4.

Similarly to quantizing covariance matrices, quantizing estimates for use in fusion methods creates certain challenges. Deterministic quantization of an estimate can introduce bias and additional noise, which (1) biases the results obtained from fusion methods and (2) invalidates the covariance matrix associated with the estimate. This is visualized on the right side of Figure 1. Both of the aforementioned issues can be addressed by using randomized quantizers, which will be discussed in Section 5 in the context of applying fusion methods to quantized data.

4. Conservative Quantization of Covariance Matrices

In the following, conservative quantizers for covariance matrices, i.e., symmetric positive semi-definite (PSD) matrices, are derived. To that end, let $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ be a quantizer that maps PSD matrices from an coefficient-wise bounded and closed set ${\mathcal{D}}_c\subset {\mathcal{S}}_{+}^n$ to a finite codebook ${\mathcal{C}}_c\subset {\mathbb{R}}^{n\times n}$. The quantizer $q_c$ should satisfy the condition

(1)$\begin{array}{cc}\hfill \forall \mathbf{X}\in {\mathcal{D}}_c:q_c\left(\mathbf{X}\right)& ⪰\mathbf{X},\hfill \end{array}$

to ensure that the quantized matrix $q_c\left(\mathbf{X}\right)$ is an upper bound on the original matrix $\mathbf{X}$. With the quantization error defined as $\Delta \left(\mathbf{X}\right)=q_c\left(\mathbf{X}\right)-\mathbf{X}$, this can also be expressed as

(2)$\begin{array}{cc}\hfill \forall \mathbf{X}\in {\mathcal{D}}_c:\Delta \left(\mathbf{X}\right)& ⪰\mathbf{0}.\hfill \end{array}$

In other words, the quantization error must always be PSD for the quantized matrix to be an upper bound on the original matrix. Ideally, the quantizer should not only produce conservative results but should also minimize the total quantization error ${\parallel \Delta \left(\mathbf{X}\right)\parallel }_F$. This requires enumerating all elements in ${\mathcal{C}}_c$ in the worst case and is thus not computationally feasible, even for relatively small matrices. Practical quantizers will therefore not be able to minimize the total quantization error exactly. To remain computationally tractable, the quantizers considered in this work operate in two steps: First, the off-diagonal coefficients are individually rounded to the nearest codeword in some off-diagonal codebook ${\mathcal{C}}_o\subset \mathbb{R}$. Then, the diagonal coefficients are individually rounded up to a codeword in some diagonal codebook ${\mathcal{C}}_d\subset \mathbb{R}$ so as to make the quantization error PSD.

4.1. Covariance Quantization Based on Diagonal Dominance

The rounding method for diagonal coefficients considered in this section is based on the notion of diagonal dominance. Diagonal dominance is a simple sufficient condition for a symmetric matrix, such as the quantization error matrix $\Delta \left(\mathbf{X}\right)$, to be PSD. A symmetric matrix $\mathbf{X}\in {\mathcal{S}}^n$ is said to be diagonally dominant if

(3)${\mathbf{X}}^{i,i}\ge \sum _{j=1\ne i}^n\left|{\mathbf{X}}^{i,j}\right|$

holds for each row $i=1,\dots ,n$. The connection between diagonal dominance and positive semi-definiteness is obtained immediately by applying the Gershgorin circle theorem [36] to a diagonally dominant matrix to lower bound its eigenvalues.

Theorem 1.

Let $\mathbf{X}\in {\mathcal{S}}^n$ be diagonally dominant, then $\mathbf{X}⪰\mathbf{0}$ holds.

The approach to conservative quantization of a PSD matrix $\mathbf{X}\in {\mathcal{D}}_c$ pursued here is to first quantize the off-diagonal coefficients of $\mathbf{X}$ using a codebook ${\mathcal{C}}_o\subset \mathbb{R}$ and to then quantize the diagonal coefficients using a codebook ${\mathcal{C}}_d\subset \mathbb{R}$ such that (3) is satisfied for the quantization error $\Delta \left(\mathbf{X}\right)$. This leads to the quantizer

(4)$\begin{array}{cc}\hfill q_c{\left(\mathbf{X}\right)}^{i,j}& =\left\{\begin{array}{cc}⌈{\mathbf{X}}^{i,j}+\sum _{k=1\ne i}^n\left|\mathrm{rd}\left({\mathbf{X}}^{i,k}\right)-{\mathbf{X}}^{i,k}\right|⌉,\hfill & i=j\hfill \\ \mathrm{rd}\left({\mathbf{X}}^{i,j}\right),\hfill & i\ne j\hfill \end{array}\right.,\hfill \end{array}$

where $\mathrm{rd}(·)$ rounds to the nearest codeword in the off-diagonal codebook ${\mathcal{C}}_o$ and $\lceil ·\rceil$ rounds up to the nearest codeword in the diagonal codebook ${\mathcal{C}}_d$. The codebooks are

(5)$\begin{array}{cc}\hfill {\mathcal{C}}_o& =\{x_{max}-k{\delta }_o|0\le k<2^b\},\hfill \end{array}$

(6)$\begin{array}{cc}\hfill {\mathcal{C}}_d& =\{x_{max}+(n-1){\delta }_o/2-k{\delta }_d|0\le k<2^b\},\hfill \end{array}$

where $x_{max}$ is the maximum off-diagonal codeword, and ${\delta }_o=x_{max}/2^{b-1}$, ${\delta }_d=(x_{max}+(n-1){\delta }_o/2)/(2^b-1)$ are quantization resolutions, with b the number of bits per codeword. This choice enables the following theorem regarding well definedness.

Theorem 2.

The quantizer $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ proposed above is well defined if the coefficients of all matrices $\mathbf{X}\in {\mathcal{D}}_c$ are contained in the interval $[min\left({\mathcal{C}}_o\right),max\left({\mathcal{C}}_o\right)]$.

Proof. 

The quantization error of an off-diagonal coefficient is ${\delta }_o/2$ at most. Therefore

$\begin{array}{c}\hfill {\mathbf{X}}^{i,i}+\sum _{k=1\ne i}^n\left|\mathrm{rd}\left({\mathbf{X}}^{i,k}\right)-{\mathbf{X}}^{i,k}\right|\le max\left({\mathcal{C}}_o\right)+(n-1)\frac{{\delta }_o}{2}\end{array}$

holds for all diagonal coefficients. Since the right hand side equals $max\left({\mathcal{C}}_d\right)$, rounding up the perturbed diagonal coefficients is always possible, and the claim holds. □

When not stated otherwise, the above conditions for well defined $q_c$ are implicitly assumed to hold. The next theorem confirms that the output of $q_c$ is indeed an upper bound for its input.

Theorem 3.

The quantizer $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ proposed above has PSD quantization error $\Delta \left(\mathbf{X}\right)=q_c\left(\mathbf{X}\right)-\mathbf{X}$ for all $\mathbf{X}\in {\mathcal{D}}_c$ and is thus conservative, that is, $q_c\left(\mathbf{X}\right)⪰\mathbf{X}$ holds for all $\mathbf{X}\in {\mathcal{D}}_c$.

Proof. 

In the following, we omit the dependence of $\Delta \left(\mathbf{X}\right)$ on $\mathbf{X}$ for brevity. The off-diagonal quantization errors are ${\Delta }^{i,j}=\mathrm{rd}\left({\mathbf{X}}^{i,j}\right)-{\mathbf{X}}^{i,j}$ and the diagonal ones are

$\begin{array}{cc}\hfill {\Delta }^{i,i}& =⌈{\mathbf{X}}^{i,i}+\sum _{j=1\ne i}^n\left|{\Delta }^{i,j}\right|⌉-{\mathbf{X}}^{i,i}.\hfill \end{array}$

By the definition of $\lceil ·\rceil$ we have

$\begin{array}{cc}\hfill {\Delta }^{i,i}& \ge \sum _{j=1\ne i}^n\left|{\Delta }^{i,j}\right|\hfill \end{array}$

and the claim follows from Theorem 1. □

Furthermore, the quantizer $q_c$ introduced above is optimal in the sense that, given codebooks ${\mathcal{C}}_{d/o}$, there is no quantizer with symmetric diagonally dominant quantization error $\Delta \left(\mathbf{X}\right)$ that has a smaller total quantization error ${\parallel \Delta \left(\mathbf{X}\right)\parallel }_F$.

Theorem 4.

Let $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ be defined by (4) with coefficient-wise codebooks ${\mathcal{C}}_d$ and ${\mathcal{C}}_o$ defined by (5) and (6). Given $\mathbf{X}\in {\mathcal{D}}_c$, the quantization error $\Delta \left(\mathbf{X}\right)=q_c\left(\mathbf{X}\right)-\mathbf{X}$ is the minimizer of

(7) $\begin{array}{cccccc}\hfill \underset{\Delta \in {\mathcal{S}}^n}{\mathrm{minimize}}& \hfill & & {\parallel \Delta \parallel }_F^2\hfill & \hfill & \end{array}$

(8) $\begin{array}{cccccc}\hfill \mathrm{subject}\mathrm{to}& & & \sum _{j=1\ne i}^n|{\Delta }^{i,j}|\le {\Delta }^{i,i}\hfill & & \forall i=1\dots n\hfill \end{array}$

(9) $\begin{array}{cccccc}& & & {\mathbf{X}}^{i,i}+{\Delta }^{i,i}\in {\mathcal{C}}_d\hfill & & \forall i=1\dots n\hfill \end{array}$

(10) $\begin{array}{cccccc}& & & {\mathbf{X}}^{i,j}+{\Delta }^{i,j}\in {\mathcal{C}}_o\hfill & & \forall i\ne j\hfill \end{array}$

where the dependency of $\Delta \left(\mathbf{X}\right)$ on $\mathbf{X}$ has been omitted for brevity.

Proof. 

The problem can be reformulated as a nested minimization, the inner one

$\begin{array}{cccccc}\hfill \underset{{\Delta }^{i,i}\in \mathbb{R},i=1,\dots ,n}{\mathrm{minimize}}& \hfill & & \sum _{i=1}^n{|{\Delta }^{i,i}|}^2\hfill & \hfill & \\ \hfill \mathrm{subject}\mathrm{to}& & & \sum _{j=1\ne i}^n|{\Delta }^{i,j}|\le {\Delta }^{i,i}\hfill & & \forall i=1\dots n\hfill \\ & & & {\mathbf{X}}^{i,i}+{\Delta }^{i,i}\in {\mathcal{C}}_d\hfill & & \forall i=1\dots n\hfill \end{array}$

being over the diagonal coefficients given the off-diagonal coefficients and the outer one

$\begin{array}{cccccc}\hfill \underset{{\Delta }^{i,j}\in \mathbb{R},i\ne j}{\mathrm{minimize}}& \hfill & & \sum _{i=1}^n|{\Delta }^{i,i*}{|}^2+\sum _{i=1}^n\sum _{j=1\ne i}^n{|{\Delta }^{i,j}|}^2\hfill & \hfill & \\ \hfill \mathrm{subject}\mathrm{to}& & & {\mathbf{X}}^{i,j}+{\Delta }^{i,j}\in {\mathcal{C}}_o\hfill & & \forall i\ne j\hfill \end{array}$

being over the off-diagonal coefficients given the solutions ${\Delta }^{i,i*}$ of the inner optimization. Furthermore, the inner minimization can be split into decoupled minimizations

$\begin{array}{cccccc}\hfill \underset{{\Delta }^{i,i}\in \mathbb{R}}{\mathrm{minimize}}& \hfill & & |{\Delta }^{i,i}{|}^2\hfill & \hfill & \\ \hfill \mathrm{subject}\mathrm{to}& & & \sum _{j=1\ne i}^n|{\Delta }^{i,j}|\le {\Delta }^{i,i}\hfill & & \\ & & & {\mathbf{X}}^{i,i}+{\Delta }^{i,i}\in {\mathcal{C}}_d\hfill & \end{array}$

for $i=1,\dots ,n$. By definition of the $\lceil ·\rceil$ operation

$\begin{array}{cc}\hfill {\Delta }^{i,i*}& =⌈{\mathbf{X}}^{i,i}+\sum _{j=1\ne i}^n\left|{\Delta }^{i,j}\right|⌉-{\mathbf{X}}^{i,i}\hfill \end{array}$

are the optimal solutions to these subproblems. They exist because $q_c$ is well defined. The minimum cost of each decoupled problem is thus

$\begin{array}{cc}\hfill |{\Delta }^{i,i*}{|}^2& ={\left|⌈{\mathbf{X}}^{i,i}+\sum _{j=1\ne i}^n\left|{\Delta }^{i,j}\right|⌉-{\mathbf{X}}^{i,i}\right|}^2,\hfill \end{array}$

which is non-decreasing in each $\left|{\Delta }^{i,j}\right|$. Using this intermediate result, the outer minimization problem can be seen to attain its minimum by separately minimizing the $|{\Delta }^{i,j}{|}^2$, as due to the non-decreasing property, $|{\Delta }^{i,i*}{|}^2$ is minimal if each $|{\Delta }^{i,j}{|}^2$ is minimal. Thus, the minimum is, by definition of $\mathrm{rd}(·)$, attained by setting ${\Delta }^{i,j*}=\mathrm{rd}\left({\mathbf{X}}^{i,j}\right)$. □

Although the above quantizer minimizes the conservativeness of the quantized matrix in the sense of Theorem 4, the inequalities (3) are only sufficient and not necessary for the quantization error to be PSD. Hence, the results of this method are usually more conservative than necessary. The proposed quantizer has a low computational complexity of $\mathcal{O}\left(n^2\right)$ because the matrix coefficients are quantized individually.

4.2. Covariance Quantization Based on Modified Cholesky Decomposition

The covariance matrix quantization approach presented in the previous section is computationally efficient but can be overly conservative. An alternative quantizer that is guaranteed to be less conservative at the cost of increased computational expense is presented in this section. The basic approach of first quantizing the off-diagonal coefficients and then finding quantized diagonal coefficients that make the overall quantization result conservative is retained. However, instead of employing diagonal dominance to find the quantized diagonal coefficients, a modified Cholesky factorization adopted from [37] is leveraged. We motivate the proposed method by first introducing the Cholesky decomposition in conjunction with a result relating its existence to positive semi-definiteness [36] (Corollary 7.2.9).

Theorem 5.

Let $\mathbf{X}\in {\mathcal{S}}^n$ be a symmetric matrix and $\mathbf{P}\in {\mathbb{R}}^{n\times n}$ a permutation matrix (Permutation matrices are orthogonal matrices that arise by permuting the rows and columns of an identity matrix. Matrix multiplication with a permutation matrix permutes either the rows or the columns of the other matrix, depending on the order of multiplication). Then there is a lower triangular matrix $\mathbf{L}\in {\mathbb{R}}^{n\times n}$ with nonnegative diagonal coefficients such that

(11) $\begin{array}{cc}\hfill \mathbf{P}\mathbf{X}{\mathbf{P}}^{\top }& =\mathbf{L}{\mathbf{L}}^{\top }\hfill \end{array}$

holds if and only if $\mathbf{X}$ is positive semi-definite. The above factorization is called a (pivoted) Cholesky decomposition of $\mathbf{X}$ with Cholesky factor $\mathbf{L}$.

Should $\mathbf{X}$ not be PSD, a so-called modified Cholesky decomposition can be performed to find a diagonal nonnegative matrix $\mathbf{D}$ such that a Cholesky decomposition $\mathbf{P}(\mathbf{X}+\mathbf{D}){\mathbf{P}}^{\top }=\mathbf{L}{\mathbf{L}}^{\top }$ exists [37,38,39]. In the following, the basic recursive approach to simultaneously compute the matrices $\mathbf{D}$, $\mathbf{P}$, and $\mathbf{L}$ is introduced, based on the exposition in [37]. The recursion begins by setting ${\mathbf{X}}_1=\mathbf{X}$. The computations

(12)$\begin{array}{cc}\hfill {\overline{\mathbf{X}}}_k& ={\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }+s_k{\underline{e}}_k{\underline{e}}_k^{\top }\hfill \end{array}$

(13)$\begin{array}{cc}\hfill {\mathbf{X}}_{k+1}& ={\overline{\mathbf{X}}}_k-{\underline{x}}_k{\underline{x}}_k^{\top }\hfill \end{array}$

are then performed for $k=1,\dots ,n$. Each ${\mathbf{P}}_k$ is a permutation matrix swapping two rows and columns such that ${\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k,k}={\mathbf{X}}_k^{m,m}$ with $m\ge k$ determined according to some criterion. For now we will assume $m=k$ so that ${\mathbf{P}}_k=\mathbf{I}$. The $s_k$ are nonnegative perturbations applied to the kth diagonal coefficient of ${\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }$. The vector ${\underline{x}}_k\in {\mathbb{R}}^n$ is selected to cancel the kth row and column of ${\overline{\mathbf{X}}}_k$. This is achieved by letting

(14)${\underline{x}}_k^{\top }=\left\{\begin{array}{cc}{\underline{0}}_n^{\top }\hfill & ,{\overline{\mathbf{X}}}_k^{k,k:}={\underline{0}}_{n-k+1}^{\top }\hfill \\ \left[\begin{array}{ccc}{\underline{0}}_{k-1}^{\top }& \sqrt{{\overline{\mathbf{X}}}_k^{k,k}}& \frac{{\overline{\mathbf{X}}}_k^{k,k+1:}}{\sqrt{{\overline{\mathbf{X}}}_k^{k,k}}}\end{array}\right]\hfill & ,\mathrm{else}\hfill \end{array}\right.$

and results in the $k-1$ upper-most/left-most rows and columns of ${\mathbf{X}}_k$ being zero. For the recursion to terminate successfully, $s_k$ must either be such that ${\overline{\mathbf{X}}}_k^{k,k}$ is positive or such that ${\overline{\mathbf{X}}}_k^{k,k:}$ is zero. This is always possible, as $s_k$ can be arbitrarily large. Unraveling the recursion up to ${\mathbf{X}}_{n+1}$ and using the fact that ${\mathbf{X}}_{n+1}=\mathbf{0}$ gives

(15)$\begin{array}{cc}\hfill \mathbf{0}& =\left(\prod _{k=1}^n{\mathbf{P}}_{n-k+1}\right)\left(\mathbf{X}+\sum _{k=1}^n{s}_k\left(\prod _{j=1}^k{\mathbf{P}}_j^{\top }{\underline{e}}_k\right){\left(\prod _{j=1}^k{\mathbf{P}}_j^{\top }{\underline{e}}_k\right)}^{\top }\right){\left(\prod _{k=1}^n{\mathbf{P}}_{n-k+1}\right)}^{\top }\hfill \\ \hfill & \phantom{=}-\sum _{k=1}^n\left(\prod _{j=1}^{n-k}{\mathbf{P}}_{n-j+1}{\underline{x}}_k\right){\left(\prod _{j=1}^{n-k}{\mathbf{P}}_{n-j+1}{\underline{x}}_k\right)}^{\top }.\hfill \end{array}$

This can be written in the more condensed form

(16)$\begin{array}{cc}\hfill \mathbf{0}& =\mathbf{P}\left(\mathbf{X}+\mathbf{D}\right){\mathbf{P}}^{\top }-\mathbf{L}{\mathbf{L}}^{\top }\hfill \end{array}$

by introducing $\mathbf{P}={\prod }_{k=1}^n{\mathbf{P}}_{n-k+1}$, $\mathbf{L}=\left[\begin{array}{ccc}{\underline{l}}_1& \cdots & {\underline{l}}_n\end{array}\right]$ with ${\underline{l}}_k={\prod }_{j=1}^{n-k}{\mathbf{P}}_{n-j+1}{\underline{x}}_k$, and

(17)$\mathbf{D}=\sum _{k=1}^n{s}_k\left(\prod _{j=1}^k{\mathbf{P}}_j^{\top }{\underline{e}}_k\right){\left(\prod _{j=1}^k{\mathbf{P}}_j^{\top }{\underline{e}}_k\right)}^{\top }.$

It can be shown that $\mathbf{P}$ is a permutation matrix, $\mathbf{L}$ is lower triangular with nonnegative diagonal coefficients, and $\mathbf{D}$ has its diagonal populated with the $s_k$ and is otherwise zero. Hence, (16) is a Cholesky decomposition of $\mathbf{X}+\mathbf{D}$ and according to Theorem 5, $\mathbf{X}+\mathbf{D}$ must be positive semi-definite. Note that the above recursion can be computed in-place essentially like an ordinary Cholesky decomposition (see for instance [40] (Algorithm 4.2.2)), the main differences being the diagonal shifts $s_k$ and allowing ${\underline{x}}_k={\underline{0}}_n$.

We will now describe how the above approach can be applied to finding quantized diagonal coefficients that make the overall quantization result conservative. For that, first quantize each off-diagonal coefficient of the given PSD matrix $\mathbf{X}\in {\mathcal{D}}_c$ by rounding it to the nearest codeword in ${\mathcal{C}}_o=\{x_{max}-k{\delta }_o|0\le k<2^b\}$ (see Section 4.1) resulting in the preliminary quantized matrix and preliminary quantization error

(18)$\begin{array}{cccc}\hfill {\mathbf{X}}_o\left(\mathbf{X}\right)& =\left\{\begin{array}{cc}{\mathbf{X}}^{i,j},\hfill & i=j\hfill \\ \mathrm{rd}\left({\mathbf{X}}^{i,j}\right),\hfill & i\ne j\hfill \end{array}\right.,\hfill & \hfill {\Delta }_o\left(\mathbf{X}\right)& ={\mathbf{X}}_o-\mathbf{X}.\hfill \end{array}$

Note that in the remainder of this section we will omit the dependence of ${\mathbf{X}}_o\left(\mathbf{X}\right)$ and ${\Delta }_o\left(\mathbf{X}\right)$ on $\mathbf{X}$ for brevity. Since the diagonal elements of ${\Delta }_o$ are zero, ${\Delta }_o$ cannot be PSD unless it is zero, as can be easily verified. Then the modified Cholesky decomposition of ${\Delta }_o$ is computed, giving a diagonal matrix $\mathbf{D}$ such that ${\Delta }_o+\mathbf{D}⪰\mathbf{0}$ holds. Adding $\mathbf{D}$ to ${\mathbf{X}}_o$ and rounding the diagonal coefficients up to the nearest codeword in ${\mathcal{C}}_d=\{x_{max}+(n-1){\delta }_o/2-k{\delta }_d|0\le k<2^b\}$ (see Section 4.1) then gives the final quantization result

(19)$\begin{array}{cc}\hfill q_c\left(\mathbf{X}\right)& =\left\{\begin{array}{cc}⌈{\mathbf{X}}_o^{i,j}+{\mathbf{D}}^{i,j}⌉,\hfill & i=j\hfill \\ {\mathbf{X}}_o^{i,j},\hfill & i\ne j\hfill \end{array}\right..\hfill \end{array}$

Assume for the moment that the quantizer defined above is well-defined, i.e., that there always are codewords in ${\mathcal{C}}_d$ that the perturbed diagonal elements can be rounded up to. In that case, the following theorem applies.

Theorem 6.

The quantizer $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ as defined above is conservative.

Proof. 

Due to the modified Cholesky decomposition, it holds that ${\mathbf{X}}_o-\mathbf{X}+\mathbf{D}={\Delta }_o+\mathbf{D}⪰\mathbf{0}$. By rounding the diagonal of ${\mathbf{X}}_o+\mathbf{D}$ up, we get ${\mathbf{X}}_o+\mathbf{D}+{\Delta }_d$ where ${\Delta }_d$ is diagonal and nonnegative and thus ${\Delta }_d⪰\mathbf{0}$. Therefore, ${\mathbf{X}}_o+\mathbf{D}+{\Delta }_d-\mathbf{X}⪰{\mathbf{X}}_o+\mathbf{D}-\mathbf{X}⪰\mathbf{0}$ or equivalently $q_c\left(\mathbf{X}\right)⪰\mathbf{X}$ holds. □

So far, the diagonal perturbations $s_k$ have been assumed to be almost arbitrary. In order to guarantee that the quantizer is well-defined, we adopt the specific choice

(20)$\begin{array}{c}\hfill s_k=max\left\{0,{∥{\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k+1:,k}∥}_1-{\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k,k}\right\},\end{array}$

described in [37]. This has several advantageous implications as can be seen from Theorem 7 [37] (Theorem 5.1.2) and the subsequent corollaries.

Theorem 7.

If $s_k$ is chosen as in (20) to compute the modified Cholesky decomposition of some $\mathbf{X}\in {\mathcal{S}}^n$, then $\mathbf{X}+\mathbf{D}$ is positive semi-definite (it can be rank-deficient) and the upper bound

(21) $s_k\le max\left\{0,\underset{j}{max}\left(-{\mathbf{X}}^{j,j}+\sum _{i=1\ne j}^n\left|{\mathbf{X}}^{i,j}\right|\right)\right\}$

holds for $k=1,\dots ,n$. The result is valid, provided each ${\mathbf{P}}_k$ swaps the kth row and column only with some subsequent row and column.

Applying the above theorem to the quantizer proposed in this section, it is evident that with the given choice of $s_k$, the diagonal perturbations are always smaller than or equal to the maximum perturbation required by the quantization approach from Section 4.1. Inspecting the proof in [37], it can indeed be deduced that every $s_k$ is smaller than or equal to its corresponding perturbation (after permutation using the ${\mathbf{P}}_k$) in the diagonal dominance based approach.

Corollary 1.

The quantizer $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ proposed in this section is well defined if the coefficients of all matrices in ${\mathcal{D}}_c$ are in the interval $[min\left({\mathcal{C}}_o\right),max\left({\mathcal{C}}_o\right)]$.

Proof. 

By applying Theorem 7 to ${\Delta }_o$, it follows that $s_k\le {max}_j{\sum }_{i=1\ne j}^n\left|{\Delta }_o^{i,j}\right|$ holds for $k=1,\dots ,n$. Comparing to (4), $s_k$ can be seen to be smaller than the maximum amount added to diagonal coefficients by the quantizer from Section 4.1. Hence, following the same argument as for Theorem 2 and using the bound on $s_k$, the claim follows. □

Corollary 2.

The quantizer $q_c:{\mathcal{D}}_c\to {\mathcal{C}}_c$ proposed in this section has lower or identical total quantization error ${\parallel \Delta \parallel }_F$ compared to the quantizer from Section 4.1.

Proof. 

By the discussion above, the diagonal perturbations $s_k$ are smaller than or equal to those used by the quantizer based on diagonal dominance. This translates into a reduced absolute deviation from the original diagonal elements, also after rounding up. The off-diagonal quantization errors are identical. Hence, the total quantization error is less than or equal to that of the quantizer based on diagonal dominance. □

The final ingredient in the above quantization approach is the choice of the permutation matrices ${\mathbf{P}}_k$ which, up to now, have been assumed to be identity matrices. We adopt the choice of ${\mathbf{P}}_k$ proposed in [37], which greatly improved performance in our experiments. Each matrix ${\mathbf{P}}_k$ is chosen in order to swap two rows and columns such that ${\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k,k}={\mathbf{X}}_k^{m,m}$ with $m=arg{max}_{k\le i\le n}{\underline{g}}_k^i$ where ${\underline{g}}_k$ is a recursively computed vector initialized at $k=1$ using

(22)$\begin{array}{cc}\hfill {\underline{g}}_1^i& ={\mathbf{X}}^{i,i}-\sum _{j=1\ne i}^n\left|{\mathbf{X}}^{i,j}\right|,i=1,\dots ,n\hfill \end{array}$

and recursively updated for each $k=1,\dots ,n$ according to

(23)$\begin{array}{cc}\hfill {\underline{g}}_{k+1}^i& ={\left({\mathbf{P}}_k{\underline{g}}_k\right)}^i+\left|{\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k,i}\right|\left(1-\frac{\parallel {\left({\mathbf{P}}_k{\mathbf{X}}_k{\mathbf{P}}_k^{\top }\right)}^{k,k+1:}{\parallel }_1}{{\overline{\mathbf{X}}}_k^{k,k}}\right),i=k+1,\dots ,n\hfill \end{array}$

after choosing the respective ${\mathbf{P}}_k$ and $s_k$. These changes do not affect the theoretical results, as they only pertain to the strategy of choosing ${\mathbf{P}}_k$. We do not take into account the remaining modifications proposed in [37], as they do not seem to improve performance in our case. Due to the modified Cholesky decomposition, the quantizer introduced in this section has computational complexity of $\mathcal{O}\left(n^3\right)$, compared to the $\mathcal{O}\left(n^2\right)$ complexity of the quantizer from Section 4.1.

5. Applications to Information Fusion

The goal of any fusion algorithm is to combine estimates ${\underline{\mathrm{x}}}_a\in {\mathbb{R}}^n$ and ${\underline{\mathrm{x}}}_b\in {\mathbb{R}}^n$ of the same random quantity $\underline{\mathrm{x}}\in {\mathbb{R}}^n$ to obtain an, in some sense, improved estimate ${\underline{\mathrm{x}}}_f\in {\mathbb{R}}^n$ of $\underline{\mathrm{x}}$. Typically, the estimates ${\underline{\mathrm{x}}}_a$ and ${\underline{\mathrm{x}}}_b$ are provided in conjunction with error covariance matrix estimates ${\mathbf{C}}_{aa}\approx \mathbb{C}({\underline{\mathrm{x}}}_a-\underline{\mathrm{x}})$ and ${\mathbf{C}}_{bb}\approx \mathbb{C}({\underline{\mathrm{x}}}_b-\underline{\mathrm{x}})$ and the fusion method uses them to compute an error covariance estimate ${\mathbf{C}}_{ff}\approx \mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$ for the fused estimate ${\underline{\mathrm{x}}}_f$.

In the following, two fusion methods from the literature that are unbiased ($\mathbb{E}\left({\underline{\mathrm{x}}}_f\right)=\mathbb{E}\left(\underline{\mathrm{x}}\right)$) and conservative (${\mathbf{C}}_{ff}⪰\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$) under certain conditions, are introduced and their application with quantized error covariance matrices and estimate vectors is considered. In that context, a quantizer for unbiased estimate vectors is derived, that retains their unbiasedness and provides a conservative estimate of the error covariance matrix of the quantization result. Finally, it is demonstrated how the covariance quantization methods from Section 4 can be applied in conjunction with the unbiased estimate quantizer to retain unbiasedness and conservativeness of the fusion methods.

5.1. Optimal Fusion and Covariance Intersection

In the following, let ${\underline{\mathrm{x}}}_a\in {\mathbb{R}}^n$ and ${\underline{\mathrm{x}}}_b\in {\mathbb{R}}^n$ be unbiased estimates of some random vector $\underline{\mathrm{x}}\in {\mathbb{R}}^n$ and let

(24)${\mathbf{C}}_{cc}=\mathbb{C}\left(\left[\begin{array}{c}{\underline{\mathrm{x}}}_a-\underline{\mathrm{x}}\\ {\underline{\mathrm{x}}}_b-\underline{\mathrm{x}}\end{array}\right]\right)=\left[\begin{array}{cc}{\mathbf{C}}_{aa}& {\mathbf{C}}_{ab}\\ {\mathbf{C}}_{ba}& {\mathbf{C}}_{bb}\end{array}\right]$

be their joint error covariance matrix. The fused estimate and its associated estimated error covariance matrix will be denoted by ${\underline{\mathrm{x}}}_f$ and ${\mathbf{C}}_{ff}$, respectively. Note that ${\mathbf{C}}_{ff}$ need not necessarily be identical to the actual error covariance matrix $\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$. In case the cross-covariance ${\mathbf{C}}_{ab}$ is known, the optimal fusion result in the BLUE (best linear unbiased estimator) sense is given by the Bar-Shalom–Campo formulas [22]

(25)$\begin{array}{cc}\hfill {\underline{\mathrm{x}}}_f& ={\underline{\mathrm{x}}}_a+\left({\mathbf{C}}_{aa}-{\mathbf{C}}_{ab}\right){\left({\mathbf{C}}_{aa}+{\mathbf{C}}_{bb}-{\mathbf{C}}_{ab}-{\mathbf{C}}_{ba}\right)}^{-1}\left({\underline{\mathrm{x}}}_b-{\underline{\mathrm{x}}}_a\right),\hfill \end{array}$

(26)$\begin{array}{cc}\hfill {\mathbf{C}}_{ff}& ={\mathbf{C}}_{aa}-\left({\mathbf{C}}_{aa}-{\mathbf{C}}_{ab}\right){\left({\mathbf{C}}_{aa}+{\mathbf{C}}_{bb}-{\mathbf{C}}_{ab}-{\mathbf{C}}_{ba}\right)}^{-1}\left({\mathbf{C}}_{aa}-{\mathbf{C}}_{ba}\right).\hfill \end{array}$

The estimated error covariance matrix computed using the Bar-Shalom–Campo formulas is exact, i.e., ${\mathbf{C}}_{ff}=\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$ holds [22]. The cross-covariance ${\mathbf{C}}_{ab}$ required by (25) and (26) can be tracked, e.g., using samples [41] to encode the cross-correlations or by a square-root decomposition [24] of the noise covariance matrices. Both approaches require additional data to be transmitted. If the error covariance matrices ${\mathbf{C}}_{aa}$ and ${\mathbf{C}}_{bb}$ are not known, but upper bounds ${\widehat{\mathbf{C}}}_{aa}⪰{\mathbf{C}}_{aa}$ and ${\widehat{\mathbf{C}}}_{bb}⪰{\mathbf{C}}_{bb}$ are available, applying (25) and (26) using the estimates yields a conservative error covariance matrix estimate ${\mathbf{C}}_{ff}⪰\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$ [42].

In the common case where the cross-covariance is unknown but not negligible, setting ${\mathbf{C}}_{ab}=\mathbf{0}$ in (25) and (26) generally does not produce a conservative error covariance matrix estimate, i.e., ${\mathbf{C}}_{ff}\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$. This means that the confidence ellipsoid induced by ${\mathbf{C}}_{ff}$ does not contain the confidence ellipsoid induced by $\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$ for any $ϵ>0$. An example of this behavior is illustrated on the left side of Figure 2.

The covariance intersection (CI) algorithm, originally devised by Julier and Uhlmann [27], enables the conservative and unbiased fusion of the estimates ${\underline{\mathrm{x}}}_a$ and ${\underline{\mathrm{x}}}_b$, regardless of their generally unknown cross-covariance, as long as conservative error covariance matrix estimates ${\widehat{\mathbf{C}}}_{aa}⪰{\mathbf{C}}_{aa}$ and ${\widehat{\mathbf{C}}}_{bb}⪰{\mathbf{C}}_{bb}$ are available. The CI algorithm itself is defined by

(27)$\begin{array}{cc}\hfill {\mathbf{C}}_{ff}^{-1}& =\omega {\widehat{\mathbf{C}}}_{aa}^{-1}+(1-\omega ){\widehat{\mathbf{C}}}_{bb}^{-1},\hfill \end{array}$

(28)$\begin{array}{cc}\hfill {\mathbf{C}}_{ff}^{-1}{\underline{\mathrm{x}}}_f& =\omega {\widehat{\mathbf{C}}}_{aa}^{-1}{\underline{\mathrm{x}}}_a+(1-\omega ){\widehat{\mathbf{C}}}_{bb}^{-1}{\underline{\mathrm{x}}}_b,\hfill \end{array}$

where any $\omega \in [0,1]$ gives an unbiased estimate ${\underline{\mathrm{x}}}_f$ and an upper bound ${\mathbf{C}}_{ff}$ on its error covariance matrix $\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$. The weight $\omega$ is determined numerically by minimizing either the trace or the determinant of ${\mathbf{C}}_{ff}$. The right side of Figure 2 shows that using CI, the confidence ellipsoid induced by ${\mathbf{C}}_{ff}$ contains the one induced by $\mathbb{C}({\underline{\mathrm{x}}}_f-\underline{\mathrm{x}})$.

5.2. Unbiased Conservative Quantization of Estimates

Applying the Bar-Shalom–Campo formulas (25) and (26) and the covariance intersection Equations (27) and (28) to quantized estimate vectors requires some consideration as naively quantizing the unbiased estimate vectors ${\underline{\mathrm{x}}}_a$ and ${\underline{\mathrm{x}}}_b$ does not retain their unbiasedness which in turn leads to biased fused estimates ${\underline{\mathrm{x}}}_f$. Moreover, quantizing estimate vectors increases their error covariance matrices, which has to be accounted for in order to retain conservativeness of the fusion algorithms. To address these issues we derive a randomized quantizer for unbiased estimate vectors that produces unbiased quantized estimate vectors and provides an upper bound on their error covariance matrices.

We begin by introducing a randomized quantizer $q_s:{\mathcal{D}}_s\to {\mathcal{C}}_s$ with ${\mathcal{D}}_s\subset \mathbb{R}$ and ${\mathcal{C}}_s\subset \mathbb{R}$ satisfying $min\left({\mathcal{D}}_s\right)$, $max\left({\mathcal{D}}_s\right)\in {\mathcal{C}}_s$, that has the desired unbiasedness property. The quantizer was proposed for estimating quantization in a different but equivalent form in [15] (see also [35,43]) and is defined by

(29)$\begin{array}{cc}\hfill q_s\left(\widehat{\mathrm{x}}\right)& =\mathrm{rd}(\widehat{\mathrm{x}}+\mathrm{n}),\hfill \end{array}$

where $\widehat{\mathrm{x}}\in \mathbb{R}$ is an estimate of a random variable $\mathrm{x}\in \mathbb{R}$, $\mathrm{rd}(·)$ rounds to the nearest codeword in ${\mathcal{C}}_s$, and $\mathrm{n}\in \mathbb{R}$ is independently uniformly distributed in the closed interval $[-{\delta }_s/2,{\delta }_s/2]$. The quantizer therefore consists of rounding combined with additive dither [44]. The codebook is given by ${\mathcal{C}}_s=\{x_{max}-k{\delta }_s|0\le k<2^b\}$, where $x_{max}$ is the maximum codeword, ${\delta }_s=x_{max}/2^{b-1}$ is the increment between adjacent codewords, and b is the number of bits required to represent a codeword. The assumption $min\left({\mathcal{D}}_s\right),max\left({\mathcal{D}}_s\right)\in {\mathcal{C}}_s$ guarantees a quantization error bounded by ${\delta }_s$. It is shown in [15] that $q_s$ satisfies

(30)$\begin{array}{cccc}\hfill \mathbb{E}\left(q_s\left(\widehat{\mathrm{x}}\right)\right)& =\mathbb{E}\left(\widehat{\mathrm{x}}\right),\hfill & \hfill \mathbb{C}\left(q_s\left(\widehat{\mathrm{x}}\right)\right)& \le \mathbb{C}\left(\widehat{\mathrm{x}}\right)+{\delta }_s^2,\hfill \end{array}$

that is, it does not add bias and provides an upper bound on the quantization result’s variance. Undesirably, the upper bound is on the variance $\mathbb{C}\left(q_s\left(\widehat{\mathrm{x}}\right)\right)$, not the error variance $\mathbb{C}(q_s\left(\widehat{\mathrm{x}}\right)-\mathrm{x})$ and the two quantities coincide only when $\mathrm{x}$ is deterministic.

We propose a randomized quantizer $q_m:{\mathcal{D}}_m\to {\mathcal{C}}_m$ for coefficient-wise bounded estimate vectors $\widehat{\underline{\mathrm{x}}}\in {\mathcal{D}}_m\subset {\mathbb{R}}^n$ of some random vector $\underline{\mathrm{x}}\in {\mathbb{R}}^n$ that is an coefficient-wise version of the one given by (29) [34]. Its domain and codebook are the Cartesian products ${\mathcal{D}}_m={\mathcal{D}}_s^n$ and ${\mathcal{C}}_m={\mathcal{C}}_s^n$. The quantization process can thus be described by

(31)$\begin{array}{cc}\hfill q_m\left(\widehat{\underline{\mathrm{x}}}\right)& =\mathrm{rd}(\widehat{\underline{\mathrm{x}}}+\underline{\mathrm{n}})\hfill \end{array}$

where $\mathrm{rd}(·)$ now denotes coefficient-wise rounding and $\underline{\mathrm{n}}\in {\mathbb{R}}^n$ has independent coefficients uniformly distributed in the closed interval $[-{\delta }_s/2,{\delta }_s/2]$. As an immediate consequence of (30) applied coefficient-wise to $q_m\left(\widehat{\underline{\mathrm{x}}}\right)$, we have the following corollary.

Corollary 3.

Let $q_m:{\mathcal{D}}_m\to {\mathcal{C}}_m$ be as in (31) and $\widehat{\underline{\mathrm{x}}}\in {\mathcal{D}}_m$, then $\mathbb{E}\left(q_m\left(\widehat{\underline{\mathrm{x}}}\right)\right)=\mathbb{E}\left(\widehat{\underline{\mathrm{x}}}\right)$ holds.

Due to rounding and dither, the quantized estimate’s error $q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}}$ contains additional noise compared to the original estimate’s error $\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}}$. Consequently, the known error covariance matrix $\mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}})$ of the original estimate must be adapted to reflect the increased uncertainty. In general, computing the exact covariance matrix of $q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}}$ is infeasible without knowledge of the distribution (if the distribution of $\widehat{\underline{\mathrm{x}}}$ was known, the approach in [45] could be used to approximate $\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}})$ arbitrarily well) of $\widehat{\underline{\mathrm{x}}}$. Therefore, a conservative upper bound for $\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}})$ in a similar vein as (30), is determined.

Theorem 8.

Let $q_m:{\mathcal{D}}_m\to {\mathcal{C}}_m$ be as in (31) and let $\widehat{\underline{\mathrm{x}}}\in {\mathcal{D}}_m$ be an estimate of a random vector $\underline{\mathrm{x}}\in {\mathbb{R}}^n$, then $\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}})⪯\mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}})+{\delta }_s^2\mathbf{I}$ holds.

Proof. 

The estimation error covariance matrix after quantization can be expanded into

$\begin{array}{cc}\hfill \mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\underline{\mathrm{x}})& =\mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}})+\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})+\mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}},q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})+\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}},\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}})\hfill \end{array}$

by adding and subtracting $\widehat{\underline{\mathrm{x}}}$. The cross-terms can be shown to be zero by using the definition of $q_m$, unbiasedness, and the tower rule to obtain

(32)$\begin{array}{cc}\hfill \mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}},q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})& =\mathbb{E}\left(\mathbb{E}\left((\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}}){(\mathrm{rd}(\widehat{\underline{\mathrm{x}}}+\underline{\mathrm{n}})-\widehat{\underline{\mathrm{x}}})}^{\top }|\widehat{\underline{\mathrm{x}}}\right)\right).\hfill \end{array}$

Due to $q_m$ being unbiased (also conditionally), $\mathbb{E}\left(\mathrm{rd}(\widehat{\underline{\mathrm{x}}}+\underline{\mathrm{n}})|\widehat{\underline{\mathrm{x}}}\right)=\widehat{\underline{\mathrm{x}}}$ holds. Since $\underline{\mathrm{x}}$ and $\underline{\mathrm{n}}$ are independent, we have $\mathbb{E}\left(\underline{\mathrm{x}}\mathrm{rd}{(\widehat{\underline{\mathrm{x}}}+\underline{\mathrm{n}})}^{\top }|\widehat{\underline{\mathrm{x}}}\right)=\mathbb{E}\left(\underline{\mathrm{x}}|\widehat{\underline{\mathrm{x}}}\right)\mathbb{E}\left(\mathrm{rd}{(\widehat{\underline{\mathrm{x}}}+\underline{\mathrm{n}})}^{\top }|\widehat{\underline{\mathrm{x}}}\right)$. Applying these equations to the inner expectation of (32) shows that

$\begin{array}{cc}\hfill \mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}},q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})& =\mathbb{E}\left(\widehat{\underline{\mathrm{x}}}{\widehat{\underline{\mathrm{x}}}}^{\top }-\widehat{\underline{\mathrm{x}}}{\widehat{\underline{\mathrm{x}}}}^{\top }-\mathbb{E}\left(\underline{\mathrm{x}}|\widehat{\underline{\mathrm{x}}}\right){\widehat{\underline{\mathrm{x}}}}^{\top }+\mathbb{E}\left(\underline{\mathrm{x}}|\widehat{\underline{\mathrm{x}}}\right){\widehat{\underline{\mathrm{x}}}}^{\top }\right)=\underline{0},\hfill \end{array}$

as claimed. As $\mathbb{C}(\widehat{\underline{\mathrm{x}}}-\underline{\mathrm{x}})$ is known, it only remains to bound $\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})$. Since $q_m$ is (conditionally) unbiased and $\underline{\mathrm{n}}$ has independent coefficients,

$\begin{array}{cc}\hfill \mathbb{E}\left((q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i)(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^j-{\widehat{\underline{\mathrm{x}}}}^j)|\widehat{\underline{\mathrm{x}}}\right)& =\mathbb{E}\left(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i|\widehat{\underline{\mathrm{x}}}\right)\mathbb{E}\left(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^j-{\widehat{\underline{\mathrm{x}}}}^j|\widehat{\underline{\mathrm{x}}}\right)=0\hfill \end{array}$

follows for $i\ne j$, which by the tower rule and unbiasedness results in

$\begin{array}{c}\hfill \mathbb{C}(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i,q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^j-{\widehat{\underline{\mathrm{x}}}}^j)=\mathbb{E}\left((q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i)(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^j-{\widehat{\underline{\mathrm{x}}}}^j)\right)=0\end{array}$

for $i\ne j$. Furthermore, it holds that $|q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i|\le {\delta }_s$ and thus $\mathbb{C}(q_m{\left(\widehat{\underline{\mathrm{x}}}\right)}^i-{\widehat{\underline{\mathrm{x}}}}^i)\le {\delta }_s^2$ for $i=1,\dots ,n$. Combined, this means that $\mathbb{C}(q_m\left(\widehat{\underline{\mathrm{x}}}\right)-\widehat{\underline{\mathrm{x}}})⪯{\delta }_s^2\mathbf{I}$. The claimed upper bound then follows immediately. □

The upper bound given above is fast to compute and does not require any knowledge of the distribution of either $\underline{\mathrm{x}}$ or $\widehat{\underline{\mathrm{x}}}$, at the cost of being overly conservative, particularly if a component of $\widehat{\underline{\mathrm{x}}}$ is concentrated between two codewords or for large ${\delta }_s$.

5.3. Quantized Optimal Fusion and Covariance Intersection

We are now in the position to formulate a process that allows to apply the Bar-Shalom–Campo formulas or covariance intersection to quantized estimates and covariance matrices while retaining unbiasedness and conservativeness of said fusion methods. The proposed approach is as follows:

• Quantize the estimates ${\underline{\mathrm{x}}}_a$ and ${\underline{\mathrm{x}}}_b$ so that the quantization results remain unbiased. Account for the potential increase in uncertainty due to the quantization process. Both goals are achieved by employing the unbiased, conservative estimate quantizer introduced in the previous subsection.

• Quantize the error covariance matrices of the quantized estimates conservatively. This is done using either the quantizer from Section 4.1 or the one from Section 4.2.

• Apply the Bar-Shalom–Campo formulas or covariance intersection to the quantized estimates and quantized error covariance matrices. Since the quantized estimates are unbiased and the quantized error covariance matrices are conservative the fusion result will also be unbiased and conservative.

In the following, the above process using CI in conjunction with either the diagonal dominance (DD)-based quantizer from Section 4.1 or the modified Cholesky (MC) decomposition-based quantizer from Section 4.2 will be referred to as DD-CI and MC-CI, respectively. The methods obtained by replacing CI with the optimal (OPT) fusion formulas in the DD-CI and MC-CI methods will be referred to as DD-OPT and MC-OPT.

6. Results and Discussion

The total quantization errors of the proposed covariance matrix quantizers are evaluated using randomly selected covariance matrices. In addition, the performance of DD-CI/OPT and MC-CI/OPT relative to CI/optimal fusion is evaluated by applying the methods to randomly generated data. Finally, the DD-CI and MC-CI approaches are evaluated in a decentralized 2D target tracking scenario.

6.1. Evaluation of the Covariance Quantizers

The two proposed covariance matrix quantizers are applied to independent random covariance matrices. The random matrices are generated as $\mathbf{X}=\mathbf{L}{\mathbf{L}}^{\top }$ where $\mathbf{L}\in {\mathbb{R}}^{n\times n}$ has zero-mean, normally distributed elements with variance one. The Frobenius norms of the resulting quantization error matrices are averaged over all samples. Figure 3 shows the averaged Frobenius norm of the diagonal dominance based quantizer and the relative improvement in average norm achieved by the modified Cholesky decomposition based quantizer for varying numbers of bits per codeword b and matrix dimensions n. For the codebooks, $x_{max}=50.0$ was used and 10,000 samples were included in each average.

The quantization error increases monotonically as b decreases with larger n leading to stronger deterioration of performance. The dependency on b is a result of the quantization resolution decreasing exponentially for decreasing b. The dependency on n is due to the fact that for increasing n the quantization error per element remains roughly the same, whereas the number of matrix elements increases quadratically. Therefore the off-diagonal quantization error increases for increasing n. The shift applied to the diagonal elements to ensure conservativeness must then grow larger with increasing n, thereby increasing the diagonal quantization error. The relative improvement in average norm can be seen to be approximately constant over b, the notable exception being $b\le 2$ where there is little to no improvement. This behavior can be understood by considering the limiting case of $b=1$. In said case, each element of the quantized matrix is either zero or the maximum codeword of the respective codebook. Since the off-diagonal elements are identical in both approaches and the diagonal elements are always rounded up, the quantized matrix and thus the quantization error are identical in both approaches.

6.2. Evaluation of Quantized Optimal Fusion and Quantized Covariance Intersection

The test data for this evaluation are generated by first drawing a zero mean Gaussian random vector $\underline{\mathrm{x}}\in {\mathbb{R}}^n$ with covariance matrix $\mathbb{C}\left(\underline{\mathrm{x}}\right)=\mathbf{I}$. This vector represents the ground truth. Then, a random vector $\underline{\mathrm{z}}={[{\underline{\mathrm{z}}}_a^{\top },{\underline{\mathrm{z}}}_b^{\top }]}^{\top }\in {\mathbb{R}}^{2n}$ is drawn from a zero mean Gaussian distribution with covariance matrix $\mathbf{L}{\mathbf{L}}^{\top }$, where $\mathbf{L}\in {\mathbb{R}}^{2n\times 2n}$ has zero mean Gaussian elements with variance one. Finally, two correlated estimates ${\underline{\mathrm{x}}}_a=\underline{\mathrm{x}}+{\underline{\mathrm{z}}}_a$ and ${\underline{\mathrm{x}}}_b=\underline{\mathrm{x}}+{\underline{\mathrm{z}}}_b$ of $\underline{\mathrm{x}}$ are computed. Optimal fusion, covariance intersection and their quantized versions are applied to the estimates ${\underline{\mathrm{x}}}_a$ and ${\underline{\mathrm{x}}}_b$ using their known conditional (cross-)covariance matrices

$\begin{array}{cc}\hfill \mathbb{C}({\underline{\mathrm{x}}}_a|\mathbf{L})& =\mathbb{C}\left(\underline{\mathrm{x}}\right)+\mathbb{C}({\underline{\mathrm{z}}}_a|\mathbf{L})\hfill \\ \hfill \mathbb{C}({\underline{\mathrm{x}}}_b|\mathbf{L})& =\mathbb{C}\left(\underline{\mathrm{x}}\right)+\mathbb{C}({\underline{\mathrm{z}}}_b|\mathbf{L})\hfill \\ \hfill \mathbb{C}({\underline{\mathrm{x}}}_a,{\underline{\mathrm{x}}}_b|\mathbf{L})& =\mathbb{C}\left(\underline{\mathrm{x}}\right)+\mathbb{C}({\underline{\mathrm{z}}}_a,{\underline{\mathrm{z}}}_b|\mathbf{L}).\hfill \end{array}$

The mean squared errors ${\mathrm{MSE}}_f=\mathbb{E}(\parallel {\underline{\mathrm{x}}}_f-\underline{\mathrm{x}}{\parallel }^2)$, where ${\underline{\mathrm{x}}}_f$ is the fused estimate with f indicating the fusion approach, are computed by repeatedly generating test data, applying the fusion approaches, and averaging the squared Euclidean norm of the resulting estimate errors. The mean traces ${\mathrm{MTR}}_f=\mathbb{E}\left(\mathrm{tr}\left({\mathbf{C}}_{ff}\right)\right)$ of the error covariance estimates ${\mathbf{C}}_{ff}$, where f indicates the fusion approach, are also computed using averaging. If any quantization operation fails for any of the test data, the computed MSE and averaged trace are discarded.

Figure 4 shows the relative increase $({\mathrm{MSE}}_{DD-OPT}-{\mathrm{MSE}}_{OPT})/{\mathrm{MSE}}_{OPT}$ of the MSE and the relative increase $({\mathrm{MTR}}_{DD-OPT}-{\mathrm{MTR}}_{OPT})/{\mathrm{MTR}}_{OPT}$ of the averaged trace when using DD-OPT instead of OPT. Figure 5 shows the relative increase $({\mathrm{MSE}}_{MC-OPT}-{\mathrm{MSE}}_{DD-OPT})/{\mathrm{MSE}}_{DD-OPT}$ of the MSE and the relative increase of the averaged trace $({\mathrm{MTR}}_{MC-OPT}-{\mathrm{MTR}}_{DD-OPT})/{\mathrm{MTR}}_{DD-OPT}$, when using MC-OPT instead of DD-OPT. Figure 6 and Figure 7 show the same quantities but compare DD-CI to CI and MC-CI to DD-CI, respectively. In all figures, varying dimensions n and numbers of bits per codeword b are considered both with and without quantizing estimate vectors. The results are obtained by averaging over 1000 independent trials and using $x_{max}=65.0$ for the codebooks ${\mathcal{C}}_m$, ${\mathcal{C}}_d$, and ${\mathcal{C}}_o$.

From Figure 4, it can be seen that for DD-OPT the increase of the estimate MSE and of the averaged trace of the error covariance estimate is moderate except for small b. Moreover, the increase in the averaged trace is larger than the increase in MSE for all n and b. This is to be expected, since the quantization process retains conservativeness. The dimensionality of the test data has varying influence on the performance, depending on b and on whether quantized estimates are being used. Using quantized estimate vectors is seen to adversely affect performance. In fact, when quantizing the estimate vectors the error covariance quantization fails below five bits per codeword, due to the excessively inflated error covariance estimate produced by the estimate quantization. Figure 5 shows that the MC-OPT approach performs better than the DD-OPT approach in terms of the average trace of the error covariance estimate and in most cases also in terms of actual MSE. Larger n leads to larger improvements. The improved performance in terms of average trace is guaranteed by the theoretical results from Section 4.2. Note that there is no guarantee that the actual MSE reduces if the error covariance matrices are quantized more accurately. It can also be seen that there is an optimal number of bits per codeword and that for small b there is little to no improvement. The latter result is due to the phenomenon discussed in Section 6.1. The results for CI, DD-CI, and MC-CI displayed in Figure 6 and Figure 7 exhibit the same general behavior as the results for OPT, DD-OPT, and MC-OPT discussed above, also in terms of theoretical guarantees. One notable difference is the relative improvement of actual MSE. In contrast to optimal fusion, the improvement does not seem to diminish for large n and small b.

6.3. Evaluation of Quantized Covariance Intersection in 2D Tracking Scenario

This evaluation scenario considers two sensor nodes that cooperatively track an object. The object is characterized by a discrete-time (nearly) constant acceleration model

$\begin{array}{ccc}\hfill {\underline{\mathrm{x}}}_{k+1}=\left[\begin{array}{cc}\mathbf{A}& \mathbf{0}\\ \mathbf{0}& \mathbf{A}\end{array}\right]{\underline{\mathrm{x}}}_k+{\underline{\mathrm{w}}}_k,& \hfill & \hfill {\underline{\mathrm{w}}}_k\sim \mathcal{N}\left(\underline{0},\left[\begin{array}{cc}\mathbf{Q}& \mathbf{0}\\ \mathbf{0}& \mathbf{Q}\end{array}\right]\right),\end{array}$

affected by the zero-mean white Gaussian noise term ${\underline{\mathrm{w}}}_k\in {\mathbb{R}}^6$. The six-dimensional state ${\underline{\mathrm{x}}}_k\in {\mathbb{R}}^6$ consists of position, velocity, and acceleration in both the $x^1$- and $x^2$-direction. The corresponding matrices of the process model are given by

$\begin{array}{ccc}\hfill \mathbf{A}=\left[\begin{array}{ccc}1& \tau & \frac{1}{2}{\tau }^2\\ 0& 1& \tau \\ 0& 0& 1\end{array}\right],& \hfill & \hfill \mathbf{Q}=0.5\left[\begin{array}{ccc}\frac{1}{20}{\tau }^5& \frac{1}{8}{\tau }^4& \frac{1}{6}{\tau }^3\\ \frac{1}{8}{\tau }^4& \frac{1}{3}{\tau }^3& \frac{1}{2}{\tau }^2\\ \frac{1}{6}{\tau }^3& \frac{1}{2}{\tau }^2& \tau \end{array}\right],\end{array}$

where $\tau >0$ is the time step [46]. For the Monte Carlo simulation with 1000 runs, the initial states ${\underline{\mathrm{x}}}_0$ are drawn from

$\begin{array}{c}\hfill {\underline{\mathrm{x}}}_0\sim \mathcal{N}\left(\left[\begin{array}{c}0\\ 0\\ 0.2\\ 0\\ 0\\ 0.3\end{array}\right],\left[\begin{array}{cccccc}0.5& 0& 0& 0& 0& 0\\ 0& 0.1& 0& 0& 0& 0\\ 0& 0& 0.05& 0& 0& 0\\ 0& 0& 0& 0.5& 0& 0\\ 0& 0& 0& 0& 0.1& 0\\ 0& 0& 0& 0& 0& 0.05\end{array}\right]\right).\end{array}$

Two sensor nodes a and b are simulated that observe projections of position and velocity according to

$\begin{array}{c}\hfill {\underline{\mathrm{z}}}_k^{a,b}=\left[\begin{array}{cccccc}cos\left({\theta }^{a,b}\right)& sin\left({\theta }^{a,b}\right)& 0& 0& 0& 0\\ 0& 0& cos\left({\theta }^{a,b}\right)& sin\left({\theta }^{a,b}\right)& 0& 0\end{array}\right]{\underline{\mathrm{x}}}_k+{\underline{\mathrm{v}}}_k^{a,b}\end{array}$

with ${\theta }^a=\frac{\pi }{4}$, ${\theta }^b=-\frac{\pi }{8}$. The zero-mean white Gaussian measurement noise terms ${\underline{\mathrm{v}}}_k^a,{\underline{\mathrm{v}}}_k^b\in {\mathbb{R}}^2$ have the covariance matrix

$\begin{array}{cc}\hfill {\mathbf{R}}^a=0.5\left[\begin{array}{cc}1& 0\\ 0& 0.1\end{array}\right],& {\mathbf{R}}^b=0.8\left[\begin{array}{cc}1& 0\\ 0& 0.5\end{array}\right],\hfill \end{array}$

respectively. Each sensor node uses a Kalman filter to compute estimates for 50 time steps. Sensor node a transmits its state and error covariance estimate to sensor node b at every 5th time step. Prior to transmission, it quantizes the estimates with the proposed method and codebook parameter $x_{max}=30.0$. Node b fuses its own estimate with the received one by employing CI. Every 11th time step, sensor node b quantizes and transmits its state and error covariance estimate to node a, which again fuses it with its own estimate using CI. The receiving node in both cases reinitializes its own estimate with the fusion result.

Figure 8 and Figure 9 compare DD-CI and MC-CI using different numbers of bits per codeword, against CI using 64-bit floating point numbers. The results for higher numbers of bits per codeword are close to the estimates obtained through CI with 64-bit floats. However, even a 5-bit quantization still yields reasonable results. Quantization using less than 5 bits per codeword leads to too conservative bounds on the error covariance matrices that cannot be encoded using the given codebook. The estimate MSE exhibits an initial transient peak. It is here, that the improved performance of MC-CI over DD-CI can be observed most clearly.

7. Conclusions

Available bandwidth and energy budget can be limiting factors for the data transmission capabilities of interconnected sensor systems. Algorithms for decentralized information fusion in networks require the exchange of estimates and, in some cases, covariance matrices. If covariance matrices need to be transmitted, they dominate the amount of transmitted data. In this paper, we have proposed two methods for the conservative quantization of covariance matrices, a method for the unbiased conservative quantization of estimates, and have applied them to optimal fusion and covariance intersection. The presented quantization approaches retain unbiasedness and conservativeness of the considered fusion methods while reducing the amount of data that must be transmitted. We have empirically demonstrated the effectiveness of the proposed covariance quantization methods, individually and in conjunction with fusion methods. Further improvements in performance could be achieved by using varying, possibly data-dependent quantization resolutions for subsets of the coefficients of the considered covariance matrices. Moreover, the proposed quantization schemes can also be applied to other sensor fusion algorithms like inverse covariance intersection. For future work, theoretical results concerning the convergence behavior of state and covariance estimates when using quantized data in a decentralized setting are of interest. Conservative vector quantization for covariance matrices is also worth consideration.

Supplementary Materials

The following are available online at https://www.mdpi.com/article/10.3390/s21093059/s1, Python implementations of the quantization approaches.

Author Contributions

Conceptualization, C.F.; methodology, C.F. and B.N.; software, C.F. and B.N.; validation, C.F. and B.N.; formal analysis, C.F.; investigation, C.F. and B.N.; resources, U.D.H.; data curation, C.F. and B.N.; writing—original draft preparation, C.F. and B.N.; writing—review and editing, U.D.H.; visualization, C.F. and B.N.; supervision, U.D.H.; project administration, U.D.H.; funding acquisition, U.D.H. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Acknowledgments

We acknowledge support by the KIT-Publication Fund of the Karlsruhe Institute of Technology.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures

Figure 1. (Left): Confidence ellipsoids of a covariance matrix (dark blue), its naively quantized version (light blue), and its conservatively quantized version (orange). (Right): Density of a Gaussian random variable (dark blue), histogram (light blue), and mean (orange) of its quantized version.

Figure 2. Confidence ellipsoids of Caa and Cbb (blue), C(x̲f−x̲) (orange, solid), and Cff (orange, dashed) when Cab≠0. The result obtained using optimal fusion with the erroneous assumption Cab=0 is shown on the left. The result achieved using CI is shown on the right.

Figure 3. Average Frobenius norm of the quantization error matrix Δdd of the diagonal dominance-based quantization approach (top), and the relative improvement achieved by the modified Cholesky-based quantization approach (bottom) for varying dimensions n and bits per codeword b.

Figure 4. Relative increase of actual MSE (solid)/averaged trace (dashed) of DD-OPT with respect to OPT for varying dimensions n and bits per codeword b. Top row with quantized estimate vector and quantized error covariance, bottom row only with quantized error covariance.

Figure 5. Relative increase of actual MSE (solid)/averaged trace (dashed) of MC-OPT with respect to DD-OPT for varying dimensions n and bits per codeword b. Top row with quantized estimate vector and quantized error covariance, bottom row only with quantized error covariance.

Figure 6. Relative increase of actual MSE (solid)/averaged trace (dashed) of DD-CI with respect to CI for varying dimensions n and bits per codeword b. Top row with quantized estimate vector and quantized error covariance, bottom row only with quantized error covariance.

Figure 7. Relative increase of actual MSE (solid)/averaged trace (dashed) of MC-CI with respect to DD-CI for varying dimensions n and bits per codeword b. Top row with quantized estimate vector and quantized error covariance, bottom row only with quantized error covariance.

Figure 8. The estimate MSE of sensor node b plotted over time step k for varying bits per codeword using DD-CI. ‘CI’ indicates the use of a 64 bit floating point representation for each scalar.

Figure 9. The estimate MSE of sensor node b plotted over time step k for varying bits per codeword using MC-CI. ‘CI’ indicates the use of a 64 bit floating point representation for each scalar.