Real vs. Complex Null Space Properties for Sparse Vector Recovery, in "Comptes Rendus de l’Academie des

We identify and solve an overlooked problem about the characterization of underdeter-mined 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 coeffi-cients, 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. Nous identifions et résolvons un problème lie ́ aux systèmes sous-determinés d’équations linéaires, plus précisément a ̀ la propriéte ́ de leurs noyaux qui caractérise le fait que les so-lutions parcimonieuses soient celles avec la plus petite norme `1. Quand les coefficients du système sont réels, les solutions parcimonieuses peuvent être considérés comme vecteurs réels ou complexes, ce qui conduit a ̀ deux propriétés des noyaux a priori distinctes. Nous démontrons que ces deux propriétés sont en fait équivalentes en établissant un lien avec un problème sur les polygones convexes du plan réel. Accessoirement, nous prouvons aussi l’équivalence entre des propriétés stables du noyau, lesquelles expliquent la stabilite ́ de la reconstruction par minimisation `1 de vecteurs qui ne sont pas exactement parcimonieux. This note deals with the recovery of sparse vectors x from incomplete measurements y = Ax, where A is an m × N matrix with m N. The interest in developing sparse data models for solving ill-posed inverse problems originates in the possibility of such a recovery in un-derdetermined situations. This is also the fundamental result underlying the recent field of Compressed Sensing, which aims at acquiring signals/images well below the Nyquist rate by exploiting their sparsity in an appropriate domain. It is well known by now that the recovery can be carried out by solving the convex optimization problem (P1) minimize ‖z‖1 subject to Az = y