PaperlayerView exact revision on arXiv

Source-linked AI summary

Rate-cost tradeoffs in control

Victoria Kostina, Babak Hassibi

arXiv:1612.02126v3cs.ITeess.SY

TL;DR

The paper asks how communication requirements constrain the achievable quadratic control cost in linear stochastic systems. It develops lower bounds for a directed-information rate-cost function across fully and partially observed, vector, and non-Gaussian settings, and shows that innovation-only lattice quantization can closely approach them. These results also connect quantized control with causal compression of Markov sources.

  • Problem

    The paper studies the fundamental tradeoff between communication rate and expected LQR cost, including the operational data-rate requirements for control over noiseless and noisy channels.

  • Method

    The paper derives rate-cost converses using directed mutual information, Shannon lower bounds, coding-memory estimates, and high-resolution variable-length vector quantization, with control-communication separation.

  • Results

    The bounds apply to vector, non-Gaussian, fully observed, and partially observed systems, and are closely approached in the high-rate, low-cost regime by variable-rate lattice schemes transmitting only innovations.

  • Takeaways & Limitations

    The rate-cost function provides a lower bound on required communication and a practical guide for selecting rates, while innovation quantization offers a simple near-achieving scheme.

Abstract

from arXiv · show

Consider a control problem with a communication channel connecting the observer of a linear stochastic system to the controller. The goal of the controller is to minimize a quadratic cost function in the state variables and control signal, known as the linear quadratic regulator (LQR). We study the fundamental tradeoff between the communication rate $r$ bits/sec and the expected cost $b$. We obtain a lower bound on a certain rate-cost function, which quantifies the minimum directed mutual information between the channel input and output that is compatible with a target LQR cost. The rate-cost function has operational significance in multiple scenarios of interest: among others, it allows us to lower-bound the minimum communication rate for fixed and variable length quantization, and for control over noisy channels. We derive an explicit lower bound to the rate-cost function, which applies to the vector, non-Gaussian, and partially observed systems, thereby extending and generalizing an earlier explicit expression for the scalar Gaussian system, due to Tatikonda el al. The bound applies as long as the differential entropy of the system noise is not $-\infty$. It can be closely approached by a simple lattice quantization scheme that only quantizes the innovation, that is, the difference between the controller's belief about the current state and the true state. Via a separation principle between control and communication, similar results hold for causal lossy compression of additive noise Markov sources. Apart from standard dynamic programming arguments, our technical approach leverages the Shannon lower bound, develops new estimates for data compression with coding memory, and uses some recent results on high resolution variable-length vector quantization to prove that the new converse bounds are tight.

I. INTRODUCTION

The paper formulates communication-constrained linear stochastic control through directed mutual information and an LQR rate-cost tradeoff. It connects this quantity to data-rate requirements for stabilization and control over noiseless or noisy channels.

  • System model: The system consists of a linear stochastic plant whose encoder observes sensor outputs and sends channel inputs to a controller that selects control actions causally.The encoder and controller both access their respective observation histories.
  • System model: The LQR cost balances state deviation from the target state with control power through weighting matrices Q, R, and S_t.The special case Q = I_n, R = 0, and S_{t+1} = I_n gives average mean-square state deviation.
  • Information constraint: Directed mutual information captures causal dependence of the control sequence on the observations and is no greater than full mutual information.The system dynamics determine the causal plant kernels, while encoder, channel, and controller form the causal channel kernels.
  • Rate-cost tradeoff: The rate-cost function is the minimum directed mutual information compatible with a target LQR cost and lower-bounds the channel capacity needed to sustain that cost.This operational connection applies to both noiseless and noisy channels, while noiseless channels can approach the bound using variable-length lattice quantization of the innovation.
  • Prior work: Earlier work established data-rate conditions for stabilization, while later results linked LQG control under communication constraints to causal rate-distortion theory.Prior converse results include bounded-noise and mean-square stabilization settings, with fixed-rate quantizers unable to maintain bounded cost under unbounded noise.

D. Our contribution

