1 Introduction

The reconstruction of structured functions from the knowledge of samples of its Fourier transform is a common problem in several scientific areas as radioastronomy, computed tomography and magnet resonance imaging, [1]. In this paper, we aim to recover specially structured functions uniquely from the smallest possible number of equidistantly distributed Fourier samples.

Within the last years, there has been an increasing interest in exploiting special properties of functions that have to be reconstructed. Usually, the central issue is the recovery of signals possessing a sparse representation in a given basis or frame from a rather small set of determining points. Particularly, compressive sensing has triggered significant research activity. For example, a trigonometric polynomial of degree N with only s≪N active terms has been shown to be recovered by \(\mathcal{O}(s \log^{4}(N))\) sampling points that are randomly chosen from a discrete set \(\{ j/N \}_{j=0}^{N-1}\), [5], or from the uniform measure on [0,1], [17]. The recovery algorithms in compressed sensing are usually based on suitable l 1-minimization methods, and exact recovery can be ensured only with a certain probability. In contrast, there exist also deterministic methods for the recovery of sparse trigonometric functions, based on the classical Prony method or the annihilating filter method, [7, 21].

In [15] and [14], the so-called approximate Prony method has been studied, and a stable algorithm was derived that works also for noisy input data while the original Prony method suffers from its numerical instabilities. Other modifications of the Prony method aiming at a more stable behavior are e.g. the Least-Squares Prony method [10], the Total-Least-Squares Prony method [10], pencil based methods [11, 12, 18] and the method in [3] using an iterative quadratic maximum likelihood approach. In [8], a pencil based approach for Prony’s method is combined with a maximum a posteriori probability estimator for stable recovery of polygon shapes from moments. In [9], a stabilization of Prony’s method is proposed, where instead of using the (perturbed) Fourier samples directly, a windowed average of their autocorrelation sequence is applied. The unknown frequency parameters are then obtained as the zeros of a suitably defined orthogonal polynomial.

Vetterli et al. [21] introduced signals with finite rate of innovation, i.e., signals with special structure having a finite number of degrees of freedom per unit of time. Using the annihilating filter method (that is equivalent to Prony’s method) they showed that finite length signals with finite rate of innovation can be completely reconstructed using a generalized Shannon sampling theorem although these signals are not bandlimited.

In the present paper, we apply the Prony method for the reconstruction of real structured functions from a small number of equidistantly distributed Fourier samples. Here, the Fourier transform \(\widehat{f}\) of a function f∈L 1(ℝd) is defined by \(\widehat{f}(\omega)=\int_{\mbox {\scriptsize $\mathbb{R}$}^{d}} f(x)\mathrm {e}^{-\mathrm {i}\omega\boldsymbol{\cdot}x}\,\mathrm{d}x\). In the univariate case, we particularly consider B-spline functions with non-uniform knots and linear combinations of non-equispaced shifts of a known “low-pass” function Φ satisfying \(\widehat{\varPhi}(\omega) \neq0\) for ω∈(−T,T), where T>0.

In the bivariate case, we want to recover the functions from only a small amount of Fourier samples on different lines through the origin. In case of separable functions as tensor products of non-uniform B-spline functions the recovery problem can be treated similarly as in the univariate case. For the non-separable case the problem is more involved. In [13], the so-called algebraic coupling of matrix pencils (ACMP) algorithm is used for recovery of bivariate exponentials, where \(\mathcal{O}(N^{2})\) samples are needed to recover a series of the form \(\sum_{k=1}^{N} a_{k} \exp(\mathrm {i}\omega_{1}T_{k}) \exp(\mathrm {i}\omega_{2}S_{k})\), see also [19, 20].

We will study linear combinations of non-uniform shifts of bivariate functions Φ of the form \(f(x_{1},x_{2})=\sum_{j=1}^{N}c_{j}\varPhi(x_{1}-v_{j,1},x_{2}-v_{j,2})\) with unknowns c j >0, v j,1, v j,2, j=1,…,N, and where \(\widehat{\varPhi}(\omega_{1}, \omega_{2})\) is bounded away from zero for \(\omega_{1}^{2}+ \omega_{2}^{2} < T^{2}\) and T>0. We show that function recovery is possible using 3N+1 Fourier samples on only three lines through the origin, where the third line is chosen dependently on the candidates for shifts found from the first two lines.

Moreover, we conjecture that one can always reconstruct the function f from 4N+1 Fourier samples given on four predetermined lines whose choice does not depend on the data. The idea of our method is related to a recent preprint, [16], where the authors propose to take sufficiently many lines for complete recovery of multivariate exponentials.

The paper is organized as follows. In Sect. 2, we shortly summarize the Prony method that will be frequently used in the remaining paper. Section 3 is devoted to univariate function recovery. We start with real step functions with compact support of the form \(f(x)=\sum_{j=1}^{N}c_{j}^{1}\mathbf{1}_{[T_{j},T_{j+1})}(x)\) with arbitrary knots T 1,…,T N+1, and show that f can be recovered by N+1 Fourier samples. The method transfers to non-uniform B-spline functions in Sect. 3.2. Moreover, we consider the reconstruction of linear combinations of non-uniform shifts of a given low-pass function Φ and its derivatives in Sect. 3.3. In Sect. 4, we study the bivariate case. We start with tensor-products of non-uniform spline functions. The non-separable case of non-uniform translates of a suitable bivariate function Φ is considered in Sect. 4.2. All recovery results are constructive. In Sect. 5 we present some numerical examples for the univariate and the bivariate case showing that the algorithms are stable for exact input data.

2 Prony method

Consider a function P(ω) of the special form

$$ P(\omega)=\sum_{j=1}^N c_j\mathrm {e}^{-\mathrm {i}\omega T_j} $$
(2.1)

with non-zero coefficients c j ∈ℝ and real frequencies T 1<T 2<⋯<T N .

We want to evaluate all frequencies T 1,…,T N and all coefficients c j , j=1,…,N, from the function values P(ℓh), ℓ=0,…,N, where h is assumed to be a positive constant with hT j ∈[−π,π) for all j∈{1,…,N}. For this purpose, the Prony method can be applied as follows.

Let us consider the complex polynomial Λ:ℂ→ℂ,

$$ \varLambda(z):=\prod_{j=1}^N \bigl(z-\mathrm {e}^{-\mathrm {i}hT_j} \bigr)=\sum_{\ell=0}^N \lambda_{\ell} z^{\ell} $$
(2.2)

with the unknown frequencies T j from (2.1), where λ ℓ are the coefficients of Λ in the monomial basis. Particularly, we have λ N =1.

Then we observe that for m=0,…,N,

Hence, the coefficient vector λ=(λ 0,…,λ N )T is the solution of the linear system

$$ \mathbf{T}_{N+1}\boldsymbol{\lambda}=\mathbf{0} $$
(2.3)

with the Toeplitz matrix \(\mathbf{T}_{N+1}:=(P(h(\ell-m)))_{m,\ell =0}^{N}\in \mathbb {R}^{(N+1)\times(N+1)}\). Observe that by \(P(-\omega)=\sum_{j=1}^{N}c_{j}\mathrm {e}^{\mathrm {i}\omega T_{j}}=\overline{P(\omega)}\) all entries of T N+1 are given. With the Vandermonde matrix \(\mathbf{V}_{N,N+1}:= (\exp(-\mathrm {i}h k T_{j}) )_{j=1,k=0}^{N}\) we have

$$\mathbf{T}_{N+1}=\mathbf{V}_{N,N+1}^*\operatorname{diag}(c_1,c_2, \ldots ,c_N)\mathbf{V}_{N,N+1}. $$

Since V N,N+1 has rank N, and c j ≠0 for j=1,…,N, we get \(\operatorname{rank}(\mathbf{T}_{N+1})=N\). Hence, the eigenvector λ of T N+1 corresponding to the eigenvalue 0 is uniquely determined by (2.3) and λ N =1.

Knowing λ, we can compute the zeros \(z_{j}:=\mathrm{e}^{-\mathrm {i}hT_{j}}\) (j=1,…,N) of the polynomial Λ and hence find the frequencies T 1,…,T N .

Finally, the coefficients c j , j=1,…,N are obtained from the linear system

$$P(\ell h)=\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\ell hT_j}, \quad\ell=0,\ldots,N. $$

We summarize the algorithm as follows.

Algorithm 2.1

Input: P(ℓh), ℓ=0,…,N, step size h.

  1. 1.

    Form the Toeplitz matrix \(\mathbf{T}_{N+1}=(P(h(\ell-m)))_{m,\ell =0}^{N}\in \mathbb {R}^{(N+1)\times(N+1)}\) using that \(P(-\ell h) = \overline {P(\ell h)}\).

  2. 2.

    Solve the system T N+1 λ=0, where λ N =1.

  3. 3.

    Compute the zeros of the polynomial \(\varLambda(z) = \sum_{\ell =0}^{N} \lambda_{\ell} z^{\ell}\) on the unit circle and extract the frequencies T j from the zeros \(z_{j}= \mathrm{e}^{- \mathrm {i}hT_{j}}\), j=1,…,N.

  4. 4.

    Compute the coefficients c j from the system \(P(\ell h)=\sum_{j=1}^{N}c_{j}\mathrm {e}^{-\mathrm {i}\ell hT_{j}}\), ℓ=0,…,N.

Output: Frequencies T j and coefficients c j , j=1,…,N, determining P(ω) in (2.1).

The procedure is not numerically stable with respect to inexact Fourier measurements. For improving the stability of the Prony method we refer to the ESPRIT method [18], the matrix pencil method [12] and the approximate Prony method [9, 15].

Remarks 2.2

1. For a unique computation of the knots T j we need to ensure that hT j ∈[−π,π), since e−iω is 2π-periodic. Otherwise, we will not be able to extract the values T j from the zeros \(z_{j}=\mathrm{e}^{-\mathrm {i}hT_{j}}\) of Λ on the unit circle uniquely.

2. While the frequencies T j are not known, one only needs to find a suitable upper bound for |T j | in order to fix a suitable step size h.

3. In applications, also the number N of terms in (2.1) is usually unknown. Having given at least an upper bound M≥N and M+1 function values P(ℓh), ℓ=0,…,M, one can also apply the above procedure (replacing N by M) and obtains N by examining \(\operatorname{rank}(\mathbf{T}_{M+1})\). In this case, (2.3) cannot longer be solved uniquely, but each zero-eigenvector will serve for the determination of the zeros of Λ on the unit circle and hence of T j , j=1,…,N, see e.g. [15].

3 Recovery of special univariate functions

3.1 Step functions

Let us consider a piecewise step function with compact support of the form

$$ f(x)=\sum_{j=1}^Nc_j^1 \, \mathbf{1}_{[T_j,T_{j+1})}(x), $$
(3.1)

where 1 [a,b) denotes the characteristic function of the interval [a,b), and \(c_{j}^{1}\) are real coefficients with \(c_{j}^{1}\neq c_{j+1}^{1}\) for all j∈{1,…,N−1}.

We want to answer the question, how many Fourier samples are needed to recover the function f.

Theorem 3.1

Let −∞<T 1<T 2<⋯<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\).

Proof

We observe from (3.1) that for ω≠0

$$ \widehat{f}(\omega)=\sum_{j=1}^N \frac{c_j^1}{\mathrm {i}\omega} \bigl(\mathrm {e}^{-\mathrm {i}\omega T_j}-\mathrm {e}^{-\mathrm {i}\omega T_{j+1}} \bigr)= \frac{1}{\mathrm {i}\omega} \sum_{j=1}^{N+1} c_j^0 \mathrm {e}^{-\mathrm {i}\omega T_j} $$

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,

$$(\mathrm {i}\omega)\widehat{f}(\omega)=\sum_{j=1}^{N+1}c_j^0 \mathrm {e}^{-\mathrm {i}\omega T_j}, $$

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 1,…,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

 □

3.2 Non-uniform spline functions

The above approach can easily be transferred to higher order non-uniform spline functions of the form

$$ f(x)=\sum_{j=1}^Nc_j^m B_j^m(x), $$
(3.2)

where \(B_{j}^{m}\) is the B-spline of order m determined by the knots T j ,…,T j+m . The B-spline functions \(B_{j}^{m}\) satisfy the recurrence relation

$$B_j^m(x)=\frac{x-T_j}{T_{j+m-1}-T_j}B_j^{m-1}(x)+ \frac {T_{j+m}-x}{T_{j+m}-T_{j+1}}B_{j+1}^{m-1}(x) $$

with \(B_{j}^{1}(x):=\mathbf{1}_{[T_{j},T_{j+1})}(x)\). For the first derivative of \(B_{j}^{m}\) we find for m≥3

$$ \bigl(B_j^m \bigr)^{\prime}(x)=(m-1) \cdot \biggl(\frac {B_j^{m-1}(x)}{T_{j+m-1}-T_j}-\frac {B_{j+1}^{m-1}(x)}{T_{j+m}-T_{j+1}} \biggr), $$
(3.3)

see [6, p. 115]. Replacing the usual differentiation by the differentiation from the right, the above formula is applicable for m=2, too. For k=1,…,m−1 we get

$$ f^{(k)}(x)=\sum_{j=1}^Nc_j^m \bigl(B_j^m \bigr)^{(k)}(x)=\sum _{j=1}^{N+k}c_j^{m-k} B_j^{m-k}(x), $$
(3.4)

where the coefficients \(c_{j}^{m-k}\) can be recursively evaluated from \(c_{j}^{m}\) using (3.3). Finally, taking the distributional derivative we have

$$ \bigl(B_j^1 \bigr)'(x)= (\mathbf{1}_{[T_j,T_{j+1})} )'(x)= \delta(x-T_j)-\delta(x-T_{j+1}), $$
(3.5)

where δ denotes the Dirac distribution with \(\widehat{\delta }(\omega)=1\) for all ω∈ℝ. Hence, the m-th derivative of f in (3.2) is a linear combination of weighted Dirac distributions,

$$f^{(m)}(x)=\sum_{j=1}^{N+m}c_j^0 \delta(x-T_j). $$

Application of the Fourier transform yields

$$ (\mathrm {i}\omega)^m\widehat{f}(\omega)=\sum _{j=1}^{N+m}c_j^0 \mathrm {e}^{-\mathrm {i}\omega T_j}. $$
(3.6)

Theorem 3.2

Suppose that there exist a knot sequence −∞<T 1<T 2<⋯<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.

Proof

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}\),

$$c_j^{k+1}= \begin{cases} c_1^0 & \mbox{for } k=0,\ j=1,\\[3pt] c_j^0+c_{j-1}^1 & \mbox{for } k=0,\ j=2,\ldots,N+m-1,\\[3pt] \bigl(\frac{T_{m+1-k}-T_1}{m-k} \bigr)c_1^k & \mbox{for } k=1,\ldots ,m-1,\ j=1,\\[3pt] \bigl(\frac{T_{m+j-k}-T_j}{m-k} \bigr)c_j^k+c_{j-1}^{k+1} & \mbox{for } k=1,\ldots,m-1,\ j=2,\ldots, N+m-k-1. \end{cases} \vspace{-10pt} $$

 □

