For-all Sparse Recovery in Near-Optimal Time

An approximate sparse recovery system in ${\mathrm{\ell }}_1$ norm consists of parameters $k$, $ϵ$, $N$, an $m$-by-$N$ measurement $\mathrm{\Phi }$, and a recovery algorithm, $\mathcal{R}$. Given a vector, $\mathbf{x}$, the system approximates $x$ by $\widehat{\mathbf{x}}=\mathcal{R}(\mathrm{\Phi }\mathbf{x})$, which must satisfy $|\widehat{$\mathbf{x}$}-$\mathbf{x}$|_1 \leq (1+\epsilon)|$\mathbf{x}$-$\mathbf{x}$_k|_1$. We consider the ‘for all’ model, in which a single matrix $\mathrm{\Phi }$, possibly ‘constructed’ non-explicitly using the probabilistic method, is used for all signals $\mathbf{x}$. The best existing sublinear algorithm by Porat and Strauss (SODA’12) uses $O(\epsilon^{-3} k\log(N/k))$measurementsandrunsintime$O(k^{1-\alpha}N^\alpha)$ for any constant $\alpha >0$. In this paper, we improve the number of measurements to $O(\epsilon^{-2} k \log(N/k))$, matching the best existing upper bound (attained by super-linear algorithms), and the runtime to $O(k^{1+\beta}$\text{poly}$(\log N,1/\epsilon))$,withamodestrestrictionthat$\epsilon \leq (\log k/\log N)^{\gamma}$,foranyconstants$\beta,\gamma > 0$\mathrm{.}When$k\leq \log^c N$ for some $c>0$, the runtime is reduced to $O(k\text{poly}(N,1\mathrm{/}ϵ))$. With no restrictions on $ϵ$, we have an approximation recovery system with $m = O(k/\epsilon \log(N/k)((\log N/\log k)^\gamma + 1/\epsilon))$ measurements.