Time-invariant prefix-free source coding for MIMO LQG control

In this work, we consider discrete-time MIMO LQG control where feedback occurs via variable-length packets (codewords) of bits that we assume are conveyed reliably (without error) from a sensor/encoder to a decoder/controller. For some constraint on LQG control performance, we seek to design a sensor/encoder and decoder/controller that minimize the time-averaged expected bitrate of the binary channel.

The motivation for this formulation is communication-efficient remote control over wireless communications. In particular, we imagine a scenario where a remote sensor platform measures some dynamical system and conveys the measurements to the controller over a noiseless binary channel. At the physical and medium access control layers, reliable control of autonomous agents over wireless has motivated the development of ultra low latency reliable communication (ULLRC). While progress has been made on the development ULLRC, the fundamental scarcity of physical layer resources motivates approaches that minimize the use of these resources. In contrast to the work on ULLRC, we aim higher on the protocol stack; namely we propose to develop control and data compression (source coding) strategies to achieve satisfactory control performance with minimal communication bitrate. The minimum average length, in bits, of the binary packets the sensor encodes are an effective surrogate for the minimum amount of physical layer resources (time/bandwidth/power) required to achieve satisfactory performance for a fixed reliability (cf. e.g. [1, Section 2.6]). We impose a prefix constraint on the codewords that ensures that other users sharing the same communication medium can identify the end of each transmitted message and thus identify the channel as free-to-use. In contrast to the prior art, this work imposes a time-invariant (TI) prefix constraint on the codewords, which simplifies the decoding architecture architecture; the end of codewords can be detected via comparison with a TI list [2].

In the prior literature, achievability results for the problem of interest follow from asymptotically bounding the output entropy of a quantizer [3][4][5]. While these bounds can nearly be achieved with zero-delay lossless source coding, they generally require that the lossless code be adapted, at every timestep, to the probability mass function of the quantizer output (cf. [6, Section IV.A]). This adds a great deal of computational complexity to the encoder and decoder.

In this work, we propose a data compression architecture for MIMO plants based on [4] and [6] that attains the desired LQG performance, satisfies a TI prefix constraint, and does not require a time-varying lossless source codec. Starting from the architecture of [4], we prove that the quantizer output has a limiting distribution. We propose to losslessly encode the quantizations with a fixed prefix-free code adapted the limiting distribution. We prove that under this modification, the codewords satisfy a TI prefix constraint without an increase in codeword length and without the complexity of time-varying lossless source coding. The architecture nearly achieves a known lower bound on the minimum expected bitrate. In particular, we use results from systems theory to extend the scalar TI achievability approach in [6] to the MIMO setting.

