2023/06/04 by Xiaoxiao Li, Li, Xiaoxiao, Zhao Song +3
Computer Science · Engineering · Mathematics · #Algorithm #Binary logarithm #Combinatorics #Computation #Computer science #Convolution (computer science) #Cryptography and Residue Arithmetic #Data Structures and Algorithms (cs.DS) #Dimension (graph theory) #Discrete mathematics #FOS: Computer and information sciences #Fast Fourier transform #Leverage (statistics) #Mathematical Approximation and Integration #Mathematical analysis #Mathematics #Sparse and Compressive Sensing Techniques #Star (game theory) #Statistics
paper · pdf · doi:10.48550/arxiv.2306.02381
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2023/06/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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‖≥ c1 = k and ‖A ⋆ B‖≤ c2 = n-k holds, we can approximately recover the all index in supp≥ c1(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≥ c1(A ⋆ B) correctly in O(k log(n) log2(k) (log(1/δ) + loglog(k))) time.