×

Stable soft extrapolation of entire functions. (English) Zbl 1421.65032

Summary: Soft extrapolation refers to the problem of recovering a function from its samples, multiplied by a fast-decaying window and perturbed by an additive noise, over an interval which is potentially larger than the essential support of the window. To achieve stable recovery one must use some prior knowledge about the function class, and a core theoretical question is to provide bounds on the possible amount of extrapolation, depending on the sample perturbation level and the function prior.
In this paper we consider soft extrapolation of entire functions of finite order and type (containing the class of bandlimited functions as a special case), multiplied by a super-exponentially decaying window (such as a Gaussian). We consider a weighted least-squares polynomial approximation with judiciously chosen number of terms and a number of samples which scales linearly with the degree of approximation. It is shown that this simple procedure provides stable recovery with an extrapolation factor which scales logarithmically with the perturbation level and is inversely proportional to the characteristic lengthscale of the function. The pointwise extrapolation error exhibits a Hölder-type continuity with an exponent derived from weighted potential theory, which changes from 1 near the available samples, to 0 when the extrapolation distance reaches the characteristic smoothness length scale of the function. The algorithm is asymptotically minimax, in the sense that there is essentially no better algorithm yielding meaningfully lower error over the same smoothness class.
When viewed in the dual domain, soft extrapolation of an entire function of order 1 and finite exponential type corresponds to the problem of (stable) simultaneous de-convolution and super-resolution for objects of small space/time extent. Our results then show that the amount of achievable super-resolution is inversely proportional to the object size, and therefore can be significant for small objects. These results can be considered as a first step towards analyzing the much more realistic ‘multiband’ model of a sparse combination of compactly-supported ‘approximate spikes’, which appears in applications such as synthetic aperture radar, seismic imaging and direction of arrival estimation, and for which only limited special cases are well-understood.

MSC:

