Data fusion, communication complexity, and decentralized detection

Decentralized detection

A 1993 survey with a unified treatment of the subject can be found in:

J. N. Tsitsiklis, "Decentralized Detection", in Advances in Signal Processing, Vol. 2, H. V. Poor and J. B. Thomas, editors, JAI Press, 1993, pp. 297-344.

If the measurements at each sensor are conditionally independent (conditional on any hypothesis), there is a lot to say:

W. P. Tay and J. N. Tsitsiklis, "Error Exponents for Decentralized Detection in Tree Networks," in Networked Sensing Information and Control, V. Saligrama (Ed.), Springer Verlag, 2008, pp. 73-92.

W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, "On the Impact of Node Failures and Unreliable Communications in Dense Sensor Networks", IEEE Transactions on Signal processing, Vol. 56, No. 6, June 2008, pp. 2535-2546.

W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, "On the Sub-exponential Decay of Detection Error Probabilities in Long Tandems", February 2007; IEEE Transactions on Information Theory, in press.

W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, "Data Fusion Trees for Detection: Does Architecture Matter?", November 2006; IEEE Transactions on Information Theory, in press.

W. P. Tay, J. N. Tsitsiklis, and M. Z. Win, "Asymptotic Performance of a Censoring Sensor Network ,'' IEEE Transactions on Information Theory, Vol. 53, No. 11, pp. 4191-4209, November 2007.

W.W. Irving and J.N. Tsitsiklis, "Some Properties of Optimal Thresholds in Decentralized Detection", IEEE Transactions on Automatic Control, Vol. 39, No. 4, April 1994, pp. 835-838.

J.N. Tsitsiklis, "Extremal Properties of Likelihood-Ratio Quantizers", IEEE Transactions on Communications, Vol. 41, No. 4, 1993, pp. 550-558.
G. Polychronopoulos and J.N. Tsitsiklis, "Explicit Solutions for some Simple Decentralized Detection Problems", IEEE Transactions on Aerospace and Electronic Systems, Vol. 26, 1990, pp. 282-291.
J.N. Tsitsiklis, "Decentralized Detection by a Large Number of Sensors", Mathematics of Control, Signals and Systems, Vol. 1, No. 2, 1988, pp. 167-182.

J.N. Tsitsiklis and M. Athans, "On the Complexity of Decentralized Decision Making and Detection Problems", IEEE Transactions on Automatic Control, Vol. 30, No.5, 1985, pp. 440-446.

Communication complexity

Agent 1 knows x, agent 2 knows y. They want to compute a function f(x,y). How much do they need to communicate? This formulation captures much of the essence of the data fusion problem:

Unfortunately, the problem is NP-complete, in general:

C.H. Papadimitriou and J.N. Tsitsiklis, "On the Complexity of Designing Distributed Protocols", Information and Control, Vol. 53, No. 3, 1982, pp. 211-218.

But for specific types of functions f, progress is possible. When x and y are continuous variables, calculating the communication complexity may involve tools from algebraic or differential geometry:

Z.-Q. Luo and J.N. Tsitsiklis, "Data Fusion with Minimal Communication", IEEE Transactions on Information Theory, Vol. 40, No. 5, September 1994, pp. 1551-1563.

Z.-Q. Luo and J.N. Tsitsiklis, "On the Communication Complexity of Distributed Algebraic Computation", Journal of the ACM, Vol. 40, No. 5, pp. 1019-1047, November 1993.

Z.-Q. Luo and J.N. Tsitsiklis, "On the Communication Complexity of Solving a Polynomial Equation", SIAM J. on Computing, Vol. 20, No. 5, October 1991, pp. 936-950.

In another variant, agent 1 knows a convex function g(.), agent 2 knows a convex function h(.) and they want optimize f(.)+g(.) within some accuracy epsilon:

J.N. Tsitsiklis and Z.-Q. Luo, "Communication Complexity of Convex Optimization", Journal of Complexity, Vol. 3, No. 3, 1987, pp. 231-243.