Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2009 Research Summary

Distributed Sparse Random Projections for Refinable Approximation

View Current Project Information

Wei Wang, Minos Garofalakis and Kannan Ramchandran

National Science Foundation CCF-0635114 and National Science Foundation CCR-0330514

We consider a wireless sensor network measuring compressible data, where p distributed data values can be well-approximated using only k < p coefficients in some orthonormal basis. We address the problem of recovering an approximation of the p data values by querying any n(p,k) sensors, so that the reconstruction error is comparable to the best k-term approximation.

We show that a simple decoder can recover compressible signals from sparse random projections, and we present a novel distributed algorithm to compute sparse random projections in sensor networks. The key idea is that the sparsity of the random projections greatly reduces the communication cost in the network. Our algorithm allows the decoder to choose the number of sensors to query according to the desired approximation error. The reconstruction quality depends only on the number of sensors queried, enabling robust refinable approximation.

W. Wang, M. Garofalakis, and K. Ramchandran, "Distributed Sparse Random Projections for Refinable Approximation," Int. Conf. Information Processing in Sensor Networks, April 2007.