×

zbMATH — the first resource for mathematics

How many Fourier samples are needed for real function reconstruction? (English) Zbl 1296.42001
Summary: In this paper we present some new results on the reconstruction of structured functions by a small number of equidistantly distributed Fourier samples. In particular, we show that real spline functions of order \(m\) with non-uniform knots containing \(N\) terms can be uniquely reconstructed by only \(m+N\) Fourier samples. Further, linear combinations of \(N\) non-equispaced shifts of a known low-pass function \(\varPhi\) can be reconstructed by \(N+1\) Fourier samples. In the bivariate case, we consider the problem of function recovering by a small amount of Fourier samples on different lines through the origin. Our methods are based on the Prony method. The proofs given in this paper are constructive. Some numerical examples show the applicability of the proposed approach.

MSC:
42A10 Trigonometric approximation
42B10 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type
65T40 Numerical methods for trigonometric approximation and interpolation
41A45 Approximation by arbitrary linear expressions
41A63 Multidimensional problems (should also be assigned at least one other classification number from Section 41-XX)
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bracewell, R.N.: The Fourier Transform and Its Applications. McGraw-Hill, New York (2000) · Zbl 0149.08301
[2] Braess, D.: Nonlinear Approximation Theory. Springer, Berlin (1986) · Zbl 0656.41001
[3] Bresler, Y., Macovski, A.: Exact maximum likelihood parameter estimation of superimposed exponential signals in noise. IEEE Trans. Acoust. Speech Signal Process.. ASSAP-34, 1081–1089 (1986) · Zbl 0628.93058 · doi:10.1109/TASSP.1986.1164949
[4] Candès, E., Fernandez-Granda, C.: Towards a mathematical theory of super-resolution. Comm. Pure Appl. Math. (to appear) · Zbl 1350.94011
[5] Candès, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52(2), 489–509 (2006) · Zbl 1231.94017 · doi:10.1109/TIT.2005.862083
[6] de Boor, C.: A Practical Guide to Splines. Springer, New York (2001) · Zbl 0987.65015
[7] Dragotti, P.L., Vetterli, M., Blu, T.: Sampling moments and reconstructing signals of finite rate of innovation: Shannon meets Strang-Fix. IEEE Trans. Signal Process. 50(6), 1417–1428 (2002) · Zbl 1369.94309 · doi:10.1109/TSP.2002.1003065
[8] Elad, M., Milanfar, P., Golub, G.H.: Shape from moments–an estimation theory perspective. IEEE Trans. Signal Process. 52(7), 1814–1829 (2004) · Zbl 1369.62145 · doi:10.1109/TSP.2004.828919
[9] Filbir, F., Mhaskar, H., Prestin, J.: On the problem of parameter estimation in exponential sums. Constr. Approx. 35, 323–343 (2012) · Zbl 1254.94015 · doi:10.1007/s00365-011-9136-9
[10] Golub, G.H., Van Loan, C.: Matrix Computations, 3rd edn. Johns Hopkins University Press, Baltimore (1996) · Zbl 0865.65009
[11] Golub, G.H., Milanfar, P., Varah, J.: A stable numerical method for inverting shape from moments. SIAM J. Sci. Comput. 21(4), 1222–1243 (1999) · Zbl 0956.65030 · doi:10.1137/S1064827597328315
[12] Hua, Y., Sarkar, T.K.: On SVD for estimating generalized eigenvalues of singular matrix pencil in noise. IEEE Trans. Signal Process. 39, 892–900 (1991) · doi:10.1109/78.80911
[13] Maravic, I., Vetterli, M.: Exact sampling results for some classes of parametric nonbandlimited 2-D signals. IEEE Trans. Signal Process. 52(1), 175–198 (2004) · Zbl 1369.94428 · doi:10.1109/TSP.2003.819984
[14] Peter, T., Potts, D., Tasche, M.: Nonlinear approximation by sums of exponentials and translates. SIAM J. Sci. Comput. 33(4), 1920–1944 (2011) · Zbl 1243.65166 · doi:10.1137/100790094
[15] Potts, D., Tasche, M.: Parameter estimation for exponential sums by approximate Prony method. Signal Process. 90(5), 1631–1642 (2010) · Zbl 1194.94128 · doi:10.1016/j.sigpro.2009.11.012
[16] Potts, D., Tasche, M.: Parameter estimation for multivariate exponential sums. Preprint (2011) · Zbl 1305.65093
[17] Rauhut, H.: Random sampling of sparse trigonometric polynomials. Appl. Comput. Harmon. Anal. 22(1), 16–42 (2007) · Zbl 1123.94004 · doi:10.1016/j.acha.2006.05.002
[18] Roy, R., Kailath, T.: ESPRIT–estimation of signal parameters via rotational invariance techniques. IEEE Trans. Acoust. Speech Signal Process. 37, 984–995 (1989) · Zbl 0701.93090 · doi:10.1109/29.32276
[19] Shukla, P., Dragotti, P.L.: Sampling schemes for 2-d signals with finite rate of innovation using kernels that reproduce polynomials. In: Proc. of IEEE Int. Conf. on Image Processing (ICIP) (2005)
[20] Vanpoucke, F., Moonen, M., Berthoumieu, Y.: An efficient subspace algorithm for 2-D harmonic retrieval. In: Proc. of IEEE Int. Conf. Acoust., Speech, Signal Processing, vol. 4, pp. 461–464 (1994)
[21] Vetterli, M., Marziliano, P., Blu, T.: Sampling signals with finite rate of innovation. IEEE Trans. Signal Process. 50(6), 1417–1428 (2002) · Zbl 1369.94309 · doi:10.1109/TSP.2002.1003065
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.