In this work, we study an LQG control system where one of two feedback channels is discrete and incurs a communication cost. We assume that a decoder (colocated with the controller) can make noiseless measurements of a subset of the state vector (referred to as side information) meanwhile a remote encoder (colocated with a sensor) can make arbitrary measurements of the entire state vector, but must convey its measurements to the decoder over a noiseless binary channel. Use of the channel incurs a communication cost, quantified as the timeaveraged expected length of prefixfree binary codeword. We study the tradeoff between the communication cost and control performance. The formulation motivates a constrained directed information minimization problem, which can be solved via convex optimization. Using the optimization, we propose a quantizer design and a subsequent achievability result.
more »
« less
A LowerBound for VariableLength Source Coding in LinearQuadraticGaussian Control With Shared Randomness
In this letter, we consider a Linear Quadratic Gaussian (LQG) control system where feedback occurs over a noiseless binary channel and derive lower bounds on the minimum communication cost (quantified via the channel bitrate) required to attain a given control performance. We assume that at every time step an encoder can convey a packet containing a variable number of bits over the channel to a decoder at the controller. Our system model provides for the possibility that the encoder and decoder have shared randomness, as is the case in systems using dithered quantizers. We define two extremal prefixfree requirements that may be imposed on the message packets; such constraints are useful in that they allow the decoder, and potentially other agents to uniquely identify the end of a transmission in an online fashion. We then derive a lower bound on the rate of prefixfree coding in terms of directed information; in particular we show that a previously known bound still holds in the case with shared randomness. We generalize the bound for when prefix constraints are relaxed, and conclude with a ratedistortion formulation.
more »
« less
 Award ID(s):
 1944318
 NSFPAR ID:
 10488407
 Publisher / Repository:
 IEEE
 Date Published:
 Journal Name:
 IEEE control systems letters
 Volume:
 6
 ISSN:
 24751456
 Page Range / eLocation ID:
 2918  2923
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Horstein, Burnashev, Shayevitz and Feder, Naghshvar et al . and others have studied sequential transmission of a kbit message over the binary symmetric channel (BSC) with full, noiseless feedback using posterior matching. Yang et al . provide an improved lower bound on the achievable rate using martingale analysis that relies on the smallenough difference (SED) partitioning introduced by Naghshvar et al . SED requires a relatively complex encoder and decoder. To reduce complexity, this paper replaces SED with relaxed constraints that admit the small enough absolute difference (SEAD) partitioning rule. The main analytical results show that achievablerate bounds higher than those found by Yang et al . [2] are possible even under the new constraints, which are less restrictive than SED. The new analysis does not use martingale theory for the confirmation phase and applies a surrogate channel technique to tighten the results. An initial systematic transmission further increases the achievable rate bound. The simplified encoder associated with SEAD has a complexity below order O ( K 2 ) and allows simulations for message sizes of at least 1000 bits. For example, simulations achieve 99% of of the channel’s 0.50bit capacity with an average block size of 200 bits for a target codeword error rate of 10 3.more » « less

In this article, we revisit the sequential sourcecoding framework to analyze fundamental performance limitations of discretetime stochastic control systems subject to feedback datarate constraints in finitetime horizon. The basis of our results is a new characterization of the lower bound on the minimum totalrate achieved by sequential codes subject to a total (across time) distortion constraint and a computational algorithm that allocates optimally the ratedistortion, for a given distortion level, at each instant of time and any fixed finitetime horizon. The idea behind this characterization facilitates the derivation of analytical , nonasymptotic , and finitedimensional lower and upper bounds in two controlrelated scenarios: a) A parallel timevarying Gauss–Markov process with identically distributed spatial components that are quantized and transmitted through a noiseless channel to a minimum meansquared error decoder; and b) a timevarying quantized linear quadratic Gaussian (LQG) closedloop control system, with identically distributed spatial components and with a random datarate allocation. Our nonasymptotic lower bound on the quantized LQG control problem reveals the absolute minimum datarates for (mean square) stability of our timevarying plant for any fixed finitetime horizon. We supplement our framework with illustrative simulation experiments.more » « less

In this work, we study the fascinating notion of outputcompressing randomized encodings for Turing Machines, in a shared randomness model. In this model, the encoder and decoder have access to a shared random string, and the efficiency requirement is, the size of the encoding must be independent of the running time and output length of the Turing Machine on the given input, while the length of the shared random string is allowed to grow with the length of the output. We show how to construct outputcompressing randomized encodings for Turing machines in the shared randomness model, assuming iO for circuits and any assumption in the set {LWE, DDH, N𝑡ℎ Residuosity}. We then show interesting implications of the above result to basic feasibility questions in the areas of secure multiparty computation (MPC) and indistinguishability obfuscation (iO): 1.Compact MPC for Turing Machines in the Random Oracle Model. In the context of MPC, we consider the following basic feasibility question: does there exist a malicioussecure MPC protocol for Turing Machines whose communication complexity is independent of the running time and output length of the Turing Machine when executed on the combined inputs of all parties? We call such a protocol as a compact MPC protocol. Hubácek and Wichs [HW15] showed via an incompressibility argument, that, even for the restricted setting of circuits, it is impossible to construct a malicious secure two party computation protocol in the plain model where the communication complexity is independent of the output length. In this work, we show how to evade this impossibility by compiling any (noncompact) MPC protocol in the plain model to a compact MPC protocol for Turing Machines in the Random Oracle Model, assuming outputcompressing randomized encodings in the shared randomness model. 2. Succinct iO for Turing Machines in the Shared Randomness Model. In all existing constructions of iO for Turing Machines, the size of the obfuscated program grows with a bound on the input length. In this work, we show how to construct an iO scheme for Turing Machines in the shared randomness model where the size of the obfuscated program is independent of a bound on the input length, assuming iO for circuits and any assumption in the set {LWE, DDH, N𝑡ℎ Residuosity}.more » « less

Locally Decodable Codes (LDCs) are errorcorrecting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. Despite exciting progress, we still don't have satisfactory answers in several important parameter regimes. For example, in the case of 3query LDCs, the gap between existing constructions and lower bounds is superpolynomial in the message length. In this work we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and PaskinCherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that 2query linear Insdel LDCs do not exist, and give an exponential lower bound for the length of all qquery Insdel LDCs with constant q. For q ≥ 3 our bounds are exponential in the existing lower bounds for Hamming LDCs. Furthermore, our exponential lower bounds continue to hold for adaptive decoders, and even in privatekey settings where the encoder and decoder share secret randomness. This exhibits a strict separation between Hamming LDCs and Insdel LDCs. Our strong lower bounds also hold for the related notion of Insdel LCCs (except in the privatekey setting), due to an analogue to the Insdel notions of a reduction from Hamming LCCs to LDCs. Our techniques are based on a delicate design and analysis of hard distributions of insertion and deletion errors, which depart significantly from typical techniques used in analyzing Hamming LDCs.more » « less