65R32 Numerical methods for inverse problems for integral equations
30D15 Special classes of entire functions of one complex variable and growth estimates
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Akinshin, A.; Batenkov, D.; Yomdin, Y., Accuracy of spike-train Fourier reconstruction for colliding nodes, 617-621, (2015) · doi:10.1109/SAMPTA.2015.7148965
[2] Batenkov, D., Stability and super-resolution of generalized spike recovery, Appl. Comput. Harmon. Anal., 45, 299-323, (2018) · Zbl 1414.94009 · doi:10.1016/j.acha.2016.09.004
[3] Batenkov, D.; Yomdin, Y., On the accuracy of solving confluent Prony systems, SIAM J. Appl. Math., 73, 134-154, (2013) · Zbl 1269.65047 · doi:10.1137/110836584
[4] Batenkov, D.; Yomdin, Y., Geometry and singularities of the Prony mapping, J. Singularities, 10, 1-25, (2014) · Zbl 1353.94014 · doi:10.5427/jsing.2014.10a
[5] Bertero, M.; de Mol, C., III super-resolution by data inversion, Prog. Opt., 36, 129-178, (1996) · doi:10.1016/S0079-6638(08)70314-7
[6] Bertero, M.; De Mol, C.; Viano, G. A., On the problems of object restoration and image extrapolation in optics, J. Math. Phys., 20, 509-521, (1979) · doi:10.1063/1.524103
[7] Bertero, M.; Viano, G. A.; Mol, C. D., Resolution beyond the diffraction limit for regularized object restoration, Opt. Acta: Int. J. Opt., 27, 307-320, (1980) · doi:10.1080/713820228
[8] Candès, E. J.; Fernandez-Granda, C., Super-resolution from noisy data, J. Fourier Anal. Appl., 19, 1229-1254, (2013) · Zbl 1312.94015 · doi:10.1007/s00041-013-9292-3
[9] Candès, E. J.; Fernandez-Granda, C., Towards a mathematical theory of super-resolution, Commun. Pure Appl. Math., 67, 906-956, (2014) · Zbl 1350.94011 · doi:10.1002/cpa.21455
[10] Cannon, J. R.; Miller, K., Some problems in numerical analytic continuation, J. Soc. Ind. Appl. Math. B, 2, 87-98, (1965) · Zbl 0214.14805 · doi:10.1137/0702007
[11] Demanet, L.; Nguyen, N., The recoverability limit for superresolution via sparsity, (2015)
[12] Demanet, L.; Townsend, A., Stable extrapolation of analytic functions, Foundations Comput. Math, 18, 1-35, (2018) · doi:10.1007/s10208-018-9384-1
[13] Donoho, D., Superresolution via sparsity constraints, SIAM J. Math. Anal., 23, 1309-1331, (1992) · Zbl 0769.42007 · doi:10.1137/0523074
[14] Filbir, F.; Mhaskar, H. N.; Prestin, J., On the problem of parameter estimation in exponential sums, Constructive Approx., 35, 323-343, (2012) · Zbl 1254.94015 · doi:10.1007/s00365-011-9136-9
[15] Gil, A.; Segura, J.; Temme, N., Numerical Methods for Special Functions, (2007), Philadelphia, PA: SIAM, Philadelphia, PA · Zbl 1144.65016
[16] Henrici, P., An algorithm for analytic continuation, SIAM J. Numer. Anal., 3, 67-78, (1966) · Zbl 0141.33302 · doi:10.1137/0703005
[17] Hoorfar, A.; Hassani, M., Inequalities on the Lambert W function and hyperpower function, J. Inequalities Pure Appl. Math., 9, 5-9, (2008) · Zbl 1163.33326
[18] Izu, S.; Lakey, J. D., Time-frequency localization and sampling of multiband signals, Acta Appl. Math., 107, 399-435, (2009) · Zbl 1178.94077 · doi:10.1007/s10440-008-9416-y
[19] Landau, H., Extrapolating a band-limited function from its samples taken in a finite interval, IEEE Trans. Inf. Theory, 32, 464-470, (1986) · Zbl 0619.94004 · doi:10.1109/TIT.1986.1057205
[20] Levin, B. Y., Lectures on Entire Functions, vol 150, (1996), Providence, RI: American Mathematical Society, Providence, RI
[21] Levin, E.; Lubinsky, D. S., Orthogonal Polynomials for Exponential Weights, (2012), New York: Springer, New York
[22] Li, W.; Liao, W., Stable super-resolution limit and smallest singular value of restricted Fourier matrices, (2017)
[23] Lindberg, J., Mathematical concepts of optical superresolution, J. Opt., 14, (2012) · doi:10.1088/2040-8978/14/8/083001
[24] Lubinsky, D. S.; Saff, E. B., Strong Asymptotics for Extremal Polynomials Associated with Weights on IR, (1988), Berlin: Springer, Berlin · Zbl 0647.41001
[25] Mhaskar, H.; Prestin, J., On the detection of singularities of a periodic function, Adv. Comput. Math., 12, 95-131, (2000) · Zbl 0937.42014 · doi:10.1023/A:1018921319865
[26] Mhaskar, H. N., Weighted polynomial approximation of entire functions on unbounded subsets of the complex plane, Canad. Math. Bull., 36, 303-313, (1993) · Zbl 0807.30023 · doi:10.4153/CMB-1993-043-4
[27] Mhaskar, H. N., Introduction to the Theory of Weighted Polynomial Approximation, (1997), Singapore: World Scientific, Singapore
[28] Mhaskar, H. N., On the representation of band limited functions using finitely many bits, J. Complexity, 18, 449-478, (2002) · Zbl 1010.41016 · doi:10.1006/jcom.2001.0637
[29] Mhaskar, H. N.; Prestin, J., On local smoothness classes of periodic functions, J. Fourier Anal. Appl., 11, 353-373, (2005) · Zbl 1096.42018 · doi:10.1007/s00041-005-4006-0
[30] Mhaskar, H. N.; Saff, E. B., Extremal problems for polynomials with exponential weights, Trans. Am. Math. Soc., 285, 203-234, (1984) · Zbl 0546.41014 · doi:10.1090/S0002-9947-1984-0748838-0
[31] Micchelli, C. A.; Rivlin, T. J., A survey of optimal recovery, Optimal Estimation in Approximation Theory, 1-54, (1977), Boston, MA: Springer, Boston, MA
[32] Micchelli, C. A.; Rivlin, T. J., Lectures on optimal recovery, Numerical Analysis Lancaster 1984, 21-93, (1985), New York: Springer, New York
[33] Miller, K., Three circle theorems in partial differential equations and applications to improperly posed problems, Arch. Ration. Mech. Anal., 16, 126-154, (1964) · Zbl 0145.14203 · doi:10.1007/BF00281335
[34] Miller, K., Least squares methods for ill-posed problems with a prescribed bound, SIAM J. Math. Anal., 1, 52-74, (1970) · Zbl 0214.14804 · doi:10.1137/0501006
[35] Miller, K.; Viano, G. A., On the necessity of nearly-best-possible methods for analytic continuation of scattering data, J. Math. Phys., 14, 1037-1048, (1973) · Zbl 0256.35066 · doi:10.1063/1.1666435
[36] Mishali, M.; Eldar, Y. C., From theory to practice: sub-nyquist sampling of sparse wideband analog signals, IEEE J. Sel. Top. Signal Process., 4, 375-391, (2010) · doi:10.1109/JSTSP.2010.2042414
[37] Paley, R. E A. C.; Wiener, N., Fourier Transforms in the Complex Domain, vol 19, (1934), New York: American Mathematical Society, New York · JFM 60.0345.02
[38] Prony, R., Essai experimental et analytique, J. Ecole. Polytech., 2, 24-76, (1795)
[39] Stallinga, S.; Rieger, B., Accuracy of the Gaussian point spread function model in 2d localization microscopy, Opt. Express, 18, 24461-24476, (2010) · doi:10.1364/OE.18.024461
[40] Stoica, P.; Moses, R., Spectral Analysis of Signals, (2005), Englewood Cliffs, NJ: Pearson/Prentice Hall, Englewood Cliffs, NJ
[41] Strichartz, R. S., A Guide to Distribution Theory and Fourier Transforms, (2003), Singapore: World Scientific, Singapore · Zbl 1029.46039
[42] Trefethen, L. N., Quantifying the ill-conditioning of analytic continuation, preprint · Zbl 1461.30014
[43] Venkataramani, R.; Bresler, Y., Optimal sub-Nyquist nonuniform sampling and reconstruction for multiband signals, IEEE Trans. Signal Process., 49, 2301-2313, (2001) · doi:10.1109/78.950786
[44] Walsh, J. L., Interpolation and Approximation by Rational Functions in the Complex Domain, vol 20, (1935), Providence, RI: American Mathematical Society, Providence, RI · JFM 61.0315.01
[45] Zhu, Z.; Wakin, M. B., Approximating sampled sinusoids and multiband signals using multiband modulated DPSS dictionaries, J. Fourier Anal. Appl., 23, 1263-1310, (2017) · Zbl 1392.94576 · doi:10.1007/s00041-016-9498-2
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.