How many Fourier samples are needed for real function reconstruction?

Let −∞<T ₁<T ₂<⋯<T _N+1<∞ and let \(c_{j}^{1}\in \mathbb {R}\) for j=1,…,N with \(c_{j}^{1}\neq c_{j+1}^{1}\) for j=1,…,N−1. Assume that the constant h>0 satisfies hT _j ∈[−π,π) for j=1,…,N+1. Then the function f in (3.1) can be completely recovered by the N+1 Fourier samples \(\widehat{f}(\ell h), \ell =1,\ldots,N+1\).

We observe from (3.1) that for ω≠0 with \(c_{j}^{0}:=c_{j}^{1}-c_{j-1}^{1}\), and with the convention that \(c_{0}^{1}=c_{N+1}^{1}=0\). Observe that \(c_{j}^{0}\neq0\) by assumption. Hence, and we can apply the Prony method described in Sect. 2 to \(P(\omega):=(\mathrm {i}\omega)\widehat{f}(\omega)\), where we use the known values In this way, we determine all values T ₁,…,T _N+1 and the corresponding coefficients \(c_{j}^{0}, j=1,\ldots,N+1\), uniquely. Finally, the coefficients \(c_{j}^{1}\) are obtained using the recursion  □

Suppose that there exist a knot sequence −∞<T ₁<T ₂<⋯<T _N+m <∞ and values \(c_{j}^{m}\in \mathbb {R}\), j=1,…,N. Assume that the constant h>0 satisfies hT _j ∈[−π,π) for all j=1,…,N+m. Then the spline function f in (3.2) can be completely recovered by the N+m Fourier samples \(\widehat{f}(\ell h)\), ℓ=1,…,N+m.

As shown above, the Fourier transform of the m-th derivative of f is of the form (3.6), and supposing that \(c_{j}^{0}\neq0\) for j=1,…,N+m, we can compute the knots T _j and the coefficients \(c_{j}^{0}\) for j=1,…,N+m uniquely by applying the Prony method given in Sect. 2 to \(P(\omega) = (\mathrm {i}\omega)^{m} \widehat{f}(\omega)\). Further, applying the formulas (3.3) and (3.5) together with (3.4), we obtain the following recursion to compute the coefficients \(c_{j}^{m}\),  □

1. The above proof of Theorem 3.2 is constructive. In particular, if N is not known, but we have an upper bound M≥N, then the Prony method will also find the correct knots T _j and the corresponding coefficients \(c_{j}^{0}\) from M+m Fourier samples, and the numerical procedure will be more stable, see e.g. [9, 14, 15].

2. In the above proof we rely upon the fact that \(c_{j}^{0}\neq0\) for j=1,…,N+m. If we have the situation that \(c_{j_{0}}^{0}=0\) for an index j ₀∈{1,…,N+m}, then we will not be able to reconstruct the knot \(T_{j_{0}}\). But this situation will only occur if the representation of f in (3.2) is redundant, i.e., if f in (3.2) can be represented by less than N summands, so we will still be able to recover the exact function f. Observe that the above recovery procedure always results in the simplest representation of f so that the reconstructed representation of f of the form (3.2) does not possess redundant terms.

3. Considering the non-linear problem to approximate a continuous univariate function f from given samples by a spline function with free knots, one wants to find optimal knots as well as optimal coefficients of the B-spline expansion f in (3.2) such that g−f is small in a given norm. This problem is very challenging but of high interest for sparse signal approximation. While the above Theorems 3.1 and 3.2 yield a reconstruction of spline functions with free knots from Fourier samples, the above problem uses sampling values of g itself. The question whether Prony-like methods may be helpful to solve this non-linear approximation problem will be subject of our further research.

Let −∞<T ₁<⋯<T _N <∞ be a real sequence and c _j ∈ℝ∖{0} for j=1,…,N. Further, let Φ∈C(ℝ)∩L ₁(ℝ) be a given function with \(|\widehat{\varPhi}(\omega)| >C_{0}\) for all ω∈(−T,T) and some C ₀>0. Let h>0 be a constant satisfying |hT _j |<min{π,T} for all j=1,…,N. Then the function f of the form (3.7) can be uniquely recovered by the Fourier samples \(\widehat{f}(\ell h)\), ℓ=0,…,N.

Using the assumption on \(\widehat{\varPhi}\) we find from (3.8) and hence we can compute all T _j and c _j by Prony’s method given in Sect. 2. □

