1D Convolution

easyFREECNNs & Sequence ModelsMachine Learning 2

Implement 1D convolution (valid mode, no padding).

Given a 1D signal and a kernel, slide the kernel across the signal and compute the dot product at each position:

$\text{output}[i] = \sum_{j=0}^{k-1} \text{signal}[i+j] \cdot \text{kernel}[j]$

Return the convolution result, rounded to 4 decimal places.

Example

Input

signal = [1, 2, 3, 4, 5]
kernel = [1, 0, -1]

Output

[-2, -2, -2]

Reasoning

Inputs: signal is a sequence of $n = 5$ samples, $1, 2, 3, 4, 5$ ; kernel holds $k = 3$ weights, $1, 0, -1$ . Valid mode keeps only placements fully inside the signal: $n - k + 1 = 3$ positions.
Position 0 covers samples $1, 2, 3$ : $1 \cdot 1 + 2 \cdot 0 + 3 \cdot (-1) = 1 + 0 - 3 = -2$ .
Position 1 covers $2, 3, 4$ : $2 \cdot 1 + 3 \cdot 0 + 4 \cdot (-1) = -2$ . Position 2 covers $3, 4, 5$ : $3 - 5 = -2$ .
Output: three values, [-2, -2, -2], already exact at 4 decimal places. With weights $1, 0, -1$ , each output is $\text{signal}[i] - \text{signal}[i+2]$ , a difference of samples two steps apart.
Notice: the signal climbs a steady $1$ per step, so every window gives the same $-2$ : a slope detector on a straight line. The kernel is applied as written, not flipped; flipping this asymmetric kernel would turn every value into $+2$ .

Constraints

signal: 1D list of numbers
kernel: 1D list of numbers (length <= len(signal))
Return 1D list of length (len(signal) - len(kernel) + 1)
Round each value to 4 decimal places

Learn this in

Text ClassificationNLP Study Plan

More from Machine Learning 2

Kernel PCAhard PCA via Covariance Matrixmedium Variance Explained Ratioeasy Feature Scalingeasy GAN Discriminator Losshard

Concept primer

Background Knowledge

1D Convolution is a fundamental concept in signal processing and machine learning, particularly in convolutional neural networks (CNNs). It involves sliding a small window, called a kernel or filter, across a larger input signal to generate a feature map. The kernel computes a weighted sum of the input values at each position, known as the dot product or inner product. This process helps extract local features from the input signal.

In the context of CNNs & Sequence Models, 1D convolution is used to process sequential data, such as time series signals, audio, or text. The kernel's size and shape determine the amount of context considered when computing the output. In this problem, we're implementing 1D convolution in valid mode, which means the kernel will only be applied to positions where it fully overlaps with the input signal, without any padding.

The mathematical formula for 1D convolution is given by: $\text{output}[i] = \sum_{j=0}^{k-1} \text{signal}[i+j] \cdot \text{kernel}[j]$ where $k$ is the size of the kernel. This formula highlights the importance of understanding array indexing and looping to implement the convolution operation efficiently.

Algorithm/Approach

The general approach to solving this problem involves using a sliding window technique to iterate over the input signal and compute the dot product with the kernel at each position. This can be achieved using nested loops, where the outer loop iterates over the signal and the inner loop computes the dot product with the kernel.

Step-by-Step Strategy

To implement the solution, follow these steps:

Initialize an empty array to store the convolution result.
Iterate over the input signal using a sliding window of size equal to the kernel size.
At each position, compute the dot product between the signal values within the window and the kernel.
Store the result in the corresponding position in the output array.
Round the final result to 4 decimal places.

Common Pitfalls

When implementing the solution, watch out for:

Incorrect indexing of the input signal and kernel arrays.
Failure to handle edge cases, such as when the kernel size is larger than the input signal.
Inefficient use of loops, leading to slow performance.

Time & Space Complexity

The expected time complexity for this problem is O(n * k), where n is the length of the input signal and k is the size of the kernel. The space complexity is O(n - k + 1), as we need to store the convolution result for each valid position. Note that these complexities assume a naive implementation using nested loops. More efficient solutions may be possible using optimized algorithms or libraries.

solution.py

Python 3.13

Test results