Accuracy of spike-train Fourier reconstruction for colliding nodes

Abstract

We consider a signal reconstruction problem for signals F of the form F(x) = Σ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j=1</sub> a <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> δ(x-x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> ) from their Fourier transform F(F)(s) = ∫ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">∞</sup> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-∞</sub> F(x)e <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">-isx</sup> dx. We assume F(F)(s) to be known for each s ε [-N,N] with an absolute error not exceeding ε > 0. We give an absolute lower bound (which is valid with any reconstruction method) for the “worst case” reconstruction error of F from F(F) for situations where the x <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> nodes are known to form an I elements cluster contained in an interval of length h <;<; 1. Using “decimation” algorithm of [6], [7] we provide an upper bound for the reconstruction error, essentially of the same form as the lower one. Roughly, our main result states that for h of order 1/N ϵ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2l-1</sup> the worst case reconstruction error of the cluster nodes is of the same order 1/N ϵ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2l-1</sup> , and hence the inside configuration of the cluster nodes (in the worst case scenario) cannot be reconstructed at all. On the other hand, decimation algorithm reconstructs F with the accuracy of order 1/N ϵ <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1/2l</sup> .