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
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
-
1$\begingroup$ This is inverse methods as a one liner ! Nice ! $\endgroup$ – chris Jul 23 '18 at 14:39
-
-
-
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.
-
2
-
1$\begingroup$ There is a strong relationship between list convolution and polynomial multiplication. $\endgroup$ – 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]]
-
$\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
-
ListDeconvolve
as you use it should produce you an approximation todata1
. See, you have to provide the kernelker
toListConvolve
. $\endgroup$ – Henrik Schumacher Jul 23 '18 at 14:07