Real versus complex null space properties for sparse vector recovery
Résumé
We identify and solve an overlooked problem about the characterization of underdetermined systems of linear equations for which sparse solutions have minimal L1-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 L1-minimization of vectors that are not exactly sparse.
Nous identifions et résolvons un problème lié aux systèmes sous-determinés d'équations linéaires, plus précisément à la propriété de leurs noyaux qui caractérise le fait que les solutions parcimonieuses soient celles avec la plus petite norme L1. Quand les coefficients du système sont réels, les solutions parcimonieuses peuvent être considérées comme vecteurs réels ou complexes, ce qui conduit à 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 stabilité de la reconstruction par minimisation L1 de vecteurs qui ne sont pas exactement parcimonieux.
Domaines
Analyse classique [math.CA]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...