sparse_convolution
Sparse convolution in python.
Uses Toeplitz convolutional matrix multiplication to perform sparse convolution.
This allows for extremely fast convolution when:
- The kernel is small (<= 30x30)
- The input array is sparse (<= 1% density)
- Many arrays are convolved with the same kernel
Install:
git clone https://github.com/RichieHakim/sparse_convolution
cd sparse_convolution
pip install -e .
Basic usage:
Convolve a single sparse 2D array with a 2D kernel.
import sparse_convolution as sc
import numpy as np
import scipy.sparse
# Create a single sparse matrix
A = scipy.sparse.rand(100, 100, density=0.1)
# Create a dense kernel
B = np.random.rand(3, 3)
# Prepare class
conv = Toeplitz_convolution2d(
x_shape=A.shape,
k=B,
mode='same',
dtype=np.float32,
)
# Convolve
C = conv(
x=A,
batching=False,
mode='same',
).toarray()
Batching usage:
Convolve multiple sparse 2D arrays with a 2D kernel.
The input arrays must be reshaped into flattened vectors and stacked into a single sparse array of shape: (n_arrays, height * width).
import sparse_convolution as sc
import numpy as np
import scipy.sparse
# Create multiple sparse matrices
# note that the shape of A will be (3, 100**2)
A = scipy.sparse.vstack([
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
scipy.sparse.rand(100, 100, density=0.1).reshape(1, -1),
]).tocsr()
# Create a dense kernel
B = np.random.rand(3, 3)
# Prepare class
conv = sc.Toeplitz_convolution2d(
x_shape=(100, 100), # note that the input shape here is (100, 100)
k=B,
mode='same',
dtype=np.float32,
)
# Convolve
C = conv(
x=A,
batching=True,
mode='same',
)
# Reshape the output back to (3, 100, 100)
C_reshaped = np.stack([c.reshape(100, 100).toarray() for c in C], axis=0)
References
- See: https://stackoverflow.com/a/51865516 and https://github.com/alisaaalehi/convolution_as_multiplication for a nice illustration.
- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.convolution_matrix.html for 1D version.
- See: https://docs.scipy.org/doc/scipy/reference/generated/scipy.linalg.matmul_toeplitz.html#scipy.linalg.matmul_toeplitz for potential ways to make this implementation faster.