Let −∞<T ₁<⋯<T _N <∞ be a real sequence and c _j,r ∈ℝ for j=1,…,N, r=0,…,R−1, where we assume that \(\sum_{r=0}^{R-1} |c_{j,r}| >0\), i.e., the coefficients c _j,r corresponding to one frequency T _j do not all vanish at the same time. Further, let Φ∈C(ℝ)∩L ₁(ℝ) be a given function with \(|\widehat{\varPhi}(\omega)| >C_{0}\) for all ω∈(−T,T) and some C ₀>0. Let h>0 be a constant satisfying |hT _j |<min{π,T} for all j=1,…,N. Then the function f in (3.9) can be uniquely recovered by the Fourier samples \(\widehat{f}(\ell h)\), ℓ=0,…,NR.

Regarding (3.10), we now want to apply Prony’s method to a function of the form and this function structure is different from (2.1) for R>1. We remark that functions Q(ω) of the above form are called extended exponential sums, see [2, p. 169]. We consider now the polynomial with unknown shifts T _j . Then we observe that for m=0,…,NR Using the notation \(S_{\nu} := \sum_{\ell=0}^{NR}\lambda_{\ell} \ell^{\nu} \mathrm {e}^{-\mathrm {i}h\ell T_{j}}\), we observe that S _ν can be written as a linear combination of the derivatives \(\varLambda^{(\mu)}(z)= \sum_{\ell=\mu}^{NR} \lambda_{\ell} \frac{\ell!}{(\ell- \mu) !} z^{\ell- \mu}\), μ=0,…,ν, i.e., there exist coefficients \(\alpha_{\mu}^{\nu}\in \mathbb {N}\) so that and because of \(\varLambda^{(\mu)}(\mathrm {e}^{-\mathrm {i}hT_{j}})=0\) for μ=0,…,R−1 we finally get Hence, the coefficient vector λ=(λ ₀,…,λ _NR ) ^T with λ _NR =1 is a zero-eigenvector of the Toeplitz matrix Observe that all entries of T _NR+1 are given, since we have \(Q(-\omega)=\overline{Q(\omega)}\) and Q(0)=0. The method now applies along the same lines as given in Sect. 2. □

1. The special functions f regarded in Sects. 3.1–3.3 are so-called functions of finite rate of innovation, as introduced for example in [21].

2. Similarly as in (3.9) we can also generalize the method to sums of B-splines and their derivatives, i.e., we can consider non-uniform translates of B-splines of different order, and f(x) can be recovered by the Fourier samples \(\widehat{f}(\ell h)\), ℓ=1,…,(N+m)m.

Let m ₁,m ₂∈ℕ be given integers, and let f be a bivariate spline function of the form (4.1) with knot sequences \(-\infty<T_{1}<\cdots<T_{N_{1}+m_{1}}<\infty\) and \(-\infty <S_{1}<\cdots<S_{N_{2}+m_{2}}<\infty\), and with real coefficients c _j,k ,j=1,…,N ₁, k=1,…,N ₂. Let h ₁ and h ₂ be two positive constants satisfying |h ₁ T _j |<π for all j=1,…,N ₁+m ₁ and |h ₂ S _k |<π for all k=1,…,N ₂+m ₂. Then f can be uniquely recovered by the (N ₁+m ₁)⋅(N ₂+m ₂) Fourier samples \(\widehat{f}(\mu h_{1},\nu h_{2})\), μ=1,…,N ₁+m ₁, ν=1,…,N ₂+m ₂.

Set \(p_{j}(\omega_{2}):=\sum_{k=1}^{N_{2}+m_{2}}c_{j,k}^{0,0}\mathrm {e}^{-\mathrm {i}\omega_{2} S_{k}}\). Then the equality (4.2) reads Fixing ω ₂:=h ₂, we apply Prony’s method from Sect. 2 to the function and obtain the knot sequence \(T_{1},\ldots,T_{N_{1}+m_{1}}\) as well as the coefficients p _j (h ₂), j=1,…,N ₁+m ₁, using the Fourier samples \(\widehat{f}(\mu h_{1},h_{2})\), μ=1,…,N ₁+m ₁. In the unlucky case that not all values p _j (h ₂), j=1,…,N ₁+m ₁ are non-zero, we do not find all values T _j by this procedure and have to repeat the method for ω ₂=2h ₂,3h ₂,… etc. in order to complete the knot sequence {T _j , j=1,…,N ₁+m ₁}.

