Near-optimal Bayesian localization via incoherence and sparsity

ABSTRACT

This paper exploits recent developments in sparse approximation and compressive sensing to efficiently perform localization in a sensor network. We introduce a Bayesian framework for the localization problem and provide sparse approximations to its optimal solution. By exploiting the spatial sparsity of the posterior density, we demonstrate that the optimal solution can be computed using fast sparse approximation algorithms. We show that exploiting the signal sparsity can reduce the sensing and computational cost on the sensors, as well as the communication bandwidth. We further illustrate that the sparsity of the source locations can be exploited to decentralize the computation of the source locations and reduce the sensor communications even further. We also discuss how recent results in 1-bit compressive sensing can significantly reduce the amount of inter-sensor communications by transmitting only the intrinsic timing information. Finally, we develop a computationally efficient algorithm for bearing estimation using a network of sensors with provable guarantees.

References

1. R. G. Baraniuk. Compressive Sensing. IEEE Signal Processing Magazine, 24(4):118-121, 2007.
2. C. M. Bishop. Pattern recognition and machine learning. Springer, 2006.
3. P. Boufounos and R. G. Baraniuk. One-Bit Compressive Sensing. In Conference on Information Sciences and Systems (CISS), Princeton, NJ, Mar 2008.
4. E. Candes and T. Tao. The Dantzig selector: statistical estimation when p is much larger than n. Annals of Statistics, 35(6):2313-2351, 2007.
5. E. J. Candès. Compressive sampling. In Proc. International Congress of Mathematicians, volume 3, pages 1433-1452, Madrid, Spain, 2006.
6. V. Cevher, M. Duarte, and R. G. Baraniuk. Distributed Target Localization via Spatial Sparsity. In European Signal Processing Conference (EUSIPCO), Lausanne, Switzerland, Aug 2008.
7. V. Cevher, A. C. Gurbuz, J. H. McClellan, and R. Chellappa. Compressive wireless arrays for bearing estimation. In Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), number 2497-2500, Las Vegas, NV, Apr 2008.
8. J. Chen, L. Yip, J. Elson, H. Wang, D. Maniezzo, R. Hudson, K. Yao, and D. Estrin. Coherent acoustic array processing and localization on wireless sensor networks. Proceedings of the IEEE, 91(8):1154-1162, 2003.
9. D. L. Donoho. Compressed Sensing. IEEE Trans. on Information Theory, 52(4):1289-1306, 2006.
10. A. Gilbert, M. Strauss, and J. Tropp. A tutorial on fast fourier sampling. IEEE Signal Processing Magazine, 25(2):57-66, March 2008.
11. I. F. Gorodnitsky and B. D. Rao. Sparse signal reconstruction from limited data using FOCUSS: A re-weighted minimum norm algorithm. IEEE Trans. Signal Processing, 45(3):600-616, 1997.
12. C. Guestrin, P. Bodi, R. Thibau, M. Paski, and S. Madden. Distributed regression: an efficient framework for modeling sensor network data. In Proc. of the Third International Symposium on Information Processing in Sensor Networks (IPSN), pages 1-10. ACM Press New York, NY, USA, 2004.
13. A. C. Gurbuz, V. Cevher, and J. H. McClellan. A compressive beamformer. In Proc. IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP), Las Vegas, Nevada, Mar 30 -Apr 4 2008.
14. J. Hill and D. Culler. Mica: a wireless platform for deeply embedded networks. Micro, IEEE, 22(6):12-24, Nov/Dec 2002.
15. A. T. Ihler. Inference in Sensor Networks: Graphical Models and Particle Methods. PhD thesis, Massachusetts Institute of Technology, 2005.
16. J. Laska, S. Kirolos, Y. Massoud, R. Baraniuk, A. Gilbert, M. Iwen, and M. Strauss. Random sampling for analog-to-information conversion of wideband signals. In IEEE Dallas Circuits and Systems Workshop, Dallas, TX, 2006.
17. J. N. Laska, S. Kirolos, M. F. Duarte, T. Ragheb, R. G. Baraniuk, and Y. Massoud. Theory and implementation of an analog-to-information conversion using random demodulation. In Proc. IEEE Int. Symposium on Circuits and Systems (ISCAS), New Orleans, LA, May 2007. To appear.
18. D. Malioutov, M. Cetin, and A. S. Willsky. A sparse signal reconstruction perspective for source localization with sensor arrays. IEEE Trans. Signal Processing, 53(8):3010-3022, 2005.
19. D. Model and M. Zibulevsky. Signal reconstruction in sensor arrays using sparse representations. Signal Processing, 86(3):624-638, 2006.
20. M. Rabbat and R. Nowak. Distributed optimization in sensor networks. In Proc. 3rd International Workshop on Inf. Processing in Sensor Networks (IPSN), pages 20-27. ACM Press New York, NY, USA, 2004.
21. G. Simon, M. Maróti, Á. Lédeczi, G. Balogh, B. Kusy, A. NÁdas, G. Pap, J. Sallai, and K. Frampton. Sensor network-based countersniper system. In Proc. of the 2nd international conference on Embedded networked sensor systems, pages 1-12. ACM New York, NY, USA, 2004.
22. E. M. Stein. Harmonic analysis real-variable methods, orthogonality, and oscillatory integrals. Princeton University Press, Princeton, NJ, 1993.
23. J. Tropp and A. C. Gilbert. Signal recovery from partial information via orthogonal matching pursuit. IEEE Trans. Info. Theory, 53(12):4655-4666, Dec. 2007.
24. J. Tropp, D. Needell, and R. Vershynin. Iterative signal recovery from incomplete and inaccurate measurements. In Information Theory and Applications, San Diego, CA, Jan. 27-Feb. 1 2008.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Design

• Hardware

  • Communication hardware, interfaces and storage

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

• Networks

  • Network services

    • Network management

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis