Sie befinden Sich nicht im Netzwerk der Universität Paderborn. Der Zugriff auf elektronische Ressourcen ist gegebenenfalls nur via VPN oder Shibboleth (DFN-AAI) möglich. mehr Informationen...
On the Error of Estimating the Sparsest Solution of Underdetermined Linear Systems
Ist Teil von
IEEE transactions on information theory, 2011-12, Vol.57 (12), p.7840-7855
Ort / Verlag
New York, NY: IEEE
Erscheinungsjahr
2011
Quelle
IEEE Electronic Library (IEL)
Beschreibungen/Notizen
Let A be an n × m matrix with m >; n, and suppose that the underdetermined linear system As = x admits a sparse solution S 0 for which ||S 0 || 0 <; 1/2 spark( A). Such a sparse solution is unique due to a well-known uniqueness theorem. Suppose now that we have somehow a solution ŝ as an estimation of s 0 , and suppose that ŝ is only "approximately sparse," that is, many of its components are very small and nearly zero, but not mathematically equal to zero. Is such a solution necessarily close to the true sparsest solution? More generally, is it possible to construct an upper bound on the estimation error ||ŝ - s 0 || 2 without knowing S 0 ? The answer is positive, and in this paper, we construct such a bound based on minimal singular values of submatrices of A. We will also state a tight bound, which is more complicated, but besides being tight, enables us to study the case of random dictionaries and obtain probabilistic upper bounds. We will also study the noisy case, that is, where x = As + n. Moreover, we will see that where ||s 0 || 0 grows, to obtain a predetermined guaranty on the maximum of ||ŝ - s 0 || 2 , ŝ is needed to be sparse with a better approximation. This can be seen as an explanation to the fact that the estimation quality of sparse recovery algorithms degrades where ||s 0 || 0 grows.