|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
19 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
On the error of estimating the sparsest solution of underdetermined linear systems | | Massoud Babaie-Zadeh
; Christian Jutten
; Hosein Mohimani
; | | Date: |
4 Dec 2011 | | Abstract: | Let A be an n by m matrix with m>n, and suppose that the underdetermined
linear system As=x admits a sparse solution s0 for which ||s0||_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 s_hat as an estimation of
s0, and suppose that s_hat 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_hat-s0||_2 without knowing s0? 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 ||s0||_0 grows, to obtain a
predetermined guaranty on the maximum of ||s_hat-s0||_2, s_hat 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
||s0||_0 grows. | | Source: | arXiv, 1112.0789 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER