Sparse Convolution for Approximate Sparse Instance

Xiaoxiao Li, Zhao Song, Guangyi ZhangarXiv 2023 · OpenReview

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.

Figure 1: Illustration of the $\partial$ operator, where $(\partial A)_i = i \cdot A_i$. This encoding allows for index recovery after hashing.

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$).

Figure 6: Randomized hashing maps elements $x_i$ into buckets based on $g(x) = x \mod p$. Multiple primes are used to minimize collisions.

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:

  1. 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.
  2. 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

Abstract

Computing the convolution $A \star 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 \star B\|_{\geq c_1} = k$ and $\|A \star B\|_{\leq c_2} = n-k$ holds, we can approximately recover the all index in $\mathrm{supp}_{\geq c_1}(A \star B)$ with point-wise error of $o(1)$ in $O(k \log (n) \log(k)\log(k/\delta))$ time. We further show that we can iteratively correct the error and recover all index in $\mathrm{supp}_{\geq c_1}(A \star B)$ correctly in $O(k \log(n) \log^2(k) (\log(1/\delta) + \log\log(k)))$ time.
BibTeX
@misc{li2023sparse,
  author = {Xiaoxiao Li and Zhao Song and Guangyi Zhang},
  title = {{Sparse Convolution for Approximate Sparse Instance}},
  year = {2023},
  eprint = {2306.02381},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2306.02381},
}
Figure