Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
nonnegative tensor factorization; proximal method; alternating least squares; enhanced line search; global convergence
nonnegative tensor factorization; proximal method; alternating least squares; enhanced line search; global convergence
Summary:
The Alternating Nonnegative Least Squares (ANLS) method is commonly used for solving nonnegative tensor factorization problems. In this paper, we focus on 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.
References:
[1] Bader, B. W., Kolda, T. G.: Tensor toolbox for Matlab, version 2.2. http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/ (2008).
[2] Bro, R.: PARAFAC. Tutorial and applications. Chemometrics and Intelligent Laboratory Systems 38 (1997), 149-171.
[3] Bro, R.: Multi-way Analysis in the Food Industry: Models, Algorithms, and Applications. Ph.D. thesis. University of Amsterdam Amsterdam (1998).
[4] Bro, R.: Exploratory study of sugar production using fluorescence spectroscopy and multi-way analysis. Chemometrics and Intelligent Laboratory Systems 46 133-147 (1999). DOI 10.1016/S0169-7439(98)00181-6
[5] Carroll, J. D., Chang, J.-J.: Analysis of individual differences in multidimensional scaling via an N-way generalization of `Eckart-Young' decomposition. Psychometrika 35 283-319 (1970). DOI 10.1007/BF02310791 | Zbl 0202.19101
[6] Cichocki, A., Zdunek, R., Amari, S.: Nonnegative matrix and tensor factorization. IEEE Signal Processing Magazine 25 142-145 (2008). DOI 10.1109/MSP.2008.4408452
[7] Cichocki, A., Zdunek, R., Choi, S., Plemmons, R., Amari, S.: 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.
[8] Cichocki, A., Zdunek, R., Choi, S., Plemmons, R., Amari, S.: 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.
[9] Cichocki, A., Zdunek, R., Phan, A. H., Amari, S.: Nonnegative Matrix and Tensor Factorizations, Applications to Exploratory Multi-way Data Analysis and Blind Source Separation. Wiley Chichester (2009).
[10] Comon, P., Luciani, X., Almeida, A. L. F. de: Tensor decompositions, alternating least squares and other tales. Journal of Chemometrics 23 393-405 (2009). DOI 10.1002/cem.1236
[11] Dhillon, I. S.: 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.
[12] Friedlander, M. P., Hatz, K.: Computing non-negative tensor factorizations. Optim. Methods Softw. 23 631-647 (2008). DOI 10.1080/10556780801996244 | MR 2440370 | Zbl 1158.65321
[13] Grippo, L., Sciandrone, M.: On the convergence of the block nonlinear Gauss-Seidel method under convex constraints. Oper. Res. Lett. 26 127-136 (2000). DOI 10.1016/S0167-6377(99)00074-7 | MR 1746833 | Zbl 0955.90128
[14] Han, L., Neumann, M., Prasad, U.: Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization. ETNA, Electron. Trans. Numer. Anal. 36 54-82, electronic only (2009-2010). MR 2779998 | Zbl 1191.65020
[15] Harshman, R. A.: Foundations of the PARAFAC procedure: Models and conditions for an ``explanatory'' multi-modal factor analysis. UCLA Working Papers in Phonetics 16 1-84, http://www.psychology.uwo.ca/faculty/harshman/wpppfac0.pdf (1970).
[16] Kim, H., Park, H., Elden, L.: 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 1147-1151 (2007).
[17] Kolda, T. G., Bader, B. W.: Tensor decompositions and applications. SIAM Rev. 51 455-500 (2009). DOI 10.1137/07070111X | MR 2535056 | Zbl 1173.65029
[18] Lee, D. D., Seung, H. S.: Learning the parts of objects by non-negative matrix factorization. Nature 401 788-791 (1999). DOI 10.1038/44565
[19] Lim, L., Comon, P.: Nonnegative approximations of nonnegative tensors. Journal of Chemometrics 23 432-441 (2009). DOI 10.1002/cem.1244
[20] Mitchell, B. C., Burdick, D. S.: Slowly converging PARAFAC sequences: Swamps and two-factor degeneracies. Journal of Chemometrics 8 155-168 (1994). DOI 10.1002/cem.1180080207
[21] Mørup, M., Hansen, L. K., Arnfred, S. M.: Algorithms for sparse nonnegative Tucker decompositions. Neural Comput. 20 2112-2131 (2008). DOI 10.1162/neco.2008.11-06-407 | Zbl 1178.68447
[22] Nion, D., Lathauwer, L. De: An enhanced line search scheme for complex-valued tensor decompositions. Application in DS-CDMA. Signal Process. 88 749-755 (2008). Zbl 1186.94262
[23] Paatero, P.: A weighted non-negative least squares algorithm for three-way `PARAFAC' factor analysis. Chemometrics and Intelligent Laboratory Systems 38 223-242 (1997).
[24] Paatero, P., Tapper, U.: Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values. Environmetrics 5 111-126 (1994). DOI 10.1002/env.3170050203
[25] Rajih, M., Comon, P., Harshman, R. A.: Enhanced line search: a novel method to accelerate PARAFAC. SIAM J. Matrix Anal. Appl. 30 1128-1147 (2008). DOI 10.1137/06065577 | MR 2447445 | Zbl 1168.65313
[26] Rayens, W. S., Mitchell, B. C.: Two-factor degeneracies and a stabilization of PARAFAC. Chemometrics and Intelligent Laboratory Systems 38 173-181 (1997). DOI 10.1016/S0169-7439(97)00033-6
[27] Rockafellar, R. T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 877-898 (1976). DOI 10.1137/0314056 | MR 0410483 | Zbl 0358.90053
[28] Royer, J.-P., Thirion-Moreau, N., Comon, P.: Computing the polyadic decomposition of nonnegative third order tensors. Signal Process. 91 2159-2171 (2011). Zbl 1219.94048
[29] Shashua, A., Hazan, T.: Non-negative tensor factorization with applications to statistics and computer vision. ICML 2005: Proceedings of the 22nd International Conference on Machine Learning ACM New York 792-799 (2005).
[30] Smilde, A., Bro, R., Geladi, P.: Multi-way Analysis: Applications in the Chemical Sciences. Wiley Chichester (2004).
[31] Tomasi, G., Bro, R.: A comparison of algorithms for fitting the PARAFAC model. Comput. Stat. Data Anal. 50 1700-1734 (2006). DOI 10.1016/j.csda.2004.11.013 | MR 2230076
[32] MATLAB 7.5.0. The Mathworks (2008).
[33] Tensor Package. http://www.i3s.unice.fr/{\tildapcomon/TensorPackage.html} Zbl 1197.15001
Search
Partner of
