Kernel estimation given original and convoluted 1D data

Question

I can't figure out how to find kernel used for convolution given original data and convoluted data. For example, If I have 1D data X and I apply convolution with some kernel phi I will get output convoluted_x like this.

import numpy as np
X = np.asarray([1,2,3,4,5,6,7,8,9,10])
phi = np.asarray([-1,0,1])
X_conv = np.convolve(X, phi, mode='same')
print(X_conv)

here, X_conv is [-2 -2 -2 -2 -2 -2 -2 -2 -2 9].

My question is if only X and X_conv are given is there any way to find kernel phi which is used for convolution?

Answer 1

If we denote the input vector with X and the output (convoluted) vector with Y, then every Y(i) is made up of a linear combination of some elements of X:

Y(i) = Sum{j} X(j) * kernel(kernelIndex(i, j))

kernelIndex is the function that gives you the specific position to access your kernel for the given convolution and is usually implementation-dependent (i.e., how you index your input / output).

For our purposes, Y(i) and X(j) are known and the kernel(…) are unknowns. For every output Y(i), we can therefore state a linear equation (as stated above)`. We can gather all these equations and solve for the unknown kernel entries. Here is an example implementation in Matlab:

function [kernel] = solveConv(source, target, kernelSize)
    sizeOfSource = size(source);
    sizeOfSource = sizeOfSource(2);
    % linear system A x = b
    A = zeros(sizeOfSource, kernelSize);
    b = zeros(sizeOfSource, 1);
    for i = 1 : sizeOfSource
        for j = 1 : kernelSize
            sourceIndex = i + (kernelSize - j) - floor(kernelSize / 2);
            if sourceIndex >= 1 && sourceIndex <= sizeOfSource
                A(i, j) = source(sourceIndex);
            end
        end
        b(i, 1) = target(i);
    end
    % solve the linear system
    kernel = A \ b;
end

You can use this function to get your kernel:

>> solveConv([1,2,3,4,5,6,7,8,9,10], [-2 -2 -2 -2 -2 -2 -2 -2 -2 9],3)
ans =

   -1.0000
   -0.0000
    1.0000

Or if you are not sure about the kernel size, try a bigger kernel:

>> solveConv([1,2,3,4,5,6,7,8,9,10], [-2 -2 -2 -2 -2 -2 -2 -2 -2 9],5)

ans =

   -0.0000
   -1.0000
   -0.0000
    1.0000
   -0.0000