Next, knowing the T _j , we compute all further coefficients p _j (νh ₂), j=1,…,N ₁+m ₁, ν=2,…,N ₂+m ₂, from the Fourier samples \(\widehat{f}(\mu h_{1},\nu h_{2})\), μ=1,…,N ₁+m ₁, ν=2,…,N ₂+m ₂, using (4.3). Afterwards, we apply the Prony method to and use p ₁(h ₂),…,p ₁((N ₂+m ₂)h ₂) in order to determine the knot sequence S ₁,… , \(S_{N_{2}+m_{2}}\) and the coefficients \(c_{1,k}^{0,0}\), k=1,…,N ₂+m ₂, uniquely. Again, in case that \(c_{1,k}^{0,0}=0\) for some k∈{1,…,N ₂+m ₂} we do not obtain all S _k and need to apply Prony’s method also to p _j (ω ₂) for j>1 in order to complete the knot sequence {S _k , k=1,…,N ₂+m ₂}.

All further coefficients \(c_{j,k}^{0,0}\) are obtained from the linear systems for each j=2,3,…,N ₁+m ₁. Finally, we have to evaluate the original coefficients \(c_{j,k}^{m_{1},m_{2}}\) from \(c_{j,k}^{0,0}\) using the recursions where r ₂=0,…,m ₂, k=1,…,N ₂+m ₂−r ₂, and where r ₁=0,…,m ₁, j=1,…,N ₁+m ₁−r ₁. □

1. Observe that in the tensor product case we usually need to apply the Prony method only twice in order to obtain the two knot sequences \(\{ T_{j}\}_{j=1,\ldots,N_{1}+m_{1}}\) and \(\{S_{k}\}_{k=1,\ldots,N_{2}+m_{2}}\). All coefficients \(c_{j,k}^{0,0}\) can afterwards be computed by a linear system of equations. As in the univariate case, the problem of vanishing terms p _j (kh ₂) or vanishing coefficients \(c_{j,k}^{0,0}\) only occurs if the function f in (4.1) contains local redundancies.

2. A tensor product of the form with two low-pass filter functions Φ ₁ and Φ ₂ satisfying \(\widehat{\varPhi}_{\nu}(\omega)\neq0\) for ω∈(−T,T) for some T>0 (ν=1,2) can be similarly handled by generalizing the results of Sect. 3.3. Fourier transform of (4.4) yields Hence, for given functions Φ ₁,Φ ₂ we can recover f completely using the Fourier samples \(\widehat{f}(\ell_{1} h_{1},\ell_{2} h_{2})\), ℓ ₁=0,…,N ₁, ℓ ₂=0,…,N ₂ by following the same lines as in the proof of Theorem 4.1. Here, h ₁,h ₂ have to satisfy |h ₁ T _j |<min{π,T} and |h ₂ S _k |<min{π,T} for all j=1,…,N ₁, k=1,…,N ₂.

Let Φ∈C(ℝ²)∩L ¹(ℝ²) be a given, real, bivariate function with \(|\widehat{\varPhi}(\omega_{1},\omega_{2})| > C_{0} >0\) for ∥ω∥₂<T for some T>0. Further, let f be a bivariate function with the sparse representation (4.5), where c _j ,v _j,1,v _j,2, j=1,…,N, are real numbers and c _j >0 for j=1,…,N. Assume that the constant h>0 satisfies h∥v _j ∥₂<min{π,T} with \(\Vert\mathbf{v}_{j}\Vert_{2}:=(v_{j,1}^{2}+v_{j,2}^{2})^{\frac {1}{2}}\) for j=1,…,N. Then f can be uniquely recovered from the set of 3N+1 Fourier samples given by where \(\alpha\in(0,\, 1 ) \setminus\{\frac{1}{2} \}\) needs to be chosen suitably.