We consider the system model depicted in Fig. 1. The system to be controlled is a TI, multidimensional, linear dynamical system (i.e., a MIMO plant) plant controlled via a feedback model where communication occurs over an ideal (delay and error free) binary channel. The plant is fully observable to an encoder/sensor block, which conveys a variable-length binary codeword $\boldsymbol{{a}}_{t}\in\{0,1\}^{*}$ over the channel to a combined decoder/controller. Upon receipt of the codeword, the decoder/controller designs the control input. Denote the state vector $\boldsymbol{{x}}_{t}\in\mathbb{R}^{m}$, the control input $\boldsymbol{{u}}_{t}\in\mathbb{R}^{u}$, and let $\boldsymbol{{w}}_{t}\sim\mathcal{N}({0},{W})$ denote processes noise assumed to be IID over time. We assume ${W}\succ{0}_{m\times m}$, i.e., the process noise covariance is full rank. We assume assume that $\boldsymbol{{x}}_{0}\sim\mathcal{N}({0},{X}_{0})$ for some $X_{0}\succeq 0$. For ${A}\in\mathbb{R}^{m\times m}$ the system matrix and ${B}\in\mathbb{R}^{m\times u}$ the feedback gain matrix, for $t\geq 0$ the plant dynamics are given by $\boldsymbol{{x}}_{t+1}={A}\boldsymbol{{x}}_{t}+{B}\boldsymbol{{u}}_{t}+\boldsymbol{{w}}_{t}$. To ensure finite control cost is attainable, we assume $({A},{B})$ are stabilizable. We assume that the encoder and decoder share access to a random uniform dither signal $\{\boldsymbol{{d}}_{t}\}$. We assume that, for some $\Delta>0$ to be specified, the random vectors $\boldsymbol{{d}}_{t}\in\mathbb{R}^{m}$ have components that are independently uniformly distributed on $[-\Delta/2,\Delta/2]$, and that the sequence $\{\boldsymbol{{d}}_{t}\}$ is IID over time. We assume that $\{\boldsymbol{{w}}_{t}\}$, $\{\boldsymbol{{d}}_{t}\}$, and $\boldsymbol{{x}}_{0}$ are mutually independent. In real-world systems, this shared randomness can be effectively accomplished using synchronized pseudorandom number generators. We assume that the encoder/sensor and the decoder/controller may be randomized given their inputs. The encoder/sensor policy in Fig. 1 is a sequence of causally conditioned Borel measurable kernels denoted $\mathbb{P}_{\mathrm{E}}[\boldsymbol{{a}}_{0}^{\infty}||\boldsymbol{{d}}_{0}^{\infty},\boldsymbol{{x}}_{0}^{\infty}]=\left\{\mathbb{P}_{\mathrm{E}}[\boldsymbol{{a}}_{t}|\boldsymbol{{a}}_{0}^{t-1},\boldsymbol{{d}}_{0}^{t},\boldsymbol{{x}}_{0}^{t}]\right\}_{t}$, and that corresponding decoder/controller policy is given by $\mathbb{P}_{\mathrm{C}}[\boldsymbol{{u}}^{\infty}||\boldsymbol{{a}}^{\infty},\boldsymbol{{d}}^{\infty}]=\left\{\mathbb{P}_{\mathrm{C}}[\boldsymbol{{u}}_{t}|\boldsymbol{{a}}^{t},\boldsymbol{{d}}^{t},\boldsymbol{{u}}^{t-1}]\right\}_{t}$. Note that under the assumed dynamics, $\boldsymbol{{x}}^{t}$ is a deterministic function of $\boldsymbol{{x}}$, $\boldsymbol{{a}}^{t-1}$, $\boldsymbol{{u}}^{t-1}$, and $\boldsymbol{{w}}^{t-1}$. We encode conditional independence assumptions in the system model by a factorization of the one-step transition kernels for $\boldsymbol{{a}}_{t}$, $\boldsymbol{{d}}_{t}$, $\boldsymbol{{u}}_{t}$, and $\boldsymbol{{w}}_{t}$. For $t\geq 0$, we assume the kernels factorize via

and that we have initially $\mathbb{P}[\boldsymbol{{a}}_{0},\boldsymbol{{d}}_{0},\boldsymbol{{u}},\boldsymbol{{w}}_{0}|\boldsymbol{{x}}_{0}]$ $=$ $\mathbb{P}[\boldsymbol{{w}}_{0}]\mathbb{P}[\boldsymbol{{d}}_{0}]\mathbb{P}_{\mathrm{E}}[\boldsymbol{{a}}_{0}|\boldsymbol{{x}}_{0},\boldsymbol{{d}}_{0}]$ $\mathbb{P}_{\mathrm{C}}[\boldsymbol{{u}}_{0}|\boldsymbol{{a}}_{0},\boldsymbol{{d}}_{0}]$. Implications of these factorization are discussed in the caption of Fig. 1.

We require the codewords to conform to a TI prefix constraint, namely that for all $i,j$ and distinct $a_{1},a_{2}\in\{0,1\}^{*}$ with both $\mathbb{P}[\boldsymbol{{a}}_{i}=a_{1}]>0$ and $\mathbb{P}[\boldsymbol{{a}}_{j}=a_{2}]>0$, $a_{1}$ is not a prefix of $a_{2}$ and vice-versa. Thus, not only must the support of the random variable $\boldsymbol{{a}}_{i}$ be a set of prefix-free binary codewords, we also require the union of the supports of the $\{\boldsymbol{{a}}_{i}\}$ be prefix-free. This is a stronger prefix constraint than was considered in [4]. The TI constraint may enable for more computationally efficient communication resource sharing; the end of a codeword can be unambiguously identified via comparing received messages against the TI union of supports. We are interested in the following optimization, over policies $\mathbb{P}_{\mathrm{E}},\mathbb{P}_{\mathrm{C}}$ that conform to the prefix constraint:

where ${Q}\succeq{0}$, ${\Phi}\succ{0}$, and $\gamma$ is the maximum tolerable LQG cost. Let $S$ be a stabilizing solution to the discrete algebraic Riccati equation (DARE) $A^{\mathrm{T}}SA-S-A^{\mathrm{T}}SB(B^{\mathrm{T}}SB+\Phi)^{-1}B^{\mathrm{T}}SA+Q=0$, $K=-(B^{\mathrm{T}}SB+\Phi)^{-1}B^{\mathrm{T}}SA$, and $\Theta=K^{\mathrm{T}}(B^{\mathrm{T}}SB+\Phi)K$. Consider the optimization

A consequence of [2] (cf. [6] and [8]) is the lower bound $\mathcal{R}(\gamma)\leq\mathcal{L}(\gamma)$. In the sequel, we will analyze the bitrate of the proposed achievability scheme in terms of $\mathcal{R}(\gamma)$.

The achievability approach we proposed is demonstrated in Fig. 2. It is almost identically to the time-varying MIMO achievability approach in [6, Section IV.B] with the exception that the lossless Shannon-Fano-Elias source codec used to encode the quantizations is TI. We first describe the signals in Fig. 2 before summarizing relevant results from [6] that simplify the analysis. Let $\hat{P}$ denote the minimizing $P$ from (3), let $\hat{P}_{+}=A\hat{P}A^{\mathrm{T}}+W$, and let $\Delta\in\mathbb{R}$, $\Delta>0$, and $C\in\mathbb{R}^{m\times m}$ be such that $\hat{P}^{-1}-\hat{P}_{+}^{-1}=C^{\mathrm{T}}C\frac{12}{\Delta^{2}}$. In this way, $\hat{P}$ ($\hat{P}_{+}$ ) is interpreted as the asymptotic (prediction) error covariance attained by a Kalman filter tracking the source process $\{\boldsymbol{{x}}_{t}\}$ under a measurement model $\boldsymbol{{y}}_{t}=C\boldsymbol{{x}}_{t}+\boldsymbol{{v}}_{t}$, where $\mathbb{E}[\boldsymbol{{v}}_{t}\boldsymbol{{v}}_{t+k}^{\mathrm{T}}]=I_{m}\frac{\Delta^{2}}{12}\mathbb{1}_{k=0}$, $\mathbb{E}[\boldsymbol{{v}}_{t}\boldsymbol{{x}}_{0}^{\mathrm{T}}]=\mathbb{E}[\boldsymbol{{v}}_{t}\boldsymbol{{w}}_{t+k}^{\mathrm{T}}]=0_{m\times m}$. We will show that this measurement model is attained by the decoder in Fig. 2 using dithered quantization.

Define a uniform elementwise quantizer via $Q_{\Delta}\colon\mathbb{R}^{m}\rightarrow\Delta\mathbb{Z}^{m}$ via $[Q_{\Delta}({x})]_{i}=k\Delta,\text{ if }[{x}]_{i}\in[k\Delta-\Delta/2,k\Delta+\Delta/2),$ e.g. each element of the vector ${x}$ is rounded to the nearest multiple of $\Delta$. Both the encoder and decoder in Fig. 2 operate identical time invariant Kalman filters that compute recursive estimates of $\boldsymbol{{x}}_{t}$ given measurements received by the decoder. Let $\overline{\boldsymbol{{x}}}_{t|t-1}$ denote the prior estimate at time $t$ and $\boldsymbol{{\overline{x}}}_{t|t}$ denote the posterior. Set $\boldsymbol{{\overline{x}}}_{0|-1}=0$. At every time $t$ the encoder and decoder produces the Kalman filter prediction error

and the linear measurement innovation $\boldsymbol{{e}}_{t}$. It then produces the discrete, dithered quantization $q_{t}=Q_{\Delta}(C\boldsymbol{{e}}_{t}+\boldsymbol{{d}}_{t})$. It encodes the discrete quantization losslessly into the codeword $\boldsymbol{{a}}_{t}$ which it transmits to the decoder. Upon receiving $\boldsymbol{{a}}_{t}$, the decoder can recover $\boldsymbol{{q}}_{t}$ exactly. It then produces the reconstruction $\boldsymbol{{\tilde{q}}}_{t}=\boldsymbol{{q}}_{t}-\boldsymbol{{d}}_{t}$. Let $\boldsymbol{{v}}_{t}=\boldsymbol{{\tilde{q}}}_{t}-C\boldsymbol{{e}}_{t}$ denote the reconstruction error. It then produces the centered measurement $\boldsymbol{{y}}_{t}=\boldsymbol{{\tilde{q}}}_{t}+C\boldsymbol{{x}}_{t|t-1}$ (equivalently $\boldsymbol{{y}}_{t}=C\boldsymbol{{x}}_{t}+\boldsymbol{{v}}_{t}$). By [4, Lemma 1], the elements $[\boldsymbol{{v}}_{t}]_{i}$ are mutually independent and uniform on $[-\Delta/2,\Delta/2]$ and furthermore $\boldsymbol{{v}}_{t}\perp\boldsymbol{{x}}_{t}$. Denote the TI Kalman filter gain $J=\hat{P}_{+}{C}^{\mathrm{T}}({C}\hat{P}_{+}{C}^{\mathrm{T}}+I_{m\times m}\frac{\Delta^{2}}{12})^{-1}$. The decoder updates its estimate via

