On the error of estimating the sparsest solution of underdetermined linear systems

Computer Science – Information Theory

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

To appear in December 2011 issue of IEEE Transactions on Information Theory

Scientific paper

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.

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

On the error of estimating the sparsest solution of underdetermined linear systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the error of estimating the sparsest solution of underdetermined linear systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the error of estimating the sparsest solution of underdetermined linear systems will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-388752

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.