# Can I use ListDeconvolve or any other functions to get the original kernel?

I have seen an example in the help document: data1 = {0., 0., 1., 2., 1., 2., 1., 0., 0., 0.}; ker = {1/3, 1/3, 1/3}; conv = ListConvolve[ker, data1, 2] my question is: Can I get the ker back from the known data1 and conv.
The document use deconv = ListDeconvolve[ker, conv, Method -> "RichardsonLucy"] but deconv is not equal to ker

• ListDeconvolve as you use it should produce you an approximation to data1. See, you have to provide the kernel ker to ListConvolve. – Henrik Schumacher Jul 23 '18 at 14:07

In this case, the following works just fine:

LeastSquares[
Transpose@Through[{RotateLeft, Identity, RotateRight}[data1]],
conv
]


{0.333333, 0.333333, 0.333333}

More general with kernel length 2 k + 1:

a = RandomReal[{-1, 1}, 100];
k = 20;
ker = RandomReal[{-1, 1}, 2 k + 1];
b = ListConvolve[ker, a, k + 1];

ker1 = LeastSquares[
Transpose[RotateRight[a, #] & /@ Range[-k, k]],
b
];

Max[Abs[ker - ker1]]


2.27596*10^-15

• This is inverse methods as a one liner ! Nice ! – chris Jul 23 '18 at 14:39
• Many thanks, chris! – Henrik Schumacher Jul 23 '18 at 14:43
• Thanks ! you have provide a very good idea – XinBae Jul 23 '18 at 14:44
• You're welcome. – Henrik Schumacher Jul 23 '18 at 14:44

This is a bit roundabout but one can treat this as a polynomial algebra problem. First pad both ends of data and convolution result with zeros so that the convolution emulates polynomial multiplication. Then do a division to get the kernel as a polynomial.

data1 = {0., 0., 1., 2., 1., 2., 1., 0., 0., 0.};
ker = {1/3, 1/3, 1/3};
conv = ListConvolve[ker, data1, 2];


Augment:

data2 = Join[{0.}, data1, {0.}];
conv2 = Join[{0., 0.}, conv, {0., 0.}];


Rewrite as explicit polynomials:

polyfactor = data2.x^Range[0, Length[data2] - 1];
polyprod = conv2.x^Range[0, Length[conv2] - 1];


Compute the kernel as coefficients of the polynomial quotient:

CoefficientList[Chop[PolynomialQuotient[polyprod, polyfactor, x]], x]

(* {0.333333333333, 0.333333333333, 0.333333333333} *)


If actual examples are large and efficiency is a concern, there are equivalent but faster ways to recover the kernel e.g. emulating the division using a Fourier transform.

• It works...but really hard to understand. – XinBae Jul 23 '18 at 15:02
• There is a strong relationship between list convolution and polynomial multiplication. – Daniel Lichtblau Jul 23 '18 at 19:27

To approximate ker using ListDeconvolve, use data1 as the kernel. Increasing MaxIterations can improve the approximation.

data1 = {0., 0., 1., 2., 1., 2., 1., 0., 0., 0.};

ker = {1/3, 1/3, 1/3};

conv = ListConvolve[ker, data1, 2];

Column[ListDeconvolve[data1, conv, MaxIterations -> #,
Method -> "RichardsonLucy"][[5 ;; 7]] & /@ Range[10, 40, 10]]


• your method looks very efficient. Can it work more general ,such as,when the convolution is not cycle? – XinBae Jul 23 '18 at 16:04
• I don't know. Suggest you experiment. – Bob Hanlon Jul 23 '18 at 16:08