Sparse Convolution for Approximate Sparse Instance
share
Computing the convolution A ⋆ B of two vectors of dimension n is one of the most important computational primitives in many fields. For the non-negative convolution scenario, the classical solution is to leverage the Fast Fourier Transform whose time complexity is O(n log n). However, the vectors A and B could be very sparse and we can exploit such property to accelerate the computation to obtain the result. In this paper, we show that when A ⋆ B_≥ c_1 = k and A ⋆ B_≤ c_2 = n-k holds, we can approximately recover the all index in supp_≥ c_1(A ⋆ B) with point-wise error of o(1) in O(k log (n) log(k)log(k/δ)) time. We further show that we can iteratively correct the error and recover all index in supp_≥ c_1(A ⋆ B) correctly in O(k log(n) log^2(k) (log(1/δ) + loglog(k))) time.
READ FULL TEXT