The convex geometry of linear inverse problems (Q1928276)

The authors consider the problem of recovery of object models from limited linear measurements. More precisely, the model is a convex combination of finite number of elements called atoms. The atomic norm \(\| \cdot\|_{\mathcal{A}}\) is defined as the gauge function of the convex hull of atoms. Given an evaluation vector \(y\) and operator \(\Phi\), the problem is to minimize \(\| x\|_{\mathcal{A}}\) subject to \(\Phi x=y\). The authors give many examples of applications. By analyzing the Gaussian width of certain tangent cones, they investigate the number of measurements for exact and robust recovery. When the atomic set has algebraic structure, the basic problem can be solved or approximated via semidefinite programming. Some results of computations illustrating the quality of approximations are also given.