| Title:
|
A proximal ANLS algorithm for nonnegative tensor factorization with a periodic enhanced line search (English) |
| Author:
|
Bunker, Douglas |
| Author:
|
Han, Lixing |
| Author:
|
Zhang, Shuhua |
| Language:
|
English |
| Journal:
|
Applications of Mathematics |
| ISSN:
|
0862-7940 (print) |
| ISSN:
|
1572-9109 (online) |
| Volume:
|
58 |
| Issue:
|
5 |
| Year:
|
2013 |
| Pages:
|
493-509 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
nonnegative tensor factorization |
| Keyword:
|
proximal method |
| Keyword:
|
alternating least squares |
| Keyword:
|
enhanced line search |
| Keyword:
|
global convergence |
| MSC:
|
15A69 |
| MSC:
|
65F99 |
| MSC:
|
65K05 |
| idZBL:
|
Zbl 06282093 |
| idMR:
|
MR3104615 |
| DOI:
|
10.1007/s10492-013-0026-2 |
| . |
| Date available:
|
2013-09-14T11:40:03Z |
| Last updated:
|
2020-07-02 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/143429 |
| . |
| Reference:
|
[1] Bader, B. W., Kolda, T. G.: Tensor toolbox for Matlab, version 2.2.http://csmr.ca.sandia.gov/~tgkolda/TensorToolbox/ (2008). |
| Reference:
|
[2] Bro, R.: PARAFAC. Tutorial and applications.Chemometrics and Intelligent Laboratory Systems 38 (1997), 149-171. |
| Reference:
|
[3] Bro, R.: Multi-way Analysis in the Food Industry: Models, Algorithms, and Applications. Ph.D. thesis.University of Amsterdam Amsterdam (1998). |
| Reference:
|
[4] Bro, R.: Exploratory study of sugar production using fluorescence spectroscopy and multi-way analysis.Chemometrics and Intelligent Laboratory Systems 46 133-147 (1999). 10.1016/S0169-7439(98)00181-6 |
| Reference:
|
[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). Zbl 0202.19101, 10.1007/BF02310791 |
| Reference:
|
[6] Cichocki, A., Zdunek, R., Amari, S.: Nonnegative matrix and tensor factorization.IEEE Signal Processing Magazine 25 142-145 (2008). 10.1109/MSP.2008.4408452 |
| Reference:
|
[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. |
| Reference:
|
[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. |
| Reference:
|
[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). |
| Reference:
|
[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). 10.1002/cem.1236 |
| Reference:
|
[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. |
| Reference:
|
[12] Friedlander, M. P., Hatz, K.: Computing non-negative tensor factorizations.Optim. Methods Softw. 23 631-647 (2008). Zbl 1158.65321, MR 2440370, 10.1080/10556780801996244 |
| Reference:
|
[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). Zbl 0955.90128, MR 1746833, 10.1016/S0167-6377(99)00074-7 |
| Reference:
|
[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). Zbl 1191.65020, MR 2779998 |
| Reference:
|
[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). |
| Reference:
|
[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). |
| Reference:
|
[17] Kolda, T. G., Bader, B. W.: Tensor decompositions and applications.SIAM Rev. 51 455-500 (2009). Zbl 1173.65029, MR 2535056, 10.1137/07070111X |
| Reference:
|
[18] Lee, D. D., Seung, H. S.: Learning the parts of objects by non-negative matrix factorization.Nature 401 788-791 (1999). 10.1038/44565 |
| Reference:
|
[19] Lim, L., Comon, P.: Nonnegative approximations of nonnegative tensors.Journal of Chemometrics 23 432-441 (2009). 10.1002/cem.1244 |
| Reference:
|
[20] Mitchell, B. C., Burdick, D. S.: Slowly converging PARAFAC sequences: Swamps and two-factor degeneracies.Journal of Chemometrics 8 155-168 (1994). 10.1002/cem.1180080207 |
| Reference:
|
[21] Mørup, M., Hansen, L. K., Arnfred, S. M.: Algorithms for sparse nonnegative Tucker decompositions.Neural Comput. 20 2112-2131 (2008). Zbl 1178.68447, 10.1162/neco.2008.11-06-407 |
| Reference:
|
[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 |
| Reference:
|
[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). |
| Reference:
|
[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). 10.1002/env.3170050203 |
| Reference:
|
[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). Zbl 1168.65313, MR 2447445, 10.1137/06065577 |
| Reference:
|
[26] Rayens, W. S., Mitchell, B. C.: Two-factor degeneracies and a stabilization of PARAFAC.Chemometrics and Intelligent Laboratory Systems 38 173-181 (1997). 10.1016/S0169-7439(97)00033-6 |
| Reference:
|
[27] Rockafellar, R. T.: Monotone operators and the proximal point algorithm.SIAM J. Control Optim. 14 877-898 (1976). Zbl 0358.90053, MR 0410483, 10.1137/0314056 |
| Reference:
|
[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 |
| Reference:
|
[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). |
| Reference:
|
[30] Smilde, A., Bro, R., Geladi, P.: Multi-way Analysis: Applications in the Chemical Sciences.Wiley Chichester (2004). |
| Reference:
|
[31] Tomasi, G., Bro, R.: A comparison of algorithms for fitting the PARAFAC model.Comput. Stat. Data Anal. 50 1700-1734 (2006). MR 2230076, 10.1016/j.csda.2004.11.013 |
| Reference:
|
[32] : MATLAB 7.5.0.The Mathworks (2008). |
| Reference:
|
[33] : Tensor Package.http://www.i3s.unice.fr/{\tildapcomon/TensorPackage.html}. Zbl 1197.15001 |
| . |
