×

A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search. (English) Zbl 1299.65065

Summary: The alternating nonnegative least squares (ANLS) method is commonly used for solving nonnegative tensor factorization problems. In this paper, we focus on an algorithmic improvement of this method. We present a proximal ANLS (PANLS) algorithm to enforce convergence. To speed up the PANLS method, we propose to combine it with a periodic enhanced line search strategy. The resulting algorithm, PANLS/PELS, converges to a critical point of the nonnegative tensor factorization problem under mild conditions. We also provide some numerical results comparing the ANLS and PANLS/PELS methods.

MSC:

65F20 Numerical solutions to overdetermined systems, pseudoinverses
15A69 Multilinear algebra, tensor calculus
65K05 Numerical mathematical programming methods
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] B. W. Bader, T. G. Kolda: Tensor toolbox for Matlab, version 2.2. http://csmr.ca.sandia.gov/ tgkolda/TensorToolbox/ (2008).
[2] R. Bro: PARAFAC. Tutorial and applications. Chemometrics and Intelligent Laboratory Systems 38 (1997), 149-171.
[3] R. Bro: Multi-way Analysis in the Food Industry: Models, Algorithms, and Applications. Ph.D. thesis. University of Amsterdam, Amsterdam, 1998.
[4] R. Bro: Exploratory study of sugar production using fluorescence spectroscopy and multi-way analysis. Chemometrics and Intelligent Laboratory Systems 46 (1999), 133-147.
[5] J. D. Carroll, J.-J. Chang: Analysis of individual differences in multidimensional scaling via an N-way generalization of ‘Eckart-Young’ decomposition. Psychometrika 35 (1970), 283-319. · Zbl 0202.19101
[6] A. Cichocki, R. Zdunek, S. Amari: Nonnegative matrix and tensor factorization. IEEE Signal Processing Magazine 25 (2008), 142-145.
[7] A. Cichocki, R. Zdunek, S. Choi, R. Plemmons, S. Amari: Non-negative tensor factorization using alpha and beta divergences. Proc. of the 32nd International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Honolulu, April 2007. · Zbl 1178.68447
[8] A. Cichocki, R. Zdunek, S. Choi, R. Plemmons, S. Amari: Novel multi-layer non-negative tensor factorization with sparsity constraints. Adaptive and Natural Computing Algorithms. Lecture Notes in Computer Science 4432. Proc. of the 8th International Conference on Adaptive and Natural Computing Algorithms, Warsaw, Poland, April 2007, Springer, Berlin. · Zbl 1186.94262
[9] A. Cichocki, R. Zdunek, A. H. Phan, S. Amari: Nonnegative Matrix and Tensor Factorizations, Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley, Chichester, 2009.
[10] P. Comon, X. Luciani, A. L. F. de Almeida: Tensor decompositions, alternating least squares and other tales. Journal of Chemometrics 23 (2009), 393-405.
[11] I. S. Dhillon: Fast Newton-type Methods for Nonnegative Matrix and Tensor Approximation. Talk given at the NSF Workshop, Future Directions in Tensor-Based Computation and Modeling, February 2009. · Zbl 1445.62136
[12] M. P. Friedlander, K. Hatz: Computing non-negative tensor factorizations. Optim. Methods Softw. 23 (2008), 631-647. · Zbl 1158.65321
[13] L. Grippo, M. Sciandrone: On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Oper. Res. Lett. 26 (2000), 127-136. · Zbl 0955.90128
[14] L. Han, M. Neumann, U. Prasad: Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization. ETNA, Electron. Trans. Numer. Anal. 36 (2009-2010), 54-82, electronic only. · Zbl 1191.65020
[15] R. A. Harshman: Foundations of the PARAFAC procedure: Models and conditions for an “explanatory” multi-modal factor analysis. UCLA Working Papers in Phonetics 16 (1970), 1-84, http://www.psychology.uwo.ca/faculty/harshman/wpppfac0.pdf.
[16] H. Kim, H. Park, L. Elden: Non-negative tensor factorization based on alternating large-scale non-negativity-constrained least squares. Proceedings of IEEE 7th International Conference on Bioinformatics and Bioengineering (BIBE07), Vol. II. 2007, pp. 1147-1151.
[17] T. G. Kolda, B. W. Bader: Tensor decompositions and applications. SIAM Rev. 51 (2009), 455-500. · Zbl 1173.65029
[18] D. D. Lee, H. S. Seung: Learning the parts of objects by non-negative matrix factorization. Nature 401 (1999), 788-791. · Zbl 1369.68285
[19] L. Lim, P. Comon: Nonnegative approximations of nonnegative tensors. Journal of Chemometrics 23 (2009), 432-441.
[20] B. C. Mitchell, D. S. Burdick: Slowly converging PARAFAC sequences: Swamps and two-factor degeneracies. Journal of Chemometrics 8 (1994), 155-168.
[21] M. Mørup, L. K. Hansen, S. M. Arnfred: Algorithms for sparse nonnegative Tucker decompositions. Neural Comput. 20 (2008), 2112-2131. · Zbl 1178.68447
[22] D. Nion, L. De Lathauwer: An enhanced line search scheme for complex-valued tensor decompositions. Application in DS-CDMA. Signal Process. 88 (2008), 749-755. · Zbl 1186.94262
[23] P. Paatero: A weighted non-negative least squares algorithm for three-way ‘PARAFAC’ factor analysis. Chemometrics and Intelligent Laboratory Systems 38 (1997), 223-242.
[24] P. Paatero, U. Tapper: Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5 (1994), 111-126.
[25] M. Rajih, P. Comon, R. A. Harshman: Enhanced line search: a novel method to accelerate PARAFAC. SIAM J. Matrix Anal. Appl. 30 (2008), 1128-1147. · Zbl 1168.65313
[26] W. S. Rayens, B. C. Mitchell: Two-factor degeneracies and a stabilization of PARAFAC. Chemometrics and Intelligent Laboratory Systems 38 (1997), 173-181.
[27] R. T. Rockafellar: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976), 877-898. · Zbl 0358.90053
[28] J.-P. Royer, N. Thirion-Moreau, P. Comon: Computing the polyadic decomposition of nonnegative third order tensors. Signal Process. 91 (2011), 2159-2171. · Zbl 1219.94048
[29] Shashua, A.; Hazan, T., Non-negative tensor factorization with applications to statistics and computer vision, 792-799 (2005), New York
[30] A. Smilde, R. Bro, P. Geladi: Multi-way Analysis: Applications in the Chemical Sciences. Wiley, Chichester, 2004.
[31] G. Tomasi, R. Bro: A comparison of algorithms for fitting the PARAFAC model. Comput. Stat. Data Anal. 50 (2006), 1700-1734. · Zbl 1445.62136
[32] MATLAB 7.5.0. The Mathworks (2008).
[33] Tensor Package. http://www.i3s.unice.fr/ pcomon/TensorPackage.html. · Zbl 1445.62136
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.