The paper develops converse bounds for rate-cost tradeoffs in linear stochastic control and shows that simple innovation-based quantizers can closely approach them. The results cover fully and partially observed systems, including vector and non-Gaussian settings, while identifying operational implications and scope limits.

  • A variable-length lattice quantizer that transmits only the state innovation closely approaches the converse, with the gap vanishing as b approaches bmin.
  • The framework extends to partially observed systems when system and observation noises are Gaussian, and applies across fixed-rate, variable-rate, noisy-channel, and non-Gaussian settings.
  • The causal Shannon lower bound supports the converse, while high-resolution quantization and lattice constructions establish near-achievability; the entropy-cost function also has direct operational meaning through variable-length quantization.
  • The paper derives a lower bound on the rate-cost function for fully observed linear stochastic systems with system noise satisfying h(V) > −∞.
  • The rate-cost bound decreases with larger target cost, approaches log |det A| as b grows, and exhibits substantial cost improvement from increasing rate from 1 to 3 nats per sample.
  • The converse remains valid for unrestricted quantizers using the entire observation history, without assuming linear structure.
  • The achievability scheme needs no common randomness, and nonuniform rate allocation across time is unnecessary for attaining the stated bound.
  • For m < n, the bounds from Theorems 1 and 3 lose their dependence on b, while Theorem 4 remains decreasing in b.

B. Partially observed system

For partially observed systems, the paper derives Gaussian rate-cost lower bounds and shows that innovation-based estimation, quantization, and control can approach the optimal tradeoff at high rates.

  • The controller’s minimum cost separates into contributions from system noise and observation noise under unconstrained communication.
  • Theorem 5 lower-bounds the rate-cost function using the steady-state covariance of the encoder’s state-estimation innovation.
  • A scheme that quantizes the innovation, recursively estimates the state, and controls from the estimate performs provably close to R(b) in the high-rate regime.
  • Theorem 6 upper-bounds the entropy-cost function for Gaussian partially observed systems at any LQR cost b > bmin.
  • Theorem 7 provides a lower bound on the rate-cost function for controllable and observable Gaussian partially observed systems.
  • Theorem 8 extends the lower bound to systems with control dimension satisfying m ≤ k ≤ n and reduces to Theorem 5 when k = m = n.

C. Operational implications

The paper interprets its rate-cost and entropy-cost bounds operationally across communication scenarios, including quantization and noisy-channel control.

  • The rate-cost and entropy-cost functions are defined as limiting mutual-information and entropy optima subject to an LQR cost constraint.

1) Control over a noisy channel

For noisy channels, the paper connects rate-cost converses to necessary channel capacity and identifies a scalar Gaussian AWGN case where the bound is attained.

  • If past channel outputs are unavailable at the encoder, directed mutual information reduces to ordinary mutual information.
  • The converse results imply lower bounds on the channel capacity necessary to stabilize the system at a target LQR cost.
  • Equality is attained for scalar Gaussian control over a scalar memoryless AWGN channel, where linear innovation transmission is optimal.
  • How closely the capacity lower bound can be approached over noisy channels remains open in general.

2) Control under fixed-rate quantization

For noiseless fixed-rate bit pipes, the rate-cost and entropy-cost functions lower-bound the quantization rate required to attain a target LQR cost.

  • For a noiseless bit pipe accepting r bits per channel use, both R(b) and H(b) lower-bound the minimum quantization rate required for cost b.
  • The converse theorems give sharp lower bounds on the minimum size of a fixed-rate quantizer compatible with LQR cost b.

3) Control under variable-length quantization

The section characterizes variable-length quantization through an operational rate-cost function, relating achievable average code length to LQR cost. The converse and achievability results also extend to prefix-free variable-length quantizers.

  • Operational rate-cost function: The minimum encoded length can fall slightly below entropy when the prefix condition is removed.This follows from lifting prefix constraints in lossless compression.
  • Operational rate-cost function: The operational rate-cost function Rvar(b) is defined by the asymptotically achievable average rate for target LQR cost b.It uses the limsup of the infimum of rates satisfying the coding constraint and cost requirement.
  • Rate-cost characterization: Rvar(b) ≥ ψ^-1(R(b)), where ψ(x) = x + log2(x + 1) + log2 e.Thus the converse theorems provide lower bounds for variable-length quantization, while the achievability results characterize the operational tradeoff.
  • Rate-cost characterization: The converse and achievability results characterize the operational rate-cost tradeoff for variable-length quantizers.The result applies to the variable-length setting considered in this section.
  • Prefix-free quantization: The same theorems characterize the operational rate-cost tradeoff for variable-length prefix-free quantizers.For prefix-free compression, the minimum average length is bounded by entropy plus one bit.

III. CAUSAL SHANNON LOWER BOUND

This section develops causal Shannon lower bounds for Markov-source compression and shows that DPCM based on quantized innovations attains the relevant causal rate- and entropy-distortion tradeoffs. The results extend to controlled processes and include refinements for singular or lower-dimensional noise structures.

  • Causal DPCM: Causal compression uses the decoder’s predicted state as side information and quantizes the current innovation.The DPCM encoder sends the quantized innovation, and the decoder reconstructs the state recursively.
  • Causal DPCM: Causal rate- and entropy-distortion functions are attained within DPCM without requiring independent innovations or encoded innovations.The result follows from Proposition 2 and permits dependence across samples.
  • Control and compression: The causal rate-distortion tradeoffs for controlled and uncontrolled Markov processes are the same when past controls are available to encoder and decoder.The processes share the same innovation process, so the same DPCM scheme encodes both.
  • Causal Shannon lower bound: Theorem 9 provides a causal rate-distortion lower bound obtained by combining Shannon’s lower bound with dynamic programming.It is presented as an extension of Shannon’s lower bound to causal compression.
  • Causal Shannon lower bound: For scalar Gauss-Markov sources, equality holds when the expression under the logarithm is at least 1.This recovers the known scalar Gaussian result.
  • Achievability: A DPCM quantizer with uniform rate and distortion allocations approaches the converse in the infinite-horizon limit.Consequently, nonuniform allocations cannot provide significant performance gains in this setting.
  • Refined bounds: When the eigenvalue dynamic range is large, projecting out smaller eigenvalues can improve the bound at medium to large distortion dimensions.Further bounds remain decreasing in distortion even when the noise covariance is singular or supported on a subspace.

IV. CONTROL, ESTIMATION AND COMMUNICATION SEPARATED

The section separates control, estimation, and communication in partially observed LQR systems. In fully observed and Gaussian partially observed cases, the rate-cost tradeoff is independent of the control sequence and reduces to causal source-compression functions.

  • Separated design: The controller uses an estimate of the encoder’s state estimate to form the control action, while encoder and controller mappings minimize LQR cost.The architecture passes encoded state information through the channel before control is applied.
  • Cost separation: The LQR cost separates into control, estimation, and communication costs for the partially observed system.The separation is established in Theorem 13 for the system and channel scenario considered.
  • Cost separation: The minimum achievable LQR cost is expressed through an infimum over admissible control sequences.Equality in the resulting decomposition is not attained in general.
  • Special cases: Equality in the cost decomposition holds for fully observed systems and Gaussian partially observed systems.In the fully observed case estimation terms vanish; in the Gaussian partially observed case they are control-independent through the Kalman filter.
  • Special cases: In fully observed and Gaussian partially observed systems, rate-cost and entropy-cost functions are independent of the control sequence.They are evaluated relative to the unconstrained minimum cost bmin and causal rate- or entropy-distortion functions.
  • Noisy channels: The separated design also yields a converse for control over noisy channels through a tracking converse.The result follows by combining the controlled and uncontrolled rate-distortion relations.

V. CONVERSE THEOREMS: TOOLS AND PROOFS

This section develops the information-theoretic tools and proofs underlying the causal converse bounds. Shannon lower bounds, entropy-power arguments, data processing, and recursive dynamic-programming estimates produce lower bounds for general causal compression settings.

  • Information-theoretic tools: The analysis relies on conditional entropy power inequalities to control how side information affects causal compression.In causal compression, each quantized output becomes side information for the next source sample.
  • Proof strategy: The entropy-power scaling argument is exact when the transformation is square or the source is Gaussian.For a general rectangular transformation, Proposition 5 supplies the corresponding inequality.
  • Information-theoretic tools: Weighted and unweighted mean-square distortion-rate functions are equated using linear transformations and data processing.The reduction uses projection onto the image of the weighting matrix.
  • Shannon lower bound: The conditional Shannon lower bound is tight when the source decomposes into side information plus isotropic Gaussian noise.At high rates, Shannon’s lower bound can be approached beyond the Gaussian case, supporting the converse’s achievability analysis.
  • Proof strategy: Theorem 9 is proved by lower-bounding each stage’s distortion with Shannon’s bound, entropy-power inequalities, and a recursive information-rate relation.The resulting recursion is averaged over time to obtain the causal lower bound.

VI. ACHIEVABILITY THEOREMS: TOOLS AND PROOFS

The achievability proof analyzes a DPCM scheme using lattice quantization of the state innovation, then bounds its entropy and distortion to establish the theorems.

  • Lattice quantization: The lattice covering efficiency ρC measures how closely Voronoi cells approximate balls, with smaller values indicating better covering.By definition, ρC ≥ 1, and values closer to 1 correspond to more sphere-like cells.
  • Proof strategy: The proof analyzes a DPCM scheme with codebook generation, encoder and decoder operations, and performance analysis.The scheme uses lattice quantization and transmits quantized innovations rather than the full state.
  • Encoder and decoder: At each time, the encoder recursively computes the state innovation from the observed state and decoder estimate, then transmits its lattice-cell index.The decoder recovers the identified cell and forms its state estimate from the quantized innovation.
  • Theorem applications: Theorem 2 follows by bounding the entropy-distortion function of the fully observed process, while Theorem 6 uses the conditional entropy-distortion function of Kalman-filter estimates.Both achievability results invoke Theorem 10 through the corresponding corollaries.

VII. CONCLUSION

The paper establishes rate-cost tradeoffs for fully and partially observed linear stochastic control and shows that variable-rate lattice quantization can approach the converse at high rate and low cost. Through separation, the conclusions also extend to causal compression of Markov sources, while several extensions remain open.

  • VII. CONCLUSION: Theorems 1, 3, 4, 5, 7, and 8 provide sharp rate-cost lower bounds for fully and partially observed control systems.The rate-cost function characterizes communication requirements compatible with attainable quadratic cost.
  • VII. CONCLUSION: At high rate and low cost, variable-rate lattice quantization approaches the converse by transmitting only the quantized state innovation.The achievability results are given for both fully and partially observed systems.
  • VII. CONCLUSION: Via the separation principle, the same converse and matching achievability extend to causal compression of Markov sources.The converse is presented as a causal counterpart of Shannon’s lower bound.
  • VII. CONCLUSION: Extending the partially observed analysis to non-Gaussian noises remains open.The paper also leaves open whether the converse can be approached by fixed-rate quantization or noisy-channel control.

APPENDIX

The appendix supplies technical tools for the achievability analysis, including entropy continuity, regular-density propagation, Wasserstein bounds, and lattice-quantizer entropy estimates. It also explains why the resulting bound approaches Shannon’s lower bound in high dimension and small distortion.

  • APPENDIX: The appendix begins with an entropy-continuity tool that bounds differential-entropy differences when two random-vector distributions are close.This tool is used alongside regularity and Wasserstein estimates in the proof machinery.
  • APPENDIX: The Wasserstein distance is defined by an infimum over joint distributions with fixed marginals, and lattice quantizers provide an upper bound on output entropy for regular densities.These results supply key ingredients for bounding quantization entropy and distortion.
  • APPENDIX: Regular densities are preserved under adding an independent bounded random vector, enabling regularity control for random vectors arising during system operation.Proposition 9 changes the regularity parameters from (c0, c1) to (c0 + c1b, c1).
  • APPENDIX: The leading term of the achievability bound is Shannon’s lower bound, while remaining terms become negligible as dimension grows and distortion decreases.The appendix attributes this behavior to the asymptotics of the correction terms and lattice covering efficiency.
  • APPENDIX: Rogers’ result supplies lattices whose covering-efficiency contribution is logarithmic in dimension, supporting the high-dimensional negligibility of correction terms.Low-dimensional constants can instead be evaluated using known thin lattice coverings such as A_n^*.
Loading 1612.02126v3…