On deterministic sketching and streaming for sparse recovery and norm estimation

摘要

We study classic streaming and sparse recovery problems using deterministic linear sketches, including ?_1/?_1 and ?_∞/?_1 sparse recovery problems (the latter also being knownas ?_1-heavy hitters), norm estimation, and approximate inner product.We focus on devising a fixedmatrixA ∈ ?~(m×n) and a deterministic recovery/estimationprocedure whichwork for all possible input vectors simultaneously. Our results improve upon existing work, the following being our main contributions: ? A proof that ?_∞/?_1 sparse recovery and inner product estimation are equivalent, and that incoherent matrices can be used to solve both problems. Our upper bound for the number of measurements is m = O(ε~(-2) min{log n, (log n/ log(1/ε))~2}), which holds for any 0 < ε < 1/2. We can also obtain fast sketching and recovery algorithms by making use of the Fast Johnson-Lindenstrauss transform. Both our running times and number of measurements improve upon previous work. We can also obtain better error guarantees than previous work in terms of a smaller tail of the input vector. ? A new lower bound for the number of linear measurements required to solve ?_1/?_1 sparse recovery.We show ?(k/ε~2 + k log(n/k)/ε) measurements are required to recover an x' with||x-x'||1 ≤ (1+ε)'x_(tail(k)_||1,wherex_(tail(k)) is x projected onto all but its largest k coordinates in magnitude.