×

zbMATH — the first resource for mathematics

Numerical reconstruction of convex polytopes from directional moments. (English) Zbl 1334.44005
Summary: We reconstruct an \(n\)-dimensional convex polytope from the knowledge of its directional moments. The directional moments are related to the projection of the polytope vertices on a particular direction. To extract the vertex coordinates from the moment information we combine established numerical algorithms such as generalized eigenvalue computation and linear interval interpolation. Numerical illustrations are given for the reconstruction of 2-d and 3-d convex polytopes.

MSC:
44A60 Moment problems
41A63 Multidimensional problems (should also be assigned at least one other classification number from Section 41-XX)
65F35 Numerical computation of matrix norms, conditioning, scaling
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Baldoni, V; Berline, N; De Loera, JA; Köppe, M; Vergne, M, How to integrate a polynomial over a simplex, Math. Comp., 80, 297-325, (2011) · Zbl 1216.68120
[2] Beck, M., Robins, S.: Computing the continuous discretely. Undergraduate Texts in Mathematics. Springer, New York (2007) · Zbl 1114.52013
[3] Beckermann, B, The condition number of real Vandermonde, Krylov and positive definite Hankel matrices, Numer. Math., 85, 553-577, (2000) · Zbl 0965.15003
[4] Beckermann, B; Golub, GH; Labahn, G, On the numerical condition of a generalized Hankel eigenvalue problem, Numer. Math., 106, 41-68, (2007) · Zbl 1121.65036
[5] Cabay, S; Meleshko, R, A weakly stable algorithm for Padé approximants and the inversion of Hankel matrices, SIAM J. Matrix Anal. Appl., 14, 735-765, (1993) · Zbl 0779.65009
[6] Cuyt, A; Golub, G; Milanfar, P; Verdonk, B, Multidimensional integral inversion, with applications in shape reconstruction, SIAM J. Sci. Comput., 27, 1058-1070, (2005) · Zbl 1099.65128
[7] Davis, PJ, Triangle formulas in the complex plane, Math. Comp., 18, 569-577, (1964) · Zbl 0121.11801
[8] Demmel, J.W.: Applied numerical linear algebra. Society for Industrial and Applied Mathematics. SIAM, PA (1997) · Zbl 0879.65017
[9] Elad, M; Milanfar, P; Golub, GH, Shape from moments—an estimation theory perspective, IEEE Trans. Signal Process., 52, 1814-1829, (2004) · Zbl 1369.62145
[10] Feldmann, S; Heinig, G, Vandermonde factorization and canonical representations of block Hankel matrices, Linear Algebra Appl., 241-243, 247-278, (1996) · Zbl 0862.15009
[11] Gautschi, W, Optimally conditioned Vandermonde matrices, Numer. Math., 24, 1-12, (1975) · Zbl 0316.65005
[12] Giesbrecht, M; Labahn, G; Lee, W-S, Symbolic-numeric sparse interpolation of multivariate polynomials, J. Symbolic Comput., 44, 943-959, (2009) · Zbl 1167.65003
[13] Golub, GH; Pereyra, V, Separable nonlinear least squares: the variable projection method and its applications, Inverse Probl., 19, r1—r26, (2003) · Zbl 1022.65014
[14] Golub, G.H., Van Loan, C.F.: Matrix computations, volume 3 of Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore, MD (1983)
[15] 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/00) · Zbl 0956.65030
[16] Gravin, N; Lasserre, J; Pasechnik, DV; Robins, S, The inverse moment problem for convex polytopes, Discrete Comput. Geom., 48, 596-621, (2012) · Zbl 1285.68198
[17] Gravin, N., Nguyen, D., Pasechnik, D., Robins, S.: The inverse moment problem for convex polytopes: implementation aspects (2014). ArXiv e-prints, 1409.3130 · Zbl 0121.11801
[18] Gustafsson, B; He, C; Milanfar, P; Putinar, M, Reconstructing planar domains from their moments, Inverse Probl., 16, 1053-1070, (2000) · Zbl 0959.44010
[19] Henrici, P.: Applied and computational complex analysis. Vol. 1. Wiley Classics Library. John Wiley & Sons Inc., New York, 1988. Power series—integration—conformal mapping—location of zeros, Reprint of the 1974 original, A Wiley-Interscience Publication · Zbl 0635.30001
[20] Higham, DJ; Higham, NJ, Structured backward error and condition of generalized eigenvalue problems, SIAM J. Matrix Anal. Appl., 20, 493-512, (1999) · Zbl 0935.65032
[21] Hua, Y; Sarkar, TK, Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise, IEEE Trans. Acoust., Speech, Signal Process., 38, 814-824, (1990) · Zbl 0706.62094
[22] Kaltofen, E; Lee, W-S, Early termination in sparse interpolation algorithms, J. Symbolic Comput., 36, 365-400, (2003) · Zbl 1074.68080
[23] Kaltofen, E.L., Lee, W.-S., Yang, Z.: Fast estimates of Hankel matrix condition numbers and numeric sparse interpolation. In SNC’11, pp 130-136. ACM Press, NY (2011) · Zbl 1347.65037
[24] Lee, W.-S.: From quotient-difference to generalized eigenvalues and sparse polynomial interpolation. In SNC’07, pp 110-116. ACM, New York (2007) · Zbl 1369.62145
[25] Milanfar, P; Verghese, G; Karl, C; Willsky, A, Reconstructing polygons from moments with connections to array processing, IEEE Trans. Signal Process., 43, 432-443, (1995)
[26] Pereyra, V., Scherer, G. (eds.): Exponential Data Fitting and its Applications. Bentham e-books., http://www.benthamscience.com/ebooks/9781608050482 (2010) · Zbl 0458.65022
[27] Riche de Prony, C.B.: Essai expérimental et analytique sur les lois de la dilatabilité des fluides élastique 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. de l’École Polytechnique 1, 24-76 (1795)
[28] Salazar Celis, O; Cuyt, A; Verdonk, B, Rational approximation of vertical segments, Numer. Algorithm., 45, 375-388, (2007) · Zbl 1151.41011
[29] Sheynin, S; Tuzikov, A, Explicit formulae for polyhedra moments, Pattern Recogn. Lett., 22, 1103-1109, (2001) · Zbl 1013.68184
[30] Wilkinson, JH, Kronecker’s canonical form and the QZ algorithm, Linear Algebra Appl., 28, 285-303, (1979) · Zbl 0458.65022
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.