and applies the certainty equivalent control input $\boldsymbol{{u}}_{t}=K\boldsymbol{{\overline{x}}}_{t|t}$. It then computes the predict estimate $\boldsymbol{{\overline{x}}}_{t|t-1}={A}\boldsymbol{{\overline{x}}}_{t-1|t-1}+{B}\boldsymbol{{u}}_{t-1}$. Since the encoder knows the quantizations $\{\boldsymbol{{q}}_{t}\}$ and the dither $\{\boldsymbol{{d}}_{t}\}$, it can recover the sequence of measurements $\{\boldsymbol{{y}}_{t}\}$. The encoder can thus compute the sequence of TI Kalman filter estimates $\{\boldsymbol{{\overline{x}}}_{t|t-1},\boldsymbol{{\overline{x}}}_{t|t}\}$. While we have yet to define how $\boldsymbol{{q}}_{t}$ is encoded into $\boldsymbol{{a}}_{t}$, we have the following.

The first statement follows from [4, Lemma 1] and the system model and the subsequent are via [6, Theorem IV.5].

The TI prefix constraint can be satisfied by encoding each $\boldsymbol{{q}}_{t}$ with the same lossless prefix code at all time. Let $\boldsymbol{{q}}$ be a discrete random variable on $\Delta\mathbb{Z}^{m}$ (the same alphabet as $\boldsymbol{{q}}_{t}$). Assume the support of $\boldsymbol{{q}}$ is such that $\mathbb{P}[\boldsymbol{{q}}=k]=0$ only if $\mathbb{P}[\boldsymbol{{q}}_{t}=k]=0$. Define $\overline{F}_{\boldsymbol{{q}}}(q)=\mathbb{P}[\boldsymbol{{q}}<q]+\frac{\mathbb{P}[\boldsymbol{{q}}=q]}{2}$, and define the encoding function $C^{\mathrm{F}}_{\boldsymbol{{q}}}(q):\Delta\mathbb{Z}^{m}\rightarrow\{0,1\}^{*}$ such that $C^{\mathrm{F}}_{\boldsymbol{{q}}}(q)$ is the binary expansion of $\overline{F}_{\boldsymbol{{q}}}(q)$ truncated to $\lceil-\log_{2}(\mathbb{P}_{\boldsymbol{{q}}}[q])\rceil+1$ bits. This is a standard, lossless, prefix-free Shannon-Fano-Elias code for the random variable $\boldsymbol{{q}}$ [13]. If we use $C^{\mathrm{F}}_{\boldsymbol{{q}}}$ to encode $\boldsymbol{{q}}_{t}$ (e.g. $\boldsymbol{{a}}_{t}=C^{\mathrm{F}}_{\boldsymbol{{q}}}(\boldsymbol{{q}}_{t})$) the codeword length satisfies

Note that if for some $k$, $\mathbb{P}[\boldsymbol{{q}}=k]=0$ while $\mathbb{P}[\boldsymbol{{q}}_{t}=k]>0$, then $D_{\mathrm{KL}}(\boldsymbol{{q}}_{t}||\boldsymbol{{q}})=\infty$. The main result of this paper is the following lemma, proved in Section IV.

This lemma allows us to bound the bitrate for when a TI prefix-free code is used in Fig. 2.

In Section IV, we use ergodic theory to prove Lemma 2.

We proceed as in [6] by analyzing the long-term behavior of the Kalman innovation and dither signals, e.g. $(\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t})$. At every $t$, the quantization error $\boldsymbol{{v}}_{t}$ is a measurable function of $(\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t})$ given by $\boldsymbol{{v}}_{t}=\boldsymbol{{q}}_{t}-{C}\boldsymbol{{e}}_{t}$, or, equivalently, $\boldsymbol{{v}}_{t}=Q_{\Delta}({C}\boldsymbol{{e}}_{t}+\boldsymbol{{d}}_{t})-\boldsymbol{{d}}_{t}-{C}\boldsymbol{{e}}_{t}$. Let $L=AJ$ and ${R}={A}-{L}{C}$. The following recursion for the $\boldsymbol{{e}}_{t}$ (cf. (4)) can be derived

By construction of $L$, $(A-LC)$ is stable, e.g. its eigenvalues lie strictly within the complex unit circle [14]. Define the state space $\mathbb{D}^{m}=\mathbb{R}^{m}\times\mathcal{B}^{m}(\Delta)$. For ${r},{\mu}\in\mathbb{R}^{m}$, $\Sigma\in\mathbb{S}_{+}^{m\times m}$, denote the PDF of a multivariate Gaussian random variable with mean ${\mu}$ and covariance $\Sigma$ evaluated at ${r}$ by $N({r};{\mu},\Sigma)$, i.e. define the function $N({r};{\mu},\Sigma):\mathbb{R}^{m}\times\mathbb{R}^{m}\times\mathbb{S}_{+}^{m}\rightarrow\mathbb{R}$ via $N({r};{\mu},\Sigma)=\frac{1}{\sqrt{(2\pi)^{m}\det{\Sigma}}}e^{-\frac{1}{2}({r}-{\mu})^{\mathrm{T}}\Sigma^{-1}({r}-{\mu})}$. Define $M\colon(x,y)\in\mathbb{D}^{m}\rightarrow\mathbb{R}^{m}$ via $M({x},{y})=R{x}-L(Q_{\Delta}(C{x}+{y})-{y}-C{x})$. By definition, the marginal PDF of the dither is $f_{\boldsymbol{{d}}_{t+1}}({d})=\frac{1}{\Delta^{m}}1_{{d}\in\mathcal{B}^{m}(\Delta)}$ for all $t$. Since $\boldsymbol{{w}}_{t}\perp(\boldsymbol{{e}}^{t},\boldsymbol{{d}}^{t})$, and $\boldsymbol{{d}}_{t+1}\perp(\boldsymbol{{e}}^{t+1},\boldsymbol{{w}}^{t}$), via (8) we have that $\{\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t}\}$ is a time-homogeneous first order Markov chain.

The PDFs of $\{\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t}\}$ factorize via $f_{\boldsymbol{{e}}_{t+1},\boldsymbol{{d}}_{t+1}|\boldsymbol{{e}}^{t},\boldsymbol{{d}}^{t}}=f_{\boldsymbol{{d}}_{t+1}}f_{\boldsymbol{{e}}_{t+1}|\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t}}$. Via (8),

Let $f_{t+1|t}=f_{\boldsymbol{{e}}_{t+1},\boldsymbol{{d}}_{t+1}|\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t}}$, and likewise $f_{t+n|t}=f_{\boldsymbol{{e}}_{t+n},\boldsymbol{{d}}_{t+n}|\boldsymbol{{e}}_{t},\boldsymbol{{d}}_{t}}$. From the foregoing, we have

Applying the Chapman-Komogorov equations to (12), it can be seen that the $n$-step transition kernels satisfy

We now state the generalization of [6, Lemma A.3].

The next lemmas describe properties of $\{\Sigma_{n}\}$ and the sequence of functions $\mu_{n}(e_{0},d_{0},v_{1}^{n-2}):\mathbb{R}^{m}\times(\mathcal{B}^{m}(\Delta))^{n-1}\rightarrow\mathbb{R}^{m}$. We recall a result from system theory.

For $\alpha$, $\beta$, and $c$ as defined in Lemmas 6 and 7, define a subset of $\mathbb{R}^{m}\times\mathbb{R}^{m\times m}$ via $\mathcal{M}(e_{0},d_{0},m,L,R,\Delta)=\{({\mu},\Sigma)\in\mathbb{R}^{m}\times\mathbb{R}^{m\times m}:\lVert{\mu}\rVert_{2}\leq\alpha\lVert M(e_{0},d_{0})\rVert+\beta,\Sigma\succeq W,\lVert\Sigma\rVert_{2}\leq c\}$. We have that $\mathcal{M}(e_{0},d_{0},m,L,R,\Delta)$ is compact (closed and bounded). This helps prove the main result of this section.