An upper bound on the estimation error of the sparsest solution of underdetermined linear systems

Massoud Babaie-Zadeh 1 G. Hosein Mohimani 2 Christian Jutten 3
1 Department of Electrical Engineering - Sharif University of Technology
2 Department of Electrical Engineering - University of California
3 GIPSA-SIGMAPHY - SIGMAPHY
GIPSA-DIS - Département Images et Signal
Abstract : Let A be an n X m matrix with m > n, and suppose the underdetermined linear system As = x admits a unique sparse solution s0 (i.e. it has a solution s0 for which ks0k0 < 1 2 spark(A)). Suppose that we have somehow a solution (sparse or non-sparse) ^s of this system as an estimation of the true sparsest solution s0. Is it possible to construct an upper bound on the estimation error k^s - s0k2 without knowing s0? The answer is positive, and in this paper we construct such a bound which, in the case A has Unique Representation Property (URP), depends on the smallest singular value of all n X n submatrices of A.
Type de document :
Communication dans un congrès
Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009
Liste complète des métadonnées

Littérature citée [30 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00369545
Contributeur : Ist Rennes <>
Soumis le : vendredi 20 mars 2009 - 11:42:09
Dernière modification le : lundi 9 avril 2018 - 12:22:34
Document(s) archivé(s) le : jeudi 10 juin 2010 - 17:37:17

Fichier

63.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00369545, version 1

Collections

SPARS09 | UGA | GIPSA-SIGMAPHY | GIPSA-DIS | GIPSA | UGA-TEST-TER

Citation

Massoud Babaie-Zadeh, G. Hosein Mohimani, Christian Jutten. An upper bound on the estimation error of the sparsest solution of underdetermined linear systems. Rémi Gribonval. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Apr 2009, Saint Malo, France. 2009. 〈inria-00369545〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

301

Téléchargements de fichiers

128

Contact


archive-ouverte@inria.fr