Sparse Exact and Approximate Recovery

• Applicants: Professor Dr. Dirk A. Lorenz; Professor Dr. Marc Emanuel Pfetsch
• Subject Area: Mathematics
• Term: from 2010 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 189141722

This project deals with the problem to recover a sparse solution of an underdetermined linear (equality) system. This topic has many applications and is a very active research area. It is located at the border between analysis and combinatorial optimization. The main goal of our project is to obtain a better understanding of the conditions under which (efficiently) finding such a sparse solution, i.e., recovery, is possible. We will pursue several steps to reach this goal. To compute optimal solutions of the problem, we will develop a branch-and-cut algorithm. To get sparse solutions for large-scale systems, we will investigate heuristic methods for this problem. Moreover, the investigation of the computational complexity of known recovery conditions as well as their extension is an important point. Very large instances of the problem will only be handable, if also the corresponding system matrices are sparse; we will therefore investigate deterministic constructions of sparse systems that allow recovery. Another issue is the stability of the recovery conditions with respect to perturbations in the system. Finally, one important technique in this area is to replace the exact problem by a convex approximation, in fact, a linear program. We will develop new techniques to solve this linear program and compare it computationally to existing approaches. Thus, our project is characterized by both theoretical and computational aspects as well as the interplay of continuous and discrete methods.

• DFG Programme: Research Grants