Real versus complex null space properties for sparse vector recovery

Simon Foucart 1 Rémi Gribonval 2
2 METISS - Speech and sound data modeling and processing
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : 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.
Document type :
Journal articles
Liste complète des métadonnées

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00539612
Contributor : Rémi Gribonval <>
Submitted on : Sunday, February 6, 2011 - 10:10:31 PM
Last modification on : Friday, January 4, 2019 - 5:32:30 PM
Document(s) archivé(s) le : Saturday, May 7, 2011 - 2:21:13 AM

File

FoGr09.pdf
Files produced by the author(s)

Identifiers

Citation

Simon Foucart, Rémi Gribonval. Real versus complex null space properties for sparse vector recovery. Comptes rendus de l'Académie des sciences. Série I, Mathématique, Elsevier, 2010, 348 (15-16), pp.863-865. ⟨10.1016/j.crma.2010.07.024⟩. ⟨inria-00539612⟩

Share

Metrics

Record views

611

Files downloads

235