Remarks 3.3

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 0∈{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.

3.3 Non-uniform translates

Let us consider functions that have a sparse representation of the form

$$ f(x)=\sum_{j=1}^Nc_j \varPhi(x-T_j) $$
(3.7)

with c j ∈ℝ∖{0} for all j=1,…,N, the knot sequence −∞<T 1<⋯<T N <∞, and where Φ∈C(ℝ)∩L 1(ℝ) is a real low-pass filter function with a Fourier transform that is bounded away from zero, i.e. \(|\widehat{\varPhi}(\omega)| > C_{0} \) for ω∈(−T,T) for some constants C 0>0 and T>0. As a low-pass filter function Φ we can take

  • the centered cardinal B-spline of order m, Φ=N m , with

    $$\widehat{N}_m(\omega)= \biggl(\operatorname{sinc} \biggl( \frac{\omega }{2} \biggr) \biggr)^m\neq0 \quad\mbox{for all }\omega \in(-2\pi,2\pi); $$

  • the Gaussian function, \(\varPhi(x)=\exp (-\frac{x^{2}}{\sigma^{2}} )\), σ>0, with

    $$\widehat{\varPhi}(\omega)=\sqrt{\pi}\cdot\sigma\cdot\exp \biggl(- \frac{\sigma^2\omega^2}{4} \biggr)>0\quad \mbox{for all }\omega\in \mathbb {R}; $$

  • the Meyer window Φ(x) with \(T=\frac{2}{3}\) and

    $$\widehat{\varPhi}(\omega)= \begin{cases} 1 & \mbox{for } \vert\omega\vert\leq\frac{1}{3},\\[3pt] \cos \bigl(\frac{\pi}{2}(3\vert\omega\vert-1 )\bigr) & \mbox{for } \frac {1}{3}<\vert\omega\vert\leq\frac{2}{3},\\[3pt] 0 & \mbox{otherwise}; \end{cases} $$

  • a real valued Gabor function \(\varPhi(x)=\mathrm {e}^{-\alpha x^{2}}\cos(\beta x)\), α>0, β>0, with

    $$\widehat{\varPhi}(\omega)=\frac{1}{2}\sqrt{\frac{\pi}{\alpha}} \biggl( \exp \biggl(-\frac{(\beta-\omega)^2}{4\alpha} \biggr)+\exp \biggl(-\frac{(\omega +\beta)^2}{4\alpha} \biggr) \biggr)>0\quad\mbox{for all }\omega\in \mathbb {R}. $$

Fourier transform of (3.7) yields

$$ \widehat{f}(\omega)= \Biggl(\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\omega T_j} \Biggr)\widehat{\varPhi}(\omega). $$
(3.8)

Theorem 3.4

Let −∞<T 1<⋯<T N <∞ be a real sequence and c j ∈ℝ∖{0} for j=1,…,N. Further, let Φ∈C(ℝ)∩L 1(ℝ) be a given function with \(|\widehat{\varPhi}(\omega)| >C_{0}\) for all ω∈(−T,T) and some C 0>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.

Proof

Using the assumption on \(\widehat{\varPhi}\) we find from (3.8)

$$\frac{\widehat{f}(\omega)}{\widehat{\varPhi}(\omega)}=\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\omega T_j}, $$

and hence we can compute all T j and c j by Prony’s method given in Sect. 2. □

The above idea can be generalized to functions f of the form

$$ f(x)=\sum_{j=1}^N\sum _{r=0}^{R-1} c_{j,r} \varPhi^{(r)}(x-T_j) $$
(3.9)

with c j,r ∈ℝ and T j ∈ℝ as before, where Φ (r) denotes the r-th derivative of Φ. Fourier transform now yields

$$ \widehat{f}(\omega)= \Biggl(\sum_{j=1}^N \sum_{r=0}^{R-1}c_{j,r}(\mathrm {i}\omega )^r\mathrm {e}^{-\mathrm {i}\omega T_j} \Biggr)\widehat{\varPhi}(\omega). $$
(3.10)

Theorem 3.5

Let −∞<T 1<⋯<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 1(ℝ) be a given function with \(|\widehat{\varPhi}(\omega)| >C_{0}\) for all ω∈(−T,T) and some C 0>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.

Proof

Regarding (3.10), we now want to apply Prony’s method to a function of the form

$$Q(\omega):=\sum_{j=1}^N\sum _{r=0}^{R-1}c_{j,r}(\mathrm {i}\omega)^r \mathrm {e}^{-\mathrm {i}\omega T_j}, $$

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

$$\varLambda(z):=\prod_{j=1}^N \bigl(z- \mathrm {e}^{-\mathrm {i}h T_j} \bigr)^R=\sum_{\ell =0}^{NR} \lambda_{\ell}z^{\ell} $$

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

$$S_{\nu}=\sum_{\mu=0}^{\nu} \alpha_{\mu}^{\nu}\varLambda^{(\mu)} \bigl( \mathrm {e}^{-\mathrm {i}hT_j} \bigr)\mathrm {e}^{-\mathrm {i}\mu hT_j}, $$

