[Propriétés du noyau pour la reconstruction de vecteurs parcimonieux : Équivalence des versions réelles et complexes]
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 . 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 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 -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 -minimization of vectors that are not exactly sparse.
Accepté le :
Publié le :
@article{CRMATH_2010__348_15-16_863_0,
author = {Foucart, Simon and Gribonval, R\'emi},
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},
url = {http://www.numdam.org/articles/10.1016/j.crma.2010.07.024/}
}
TY - JOUR AU - Foucart, Simon AU - Gribonval, Rémi 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 UR - http://www.numdam.org/articles/10.1016/j.crma.2010.07.024/ DO - 10.1016/j.crma.2010.07.024 LA - en ID - CRMATH_2010__348_15-16_863_0 ER -
%0 Journal Article %A Foucart, Simon %A Gribonval, Rémi %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 %U http://www.numdam.org/articles/10.1016/j.crma.2010.07.024/ %R 10.1016/j.crma.2010.07.024 %G en %F CRMATH_2010__348_15-16_863_0
Foucart, Simon; Gribonval, Rémi. Real versus complex null space properties for sparse vector recovery. Comptes Rendus. Mathématique, Tome 348 (2010) no. 15-16, pp. 863-865. doi : 10.1016/j.crma.2010.07.024. http://www.numdam.org/articles/10.1016/j.crma.2010.07.024/
[1] Optimally sparse representation in general (nonorthogonal) dictionaries via minimization, Proc. Natl. Acad. Sci. USA, Volume 100 (2003) no. 5, pp. 2197-2202
[2] 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] On quasivector spaces of convex bodies and zonotopes, Numer. Algorithms, Volume 37 (2004), pp. 263-274
[5] The circumference of a convex polygon, Proc. Amer. Math. Soc., Volume 12 (1961) no. 3, pp. 506-509
[6] 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).
