Many algorithms and techniques in computer science, optimization and coding theory exploit data sparsity in order to allow for compact signal/data representation and efficient processing. Because an overwhelming number of signals encountered both in nature and man-made networks are inherently sparse, such techniques have found many applications in network security, computational imaging, astronomical data analysis, and the life sciences, in particular, bioinformatics and neuroscience.
Sparse data processing has also recently received significant attention with the emergence of the new field of compressive sensing, also closely tied to coding and optimization theory, statistics, streaming algorithms analysis, and random matrix theory. Consequently, fundamental advances in this area can have broad impacts on many scientific and mathematical disciplines. The fundamental problem in compressed sensing is to design the fewest measurements of signals so they may be reconstructed efficiently to desired accuracy; the results here lead to ultimately much fewer measurements than the Nyquist sampling rate that has been the golden standard for long. This is an exciting development that has been spawned by new mathematical and algorithmic techniques. There is a growing community of researchers exploring the applications of this breakthrough to various imaging applications in the sciences, analog-to-information conversion in sensor design, and elsewhere. Still, a lot remains to be done in terms of understanding the full power of these techniques, extending the fundamental problem to richer signals and expanding the range of applications.
Recent research has shown that compressive sensing, coding theory, and streaming algorithms share the same underlying working principles, and that they can be used to address several modern network applications dealing with massive and distributed stored data and data streams, which calls for efficient real-time inference under strict communication, computation and memory (CCM) constraints. A few examples of such applications include identifying a small number of "heavy hitter" ips (delivering a large amount of traffic) out of many millions of source ips that send traffic into a government or corporate network; accurately counting the number of distinct objects simultaneously observed by multiple sensors in a large sensor network with minimum communications; checking consistency and localizing inconsistent records between a master database and its remote copies with billions of records. Exact solutions of many such problems are unattainable because of the CCM constraints.
We propose a combined activity that will first bring together an interdisciplinary group of researchers in a "working group" and then include them in a larger, more public workshop. We propose to have 1.5 days of a "working group" on March 25-26, 2009, that will explore the fundamental principles shared by compressive sensing, coding, statistics and streaming algorithms from the perspective of theoretical computer science. The organizers have a unique joint expertise in all these areas, and will therefore be able to recruit a diverse group of participants for a working group, performing research at the intersection of these seemingly diverse research fields. The working group would be followed by 1.5 days of a more public workshop on the same theme, emphasizing recent developments, and ending on March 27. These activities will be organized to address past and especially current areas of research as well as identifying promising areas for future research.