In a recent post I wrote about time varying channels. These were operators, described by the spreading function , mapping an input signal to an output signal via
1. The problem statement
In this post I write about the problem of identifying the channels from input-output measurements. More precisely, the question is as follows:
Is it possible to choose a single input signal such that the corresponding output signal allows the computation of the spreading function?
At first sight this seems hopeless: The degrees of freedom we have is a single function and we look for a function . However, additional assumptions on may help and indeed there is the following identification theorem due to Kailath:
Probably this looks a bit weird: The size of the support shall allow for identification? However, after turning the problem a bit around one sees that there is an intuitive explanation for this theorem which also explains the constant .
2. Translation to integral operators
The first step is, to translate the problem into one with integral operators of the form
and hence, identifying is equivalent to identifying (by the way: I use the same normalization of the Fourier transform as in this post).
From my point of view, the formulation of the identification problem is a bit clearer in the form of the integral operator . It very much resembles “matrix-vector multiplication”: First you multiply with you input signal in (forming “pointwise products of the rows and the input vector” as in matrix-vector multiplication) and then integrate with respect to (“summing up” the result).
3. Sending Diracs through the channel
Now, let’s see, if we can identify from a single input-output measurement. We start, and send a single Dirac impulse through the channel: . This formally gives
Ok, this is not too much. From the knowledge of we can directly infer the values but that’s it – nothing more.
But we could also send a Dirac at a different position , and obtain
Ok, different Diracs give us information about for all but only for a single . Let’s send a whole spike train (or Dirac comb) of “width” : . We obtain
Oh – this does not reveal a single value of but “aggregated” values…
4. Choosing the right spike train
Now let’s translate the one condition on we have to a condition on : The support of is contained in a rectangle with area less then . Let’s assume that this rectangle in centered around zero (which is no loss of generality) and denote it by , i.e. if or (and of course ). From (1) we conclude that
In the -plane, the support looks like this:
If we now send this spike train in the channel, we can visualize the output as follows:
We observe that in this case we can infer the values of at some points but at other points we have an overlap and only observe a sum of and . But if we make large enough, namely larger than , we identify the values of exactly in the output signal!
5. Is that enough?
Ok, now we know something about but how can we infer the rest of the values? Don’t forget, that we know that and that we know that is supported in . Up to now we only used the value of . How does the support limitation if translates to ? We look again at (1) and see: The function is bandlimited with bandwidth for every . And what do we know about these functions ? We know the samples . In other words, we have samples of with the sampling rate . But there is the famous Nyquist-Shannon sampling theorem:
Theorem 2 (Nyquist-Shannon) A function which is bandlimited with bandwidth is totally determined by its discrete time samples , and it holds that
We are happy with the first assertion: The samples totally determine the function if they are dense enough. In our case the bandwidth of is and hence, we need the sampling rate . What we have, are samples with rate .
We collect our conditions on : We need
- larger than to separate the values of in the output.
- smaller than to determine the full functions .
Both together say
Such a exists, if and we have proven Theorem 1.
6. Concluding remarks
The proof of Kailath’s theorem reveal the role of the constraint : We want not to be too large to be able to somehow separate the values of in the output measurement and we need not too large to ensure that we can interpolate the values exactly.
However, a severe drawback of this results is that one needs to know to construct the “sensing signal” which was the spike train . Moreover, this sensing signal has itself an infinite bandwidth which is practically not desirable. It seems to be an open question whether there are more practical sensing signals.
There is more known about sensing of time varying channels: The support of does not have to be in a rectangle, it is enough if the measure of the support is smaller than (a result usually attributed to Bello). Moreover, there are converse results which say that linear and stable identification is only possible under this restriction on the support size (see the work of Götz Pfander and coauthors).