A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search

Douglas Bunker; Lixing Han; Shu Hua Zhang

Applications of Mathematics (2013)

  • Volume: 58, Issue: 5, page 493-509
  • ISSN: 0862-7940

Abstract

top
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.

How to cite

top

Bunker, Douglas, Han, Lixing, and Zhang, Shu Hua. "A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search." Applications of Mathematics 58.5 (2013): 493-509. <http://eudml.org/doc/260614>.

@article{Bunker2013,
abstract = {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.},
author = {Bunker, Douglas, Han, Lixing, Zhang, Shu Hua},
journal = {Applications of Mathematics},
keywords = {nonnegative tensor factorization; proximal method; alternating least squares; enhanced line search; global convergence; nonnegative tensor factorization; proximal method; alternating least squares methods; enhanced line search; global convergence; numerical results},
language = {eng},
number = {5},
pages = {493-509},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search},
url = {http://eudml.org/doc/260614},
volume = {58},
year = {2013},
}

TY - JOUR
AU - Bunker, Douglas
AU - Han, Lixing
AU - Zhang, Shu Hua
TI - A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search
JO - Applications of Mathematics
PY - 2013
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 58
IS - 5
SP - 493
EP - 509
AB - 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.
LA - eng
KW - nonnegative tensor factorization; proximal method; alternating least squares; enhanced line search; global convergence; nonnegative tensor factorization; proximal method; alternating least squares methods; enhanced line search; global convergence; numerical results
UR - http://eudml.org/doc/260614
ER -

References

top
  1. Bader, B. W., Kolda, T. G., Tensor toolbox for Matlab, version 2.2, http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/ (2008). (2008) 
  2. Bro, R., PARAFAC. Tutorial and applications, Chemometrics and Intelligent Laboratory Systems 38 (1997), 149-171. (1997) 
  3. Bro, R., Multi-way Analysis in the Food Industry: Models, Algorithms, and Applications. Ph.D. thesis, University of Amsterdam Amsterdam (1998). (1998) 
  4. Bro, R., 10.1016/S0169-7439(98)00181-6, Chemometrics and Intelligent Laboratory Systems 46 133-147 (1999). (1999) DOI10.1016/S0169-7439(98)00181-6
  5. Carroll, J. D., Chang, J.-J., 10.1007/BF02310791, Psychometrika 35 283-319 (1970). (1970) Zbl0202.19101DOI10.1007/BF02310791
  6. Cichocki, A., Zdunek, R., Amari, S., 10.1109/MSP.2008.4408452, IEEE Signal Processing Magazine 25 142-145 (2008). (2008) DOI10.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). (2009) 
  10. Comon, P., Luciani, X., Almeida, A. L. F. de, 10.1002/cem.1236, Journal of Chemometrics 23 393-405 (2009). (2009) DOI10.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., 10.1080/10556780801996244, Optim. Methods Softw. 23 631-647 (2008). (2008) Zbl1158.65321MR2440370DOI10.1080/10556780801996244
  13. Grippo, L., Sciandrone, M., 10.1016/S0167-6377(99)00074-7, Oper. Res. Lett. 26 127-136 (2000). (2000) Zbl0955.90128MR1746833DOI10.1016/S0167-6377(99)00074-7
  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). (2009) Zbl1191.65020MR2779998
  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). (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). (2007) 
  17. Kolda, T. G., Bader, B. W., 10.1137/07070111X, SIAM Rev. 51 455-500 (2009). (2009) Zbl1173.65029MR2535056DOI10.1137/07070111X
  18. Lee, D. D., Seung, H. S., 10.1038/44565, Nature 401 788-791 (1999). (1999) DOI10.1038/44565
  19. Lim, L., Comon, P., 10.1002/cem.1244, Journal of Chemometrics 23 432-441 (2009). (2009) DOI10.1002/cem.1244
  20. Mitchell, B. C., Burdick, D. S., 10.1002/cem.1180080207, Journal of Chemometrics 8 155-168 (1994). (1994) DOI10.1002/cem.1180080207
  21. Mørup, M., Hansen, L. K., Arnfred, S. M., 10.1162/neco.2008.11-06-407, Neural Comput. 20 2112-2131 (2008). (2008) Zbl1178.68447DOI10.1162/neco.2008.11-06-407
  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). (2008) Zbl1186.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). (1997) 
  24. Paatero, P., Tapper, U., 10.1002/env.3170050203, Environmetrics 5 111-126 (1994). (1994) DOI10.1002/env.3170050203
  25. Rajih, M., Comon, P., Harshman, R. A., 10.1137/06065577, SIAM J. Matrix Anal. Appl. 30 1128-1147 (2008). (2008) Zbl1168.65313MR2447445DOI10.1137/06065577
  26. Rayens, W. S., Mitchell, B. C., 10.1016/S0169-7439(97)00033-6, Chemometrics and Intelligent Laboratory Systems 38 173-181 (1997). (1997) DOI10.1016/S0169-7439(97)00033-6
  27. Rockafellar, R. T., 10.1137/0314056, SIAM J. Control Optim. 14 877-898 (1976). (1976) Zbl0358.90053MR0410483DOI10.1137/0314056
  28. Royer, J.-P., Thirion-Moreau, N., Comon, P., Computing the polyadic decomposition of nonnegative third order tensors, Signal Process. 91 2159-2171 (2011). (2011) Zbl1219.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). (2005) 
  30. Smilde, A., Bro, R., Geladi, P., Multi-way Analysis: Applications in the Chemical Sciences, Wiley Chichester (2004). (2004) 
  31. Tomasi, G., Bro, R., 10.1016/j.csda.2004.11.013, Comput. Stat. Data Anal. 50 1700-1734 (2006). (2006) MR2230076DOI10.1016/j.csda.2004.11.013
  32. MATLAB 7.5.0, The Mathworks (2008). (2008) 
  33. Tensor Package, http://www.i3s.unice.fr//TensorPackage.html. Zbl1197.15001

NotesEmbed ?

top

You must be logged in to post comments.