Appendix
To reconstruct a function of the form
$$f(t) = \sum _{i=1}^n \alpha _i \cos (\phi _{i} t)$$
from equidistantly collected samples
\(f_j\) at
\(t=j\Delta \), in other words to recover the unknown parameters
\(\phi _{i}\) and coefficients
\(\alpha _i\), the sampling step
\(\Delta \) needs to satisfy the Shannon-Nyquist constraint
$$\Delta < \pi / \max _{i=1, \ldots , n} |\phi _{i}|.$$
Since we do not distinguish
\(\phi _{i}\) from
\(-\phi _{i}\) in this case, we can simply drop the sign information in
\(\phi _{i}\) from here on and write
\(\Delta = \pi /R\) with
$$0 \le \max _{i=1, \ldots , n} \phi _{i} < R.$$
The challenge we consider now is to retrieve the parameters
\(\phi _{i}\) and coefficients
\(\alpha _i\) from sub-Nyquist rate collected samples
\(f_{j\sigma }\) at
\(t=j\sigma \Delta \) with
\(\sigma >1\) and the shifted evaluations
\(f_{j\sigma +\tau }\) at
\(t=(j\sigma +\tau )\Delta \) with
\(\gcd (\sigma ,\tau )=1\). In Section
3.1 we describe how for
\(i=1, \ldots , n\) the values
$$\begin{aligned} C_{i,\sigma } :=&\cos (\phi _{i}\sigma \Delta ), \\ C_{i,\tau } :=&\cos (\phi _{i}\tau \Delta ) \end{aligned}$$
are obtained. The aim is to extract the correct value for
\(\phi _{i}\) from the knowledge of the evaluations
\(C_{i,\sigma }\) and
\(C_{i,\tau }\), particularly when
\((\sigma \Delta ) \max _{i=1, \ldots , n}\phi _{i} \ge \pi \) and the parameter
\(\phi _{i}\) cannot be obtained uniquely from
\(C_{i,\sigma }\) alone. We now discuss the unique identification of this parameter
\(\phi _{i}\) and in doing so we further drop the index
i. Let us denote
$$\begin{aligned} \begin{aligned} A_{\sigma } :=&{{\,\text{Arccos}\,}}(C_{\sigma }), \\ A_{\tau } :=&{{\,\text{Arccos}\,}}(C_{\tau }) \end{aligned} \end{aligned}$$
(34)
where
\({{\,\text{Arccos}\,}}(\cdot ) \in [0,\pi ]\) indicates the principal value of the inverse cosine function. Knowing that
\(0 \le A_\sigma , A_\tau \le \pi \) and that
\(0 \le \phi \sigma \Delta < \sigma \pi \), we find that all possible positive arguments
\(\phi \sigma \Delta \) of
\(C_\sigma \) are in
\(\mathcal{A}_{\sigma ,1} \cup \mathcal{A}_{\sigma ,2}\) with
$$\begin{aligned} \mathcal{A}_{\sigma ,1} :=&\{A_\sigma + 2\pi \ell \mid 0 \le \ell \le \lceil \sigma /2\rceil -1 \}, \\ \mathcal{A}_{\sigma ,2} :=&\{(2\pi -A_\sigma ){{\,\text{sgn}\,}}(A_\sigma ) + 2\pi \ell \mid 0 \le \ell \le \lceil \sigma /2\rceil -1 \}, \end{aligned}$$
where
\({{\,\text{sgn}\,}}(a_\sigma )=+1\) for
\(0<A_\sigma \le \pi \) and
\({{\,\text{sgn}\,}}(0)=0\). The set
\(\mathcal{A}_{\sigma ,1} \cup \mathcal{A}_{\sigma ,2}\) may even contain some candidate arguments of
\(C_\sigma \) that do not satisfy the bounds, but this does not create a problem in the identification of the correct
\(\phi <R\). Along the same lines, sets
\(\mathcal{A}_{\tau ,1}\) and
\(\mathcal{A}_{\tau ,2}\) can be constructed.
We further denote
$$\begin{aligned} \begin{aligned} \phi _{\sigma }&:= A_\sigma /(\sigma \Delta ) = {A_\sigma R \over \sigma \pi }, \\ \phi _{\tau }&:= A_\tau /(\tau \Delta ) = {A_\tau R \over \tau \pi }. \end{aligned} \end{aligned}$$
(35)
Then the possible solutions for
\(\phi \) to
\(C_\sigma =\cos (\phi \sigma \Delta )\) are in
\(\Phi _{\sigma ,1} \cup \Phi _{\sigma ,2}\) where
$$\begin{aligned} \Phi _{\sigma ,1} :=&\{\phi _\sigma + 2R \ell /\sigma \mid 0 \le \ell \le \lceil \sigma /2\rceil -1 \} \cap [0,R), \end{aligned}$$
(36)
$$\begin{aligned} \Phi _{\sigma ,2} :=&\{(2R/\sigma -\phi _\sigma ){{\,\text{sgn}\,}}(\phi _\sigma ) + 2R \ell /\sigma \mid 0 \le \ell \le \lceil \sigma /2\rceil -1 \} \cap [0,R). \end{aligned}$$
(37)
Analogously, the possible solutions to
\(C_\tau =\cos (\phi \tau \Delta )\) are in
\(\Phi _{\tau ,1} \cup \Phi _{\tau ,2}\) where
$$\begin{aligned} \Phi _{\tau ,1} :=&\{\phi _\tau + 2R \ell /\tau \mid 0 \le \ell \le \lceil \tau /2\rceil -1 \} \cap [0,R), \end{aligned}$$
(38)
$$\begin{aligned} \Phi _{\tau ,2} :=&\{(2R/\tau -\phi _\tau ){{\,\text{sgn}\,}}(\phi _\tau ) + 2R \ell /\tau \mid 0 \le \ell \le \lceil \tau /2\rceil -1 \} \cap [0,R). \end{aligned}$$
(39)
One statement is obvious: whatever the choice for
\(\sigma \) and
\(\tau \), both
\(\Phi _{\sigma ,1} \cup \Phi _{\sigma ,2}\) and
\(\Phi _{\tau ,1} \cup \Phi _{\tau ,2}\) contain the unknown value for
\(\phi \) which produced
\(C_\sigma \) and
\(C_\tau \). What remains open is the question whether
\(\left( \Phi _{\sigma ,1}\cup \Phi _{\sigma ,2} \right) \cap \left( \Phi _{\sigma ,1}\cup \Phi _{\sigma ,2} \right) \) is a singleton. And in case it is not, we want to find an algorithm that can identify the correct
\(\phi \).
When either \(\phi _\sigma =0\) or \(\phi _\sigma = R/\sigma \) the sets \(\Phi _{\sigma ,1}\) and \(\Phi _{\sigma ,2}\) coincide. And similarly for \(\phi _\tau \). On the other hand, if these sets do not coincide, they are disjoint. So the true value for the unknown parameter \(\phi \) can belong to any of the intersections \(\Phi _{\sigma ,1} \cap \Phi _{\tau ,1}, \Phi _{\sigma ,1} \cap \Phi _{\tau ,2}, \Phi _{\sigma ,2} \cap \Phi _{\tau ,1}, \Phi _{\sigma ,2} \cap \Phi _{\tau ,2}\). A sequence of lemmas will lead to the conclusion that the four intersections do not deliver more than two distinct elements. Thereafter we indicate how to identify the only true value for the unkown \(\phi \).
When the sets \(\Phi _{\sigma ,1}\) and \(\Phi _{\sigma ,2}\) coincide and the sets \(\Phi _{\tau ,1}\) and \(\Phi _{\tau ,2}\) do as well, then that unique intersection is \(\phi =\phi _\sigma =\phi _\tau =0\). Because \(\gcd (\sigma ,\tau )=1\), other common elements coming from either \(\phi _\sigma =2R/\sigma \) or \(\phi _\tau =2R/\tau \) cannot exist.
We now continue with the situation where either the sets in (
36) and (
37) or the sets in (
38) and (
39) do not coincide, so that there are always at least 3 distinct sets in the running. Without loss of generality, we assume that a common element belongs to
\(\Phi _{\sigma ,1} \cap \Phi _{\tau ,1}\) and we build our reasoning from there.
While, assuming \(\Phi _{\sigma ,1}\cap \Phi _{\tau ,1} \not = \emptyset \), we have seen in Lemma 1 that this intersection is a singleton, and we have seen in Lemma 2 that then \(\Phi _{\sigma ,2}\cap \Phi _{\tau ,2} = \emptyset \), we know nothing so far about the other two intersections \(\Phi _{\sigma ,1}\cap \Phi _{\tau ,2}\) and \(\Phi _{\sigma ,2}\cap \Phi _{\tau ,1}\).
We have built our sequence of proofs from Lemma 2 on, without loss of generality, on the fact that \(\Phi _{\sigma , 1} \cap \Phi _{\tau ,1} \not = \emptyset \) and the fact that \(\Phi _{\sigma ,1}\) and \(\Phi _{\sigma ,2}\) on the one hand and \(\Phi _{\tau ,1}\) and \(\Phi _{\tau ,2}\) on the other do not collide at the same time. Finally, from Lemma 3 we know that (\(\Phi _{\sigma ,1}\cap \Phi _{\tau ,1} \not = \emptyset \) and \(\Phi _{\sigma ,2}\cap \Phi _{\tau ,1} \not = \emptyset \)) or (\(\Phi _{\sigma ,1}\cap \Phi _{\tau ,1} \not = \emptyset \) and \(\Phi _{\sigma ,1}\cap \Phi _{\tau ,2} \not = \emptyset \)) cannot occur concurrently, but either one of these cases remains possible.
In general, when at least 3 of the 4 sets
\(\Phi _{\sigma , 1}, \Phi _{\sigma , 2}, \Phi _{\tau ,1}, \Phi _{\tau ,2}\) are distinct, then at most 2 of the 4 intersections
$$\Phi _{\sigma ,i} \cap \Phi _{\tau ,j}, \qquad 1 \le i,j \le 2$$
are nonempty, with each of the nonempty intersections being a singleton. Further down we illustrate the actual existence of a case, where two intersections are nonempty and consequently the true value of the unknown
\(\phi \) cannot be identified from the evaluations
\(\cos (\phi \sigma \Delta )\) and
\(\cos (\phi \tau \Delta )\) with
\(\gcd (\sigma ,\tau )=1\).
In this case we need to collect a third value
\(C_\rho :=\cos (\phi \rho \Delta )\) with
\(\gcd (\sigma ,\rho )=1\) and
\(\gcd (\tau ,\rho )=1\). With
\(A_\rho \) and
\(\phi _\rho \) defined as in (
34) and (
35), and
\(\Phi _{\rho ,1}\) and
\(\Phi _{\rho ,2}\) defined as in (
36) and (
37), we know, as before, that
\(\Phi _{\rho ,1}\cup \Phi _{\rho ,2}\) contains the correct value for
\(\phi \). We also know, because of the remark formulated after the proof of Lemma 1, that at least 5 of the 6 involved sets
\({\Phi }_{\sigma ,1}, {\Phi }_{\sigma ,2}, {\Phi }_{\tau ,1}, {\Phi }_{\tau ,2}, {\Phi }_{\rho ,1}, {\Phi }_{\rho ,2}\) are distinct unless
\(\phi =0\).
We now inspect
$$\begin{aligned} \begin{aligned} \left[ \cup _{i, j=1}^2 \left( \Phi _{\sigma , i} \cap \Phi _{\tau , j} \right) \right]&\cap \left( \Phi _{\rho ,1} \cup \Phi _{\rho ,2} \right) \\&= \left( \cup _{k=1}^2 \Phi _{\sigma , i_1} \cap \Phi _{\tau ,j_1} \cap \Phi _{\rho ,k} \right) \\&\cup \left( \cup _{k=1}^2 \Phi _{\sigma , i_2} \cap \Phi _{\tau ,j_2} \cap \Phi _{\rho ,k} \right) \end{aligned} \end{aligned}$$
(40)
where
\(i_1, j_1, i_2, j_2\) index the subsets that produce the nonempty intersections of the relatively prime pair
\(\sigma \) and
\(\tau \), with either
\(i_1 \not = i_2\) or
\(j_1 \not = j_2\) but not both. We have built our sequence of proofs, without loss of generality, on the fact that
\(i_1=1, j_1=1\) and have found that it is then possible that
\(i_2=2, j_2=1\). We now continue the proofs from that case and inspect the 4 new intersections in (
40).
As a consequence of the Lemmas 4 and 5, the unique true
\(\phi \) is identified in
$$\Phi _{\sigma ,1}\cap \Phi _{\tau ,1}\cap \Phi _{\rho ,1} \text { or } \Phi _{\sigma ,2}\cap \Phi _{\tau ,1}\cap \Phi _{\rho ,2}.$$
So the unknown parameter
\(\phi \) is identified uniquely from at most 3 values
\(C_\sigma , C_\tau , C_\rho \) with
\(\sigma , \tau , \rho \) all mutually prime. An easy choice for
\(\rho \) is
\(\rho =\sigma +\tau \) as this minimizes the number of additional samples as explained in Section
3, and also
\(\gcd (\sigma ,\sigma +\tau )=1=\gcd (\tau ,\sigma +\tau )\) when
\(\gcd (\sigma ,\tau )=1\).
As promised, we show an example where
\(\Phi _{\sigma ,1}\cap \Phi _{\tau ,1} \not = \emptyset \) and
\(\Phi _{\sigma ,2}\cap \Phi _{\tau ,1} \not = \emptyset \). Consider
\(\phi =70800/1547 < 1000=R\) with
\(\Delta =\pi /R\). Choose
\(\sigma =299\) and
\(\tau =357\) with
\(\gcd (\sigma ,\tau )=1\). With
$$\phi _\sigma =100000/35581, \qquad \ell =68 \le \lceil \sigma /2 \rceil -1 = 149,$$
we have
\(\phi \in \Phi _{\sigma ,1}\). With
$$\phi _\tau =6000/1547, \qquad \ell = 81 \le \lceil \tau /2 \rceil -1 = 178,$$
we find
\(\phi \in \Phi _{\tau ,1}\). Unfortunately, since
\(\phi _\tau = 2R/\sigma -\phi _\sigma \) we also have
\(\phi _\tau \in \Phi _{\sigma ,2}\cap \Phi _{\tau ,1} \not = \emptyset \).
As a last remark, we add that even replacing (
13) by the stricter constraint
$$|\phi _{i}|\Delta <\pi /2, \qquad i=1, \ldots , n$$
does not guarantee that each
\(\phi \) can be identified from only
\(C_\sigma \) and
\(C_\tau \). We illustrate this with a counterexample. Let
\(\phi =3300/133 < 50=R\) with
\(\Delta = \pi /(2R)\). With
\(\sigma =21\) and
\(\tau =19\) we find
$$\begin{aligned}\begin{gathered} \phi _\sigma =500/133, \qquad (2\pi )/(\sigma \Delta )-\phi _\sigma =2300/399, \\ \phi _\tau =500/133, \qquad (2\pi )/(\tau \Delta )-\phi _\tau =900/133. \end{gathered}\end{aligned}$$
This leads to
\(\Phi _{\sigma ,1}\cap \Phi _{\tau ,1} = \{500/133\}\) and
\(\Phi _{\sigma ,2}\cap \Phi _{\tau ,1} = \{3300/133\}\).