Real versus complex null space properties for sparse vector recovery

We identify and solve an overlooked problem about the characterization of underdetermined systems of linear equations for which sparse solutions have minimal 1-norm. This characterization is known as the null space property. When the system has real coefficients, sparse solutions can be considered either as real or complex vectors, leading to two seemingly distinct null space properties. We prove that the two properties actually coincide by establishing a link with a problem about convex polygons in the real plane. Incidentally, we also show the equivalence between stable null space properties which account for the stable reconstruction by 1-minimization of vectors that are not exactly sparse. 2010 Acadmie des sciences.

Real versus complex null space properties for sparse vector recovery Academic Article