5
$\begingroup$

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

| improve this question | |
$\endgroup$
  • $\begingroup$ ListDeconvolve as you use it should produce you an approximation to data1. See, you have to provide the kernel ker to ListConvolve. $\endgroup$ – Henrik Schumacher Jul 23 '18 at 14:07
10
$\begingroup$

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

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

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.

| improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ It works...but really hard to understand. $\endgroup$ – XinBae Jul 23 '18 at 15:02
  • 1
    $\begingroup$ There is a strong relationship between list convolution and polynomial multiplication. $\endgroup$ – Daniel Lichtblau Jul 23 '18 at 19:27
4
$\begingroup$

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]]

enter image description here

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.