We give a constructive proof. From (4.6) we obtain for ω ₂=0 However, we are faced with the problem that two or more shifts v _j =(v _j,1,v _j,2) may possess the same first coordinate. Let us assume that the wanted set {v _1,1,…,v _N,1} of first coordinates contains N ₁≤N distinct values \(\widetilde {v}_{1,1},\ldots,\widetilde{v}_{N_{1},1}\). Then we find where for the true first coordinates of the wanted shifts it follows that \({v}_{j,1}\in\widetilde{V}_{1}:=\{\widetilde{v}_{1,1},\ldots ,\widetilde{v}_{N_{1},1}\}\) for each j=1,…,N, and where \(c_{k}^{1}\) is the sum of all coefficients belonging to shift vectors with the same first coordinate \(\widetilde{v}_{k,1}\), Observe that \(c_{k}^{1}>0\) for all k=1,…,N ₁, since we consider only the case c _j >0 for all j=1,…,N. Applying Prony’s method in Sect. 2 to (4.7) using the Fourier samples \(\widehat{f}(\ell h,0)\), ℓ=0,…,N, provides us the values \(\widetilde{v}_{1,1},\ldots ,\widetilde{v}_{N_{1},1}\) and the corresponding coefficients \(c_{k}^{1}\), k=1,…,N ₁.

Analogously, we observe from (4.6) with ω ₁=0 that where \(\widetilde{v}_{k,2}\) are the distinct values of the set {v _1,2,…,v _N,2} and \(c_{k}^{2}\) are the corresponding coefficients for k=1,…,N ₂, N ₂≤N. The values \(\widetilde {v}_{k,2}\), \(c_{k}^{2}\), k=1,…,N ₂, are computed by Prony’s method from the samples \(\widehat{f}(0,\ell h)\), ℓ=0,…,N.

Hence, the true shift vectors v _j have to be contained in the set where \(\widetilde{V}_{\nu}:=\{\widetilde{v}_{k,\nu}: k=1,\ldots,N_{\nu }\}\), ν=1,2. In order to find the true shift vectors v _j we now determine an angle απ, such that the orthogonal projections of all v∈G onto the line y=tan(απ)x are distinct, i.e. that (cosαπ)v ₁+(sinαπ)v ₂ are distinct for all v∈G. Since G contains N ₁ N ₂≤N ² entries, such a number \(\alpha\in(0, \, 1) \setminus\{\frac{1}{2}\}\) can always be found.

Now, we consider where \(\widetilde{v}_{k,3}\), k=1,…,N ₃ with N ₃≤N are the distinct values of the set {v _j,1cos(απ)+v _j,2sin(απ): j=1,…,N}. However, the construction of α yields that N ₃=N since all possible shift vectors yield different projections onto the third line y=tan(απ)x.

Let \(\widetilde{V}_{3}:=\{\widetilde{v}_{k,3}: k=1,\ldots,N\}\) be the set of distinct frequencies, and let \(c_{k}^{3}\) be the corresponding coefficients obtained by applying the Prony method to the samples \(\widehat{f}( \cos(\alpha\pi)\ell h,\sin(\alpha\pi)\ell h)\), ℓ=0,…,N. Hence, the point set contains now only the N wanted shifts v _j , and the corresponding coefficients c _j are given by the set \(\{ c_{j}^{3}, \ j=1, \ldots, N \}\). □

1. In the reconstruction scheme given in Theorem 4.3, the angle α of the third line of Fourier samples has to be taken dependently on the set G, i.e., dependently on the candidates for shifts in G found from the first two lines. For practical purposes it would be of great interest to compute the wanted shifts and coefficients of f in (4.5) from given Fourier samples taken beforehand independently from the shifts in f. In fact, for most practical cases, the consideration of the point set \(\widetilde{G}\) (with a priori given angle απ) already yields a sufficiently small set of candidates, such that the true shifts can be found using the N ₁+N ₂+N ₃ conditions of the form (4.8) (or similar to (4.8)) for the coefficients. However, counterexamples can be found for certain sets of shifts with special symmetry properties, where a complete reconstruction of f is not possible. We conjecture that the set of Fourier samples on four lines of the form where α satisfies \(\tan(\alpha\pi) \neq\frac{1}{n}\) for n∈ℕ, always suffices for a unique reconstruction of f. Here, we consider the Fourier samples on four lines where the first two lines are orthogonal and the last two are also orthogonal. In this case, the true shift vectors v _j have to be contained in the set where \(\widetilde{V}_{\nu}:=\{\widetilde{v}_{k,\nu}: k=1,\ldots,N_{\nu }\}\), ν=1,2,3,4. Moreover, the Prony method provides N ₁+N ₂+N ₃+N ₄ conditions for the coefficients of the form (4.8) (or similar to (4.8)) that can be applied for determining all true shifts of f.

2. The considered idea of function reconstruction can also be generalized to d-variate functions (d>2).