Sublinear Time, Measurement-Optimal, Sparse Recovery For All

Computer Science – Data Structures and Algorithms

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Corrected argument with minor change to results

Scientific paper

An approximate sparse recovery system in ell_1 norm formally consists of parameters N, k, epsilon an m-by-N measurement matrix, Phi, and a decoding algorithm, D. Given a vector, x, where x_k denotes the optimal k-term approximation to x, the system approximates x by hat_x = D(Phi.x), which must satisfy ||hat_x - x||_1 <= (1+epsilon)||x - x_k||_1. Among the goals in designing such systems are minimizing m and the runtime of D. We consider the "forall" model, in which a single matrix Phi is used for all signals x. All previous algorithms that use the optimal number m=O(k log(N/k)) of measurements require superlinear time Omega(N log(N/k)). In this paper, we give the first algorithm for this problem that uses the optimum number of measurements (up to a constant factor) and runs in sublinear time o(N) when k=o(N), assuming access to a data structure requiring space and preprocessing O(N).

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

Sublinear Time, Measurement-Optimal, Sparse Recovery For All 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 Sublinear Time, Measurement-Optimal, Sparse Recovery For All, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sublinear Time, Measurement-Optimal, Sparse Recovery For All will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-76300

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