TY - GEN

T1 - Fundamental limits of distributed tracking

AU - Kostina, Victoria

AU - Hassibi, Babak

N1 - KAUST Repository Item: Exported on 2022-06-30
Acknowledgements: This work was supported in part by the National Science Foundation (NSF) under grants CCF- 1751356 and CCF-1817241. The work of Babak Hassibi was supported in part by the NSF under grants CNS-0932428, CCF-1018927, CCF- 1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASA's Jet Propulsion Laboratory through the President and Director's Fund, and by King Abdullah University of Science and Technology.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2020/8/24

Y1 - 2020/8/24

N2 - Consider the following communication scenario. An n-dlmensional source with memory is observed by K isolated encoders via parallel channels, who causally compress their observations to transmit to the decoder via noiseless rate-constrained links. At each time instant, the decoder receives K new codewords from the observers, combines them with the past received codewords, and produces a minimum- distortion estimate of the latest block of n source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining memory of the past.We prove a coding theorem showing that the minimum asymptotically (as n → ∞) achievable sum rate required to achieve a target distortion is equal to the directed mutual information from the observers to the decoder minimized subject to the distortion constraint and the separate encoding constraint. For the Gauss-Markov source observed via K parallel AWGN channels, we solve that minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels.The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers.

AB - Consider the following communication scenario. An n-dlmensional source with memory is observed by K isolated encoders via parallel channels, who causally compress their observations to transmit to the decoder via noiseless rate-constrained links. At each time instant, the decoder receives K new codewords from the observers, combines them with the past received codewords, and produces a minimum- distortion estimate of the latest block of n source symbols. This scenario extends the classical one-shot CEO problem to multiple rounds of communication with communicators maintaining memory of the past.We prove a coding theorem showing that the minimum asymptotically (as n → ∞) achievable sum rate required to achieve a target distortion is equal to the directed mutual information from the observers to the decoder minimized subject to the distortion constraint and the separate encoding constraint. For the Gauss-Markov source observed via K parallel AWGN channels, we solve that minimal directed mutual information problem, thereby establishing the minimum asymptotically achievable sum rate. Finally, we explicitly bound the rate loss due to a lack of communication among the observers; that bound is attained with equality in the case of identical observation channels.The general coding theorem is proved via a new nonasymptotic bound that uses stochastic likelihood coders and whose asymptotic analysis yields an extension of the Berger-Tung inner bound to the causal setting. The analysis of the Gaussian case is facilitated by reversing the channels of the observers.

UR - http://hdl.handle.net/10754/679503

UR - https://ieeexplore.ieee.org/document/9174006/

UR - http://www.scopus.com/inward/record.url?scp=85090410989&partnerID=8YFLogxK

U2 - 10.1109/ISIT44484.2020.9174006

DO - 10.1109/ISIT44484.2020.9174006

M3 - Conference contribution

SN - 9781728164328

SP - 2438

EP - 2443

BT - 2020 IEEE International Symposium on Information Theory (ISIT)

PB - IEEE

ER -