Loading...
Please wait, while we are loading the content...
Similar Documents
Cross Validation in Compressed Sensing via the Johnson Lindenstrauss Lemma
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ward, Rachel Mizsei |
| Copyright Year | 2008 |
| Abstract | Compressed Sensing decoding algorithms aim to reconstruct an unknown N dimensional vector x from m < N given measurements y = Phi x, with an assumed sparsity constraint on x. All algorithms presently are iterative in nature, producing a sequence of approximations (s_1, s_2, ...) until a certain algorithm-specific stopping criterion is reached at iteration j*, at which point the estimate x* = s_j* is returned as an approximation to x. In many algorithms, the error || x - x* ||_2 of the approximation is bounded above by a function of the error between x and the best k-term approximation to x. However, as x is unknown, such estimates provide no numerical bounds on the error. In this paper, we demonstrate that tight numerical upper and lower bounds on the error || x - s_j ||_2 for j <= p iterations of a compressed sensing decoding algorithm are attainable with little effort. More precisely, we assume a maximum iteration length of p is pre-imposed; we reserve 4 log p of the original m measurements and compute the s_j from the remaining measurements; the errors ||x - s_j||_2 for j = 1, ..., p can then be bounded with high probability. As a consequence, a numerical upper bound on the error between x and the best k-term approximation to x can be estimated with almost no cost. Our observation has applications outside of Compressed Sensing as well. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://arxiv.org/pdf/0803.1845v1.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
