Mathematics – Numerical Analysis
Scientific paper
2008-03-12
Mathematics
Numerical Analysis
title changed; paper rewritten to include more examples 18 pages, one figure
Scientific paper
Compressed Sensing decoding algorithms can efficiently recover an N dimensional real-valued vector x to within a factor of its best k-term approximation by taking m = 2klog(N/k) measurements y = Phi x. If the sparsity or approximate sparsity level of x were known, then this theoretical guarantee would imply quality assurance of the resulting compressed sensing estimate. However, because the underlying sparsity of the signal x is unknown, the quality of a compressed sensing estimate x* using m measurements is not assured. Nevertheless, we demonstrate that sharp bounds on the error || x - x* ||_2 can be achieved with almost no effort. More precisely, we assume that a maximum number of measurements m is pre-imposed; we reserve 4log(p) of the original m measurements and compute a sequence of possible estimates (x_j)_{j=1}^p to x from the m - 4log(p) remaining measurements; the errors ||x - x*_j ||_2 for j = 1, ..., p can then be bounded with high probability. As a consequence, numerical upper and lower bounds on the error between x and the best k-term approximation to x can be estimated for p values of k with almost no cost. Our observation has applications outside of compressed sensing as well.
No associations
LandOfFree
Compressed Sensing with Cross Validation 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 Compressed Sensing with Cross Validation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Compressed Sensing with Cross Validation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-69288