Comptes Rendus
no. 15-16
Mathematical Analysis/Theory of Signals
Real versus complex null space properties for sparse vector recovery
[Propriétés du noyau pour la reconstruction de vecteurs parcimonieux : Équivalence des versions réelles et complexes]

Présenté par : Yves Meyer

Simon Foucart1 ; Rémi Gribonval1, 2
1 Laboratoire Jacques-Louis Lions, Université Pierre-et-Marie-Curie, 4, place Jussieu, 75005 Paris, France
2 Centre de Recherche INRIA Rennes - Bretagne Atlantique, Campus de Beaulieu, F-35042 Rennes cedex, France
Comptes Rendus. Mathématique, Volume 348 (2010) no. 15-16, pp. 863-865.

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 ℓ1. 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 ℓ1 de vecteurs qui ne sont pas exactement parcimonieux.

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.

Reçu le :
Accepté le :
Publié le :
DOI : 10.1016/j.crma.2010.07.024

Simon Foucart 1 ; Rémi Gribonval 1, 2

1 Laboratoire Jacques-Louis Lions, Université Pierre-et-Marie-Curie, 4, place Jussieu, 75005 Paris, France
2 Centre de Recherche INRIA Rennes - Bretagne Atlantique, Campus de Beaulieu, F-35042 Rennes cedex, France 
@article{CRMATH_2010__348_15-16_863_0,
     author = {Simon Foucart and R\'emi Gribonval},
     title = {Real versus complex null space properties for sparse vector recovery},
     journal = {Comptes Rendus. Math\'ematique},
     pages = {863--865},
     publisher = {Elsevier},
     volume = {348},
     number = {15-16},
     year = {2010},
     doi = {10.1016/j.crma.2010.07.024},
     language = {en},
}
TY  - JOUR
AU  - Simon Foucart
AU  - Rémi Gribonval
TI  - Real versus complex null space properties for sparse vector recovery
JO  - Comptes Rendus. Mathématique
PY  - 2010
SP  - 863
EP  - 865
VL  - 348
IS  - 15-16
PB  - Elsevier
DO  - 10.1016/j.crma.2010.07.024
LA  - en
ID  - CRMATH_2010__348_15-16_863_0
ER  - 
%0 Journal Article
%A Simon Foucart
%A Rémi Gribonval
%T Real versus complex null space properties for sparse vector recovery
%J Comptes Rendus. Mathématique
%D 2010
%P 863-865
%V 348
%N 15-16
%I Elsevier
%R 10.1016/j.crma.2010.07.024
%G en
%F CRMATH_2010__348_15-16_863_0
Simon Foucart; Rémi Gribonval. Real versus complex null space properties for sparse vector recovery. Comptes Rendus. Mathématique, Volume 348 (2010) no. 15-16, pp. 863-865. doi : 10.1016/j.crma.2010.07.024. https://comptes-rendus.academie-sciences.fr/mathematique/articles/10.1016/j.crma.2010.07.024/

[1] D. Donoho; M. Elad Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ1 minimization, Proc. Natl. Acad. Sci. USA, Volume 100 (2003) no. 5, pp. 2197-2202

[2] R. Gribonval; M. Nielsen Highly sparse representations from dictionaries are unique and independent of the sparseness measure, Appl. Comput. Harmon. Anal., Volume 22 (2007) no. 3, pp. 335-355

[3] M.-J. Lai, Y. Liu, The null space property for sparse recovery from multiple measurement vectors, preprint.

[4] S. Markov On quasivector spaces of convex bodies and zonotopes, Numer. Algorithms, Volume 37 (2004), pp. 263-274

[5] F. Spitzer; H. Widom The circumference of a convex polygon, Proc. Amer. Math. Soc., Volume 12 (1961) no. 3, pp. 506-509

[6] E. van den Berg; M.P. Friedlander Theoretical and empirical results for recovery from multiple measurements, IEEE Trans. Info. Theory, Volume 56 (2010) no. 5, pp. 2516-2527

Cité par Sources :

☆ This work has been supported by the French National Research Agency (ANR) through the project ECHANGE (ANR-08-EMER-006).

Commentaires - Politique