and because of \(\varLambda^{(\mu)}(\mathrm {e}^{-\mathrm {i}hT_{j}})=0\) for μ=0,…,R−1 we finally get

$$\sum_{\ell=0}^{NR}\lambda_{\ell}Q \bigl(h(\ell-m) \bigr)=0. $$

Hence, the coefficient vector λ=(λ 0,…,λ NR )T with λ NR =1 is a zero-eigenvector of the Toeplitz matrix

$$\mathbf{T}_{NR+1}:= \bigl(Q \bigl(h(\ell-m) \bigr) \bigr)_{m,\ell=0}^{NR} \in \mathbb {R}^{(NR+1)\times(NR+1)}. $$

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. □

Remarks 3.6

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,

$$f(x)=\sum_{j=1}^N\sum _{r=1}^m c_{j,r} B_j^r(x), $$

and f(x) can be recovered by the Fourier samples \(\widehat{f}(\ell h)\), ℓ=1,…,(N+m)m.

4 Recovery of special bivariate functions

4.1 Tensor products of non-uniform spline functions

Let us consider now a non-uniform tensor product spline representation

$$ f(x_1,x_2)=\sum _{j=1}^{N_1}\sum_{k=1}^{N_2}c_{j,k}^{m_1,m_2}B_j^{m_1}(x_1)B_k^{m_2}(x_2), $$
(4.1)

where \(B_{j}^{m_{1}}\) and \(B_{k}^{m_{2}}\) are B-splines of order m 1 and m 2, respectively, determined by the knot sequences \(T_{j},\ldots ,T_{j+m_{1}}\) and \(S_{k},\ldots,S_{k+m_{2}}\), respectively. Analogously as in Sect. 3.2, differentiation yields

$$\frac{\partial^{m_1}}{\partial x_1^{m_1}}\frac{\partial^{m_2}}{\partial x_2^{m_2}}f(x_1,x_2)=\sum _{j=1}^{N_1+m_1}\sum _{k=1}^{N_2+m_2}c_{j,k}^{0,0}\cdot \delta(x_1-T_j)\cdot\delta(x_2-S_k). $$

Fourier transform gives

$$ (\mathrm {i}\omega_{1})^{m_1}(\mathrm {i}\omega_2)^{m_2}\widehat{f}(\omega_1, \omega_2)=\sum_{j=1}^{N_1+m_1} \Biggl(\sum_{k=1}^{N_2+m_2}c_{j,k}^{0,0} \mathrm {e}^{-\mathrm {i}\omega_2S_k} \Biggr)\mathrm {e}^{-\mathrm {i}\omega_1T_j}. $$
(4.2)

Theorem 4.1

Let m 1,m 2∈ℕ 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 1, k=1,…,N 2. Let h 1 and h 2 be two positive constants satisfying |h 1 T j |<π for all j=1,…,N 1+m 1 and |h 2 S k |<π for all k=1,…,N 2+m 2. Then f can be uniquely recovered by the (N 1+m 1)⋅(N 2+m 2) Fourier samples \(\widehat{f}(\mu h_{1},\nu h_{2})\), μ=1,…,N 1+m 1, ν=1,…,N 2+m 2.

Proof

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

$$ (\mathrm {i}\omega_1)^{m_1}(\mathrm {i}\omega_2)^{m_2}\widehat{f}(\omega_1, \omega_2)=\sum_{j=1}^{N_1+m_1}p_j( \omega_2)\mathrm {e}^{-\mathrm {i}\omega_1 T_j}. $$
(4.3)

Fixing ω 2:=h 2, we apply Prony’s method from Sect. 2 to the function

$$P(\omega_1):=(\mathrm {i}\omega_1)^{m_1}(\mathrm {i}h_2)^{m_2}\widehat{f}(\omega_1,h_2)= \sum_{j=1}^{N_1+m_1}p_j(h_2) \mathrm {e}^{-\mathrm {i}\omega_1 T_j} $$

and obtain the knot sequence \(T_{1},\ldots,T_{N_{1}+m_{1}}\) as well as the coefficients p j (h 2), j=1,…,N 1+m 1, using the Fourier samples \(\widehat{f}(\mu h_{1},h_{2})\), μ=1,…,N 1+m 1. In the unlucky case that not all values p j (h 2), j=1,…,N 1+m 1 are non-zero, we do not find all values T j by this procedure and have to repeat the method for ω 2=2h 2,3h 2,… etc. in order to complete the knot sequence {T j , j=1,…,N 1+m 1}.

Next, knowing the T j , we compute all further coefficients p j (νh 2), j=1,…,N 1+m 1, ν=2,…,N 2+m 2, from the Fourier samples \(\widehat{f}(\mu h_{1},\nu h_{2})\), μ=1,…,N 1+m 1, ν=2,…,N 2+m 2, using (4.3). Afterwards, we apply the Prony method to

$$p_1(\omega_2)=\sum_{k=1}^{N_2+m_2}c_{1,k}^{0,0} \mathrm {e}^{-\mathrm {i}\omega_2 S_k} $$

