×

zbMATH — the first resource for mathematics

Best nonnegative rank-one approximations of tensors. (English) Zbl 07141462
MSC:
90C23 Polynomial optimization
15A18 Eigenvalues, singular values, and eigenvectors
15A42 Inequalities involving eigenvalues and eigenvectors
15A69 Multilinear algebra, tensor calculus
90C22 Semidefinite programming
Software:
SDPNAL+; SDPT3; SeDuMi
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] E. Allman, J. Rhodes, B. Sturmfels, and P. Zwiernik, Tensors of nonnegative rank two, Linear Algebra Appl., 473 (2015), pp. 37–53. · Zbl 1312.15033
[2] N. Asgarian and R. Greiner, Using Rank-1 Biclusters to Classify Microarray Data, Department of Computing Science and the Alberta Ingenuity Center for Machine Learning, University of Alberta, Edmonton, Canada, 2006.
[3] A. Ben-Tal and A. Nemirovskii, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, SIAM, Philadelphia, PA, 2001.
[4] S. Bergmann, J. Ihmels, and N. Barkai, Iterative signature algorithm for the analysis of large-scale gene expression data, Phys. Rev. E, 67 (2003), 031902.
[5] M. Biggs, A. Ghodsi, and S. Vavasis, Nonnegative matrix factorization via rank-one downdating, in Proceedings of the International Conference on Machine Learning, 2008.
[6] J. Bochnak, M. Coste, and M.-F. Roy, Real Algebraic Geometry, Springer, Berlin, 1998. · Zbl 0912.14023
[7] R. Bro and S. De Jong, A fast non-negativity-constrained least squares algorithm, J. Chemometrics, 11 (1997), pp. 393–401.
[8] A. Cichocki, R. Zdunek, A. Phan, and S. Amari, Nonnegative Matrix and Tensor Factorizations: Application to Exploratory Multi-Way Data Analysis and Blind Separation, Wiley, Hoboken, NJ, 2009.
[9] J. Cohen and U. Rothblum, Nonnegative ranks, decompositions and factorizations of nonnegative matrices, Linear Algebra Appl., 190 (1993), pp. 149–168. · Zbl 0784.15001
[10] R. Curto and L. Fialkow, Solution of the Truncated Complex Moment Problem for Flat Data, Mem. Amer. Math. Soc. 119, American Mathematical Society, Providence, RI, 1996. · Zbl 0876.30033
[11] L. De Lathauwer, B. De Moor, and J. Vandewalle, A multilinear singular value decomposition, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1253–1278. · Zbl 0962.15005
[12] L. De Lathauwer, B. De Moor, and J. Vandewalle, On the best rank-\(1\) and rank-\((r_1, r_2,\dots,r_n)\) approximation of higher-order tensors, SIAM J. Matrix Anal. Appl., 21 (2000), pp. 1324–1342. · Zbl 0958.15026
[13] O. Debals, M. Van Barel, and L. De Lathauwer, Nonnegative matrix factorization using nonnegative polynomial approximations, IEEE Signal Process. Lett., 24 (2017), pp. 948–952.
[14] P. Dickinson and L. Gijben, On the computational complexity of membership problems for the completely positive cone and its dual, Comput. Optim. Appl., 57 (2014), pp. 403–415. · Zbl 1330.90103
[15] D. FitzGerald, M. Cranitch, and E. Coyle, Non-negative tensor factorisation for sound source separation, in Proceedings of the Irish Signals and Systems Conference, 2005.
[16] M. Friedlander and K. Hatz, Computing nonnegative tensor factorizations, Comput. Optim. Appl., 23 (2008), pp. 631–647. · Zbl 1158.65321
[17] K. Fujisawa, Y. Futakata, M. Kojima, S. Matsuyama, S. Nakamura, K. Nakata, and M. Yamashita, SDPA-M (Semidefinite Programming Algorithm in MATLAB), http://homepage.mac.com/klabtitech/sdpa-homepage/download.html.
[18] M. Garey and D. Johnson, Computers and Intractability, A Guide to the Theory of NP-Completeness, Freeman, New York, NY, 1980. · Zbl 0411.68039
[19] N. Gillis, Approximation et sous-approximation de matrices par factorisation positive: algorithmes, complexité et applications, Master’s Thesis, Université Catholique de Louvain, Louvain-la-Neuve, Belgium, 2006.
[20] G. Hardy, J. Littlewood, and G. Pólya, Inequalities, 2nd ed., Cambridge University Press, Cambridge, UK, 1952.
[21] J. H\aastad, Tensor rank is NP-complete, J. Algorithms, 11 (1990), pp. 644–654.
[22] T. Hazan, S. Polak, and A. Shashua, Sparse image coding using a \(3\) D non-negative tensor factorization, in Proceedings of the 10th IEEE International Conference on Computer Vision, Vol. 1, IEEE Computer Society Press, 2005, pp. 50–57.
[23] S. Hu and G. Li, Convergence rate analysis for the higher order power method in best rank one approximations of tensors, Numer. Math., 140 (2018), pp. 993–1031. · Zbl 1404.65035
[24] K. Huang, N. Sidiropoulos, and A. Liavas, A flexible and efficient algorithmic framework for constrained matrix and tensor factorization, IEEE Trans. Signal Process., 64 (2016), pp. 5052–5065. · Zbl 1414.94253
[25] E. Kofidis and P. Regalia, On the best rank-1 approximation of higher-order supersymmetric tensors, SIAM J. Matrix Anal. Appl., 23 (2002), pp. 863–884. · Zbl 1001.65035
[26] T. Kolda and B. Bader, Tensor decompositions and applications, SIAM Rev., 51 (2009), pp. 455–500.
[27] T. Kolda and J. Mayo, Shifted power method for computing tensor eigenpairs, SIAM J. Matrix Anal. Appl., 32 (2011), pp. 1095–1124. · Zbl 1247.65048
[28] J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM J. Optim., 11 (2001), pp. 796–817. · Zbl 1010.90061
[29] C. Lawson and R. Hanson, Solving Least Squares Problems, Prentice-Hall, Englewood Cliffs, NJ, 1974. · Zbl 0860.65028
[30] D. Lee and H. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), pp. 788–791. · Zbl 1369.68285
[31] B. Levin, On Calculating Maximum Rank-One under Approximations for Positive Arrays, Technical report B-48, Division of Biostatistics, Columbia University, New York.
[32] L.-H. Lim, Tensors and hypermatrices, in Handbook of Linear Algebra, L. Hogben, ed., CRC Press, Boca Raton, FL 2013, Chapter 15.
[33] L.-H. Lim and P. Comon, Nonnegative approximations of nonnegative tensors, J. Chemometrics, 23 (2009), pp. 432–441.
[34] C. Ling, J. Nie, L. Qi, and Y. Ye, Biquadratic optimization over unit spheres and semidefinite programming relaxations, SIAM J. Optim., 20 (2009), pp. 1286–1310. · Zbl 1221.90074
[35] T. Motzkin and E. Straus, Maxima for graphs and a new proof of a theorem of Túran, Canad. J. Math., 17 (1965), pp. 533–540. · Zbl 0129.39902
[36] K. Murty and S. Kabadi, Some NP-complete problems in quadratic and nonlinear programming, Math. Program., 39 (1987), pp. 117–129. · Zbl 0637.90078
[37] J. Nie, Sums of squares methods for minimizing polynomial forms over spheres and hypersurfaces, Front. Math. China, 7 (2012), pp. 321–346. · Zbl 1277.65046
[38] J. Nie, Optimality conditions and finite convergence of Lasserre’s hierarchy, Math. Program., 146 (2014), pp. 97–121. · Zbl 1300.65041
[39] J. Nie, J. Demmel, and B. Sturmfels, Minimizing polynomials via sums of squares over the gradient ideal, Math. Program., 106 (2006), pp. 587–606. · Zbl 1134.90032
[40] J. Nie and M. Schweighofer, On the complexity of Putinar’s Positivstellensatz, J. Complexity, 23 (2007), pp. 135–150. · Zbl 1143.13028
[41] J. Nie and L. Wang, Semidefinite relaxations for best rank-\(1\) tensor approximations, SIAM J. Matrix Anal. Appl., 35 (2014), pp. 1155–1179. · Zbl 1305.65134
[42] J. Nie, Z. Yang, and X. Zhang, A complete semidefinite algorithm for detecting copositive matrices and tensors, SIAM J. Optim., 28 (2018), pp. 2902–2921. · Zbl 1406.15026
[43] J. Nie and X. Zhang, Positive maps and separable matrices, SIAM J. Optim., 26 (2016), pp. 1236–1256. · Zbl 1338.15066
[44] P. Paatero, A weighted non-negative least squares algorithm for three-way “PARAFAC” factor analysis, Chemometrics. Intell. Lab. Syst., 38 (1997), pp. 223–242.
[45] P. Paatero and U. Tapper, Positive matrix factorization: a non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5 (1994), pp. 111–126.
[46] P. Parrilo and B. Sturmfels, Minimizing polynomial functions, in Algorithmic and Quantitative Real Algebraic Geometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 60 American Mathematical Society, Providence, RI 2003, pp. 83–99. · Zbl 1099.13516
[47] J. Pena, J. Vera, and L. Zuluaga, Completely positive reformulations for polynomial optimization, Math. Program., 151 (2014), pp. 405–431. · Zbl 1328.90114
[48] G. Pólya, Über positive Darstellung von Polynomen Vierteljschr, Naturforsch. Ges. Zürich., 73 (1928), pp. 141–145.
[49] V. Powers and B. Reznick, A new bound for Pólya’s theorem with applications to polynomials positive on polyhedra, J. Pure Appl. Algebra, 164 (2001), pp. 221–229. · Zbl 1075.14523
[50] M. Putinar, Positive polynomials on compact semi-algebraic sets, Indiana Univ. Math. J., 42 (1993), pp. 969–984. · Zbl 0796.12002
[51] L. Qi, Symmetric nonnegative tensors and copositive tensors, Linear Algebra Appl., 439 (2013), pp. 228–238. · Zbl 1281.15025
[52] Y. Qi, P. Comon, and L.-H. Lim, Uniqueness of nonnegative tensor approximations, IEEE Trans. Inform. Theory, 62 (2016), pp. 2170–2183. · Zbl 1359.94155
[53] B. Reznick, Some concrete aspects of Hilbert’s 17th problem, Contemp. Math., 253 (2000), pp. 251–272. · Zbl 0972.11021
[54] J.-P. Royer, N. Thirion-Moreau, and P. Comon, Computing the polyadic decomposition of nonnegative third order tensors, Signal Process., 91 (2011), pp. 2159–2171. · Zbl 1219.94048
[55] A. Shashua and T. Hazan, Non-negative tensor factorization with applications to statistics and computer vision, in Proceedings of the 22nd International Conference on Machine Learning, 2005, pp. 792–799.
[56] A. Shashua and A. Levin, Linear image coding for regression and classification using the tensor-rank principle, in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 2001.
[57] A. Shashua, R. Zass, and T. Hazan, Multi-way clustering using super-symmetric non-negative tensor factorization, in Proceedings of the 9th European Conference on Computer Vision, Part IV, 2006, pp. 595–608.
[58] N. Sidiropoulos, L. De Lathauwer, X. Fu, K. Huang, E. Papalexakis, and C. Faloutsos, Tensor decomposition for signal processing and machine learning, IEEE Trans. Signal Process., 65 (2017), pp. 3551–3582. · Zbl 1415.94232
[59] J. Sturm, SeDuMi 1.02: A Matlab toolbox for optimization over symmetric cones, Optim. Methods Softw., 11 & 12 (1999), pp. 625–653. · Zbl 0973.90526
[60] D. Sun, K.-C. Toh, and L. Yang, A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type constraints, SIAM J. Optim., 25 (2015), pp. 882–915. · Zbl 1328.90083
[61] D. Sun, K.-C. Toh, Y. Yuan, and X.-Y. Zhao, SDPNAL+: A MATLAB software for semidefinite programming with bound constraints (version 1.0), Optim. Methods Softw., in press. · Zbl 1432.90104
[62] K.-C. Toh, M. Todd, and R. Tutuncu, SDPT3: A Matlab software package for semidefinite programming, Optim. Methods Softw., 11 (1999), pp. 545–581. · Zbl 0997.90060
[63] S. Vavasis, On the complexity of nonnegative matrix factorization, SIAM J. Optim., 20 (2009), pp. 1364–1377. · Zbl 1206.65130
[64] M. Welling and M. Weber, Positive tensor factorization, Pattern Recogn. Lett., 22 (2001), pp. 1255–1261. · Zbl 0990.68123
[65] L. Yang, D. Sun, and K.-C. Toh, SDPNAL+: A majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints, Math. Program. Comput., 7 (2015), pp. 331–366. · Zbl 1321.90085
[66] X.-Y. Zhao, D. Sun, and K.-C. Toh, A Newton-CG augmented Lagrangian method for semidefinite programming, SIAM J. Optim., 20 (2010), pp. 1737–1765. · Zbl 1213.90175
[67] G. Zhou, A. Cichocki, Q. Zhao, and S. Xie, Efficient nonnegative Tucker decompositions: Algorithms and uniqueness, IEEE Trans. Image Process., 24 (2015), pp. 4990–5003. · Zbl 1408.94841
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.