APPROXIMATE SPARSE RECOVERY: OPTIMIZING TIME AND MEASUREMENTS
A Euclidean approximate sparse recovery system consists of parameters k, N, an m-by-N measurement matrix, Phi, and a decoding algorithm, D. Given a vector, x, the system approximates x by (x) over cap = D(Phi x), which must satisfy |(x) over cap -x|(2) <= C|x - x(k)|(2), where x(k) denotes the optimal k-term approximation to x. (The output (x) over cap may have more than k terms.) For each vector x, the system must succeed with probability at least 3/4. Among the goals in designing such systems are minimizing the number m of measurements and the runtime of the decoding algorithm, D. In this paper, we give a system with m = O(k log(N/k)) measurements-matching a lower bound, up to a constant factor-and decoding time k log(O(1)) N, matching a lower bound up to a polylog(N) factor. We also consider the encode time (i.e., the time to multiply Phi by x), the time to update measurements (i.e., the time to multiply Phi by a 1-sparse x), and the robustness and stability of the algorithm (resilience to noise before and after the measurements). Our encode and update times are optimal up to log(k) factors. The columns of F have at most O(log(2)(k) log(N/k)) nonzeros, each of which can be found in constant time. Our full result, a fully polynomial randomized approximation scheme, is as follows. If x = x(k)+nu(1), where nu(1) and nu(2) (below) are arbitrary vectors (regarded as noise), then setting (x) over cap = D(Phi x + nu(2)), and for properly normalized Phi, we get |x - (x) over cap|(2)(2) <= (1 + epsilon) |nu(1)|(2)(2) + epsilon |nu(2)|(2)(2) using O((k/epsilon) log(N/k)) measurements and (k/epsilon) log(O(1))(N) time for decoding.
approximation embedding sketching sparse approximation sublinear algorithms