Convolution of Vector

Convolution is a mathematical operation that blends two vectors together. Given two vectors ( A ) and ( B ), the convolution ( C ) is obtained by “sliding” ( A ) across ( B ) and summing the overlapping elements at each point. This operation is often used in signal processing, image processing, and data analysis.

Let’s consider the concept of vector convolution, often used in signal processing or image manipulation. Let’s assume we have two 1D arrays (vectors):

A = [2, 1, 2, 1] (Signal)
B = [1, 0, 3] (Kernel)

The convolution process involves flipping the Kernel (B) and sliding it across the Signal (A), multiplying overlapping elements and summing them up to form a new array (Convolution Result).

Visually, consider this representation:

Flip B: [3, 0, 1]
Pad zeros in A: [0, 0, 2, 1, 2, 1, 0, 0]

Start sliding:

Step 1:
A: 0  0  2  1  2  1  0  0
B: 3  0  1

Result: (0*3) + (0*0) + (2*1) = 2

Step 2:
A: 0  0  2  1  2  1  0  0
   B: 3  0  1

Result: (0*3) + (2*0) + (1*1) = 1

Step 3:
A: 0  0  2  1  2  1  0  0
      B: 3  0  1

Result: (0*3) + (2*0) + (1*1) = 1

…and so on.

The resulting array from the convolution will be [2, 1, 1, ...].

Understanding this visual representation will help you when you look at code that performs convolution on vectors.

Convolution of vectors is often used in signal processing to blend two signals, or a signal and a filter, together. It involves reversing one vector and then sliding it across another vector, taking the dot product at each position.

Visual Representation:

Imagine we have two vectors, ( A = [a_1, a_2, a_3] ) and ( B = [b_1, b_2] ).

Step 1: Reverse ( B ) [ B_{\text{reversed}} = [b_2, b_1] ]

Step 2: Slide and Multiply

  a1  a2  a3                  a1  a2  a3                     a1  a2  a3
|---|---|---|              |---|---|---|                 |---|---|---|
                            b2  b1                         b1  b2
                          |---|---|                       |---|---|

In each position, multiply the overlapping elements and sum them up:

( (a_2 \times b_1) + (a_3 \times b_2) )
( (a_1 \times b_1) + (a_2 \times b_2) )
( (a_1 \times b_2) )

Step 3: Sum up to form Convolution Vector [ C = [c_1, c_2, c_3] ] Where ( c_i ) are the sums from Step 2.

Convolution blends two vectors together in a specific manner defined by reversing and sliding. Each element in the resulting vector is formed by taking the dot product of overlapping elements during the slide. This is useful in various applications like signal processing and image filtering.

Solution

Here are code snippets to implement convolution of vectors in Java, C++, and Python.

Java

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Convolution {
    public static double[] convolve(double[] A, double[] B) {
        int lenA = A.length;
        int lenB = B.length;
        double[] C = new double[lenA + lenB - 1];

        for (int i = 0; i < lenA; i++) {
            for (int j = 0; j < lenB; j++) {
                C[i + j] += A[i] * B[j];
            }
        }

        return C;
    }

    public static void main(String[] args) {
        double[] A = {1, 2, 3};
        double[] B = {4, 5};
        double[] result = convolve(A, B);

        for (double num : result) {
            System.out.print(num + " ");
        }
    }
}

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <vector>

std::vector<double> convolve(const std::vector<double>& A, const std::vector<double>& B) {
    int lenA = A.size();
    int lenB = B.size();
    std::vector<double> C(lenA + lenB - 1, 0);

    for (int i = 0; i < lenA; ++i) {
        for (int j = 0; j < lenB; ++j) {
            C[i + j] += A[i] * B[j];
        }
    }

    return C;
}

int main() {
    std::vector<double> A = {1, 2, 3};
    std::vector<double> B = {4, 5};
    std::vector<double> result = convolve(A, B);

    for (const auto& num : result) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

Python

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def convolve(A, B):
    lenA = len(A)
    lenB = len(B)
    C = [0] * (lenA + lenB - 1)

    for i in range(lenA):
        for j in range(lenB):
            C[i + j] += A[i] * B[j]

    return C

A = [1, 2, 3]
B = [4, 5]
result = convolve(A, B)
print(result)

Key Takeaways

Convolution blends two vectors ( A ) and ( B ) to produce a new vector ( C ).
The code examples show how to implement the convolution operation in Java, C++, and Python.
Nested loops iterate through each element in ( A ) and ( B ) to perform the sum of products, which forms ( C ).
The length of the resulting vector ( C ) is ( \text{len}(A) + \text{len}(B) - 1 ).