Information-theoretic lower bounds on the estimation error are derived for problems of distributed computation. These bounds hold for a network attempting to compute a real-vector-valued function of the global information, when the nodes have access to partial information and can communicate through noisy transmission channels. The presented bounds are algorithm-independent, and improve on recent results by Ayaso et al., where the exponential decay rate of the mean square error was upper-bounded by the minimum normalized cut-set capacity. We show that, if the transmission channels are stochastic, the highest achievable exponential decay rate of the mean square error is in general strictly smaller than the minimum normalized cut-set capacity of the network. This is due to atypical channel realizations, which, despite their asymptotically vanishing probability, affect the error exponent. © 2009 IEEE.
Lower bounds on the estimation error in problems of distributed computation / Como, G.; Dahleh, M.. - ELETTRONICO. - (2009), pp. 70-76. (Intervento presentato al convegno Information Theory and Applications Workshop, ITA 2009 tenutosi a San Diego, CA, usa nel 2009) [10.1109/ITA.2009.5044925].
Lower bounds on the estimation error in problems of distributed computation
Como G.;
2009
Abstract
Information-theoretic lower bounds on the estimation error are derived for problems of distributed computation. These bounds hold for a network attempting to compute a real-vector-valued function of the global information, when the nodes have access to partial information and can communicate through noisy transmission channels. The presented bounds are algorithm-independent, and improve on recent results by Ayaso et al., where the exponential decay rate of the mean square error was upper-bounded by the minimum normalized cut-set capacity. We show that, if the transmission channels are stochastic, the highest achievable exponential decay rate of the mean square error is in general strictly smaller than the minimum normalized cut-set capacity of the network. This is due to atypical channel realizations, which, despite their asymptotically vanishing probability, affect the error exponent. © 2009 IEEE.File | Dimensione | Formato | |
---|---|---|---|
Como09IEEEL.ower.Bounds.pdf
non disponibili
Descrizione: Articolo principale
Tipologia:
2a Post-print versione editoriale / Version of Record
Licenza:
Non Pubblico - Accesso privato/ristretto
Dimensione
906.52 kB
Formato
Adobe PDF
|
906.52 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
https://hdl.handle.net/11583/2831646