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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [30 references]  Display  Hide  Download
https://hal.inria.fr/inria-00369545
Contributor : Ist Rennes <>
Submitted on : Friday, March 20, 2009 - 11:42:09 AM
Last modification on : Wednesday, August 7, 2019 - 12:18:06 PM
Long-term archiving on : Thursday, June 10, 2010 - 5:37:17 PM

File

63.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00369545, version 1

Collections

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

Citation

Massoud Babaie-Zadeh, G. Hosein Mohimani, Christian Jutten. An upper bound on the estimation error of the sparsest solution of underdetermined linear systems. SPARS'09 - Signal Processing with Adaptive Sparse Structured Representations, Inria Rennes - Bretagne Atlantique, Apr 2009, Saint Malo, France. ⟨inria-00369545⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

344

Files downloads

411

Contact


archive-ouverte@inria.fr