and use p 1(h 2),…,p 1((N 2+m 2)h 2) in order to determine the knot sequence S 1,… , \(S_{N_{2}+m_{2}}\) and the coefficients \(c_{1,k}^{0,0}\), k=1,…,N 2+m 2, uniquely. Again, in case that \(c_{1,k}^{0,0}=0\) for some k∈{1,…,N 2+m 2} we do not obtain all S k and need to apply Prony’s method also to p j (ω 2) for j>1 in order to complete the knot sequence {S k , k=1,…,N 2+m 2}.

All further coefficients \(c_{j,k}^{0,0}\) are obtained from the linear systems

$$p_j(\nu h_2)=\sum_{k=1}^{N_2+m_2}c_{j,k}^{0,0} \mathrm {e}^{-\mathrm {i}\nu h_2 S_k}, \quad\nu=1,\ldots,N_2+m_2 $$

for each j=2,3,…,N 1+m 1. Finally, we have to evaluate the original coefficients \(c_{j,k}^{m_{1},m_{2}}\) from \(c_{j,k}^{0,0}\) using the recursions

$$c_{j,k}^{r_1+1,r_2}= \begin{cases} c_{1,k}^{0,r_2} & \mbox{for } r_1=0,\ j=1,\\[3pt] c_{j,k}^{0,r_2}+c_{j-1,k}^{1,r_2} & \mbox{for } r_1=0,\ j=2,\ldots ,N_1+m_1-1,\\[3pt] \bigl(\frac{T_{m_1+1-r_1}-T_1}{m_1-r_1} \bigr)c_{1,k}^{r_1,r_2} & \mbox{for } r_1=1,\ldots,m_1-1,\ j=1,\\[3pt] \bigl(\frac{T_{m_1+j-r_1}-T_j}{m_1-r_1} \bigr)c_{j,k}^{r_1,r_2}+c_{j-1,k}^{r_1+1,r_2} & \parbox{4.7cm}{ for $r_{1}=1,\ldots,m_{1}-1$,\\ \hspace*{0.35cm} $j=2,\ldots, N_{1}+m_{1}-r_{1}-1$,} \end{cases} $$

where r 2=0,…,m 2, k=1,…,N 2+m 2−r 2, and

$$c_{j,k}^{r_1,r_2+1}= \begin{cases} c_{j,1}^{r_1,0} & \mbox{for } r_2=0,\ k=1,\\[3pt] c_{j,k}^{r_1,0}+c_{j,k-1}^{r_1,1} & \mbox{for } r_2=0,\ k=2,\ldots ,N_2+m_2-1,\\[3pt] \bigl(\frac{S_{m_2+1-r_2}-S_1}{m_2-r_2} \bigr)c_{j,1}^{r_1,r_2} & \mbox{for } r_2=1,\ldots,m_2-1,\ k=1,\\[3pt] \bigl(\frac{S_{m_2+k-r_2}-S_k}{m_2-r_2} \bigr)c_{j,k}^{r_1,r_2}+c_{j,k-1}^{r_1,r_2+1} & \parbox{4.7cm}{for $r_{2}=1,\ldots,m_{2}-1$,\\ \hspace*{0.4cm} $k=2,\ldots, N_{2}+m_{2}-r_{2}-1$,} \end{cases} $$

where r 1=0,…,m 1, j=1,…,N 1+m 1−r 1. □

Remarks 4.2

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 2) 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

$$ f(x_1,x_2):=\sum _{j=1}^{N_1}\sum_{k=1}^{N_2}c_{j,k} \varPhi_1(x_1-T_j)\varPhi_2(x_2-S_k) $$
(4.4)

with two low-pass filter functions Φ 1 and Φ 2 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

$$\widehat{f}(\omega_1,\omega_2)= \Biggl(\sum _{j=1}^{N_1}\sum_{k=1}^{N_2}c_{j,k} \mathrm {e}^{-\mathrm {i}\omega_1 T_j}\mathrm {e}^{-\mathrm {i}\omega_2 S_k} \Biggr)\widehat{\varPhi}_1( \omega_1)\widehat{\varPhi}_2(\omega_2). $$

Hence, for given functions Φ 1,Φ 2 we can recover f completely using the Fourier samples \(\widehat{f}(\ell_{1} h_{1},\ell_{2} h_{2})\), ℓ 1=0,…,N 1, ℓ 2=0,…,N 2 by following the same lines as in the proof of Theorem 4.1. Here, h 1,h 2 have to satisfy |h 1 T j |<min{π,T} and |h 2 S k |<min{π,T} for all j=1,…,N 1, k=1,…,N 2.

4.2 Non-uniform translates of radial functions

For a given bivariate radial function Φ(x 1,x 2)∈C(ℝ2)∩L 1(ℝ2) we assume that \(\widehat{\varPhi}(\omega_{1},\omega_{2})\) is bounded and satisfies \(|\widehat{\varPhi}(\omega_{1},\omega_{2})| > C_{0}>0\) for ω:=(ω 1,ω 2)T with \(\Vert\omega\Vert_{2}=(\omega_{1}^{2}+\omega_{2}^{2})^{\frac{1}{2}}<T\) and a suitable constant T>0. Such a function Φ can be simply constructed with the help of a univariate low-pass function as given in Sect. 3.3 with

