Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Distributed Sparse Random Projections for Refinable Approximation

View Current Project Information

Wei Wang, Minos Garofalakis and Kannan Ramchandran

Consider a large-scale wireless sensor network measuring compressible data, where n distributed data values can be well-approximated using only k < n coefficients of some known transform. We address the problem of recovering an approximation of the n data values by querying any L sensors, so that the reconstruction error is comparable to the optimal k-term approximation. To solve this problem, we present a novel distributed algorithm based on sparse random projections, which requires no global coordination or knowledge. The key idea is that the sparsity of the random projections greatly reduces the communication cost of pre-processing the data. Our algorithm allows the collector 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," Proc. Int'l. Conf. Information Processing in Sensor Networks, April 2007.