×

zbMATH — the first resource for mathematics

Reconstruction of polygonal shapes from sparse Fourier samples. (English) Zbl 1362.94012
In this interesting paper, the authors reconstruct the characteristic function \(f(x_1,x_2) = 1_D(x_1,x_2)\) of a simply-connected polygonal domain \(D \subset {\mathbb R}^2\) from relatively few samples of the Fourier transform \(\hat f\). This reconstruction method is based on a stable Prony method (such as approximate Prony method, MUSIC or ESPRIT) for the recovery of univariate exponential sums. By this approach, the authors reconstruct the vertices of the polygon in a correct way. It is remarkable that this method works also for a non-convex polygonal domain \(D\).
Note that the reconstruction of a convex polygonal domain \(D \subset \mathbb C\) from given moments were presented by G. H. Golub et al. [SIAM J. Sci. Comput. 21, No. 4, 1222–1243 (1999; Zbl 0956.65030)].

MSC:
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
42B10 Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type
65D20 Computation of special functions and constants, construction of tables
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bracewell, R. N., The Fourier transform and its applications, (2000), McGraw-Hill New York · Zbl 0068.16503
[2] Hildebrand, F. B., Introduction to numerical analysis, (1987), Dover Publications New York, Unabridged, slightly corrected republication · Zbl 0641.65001
[3] de Prony, G. C.F. M.R., Essai expérimental et analytique sur LES lois de la dilatabilité des fluides élastiques et sur celles de la force expansive de la vapeur de l’eau et de la vapeur de l’alkool, à différentes températures, J. École Polytech., 1, 24-76, (1795), Quoted from [13]
[4] Potts, D.; Tasche, M., Parameter estimation for exponential sums by approximate prony method, Signal Process., 90, 5, 1631-1642, (2010) · Zbl 1194.94128
[5] Potts, D.; Tasche, M., Nonlinear approximation by sums of nonincreasing exponentials, Appl. Anal., 90, 609-626, (2011) · Zbl 1222.41025
[6] Filbir, F.; Mhaskar, H. N.; Prestin, J., On the problem of parameter estimation in exponential sums, Constr. Approx., 35, 3, 323-343, (2012) · Zbl 1254.94015
[7] Mhaskar, H. N.; Prestin, J., On the detection of singularities of a periodic function, Adv. Comput. Math., 12, 2-3, 95-131, (2000) · Zbl 0937.42014
[8] Mhaskar, H. N.; Prestin, J., On local smoothness classes of periodic functions, J. Fourier Anal. Appl., 11, 3, 353-373, (2005) · Zbl 1096.42018
[9] Roy, R.; Kailath, T., ESPRIT—estimation of signal parameters via rotational invariance techniques, IEEE Trans. Acoust. Speech Signal Process., 37, 7, 984-995, (1989)
[10] Hua, Y.; Sarkar, T. K., Matrix pencil method for estimating parameter of exponentially damped/undamped sinusoids in noise, IEEE Trans. Acoust. Speech Signal Process., 38, 5, 814-824, (1990) · Zbl 0706.62094
[11] Schmidt, R. O., Multiple emitter location and signal parameter estimation, IEEE Trans. Antennas and Propagation, 34, 3, 276-280, (1986)
[12] Potts, D.; Tasche, M., Parameter estimation for nonincreasing exponential sums by prony-like methods, Linear Algebra Appl., 439, 4, 1024-1039, (2013) · Zbl 1281.65021
[13] Peter, T., Generalized prony method, (2014), Der Andere Verlag Uelvesbüll
[14] Wischerhoff, M., Real function reconstruction from sparse Fourier samples, PAMM. Proc. Appl. Math. Mech., 13, 1, 491-492, (2013)
[15] Plonka, G.; Wischerhoff, M., How many Fourier samples are needed for real function reconstruction?, J. Appl. Math. Comput., 42, 1-2, 117-137, (2013) · Zbl 1296.42001
[16] Potts, D.; Tasche, M., Parameter estimation for multivariate exponential sums, Electron. Trans. Numer. Anal., 40, 204-224, (2013) · Zbl 1305.65093
[17] Milanfar, P.; Verghese, G. C.; Karl, W. C.; Willsky, A. S., Reconstructing polygons from moments with connections to array processing, IEEE Trans. Signal Process., 43, 2, 432-443, (1995)
[18] 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
[19] 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
[20] Durocher, S., Graph-theoretic and geometric algorithms associated with moment-based polygon reconstruction, (1999), Department of Computer Science, University of British Columbia, (Master’s thesis)
[21] Gravin, N.; Lasserre, J.; Pasechnik, D. V.; Robins, S., The inverse moment problem for convex polytopes, Discrete Comput. Geom., 48, 3, 596-621, (2012) · Zbl 1285.68198
[22] Collowald, M.; Cuyt, A.; Hubert, E.; Lee, W.-S.; Celis, O. S., Numerical reconstruction of convex polytopes from directional moments, Adv. Comput. Math., (2015) · Zbl 1334.44005
[23] Cuyt, A.; Golub, G.; Milanfar, P.; Verdonk, B., Multidimensional integral inversion, with applications in shape reconstruction, SIAM J. Sci. Comput., 27, 3, 1058-1070, (2005) · Zbl 1099.65128
[24] Komrska, J., Simple derivation of formulas for Fraunhofer diffraction at polygonal apertures, J. Opt. Soc. Amer., 72, 10, 1382-1384, (1982)
[25] Buhmann, M.; Pinkus, A., On a recovery problem, Ann. Numer. Math., 4, 129-142, (1997) · Zbl 0892.42016
[26] Peter, T.; Potts, D.; Tasche, M., Nonlinear approximation by sums of exponentials and translates, SIAM J. Sci. Comput., 33, 4, 1920-1947, (2011) · Zbl 1243.65166
[27] Gustafsson, B.; He, C.; Milanfar, P.; Putinar, M., Reconstructing planar domains from their moments, Inverse Problems, 16, 4, 1053-1070, (2000) · Zbl 0959.44010
[28] Brion, M., Points entiers dans LES polyèdres convexes, Ann. Sci. Éc. Norm. Supér., 21, 4, 653-663, (1988) · Zbl 0667.52011
[29] Beck, M.; Robins, S., Computing the continuous discretely, (2007), Springer New York · Zbl 1114.52013
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.