×

Tensor decomposition and homotopy continuation. (English) Zbl 1377.65057

Summary: A computationally challenging classical elimination theory problem is to compute polynomials which vanish on the set of tensors of a given rank. By moving away from computing polynomials via elimination theory to computing pseudowitness sets via numerical elimination theory, we develop computational methods for computing ranks and border ranks of tensors along with decompositions. More generally, we present our approach using joins of any collection of irreducible and nondegenerate projective varieties \(X_1,\ldots,X_k\subset\mathbb{P}^N\) defined over \(\mathbb{C}\). After computing ranks over \(\mathbb{C}\), we also explore computing real ranks. A variety of examples are included to demonstrate the numerical algebraic geometric approaches.

MSC:

65H10 Numerical computation of solutions to systems of equations
14Q15 Computational aspects of higher-dimensional varieties
15A69 Multilinear algebra, tensor calculus
13P05 Polynomials, factorization in commutative rings

Software:

SeDiMO; PHCpack; Bertini
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Abo, H.; Ottaviani, G.; Peterson, C., Induction for secant varieties of Segre varieties, Trans. Am. Math. Soc., 361, 2, 767-792 (2009) · Zbl 1170.14036
[2] Abo, H.; Ottaviani, G.; Peterson, C., Non-defectivity of Grassmannians of planes, J. Algebraic Geom., 21, 1, 1-20 (2012) · Zbl 1242.14050
[3] Achilles, R.; Manaresi, M.; Schenzel, P., A degree formula for secant varieties of curves, Proc. Edinb. Math. Soc., 57, 305-322 (2014) · Zbl 1300.14032
[4] Alekseev, V. B.; Smirnov, A. V., On the exact and approximate bilinear complexities of multiplication of \(4 \times 2\) and \(2 \times 2\) matrices, Proc. Steklov Inst. Math., 282, 123-139 (2013) · Zbl 1317.68061
[5] Alexander, J.; Hirschowitz, A., Polynomial interpolation in several variables, J. Algebraic Geom., 4, 2, 201-222 (1995) · Zbl 0829.14002
[6] Allman, E. S.; Rhodes, J. A., Phylogenetic ideals and varieties for the general Markov model, Adv. Appl. Math., 40, 2, 127-148 (2008) · Zbl 1131.92046
[7] Aubry, P.; Rouillier, F.; Safey El Din, M., Real solving for positive dimensional systems, J. Symb. Comput., 34, 6, 543-560 (2002) · Zbl 1046.14031
[8] Ballico, E., On the typical rank of real polynomials (or symmetric tensors) with a fixed border rank, Acta Math. Vietnam., 39, 3, 367-378 (2014) · Zbl 1308.14054
[9] Banchi, M., Rank and border rank of real ternary cubics, Boll. Unione Mat. Ital., 8, 1, 65-80 (2015) · Zbl 1332.15058
[10] Bates, D. J.; Hauenstein, J. D.; McCoy, T. M.; Peterson, C.; Sommese, A. J., Recovering exact results from inexact numerical data in algebraic geometry, Exp. Math., 22, 1, 38-50 (2013) · Zbl 1284.14084
[11] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Bertini: software for numerical algebraic geometry, available at · Zbl 1143.65344
[12] Bates, D. J.; Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Numerically Solving Polynomial Systems with Bertini, Software Environ. Tools, vol. 25 (2013), SIAM: SIAM Philadelphia · Zbl 1295.65057
[13] Bates, D. J.; Oeding, L., Toward a Salmon conjecture, Exp. Math., 20, 3, 358-370 (2011) · Zbl 1262.14056
[14] Baur, K.; Draisma, J.; de Graaf, W., Secant dimensions of minimal orbits: computations and conjectures, Exp. Math., 16, 2, 239-250 (2007) · Zbl 1162.14038
[15] Bernardi, A.; Gimigliano, A.; Idà, M., Computing symmetric rank for symmetric tensors, J. Symb. Comput., 46, 34-53 (2011) · Zbl 1211.14057
[16] Bernardi, A.; Brachat, J.; Mourrain, B., A comparison of different notions of ranks of symmetric tensors, Linear Algebra Appl., 460, 205-230 (2014) · Zbl 1298.15034
[17] Bernardi, A.; Ranestad, K., On the cactus rank of cubic forms, J. Symb. Comput., 50, 291-297 (2013) · Zbl 1258.14063
[18] Bernardi, A.; Vanzo, D., A new class of non-identifiable skew symmetric tensors (2016), preprint
[19] Bini, D.; Capovani, M.; Romani, F.; Lotti, G., \(O(n^{2.7799})\) complexity for \(n \times n\) approximate matrix multiplication, Inf. Process. Lett., 8, 5, 234-235 (1979) · Zbl 0395.68048
[20] Blekherman, G., Typical real ranks of binary forms, Found. Comput. Math., 15, 3, 793-798 (2015) · Zbl 1330.14096
[21] Blekherman, G.; Hauenstein, J. D.; Ottem, J. C.; Ranestand, K.; Sturmfels, B., Algebraic boundaries of Hilbert’s SOS cones, Compos. Math., 148, 6, 1717-1735 (2012) · Zbl 1273.13043
[22] Blekherman, G.; Teitler, Z., On maximum, typical, and generic ranks, Math. Ann., 362, 3, 1021-1031 (2015) · Zbl 1326.15034
[23] Boji, M.; Carlini, E.; Geramita, A. V., Monomials as sums of powers: the real binary case, Proc. Am. Math. Soc., 139, 3039-3043 (2011) · Zbl 1225.14048
[24] Buczyńska, W.; Buczyński, J., On differences between the border rank and the smoothable rank of a polynomial, Glasg. Math. J., 57, 401-413 (2015) · Zbl 1350.14044
[25] Catalisano, M. V.; Geramita, A. V.; Gimigliano, A., Secant varieties of Grassmann varieties, Proc. Am. Math. Soc., 133, 3, 633-642 (2005) · Zbl 1077.14065
[26] Causa, A.; Re, R., On the maximum rank of a real binary form, Ann. Mat. Pura Appl., 190, 1, 55-59 (2011) · Zbl 1222.14123
[27] Chevalier, P.; Albera, L.; Ferreol, A.; Comon, P., On the virtual array concept for higher order array processing, IEEE Trans. Signal Process., 53, 1254-1271 (2005) · Zbl 1370.94091
[28] Comas, G.; Seiguer, M., On the rank of a binary form, Found. Comput. Math., 11, 1, 65-78 (2011) · Zbl 1211.14059
[29] Comon, P., Independent component analysis, (Lacoume, J. L., Higher-Order Statistics (1992), Elsevier), 29-38
[30] Comon, P., Tensor decompositions, (McWhirter, J. G.; Proudler, I. K., Mathematics in Signal Processing V (2002), Clarendon Press: Clarendon Press Oxford, UK), 1-24 · Zbl 1014.65007
[31] Comon, P.; Jutten, C., Handbook of Blind Source Separation: Independent Component Analysis and Applications (2010), Academic Press: Academic Press London, UK
[32] Comon, P.; Ottaviani, G., On the typical rank of real binary forms, Linear Multilinear Algebra, 60, 6, 657-667 (2012) · Zbl 1248.15021
[33] Coppersmith, D.; Winograd, S., Matrix multiplication via arithmetic progressions, J. Symb. Comput., 9, 3, 251-280 (1990) · Zbl 0702.65046
[34] Cox, D.; Sidman, J., Secant varieties of toric varieties, J. Pure Appl. Algebra, 209, 3, 651-669 (2007) · Zbl 1115.14045
[35] Cueto, M. A.; Tobis, E. A.; Yu, J., An implicitization challenge for binary factor analysis, J. Symb. Comput., 45, 12, 1296-1315 (2010) · Zbl 1203.14057
[36] Daleo, N. S., Algorithms and Applications in Numerical Elimination Theory (2015), North Carolina State University, PhD dissertation
[37] Daleo, N. S.; Hauenstein, J. D., Numerically deciding the arithmetically Cohen-Macaulayness of a projective scheme, J. Symb. Comput., 72, 128-146 (2016) · Zbl 1329.14108
[38] Daleo, N. S.; Hauenstein, J. D., Numerically testing generically reduced projective schemes for the arithmetic Gorenstein property, (Lect. Notes Comput. Sci., vol. 9582 (2016)), 137-142 · Zbl 1460.14106
[39] Daleo, N. S.; Hauenstein, J. D.; Oeding, L., Computations and equations for Segre-Grassmann hypersurfaces, Port. Math., 73, 1, 71-90 (2016) · Zbl 1350.14034
[40] de Lathauwer, L.; Castaing, J., Tensor-based techniques for the blind separation of DS-CDMA signals, Signal Process., 87, 2, 322-336 (2007) · Zbl 1186.94413
[41] Draisma, J.; Horobeţ, E.; Ottaviani, G.; Sturmfels, B.; Thomas, R., The Euclidean distance degree of an algebraic variety, Found. Comput. Math., 16, 1, 99-149 (2016) · Zbl 1370.51020
[42] Eisert, J.; Gross, D., Multiparticle entanglement, (Bruß, Dagmar; etal., Lectures on Quantum Information. Lectures on Quantum Information, Phys. Textbook (2007), Wiley-VCH: Wiley-VCH Weinheim), 237-252 · Zbl 1138.81353
[43] Ellingsrud, G.; Stromme, S. A., Bott’s formula and enumerative geometry, J. Am. Math. Soc., 9, 175-193 (1996) · Zbl 0856.14019
[44] Griffin, Z. A.; Hauenstein, J. D., Real solutions to systems of polynomial equations and parameter continuation, Adv. Geom., 15, 2, 173-187 (2015) · Zbl 1309.65056
[45] Gurevich, G. B., Foundations of the Theory of Algebraic Invariants (1964), P. Noordhoff Ltd.: P. Noordhoff Ltd. Groningen · Zbl 0128.24601
[46] Gurevich, G. B., Sur les trivecteurs dans l’espace à sept dimensions, Dokl. Akad. Nauk SSSR, III, 567-569 (1934) · JFM 60.0685.03
[47] Hauenstein, J. D., Numerically computing real points on algebraic sets, Acta Appl. Math., 125, 1, 105-119 (2013) · Zbl 1269.65048
[48] Hauenstein, J. D.; Ikenmeyer, C.; Landsberg, J. M., Equations for lower bounds on border rank, Exp. Math., 22, 4, 372-383 (2013) · Zbl 1361.68098
[49] Hauenstein, J. D.; Liddell, A. C., Certified predictor-corrector tracking for Newton homotopies, J. Symb. Comput., 74, 239-254 (2016) · Zbl 1329.65110
[50] Hauenstein, J. D.; Mourrain, B.; Szanto, A., On deflation and multiplicity structure, J. Symb. Comput., 83, 228-253 (2017) · Zbl 1387.13063
[51] Hauenstein, J. D.; Oeding, L.; Ottaviani, G.; Sommese, A. J., Homotopy techniques for tensor decomposition and perfect identifiability, in press · Zbl 1440.15019
[52] Hauenstein, J. D.; Sommese, A. J., Membership tests for images of algebraic sets by linear projections, Appl. Math. Comput., 219, 12, 6809-6818 (2013) · Zbl 1285.14066
[53] Hauenstein, J. D.; Sommese, A. J., Witness sets of projections, Appl. Math. Comput., 217, 7, 3349-3354 (2010) · Zbl 1203.14072
[54] Hauenstein, J. D.; Sommese, A. J.; Wampler, C. W., Regenerative cascade homotopies for solving polynomial systems, Appl. Math. Comput., 218, 4, 1240-1246 (2011) · Zbl 1231.65190
[55] Hauenstein, J. D.; Wampler, C. W., Unification and extension of intersection algorithms in numerical algebraic geometry, Appl. Math. Comput., 293, 226-243 (2017) · Zbl 1411.65075
[56] Hauenstein, J. D.; Wampler, C. W., Isosingular sets and deflation, Found. Comput. Math., 13, 3, 371-403 (2013) · Zbl 1276.65029
[57] Iarrobino, A. A.; Kanev, V., Power Sums, Gorenstein Algebras, and Determinantal Loci, Lect. Notes Math., vol. 1721 (1999), Springer-Verlag: Springer-Verlag Berlin, Appendix C by Iarrobino and Steven L. Kleiman · Zbl 0942.14026
[58] Jiang, T.; Sidiropoulos, N. D., Kruskal’s permutation lemma and the identification of CANDECOMP/PARAFAC and bilinear models with constant modulus constraints, IEEE Trans. Signal Process., 52, 9, 2625-2636 (2004) · Zbl 1369.94186
[59] Kolda, T. G.; Bader, B. W., Tensor decompositions and applications, SIAM Rev., 51, 3, 455-500 (2009) · Zbl 1173.65029
[60] Landsberg, J. M., Tensors: Geometry and Applications, Grad. Stud. Math., vol. 128 (2012), American Mathematical Society: American Mathematical Society Providence, RI · Zbl 1238.15013
[61] Landsberg, J. M.; Ryder, N., On the geometry of border rank algorithms for \(n \times 2\) and \(2 \times 2\) matrix multiplication, Exp. Math., 26, 3, 275-286 (2016) · Zbl 1409.68333
[62] Landsberg, J. M.; Teitler, Z., On the ranks and border ranks of symmetric tensors, Found. Comput. Math., 10, 3, 339-366 (2010) · Zbl 1196.15024
[63] Long, C.; Sullivant, S., Tying up loose strands: defining equations of the strand symmetric model, J. Algebraic Stat., 6, 1, 17-23 (2015) · Zbl 1346.92047
[64] Martin del Campo, A.; Rodriguez, J. I., Critical points via monodromy and local methods, J. Symb. Comput., 79, 3, 559-574 (2017) · Zbl 1365.14003
[65] McCullagh, P., Tensor Methods in Statistics, Monogr. Stat. Appl. Probab. (1987), Chapman & Hall: Chapman & Hall London · Zbl 0732.62003
[66] Morgan, A. P.; Sommese, A. J., Coefficient-parameter polynomial continuation, Appl. Math. Comput.. Appl. Math. Comput., Appl. Math. Comput., 51, 2, 207-160 (1992), Errata: · Zbl 0755.65050
[67] Oeding, L.; Ottaviani, G., Eigenvectors of tensors and algorithms for Waring decomposition, J. Symb. Comput., 54, 9-35 (2013) · Zbl 1277.15019
[68] Ottaviani, G.; Spaenlehauer, P.-J.; Sturmfels, B., Exact solutions in structured low-rank approximation, SIAM J. Matrix Anal. Appl., 35, 4, 1521-1542 (2014) · Zbl 1318.14057
[69] Ranestad, K., The degree of the secant variety and the join of monomial curves, Collect. Math., 57, 1, 27-41 (2006) · Zbl 1147.14306
[70] Rouillier, F.; Roy, M.-F.; Safey El Din, M., Finding at least one point in each connected component of a real algebraic set defined by a single equation, J. Complex., 16, 4, 716-750 (2000) · Zbl 1009.14010
[71] Schouten, J. A., Klassifizierung der alternierenden Gröszen dritten Grades in 7 Dimensionen, Rend. Circ. Mat. Palermo, 55, 1, 137-156 (1931) · JFM 57.0975.01
[72] Schultz, T.; Seidel, H. P., Estimating crossing fibers: a tensor decomposition approach, IEEE Trans. Vis. Comput. Graph., 48, 6, 1635-1642 (2008)
[73] Seidenberg, A., A new decision method for elementary algebra, Ann. Math. (2), 60, 365-374 (1954) · Zbl 0056.01804
[74] Sidiropoulos, N. D.; Giannakis, G. B.; Bro, R., Blind PARAFAC receivers for DS-CDMA systems, IEEE Trans. Signal Process., 48, 3, 810-823 (2000)
[75] Smilde, A.; Bro, R.; Geladi, P., Multi-Way Analysis (2004), Wiley
[76] Smirnov, A. V., The bilinear complexity and practical algorithms for matrix multiplication, Zh. Vychisl. Mat. Mat. Fiz., 53, 12, 1970-1984 (2013) · Zbl 1313.65094
[77] Sommese, A. J.; Verschelde, J., Numerical homotopies to compute generic points on positive dimensional algebraic sets, J. Complex., 16, 3, 572-602 (2000) · Zbl 0982.65070
[78] Sommese, A. J.; Verschelde, J.; Wampler, C. W., Numerical irreducible decomposition using projections from points on components, (Contemp. Math., vol. 206 (2001)), 37-51 · Zbl 1061.68593
[79] Sommese, A. J.; Verschelde, Jan; Wampler, C. W., Numerical irreducible decomposition using PHCpack, (Joswig, M.; Takayama, N., Mathematics and Visualization (2003), Springer-Verlag), 109-130 · Zbl 1027.65066
[80] Sommese, A. J.; Wampler, C. W., The Numerical Solution of Systems of Polynomials Arising in Engineering and Science (2005), World Scientific Press: World Scientific Press Singapore · Zbl 1091.65049
[81] Strassen, V., Rank and optimal computation of generic tensors, Linear Algebra Appl., 52, 645-685 (1983) · Zbl 0514.15018
[82] Sylvester, J. J., Sur une extension d’un théorème de Clebsh relatif aux courbes du quatrième degré, C. R. Math. Acad. Sci. Paris, 102, 1532-1534 (1886) · JFM 18.0695.06
[83] Valiant, L. G., Quantum computers that can be simulated classically in polynomial time, (Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing (2001), ACM: ACM New York), 114-123, (electronic) · Zbl 1323.68283
[84] Wu, W.; Reid, G., Finding points on real solution components and applications to differential polynomial systems, (ISSAC 2013 (2013), ACM: ACM New York), 339-346 · Zbl 1360.14145
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.