×

zbMATH — the first resource for mathematics

Learning algebraic varieties from samples. (English) Zbl 06946762
Summary: We seek to determine a real algebraic variety from a fixed finite subset of points. Existing methods are studied and new methods are developed. Our focus lies on aspects of topology and algebraic geometry, such as dimension and defining polynomials. All algorithms are tested on a range of datasets and made available in a Julia package.

MSC:
13P25 Applications of commutative algebra (e.g., to statistics, control theory, optimization, etc.)
14P25 Topology of real algebraic varieties
62J02 General nonlinear regression
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aamari, E., Kim, J., Chazal, F., Michel, B., Rinaldo, A., Wasserman, L.: Estimating the reach of a manifold. arXiv:1705.04565 · Zbl 1418.62100
[2] Adams, H., Tausz, A.: JavaPlex tutorial. http://www.math.colostate.edu/ adams/research/javaplex_tutorial.pdf. Accessed 24 February 2018
[3] Améndola, C; Faugère, J-C; Sturmfels, B, Moment varieties of Gaussian mixtures, J. Algebr. Stat., 7, 14-28, (2016) · Zbl 1361.13017
[4] Basson, R., Lercier, R., Ritzenthaler, C., Sijsling, J.: An explicit expression of the Lüroth invariant. ISSAC 2013. Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation, pp. 31-36. ACM, New York (2013) · Zbl 1360.68915
[5] Bates, D., Hauenstein, J., Sommese, A., Wampler, C.: Numerically Solving Polynomial Systems with Bertini, Software, Environments, and Tools. SIAM, Philadelphia, PA (2013) · Zbl 1295.65057
[6] Bezanson, J; Edelman, A; Karpinski, S; Shah, V, Julia: a fresh approach to numerical computing, SIAM Rev., 59, 65-98, (2017) · Zbl 1356.68030
[7] Bjoerck, A; Pereyra, V, Solutions of Vandermonde systems of equations, Math. Comput., 24, 893-903, (1970) · Zbl 0221.65054
[8] Blekherman, G., Parrilo, P., Thomas, R.: Semidefinite Optimization and Convex Algebraic Geometry, MOS-SIAM Series on Optimization, vol. 13 (2012) · Zbl 1260.90006
[9] Breiding, P., Timme, S.: HomotopyContinuation.jl—a package for solving systems of polynomial equations in Julia. arXiv:1711.10911 · Zbl 1396.14003
[10] Brown, MW; Martin, S; Pollock, SN; Coutsias, EA; Watson, JP, Algorithmic dimensionality reduction for molecular structure analysis, J. Chem. Phys., 129, 064118, (2008)
[11] Bürgisser, P., Cucker, F., Lairez, P.: Computing the homology of basic semialgebraic sets in weak exponential time. arXiv:1706.07473 · Zbl 1426.14016
[12] Camastra, F, Data dimensionality estimation methods: a survey, Pattern Recogn., 36, 2945-2954, (2003) · Zbl 1059.68100
[13] Camastra, F; Staiano, A, Intrinsic dimension estimation: advances and open problems, Inf. Sci., 328, 26-41, (2016) · Zbl 1392.62171
[14] Carlsson, G, Topology and data, Bull. Am. Math. Soc., 46, 255-308, (2009) · Zbl 1172.62002
[15] Cifuentes, D; Parrilo, P, Sampling algebraic varieties for sum of squares programs, SIAM J. Optim., 27, 2381-2404, (2017) · Zbl 1386.90099
[16] Cox, D., Little, J., O’Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, Undergraduate Texts in Mathematics, 4th edn. Springer, Berlin (2015) · Zbl 1335.13001
[17] Cueto, M.A., Morton, J., Sturmfels, B.: Geometry of the restricted Boltzmann machine. Algebraic Methods in Statistics and Probability. Contemporary Mathematics, vol. 516, pp. 135-153. AMS, Providence (2010) · Zbl 05777868
[18] Daleo, N., Hauenstein, J.: Numerically deciding the arithmetically Cohen-Macaulayness of a projective scheme. J. Symb. Comput. 72, 128-146 (2016) · Zbl 1329.14108
[19] Demmel, J.W.: Applied Numerical Linear Algebra. SIAM, Philadelphia (1997) · Zbl 0879.65017
[20] Deza, M., Laurent, M.: Geometry of Cuts and Metrics, Algorithms and Combinatorics, vol. 15. Springer, Berlin (1997) · Zbl 0885.52001
[21] Diaconis, P; Holmes, S; Shahshahani, M, Sampling from a manifold, Inst. Math. Stat. Collect., 10, 102-125, (2013) · Zbl 1356.62015
[22] Díaz, M., Quiroz, A., Velasco, M.: Local angles and dimension estimation from data on manifolds. arXiv:1805.01577
[23] Draisma, J; Horobeţ, E; Ottaviani, G; Sturmfels, B; Thomas, R, The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16, 99-149, (2016) · Zbl 1370.51020
[24] Drton, M., Sturmfels, B., Sullivant, S.: Lectures on Algebraic Statistics, Oberwolfach Seminars, vol. 39. Birkhäuser, Basel (2009) · Zbl 1166.13001
[25] Dufresne, E., Edwards, P., Harrington, H., Hauenstein, J.: Sampling real algebraic varieties for topological data analysis. arXiv:1802.07716
[26] Eklund, D.: The numerical algebraic geometry of bottlenecks. arXiv:1804.01015
[27] Federer, H, Curvature measures, Trans. Am. Math. Soc., 93, 418-491, (1959) · Zbl 0089.38402
[28] Griffin, Z., Hauenstein, J., Peterson, C., Sommese, A.: Numerical computation of the Hilbert function and regularity of a zero dimensional scheme. Connections Between Algebra. Combinatorics, and Geometry, Springer Proceedings in Mathematics and Statistics, vol. 76, pp. 235-250. Springer, New York (2014) · Zbl 1315.13032
[29] Harris, J.: Algebraic Geometry. A First Course, Graduate Texts in Mathematics, vol. 133. Springer, New York (1992) · Zbl 0779.14001
[30] Henselman, G., Ghrist, R.: Matroid filtrations and computational persistent homology. arXiv:1606.00199
[31] Higham, N.: Accuracy and Stability of Numerical Algorithms, 2nd edn. SIAM, Philadelphia (2002) · Zbl 1011.65010
[32] Horobeţ, E., Weinstein, M.: Offset hypersurfaces and persistent homology of algebraic varieties. arXiv:1803.07281
[33] Howard, R.: The kinematic formula in Riemannian homogeneous spaces. Mem. Am. Math. Soc. 106(509) (1993) · Zbl 0810.53057
[34] Jain, A., Dubes, R.: Algorithms for Clustering Data. Prentice-Hall, Upper Saddle River, NJ (1998) · Zbl 0665.62061
[35] Kileel, J; Kukelova, Z; Pajdla, T; Sturmfels, B, Distortion varieties, Found. Comput. Math., 18, 1043-1071, (2018) · Zbl 1408.14191
[36] Kummer, M., Vinzant, C.: The Chow form of a reciprocal linear space. Michigan Math. J. arXiv:1610.04584
[37] Landsberg, J.M.: Tensors: Geometry and Applications, Graduate Studies in Mathematics, vol. 128. American Mathematical Society, Providence, RI (2012)
[38] Lee, J.A., Verleysen, M.: Nonlinear Dimensionality Reduction. Information Science and Statistics. Springer, New York (2007) · Zbl 1128.68024
[39] Leichtweiss, K, Zur riemannschen geometrie in grassmannschen mannigfaltigkeiten, Math. Z., 76, 334-366, (1961) · Zbl 0113.37102
[40] Levina, E; Bickel, P, Maximum likelihood estimation of intrinsic dimension, Adv. Neural Inf. Process. Syst., 17, 777-784, (2004)
[41] Ma, Y; Yang, A; Derksen, H; Fossum, R, Estimation of subspace arrangements with applications in modeling and segmenting mixed data, SIAM Rev., 50, 413-458, (2008) · Zbl 1147.52010
[42] Martin, S; Thompson, A; Coutsias, EA; Watson, JP, Topology of cyclo-octane energy landscape, J. Chem. Phys., 132, 234115, (2010)
[43] Mezzadri, F, How to generate matrices from the classical compact groups, Not. AMS, 54, 592-604, (2007) · Zbl 1156.22004
[44] Möller, H., Buchberger, B.: The construction of multivariate polynomials with preassigned zeros. Computer Algebra (Marseille 1982). Lecture Notes in Computer Science, vol. 144, pp. 24-31. Springer, Berlin (1982) · Zbl 0549.68026
[45] Mustaţǎ, M.: Graded Betti numbers of general finite subsets of points on projective varieties. Pragmat. 1997 Mat. (Catania) 53, 53-81 (1998) · Zbl 0943.13010
[46] Niyogi, P; Smale, S; Weinberger, S, Finding the homology of submanifolds with high confidence from random samples, Discrete Comput. Geom., 39, 419-441, (2008) · Zbl 1148.68048
[47] Olver, PJ, On multivariate interpolation, Stud. Appl. Math., 116, 201-240, (2006) · Zbl 1145.41311
[48] Pan, VY, How bad are Vandermonde matrices?, SIAM J. Matrix Anal. Appl., 37, 676-694, (2016) · Zbl 1382.15008
[49] Plaumann, D; Sturmfels, B; Vinzant, C, Quartic curves and their bitangents, J. Symb. Comput., 46, 712-733, (2011) · Zbl 1214.14049
[50] Santalo, L.: Integral Geometry and Geometric Probability. Addison-Wesley, Reading (1976) · Zbl 0342.53049
[51] Sturmfels, B; Welker, V, Commutative algebra of statistical ranking, J. Algebra, 361, 264-286, (2012) · Zbl 1316.13042
[52] The Pattern Analysis Lab at Colorado State University: A fractal dimension for measures via persistent homology (Preprint) (2018)
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.