$$\varPhi(x_1,x_2):=\varPhi(r), \quad r:= \bigl(x_1^2+x_2^2 \bigr)^{\frac{1}{2}}. $$

Let us consider now a function f(x 1,x 2) with the sparse representation

$$ f(x_1,x_2)=\sum _{j=1}^Nc_j\varPhi(x_1-v_{j,1},x_2-v_{j,2}). $$
(4.5)

As before, we would like to answer the questions, how many Fourier samples are needed to recover f if Φ and N are known, and how to compute the real shifts \({\bf v}_{j}:=(v_{j,1},v_{j,2})\) and the real coefficients c j , j=1,…,N, from these samples. Observe that this problem is completely different from the separable case considered in Sect. 4.1.

Fourier transform of (4.5) yields

$$ \widehat{f}(\omega_1,\omega_2)= \Biggl(\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\cdot (\omega_1v_{j,1}+\omega_2v_{j,2})} \Biggr)\widehat{\varPhi}(\omega_1, \omega_2). $$
(4.6)

In the following, we consider only the case c j >0 for all j=1,…,N.

Theorem 4.3

Let Φ∈C(ℝ2)∩L 1(ℝ2) be a given, real, bivariate function with \(|\widehat{\varPhi}(\omega_{1},\omega_{2})| > C_{0} >0\) for ∥ω∥2<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 ∥2<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

$$\bigl\{\widehat{f}(0,0), \widehat{f}(\ell h,0), \widehat{f}(0,\ell h), \widehat{f} \bigl(\cos(\alpha\pi)\ell h,\sin(\alpha\pi)\ell h \bigr),\ \ell=1,\ldots,N \bigr\}, $$

where \(\alpha\in(0,\, 1 ) \setminus\{\frac{1}{2} \}\) needs to be chosen suitably.

Proof

We give a constructive proof. From (4.6) we obtain for ω 2=0

$$\frac{\widehat{f}(\omega_1,0)}{\widehat{\varPhi}(\omega_1,0)}=\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\omega_1v_{j,1}}. $$

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 1≤N distinct values \(\widetilde {v}_{1,1},\ldots,\widetilde{v}_{N_{1},1}\). Then we find

$$ \frac{\widehat{f}(\omega_1,0)}{\widehat{\varPhi}(\omega_1,0)}=\sum_{k=1}^{N_1}c_k^1 \mathrm {e}^{-\mathrm {i}\omega_1\widetilde{v}_{k,1}}, $$
(4.7)

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}\),

$$ c_k^1:=\sum_{\stackrel{j}{v_{j,1}=\widetilde{v}_{k,1}}}c_j, \quad k=1,\ldots,N_1. $$
(4.8)

Observe that \(c_{k}^{1}>0\) for all k=1,…,N 1, 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 1.

Analogously, we observe from (4.6) with ω 1=0 that

$$\frac{\widehat{f}(0,\omega_2)}{\widehat{\varPhi}(0,\omega_2)}=\sum_{j=1}^Nc_j \mathrm {e}^{-\mathrm {i}\omega_2 v_{j,2}}=\sum_{k=1}^{N_2}c_k^2 \mathrm {e}^{-\mathrm {i}\omega _2\widetilde{v}_{k,2}}, $$

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 2, N 2≤N. The values \(\widetilde {v}_{k,2}\), \(c_{k}^{2}\), k=1,…,N 2, 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

$$G:= \bigl\{ \mathbf{v}=(v_1,v_2): v_1\in \widetilde{V}_1,\ v_2\in\widetilde{V}_2 \bigr\} , $$

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 1+(sinαπ)v 2 are distinct for all v∈G. Since G contains N 1 N 2≤N 2 entries, such a number \(\alpha\in(0, \, 1) \setminus\{\frac{1}{2}\}\) can always be found.

Now, we consider

$$\frac{\widehat{f}(\omega_1\cos(\alpha\pi),\omega_1\sin(\alpha\pi ))}{\widehat{\varPhi}(\omega_1\cos(\alpha\pi),\omega_1\sin(\alpha\pi))} = \sum_{k=1}^{N_3}c_k^3 \mathrm {e}^{-\mathrm {i}\omega_1\widetilde{v}_{k,3}}, $$

where \(\widetilde{v}_{k,3}\), k=1,…,N 3 with N 3≤N are the distinct values of the set {v j,1cos(απ)+v j,2sin(απ): j=1,…,N}. However, the construction of α yields that N 3=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

$$\widetilde{G}:= \bigl\{ \mathbf{v}=(v_1,v_2): v_1\in\widetilde{V}_1,\ v_2\in \widetilde{V}_2,\ v_1\cos(\alpha\pi)+v_2\sin( \alpha\pi)\in\widetilde {V}_3 \bigr\} $$

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 \}\). □

In order to improve the robustness of the reconstruction method, the angle α should be chosen such that the minimal distance between two orthogonal projections of elements from G onto the line y=tan(απ)x is maximized. With θ α :=(cos(απ),sin(απ))T, the projection point p v of v onto this line is

$$\mathbf{p}_\mathbf{v} = \langle\mathbf{v}, \theta_{\alpha} \rangle \theta_{\alpha} = \bigl( \cos(\alpha\pi) v_{1} + \sin(\alpha\pi) v_{2} \bigr) \theta_{\alpha}. $$

Hence, we need to maximize the minimal distance of two projection points with respect to α, i.e., we have to solve the max-min problem

Remarks 4.4

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 1+N 2+N 3 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 1+N 2+N 3+N 4 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).

5 Numerical results

We want to apply the described reconstruction methods to examples of step functions, non-uniform spline functions and non-uniform translates of radial functions. All examples considered in this section have been computed using MATLAB 7.11 with double precision arithmetic on a MacBook Pro with a 2.4 GHz Intel Core 2 Duo processor.

In the first two examples we consider the reconstruction of univariate functions. Figure 1 presents a step function that is determined by the knot sequence {T j } j=1,…,7 and the coefficient sequence {c j } j=1,…,6 given in Table 1. Observe that the knots T 1=−11.5 and T 2=−11.43 are very close, and that the difference of the two successive coefficients c 3=1.2 and c 4=1.1 is rather small. To show the exactness of the reconstruction we have displayed the absolute reconstruction errors \(\vert T_{j}^{*}-T_{j}\vert, j=1,\ldots,7\), and \(\vert c_{j}^{*}-c_{j}\vert, j=1,\ldots,6\), where \(T_{j}^{*}\) and \(c_{j}^{*}\) denote the reconstructed knot values and coefficient values, respectively.

Fig. 1
figure 1

Original function of the form (3.1) with N=6 determined by {T j } and {c j } given in Table 1

Full size image
Table 1 Parameters for the original function in Fig. 1 and reconstruction errors, where h=0.27
Full size table

The second example shows the results for the reconstruction of a non-uniform spline function of the form (3.2), see Fig. 2. We have taken N=5 and non-uniform B-splines of order m=5. The original parameters T j and c j are listed in Table 2, and we also compare them with the reconstructed values \(T_{j}^{*}\) and \(c_{j}^{*}\), respectively.

Fig. 2
figure 2

Original function of the form (3.2) determined by {T j } and {c j } (see Table 2) with N=5, m=5

Full size image
Table 2 Parameters for the original function in Fig. 2 and reconstruction errors, where h=0.5
Full size table

In the last two examples, we want to show how our proposed algorithm works for the case of non-uniform translates of bivariate radial functions. Therefore, we have taken the radial function \(\varPhi (x_{1},x_{2}):=\exp (-\alpha\cdot(x_{1}^{2}+x_{2}^{2}) )\) with α=0.05 and a discrete grid setting with 128×128 points where the values for the first and the second coordinate are ranging from −64 to 63 and from −63 to 64, respectively.

First, we have taken an original function which consists only of four summands, but where three shift vectors are lying closely to each other on the same vertical line, see Fig. 3. The determining parameters are listed in Table 3. In addition, also the absolute reconstruction errors between the original parameters and the reconstructed parameters \(v_{j,1}^{*}\), \(v_{j,2}^{*}\) and \(c_{j}^{*}\), respectively, are listed in Table 3. We have used these parameters to evaluate the reconstructed function on the discrete grid and to compare it with the original function on this grid. In this way we get a maximal absolute error between the original and the reconstructed function of approximately 1.175⋅10−8.

Fig. 3
figure 3

Original function of the form (4.5) determined by {v j } and {c j } given in Table 3

Full size image
Table 3 Parameters for the original function in Fig. 3 and reconstruction errors, where \(\alpha=\frac{4}{9}\)
Full size table

The second bivariate function, where we have applied our algorithm, is displayed in Fig. 4. Considering only the shift vectors and not the coefficients, this function has an 8-fold rotation symmetry. For the original parameters and the reconstruction errors see Table 4. Again, we have used the reconstructed parameters to evaluate the function on the discrete grid. Comparison with the original function yields a maximal absolute error of approximately 5.193⋅10−10.

Fig. 4
figure 4

Original function of the form (4.5) determined by {v j } and {c j } given in Table 4

Full size image
Table 4 Parameters for the original function in Fig. 4 and reconstruction errors, where α=0.4375
Full size table

6 Conclusion

In this paper, we have emphasized the question of how to reconstruct structured functions by means of a smallest number of Fourier data. However, in case of noisy Fourier measurements, the performance of reconstruction can be greatly improved if a larger number of Fourier data is available, see e.g. [9, 12, 15, 18]. In particular, for small data sets we recommend the preprocessing step of data filtering presented in [9]. In that reference, one can also find error estimates for the obtained function parameters.

Recently, Candès et al. [4] proposed the reconstruction of functions of the form (2.1) using a total variation minimization formulation. To tackle this minimization problem, a semidefinite program is applied to solve the dual problem in a first step. The obtained vector is used to define a special polynomial whose zeros on the unit circle are related to the wanted parameters T j . The exact connections between the minimization approach in the context of super-resolution and the direct algorithms for the Prony method will be subject of further research.