Abstract
Convolution is a cornerstone of modern computing, yet its standard $O(n \log n)$ complexity via the Fast Fourier Transform (FFT) becomes a bottleneck for massive datasets. This paper presents sub-linear time algorithms for convolution when the output is "approximately sparse"—containing a few significant values amidst noise. By combining randomized hashing with a novel "derivative" operator, the proposed methods achieve significant speedups, making them ideal for large-scale applications in signal processing and data mining.
Introduction
The convolution operation ($A \star B$) is ubiquitous in fields ranging from computer vision to graph analysis. While the FFT provides an efficient $O(n \log n)$ solution, many real-world signals are sparse or approximately sparse. Previous work has focused on exactly sparse vectors, but real-world data often contains a "long tail" of small, non-zero noise. This research addresses the challenge of recovering significant indices and values from such noisy, approximately sparse convolutions in sub-linear time.
Methodology: Hashing and the $\partial$ Trick
The proposed approach relies on two key techniques to reduce the computational burden of the FFT.
The $\partial$ Operator
A central innovation is the introduction of the $\partial$ (partial) notation. For a vector $A$, the operator is defined as $(\partial A)_i = A_i \cdot i$. This transformation encodes the index of each element directly into its value.
When the convolution $(A \star B)$ is hashed into smaller buckets, the ratio of the hashed value of $\partial(A \star B)$ to the hashed value of $(A \star B)$ reveals the original index $i$, provided the bucket contains only one significant element.
Randomized Hashing
To achieve sub-linear complexity, the algorithms map high-dimensional vectors into smaller ones using randomized hash functions (typically modulo a prime $p$).
By performing convolutions on these reduced-size vectors using standard FFT, the algorithm avoids the $O(n \log n)$ cost of the full-scale operation.
Proposed Algorithms
The paper details two primary algorithms:
- Approximate Recovery: This algorithm uses multiple hash functions and computes the median of results to filter out collisions. It recovers significant indices with a point-wise error of $o(1)$ in $O(k \log n \log k \log(k/\delta))$ time.
- Iterative Correction: To achieve exact recovery, an iterative "peeling" process is used. It identifies the largest components, calculates the residual by subtracting their contributions, and repeats. This process corrects errors from noise or collisions, achieving exact recovery in $O(k \log n \log^2 k (\log(1/\delta) + \log \log k))$ time.
Key Results and Insights
The algorithms provide a significant theoretical advantage over the classical FFT when the sparsity $k$ is much smaller than the vector size $n$. The running time depends primarily on $k$ and $\log n$, allowing for extreme scalability. A critical assumption is the non-negativity of input vectors, which prevents noise from canceling out significant signals, ensuring the "long tail" remains manageable.
Limitations and Future Work
While theoretically robust, the current framework requires non-negative inputs and a clear "sparsity gap" between significant elements and noise. Future research could explore generalizations to complex or signed numbers and evaluate practical performance against highly optimized libraries like FFTW, where constant factors and hardware-level optimizations are paramount.
Summary updated