In the past ten years the theoretical computer science, applied math and electrical engineering communities have extensively studied variants of the problem of ``solving" an under-determined linear system. One common mathematical feature that allows us to solve these problems is sparsity; roughly speaking, as long as the unknown vector does not contain too many non-zero components (or has a few dominating components), we can ``solve'' the under-determined system for the unknown vector. These problems are referred to as sparse approximation problems and have applications in diverse areas such as signal and image processing, biology, imaging, tomography, machine learning and others. The proposed research project aims to develop a comprehensive, rigorous theory of sparse approximation, broadly defined. The research proposal entails two complementary research directions: (1) a robust and more complete view of the combinatorial, algorithmic, and complexity-theoretic foundations of sparse approximations (including its generalization to functional sparse approximation where we want to ``solve" for some function of the unknown vector instead of the vector itself), (2) coupled with either its interactions or direct applications in other areas of theoretical computer science, from complexity theory to coding theory, and of electrical engineering, from signal processing to analog-to-digital converters. A general theory of sparse approximation that concentrates both on the optimal tradeoffs between competing parameters and the computational feasibility of attaining such tradeoffs will not only help explore the theoretical limits and possibilities of sparse approximations, but also feed algorithmic techniques and theoretical benchmarks back to its application areas. Sparse approximation already has been shown to have impact in a variety of fields, including imaging and signal processing, Internet traffic analysis, and design of experiments in biology and drug design.
