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].
Titolo: | Lower bounds on the estimation error in problems of distributed computation | |
Autori: | ||
Data di pubblicazione: | 2009 | |
Abstract: | Information-theoretic lower bounds on the estimation error are derived for problems of distribute...d 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. | |
ISBN: | 978-1-4244-3990-4 | |
Appare nelle tipologie: | 4.1 Contributo in Atti di convegno |
File in questo prodotto:
File | Descrizione | Tipologia | Licenza | |
---|---|---|---|---|
Como09IEEEL.ower.Bounds.pdf | Articolo principale | 2a Post-print versione editoriale / Version of Record | Non Pubblico - Accesso privato/ristretto | Administrator Richiedi una copia |
http://hdl.handle.net/11583/2831646