×

Computing the polyadic decomposition of nonnegative third order tensors. (English) Zbl 1219.94048

Summary: Computing the minimal polyadic decomposition (also often referred to as canonical decomposition or sometimes Parafac) amounts to finding the global minimum of a coercive polynomial in many variables. In the case of arrays with nonnegative entries, the low-rank approximation problem is well posed. In addition, due to the large dimension of the problem, the decomposition can be rather efficiently calculated with the help of preconditioned nonlinear conjugate gradient algorithms, as subsequently shown, if equipped with an algebraic calculation of the globally optimal stepsize in low dimension. Other algorithms are also studied (gradient and quasi-Newton approaches) for comparisons. Two versions of each algorithm are considered: the enhanced line search version (ELS), and the backtracking version alternating with ELS. Computer simulations are provided and demonstrate the good behavior of these algorithms dedicated to nonnegative arrays, compared to others put forward in the literature. Finally, applications in the context of data analysis illustrate various algorithms. The main advantage of the suggested approach is to explicitly take into account the nonnegative nature of the loading matrices in the problem parameterization, instead of enforcing positive entries by projection. According to the experiments we have run, such an approach also happens to be more robust with respect to possible modeling errors.

MSC:

94A12 Signal theory (characterization, reconstruction, filtering, etc.)
PDFBibTeX XMLCite
Full Text: DOI HAL

References:

[1] Boyd, S.; Vandenberghe, L.: Convex optimization, (March 2004) · Zbl 1058.90049
[2] Bro, R.: PARAFAC: tutorial and applications, Chemometrics intell. Lab. syst. 38, 149-171 (1997)
[3] R. Bro, Multi-way analysis in the food industry: models, algorithms and applications. Ph.D. Thesis, University of Amsterdam, Amsterdam, The Netherlands, 1998.
[4] Carroll, P.; Chang, J. J.: Analysis of individual differences in multi-dimensional scaling via n-way generalization of Eckart–Young decomposition, Psychometrika 35, 283-319 (1970) · Zbl 0202.19101 · doi:10.1007/BF02310791
[5] Cichocki, A.; Zdunek, R.; Phan, A. H.; Amari, S. I.: Non negative matrix and tensor factorizations: application to exploratory multi-way data analysis and blind separation, (2009)
[6] P. Comon, Tensors, usefulness and unexpected properties. In: 15th IEEE Workshop on Statistical Signal Processing (SSP’09), Cardiff, UK, August 31–September 3, 2009, pp. 781–788, keynote.
[7] Comon, P.; Luciani, X.; De Almeida, A. L. F.: Tensor decompositions, alternating least squares and other tales, J. chemometrics 23, No. August, 393-405 (2009)
[8] A. Franc, Etude algébrique des multi-tableaux: apport de l’algèbre tensorielle. Ph.D. Thesis, University of Montepellier II, Montpellier, France, 1992.
[9] Ghennioui, H.; Thirion-Moreau, N.; Moreau, E.; Aboutajdine, D.: Gradient based joint block diagonalization algorithms: application to blind separation of FIR convolutive sources mixtures, EURASIP signal process. 90, No. 6, 1836-1849 (2010) · Zbl 1197.94054 · doi:10.1016/j.sigpro.2009.12.002
[10] R.A. Harshman, Foundation of the PARAFAC procedure: models and conditions for an explanatory multimodal factor analysis, in: UCLA Working Papers in Phonetics, vol. 16, 1970, pp. 1–84.
[11] Hitchcock, F. L.: The expression of a tensor or a polyadic as a sum of products, J. math. Phys. 6, 165-189 (1927) · JFM 53.0095.01
[12] Jiang, J. H.; Wu, H. L.; Li, Y.; Yu, R. Q.: Alternating coupled vectors resolution (ACOVER) method for trilinear analysis of three-way data, J. chemometrics 13, No. 6, 557-578 (1999)
[13] Kolda, T. G.; Bader, B. W.: Tensor decompositions and applications, SIAM rev. 51, No. 3, 455-500 (2009) · Zbl 1173.65029 · doi:10.1137/07070111X
[14] Lickteig, T.: Typical tensorial rank, Linear algebra appl. 69, 95-120 (1985) · Zbl 0575.15013 · doi:10.1016/0024-3795(85)90070-9
[15] Lim, L. H.; Comon, P.: Non negative approximations of nonnegative tensors, J. chemometrics 23, No. August, 432-441 (2009)
[16] Luciani, X.; Mounier, S.; Redon, R.; Bois, A.: A simple correction method of inner filter effects affecting FEEM and its application to the PARAFAC decomposition, Chemometrics intell. Lab. syst. 96, No. 2, 227-238 (2009)
[17] Luenberger, D. G.: Optimization by vector space methods, (1969) · Zbl 0176.12701
[18] Luenberger, D. G.; Ye, Y.: Linear and non linear programming, (2008) · Zbl 1207.90003
[19] Magnus, J. R.; Neudecker, H.: Matrix differential calculus with applications in statistics and econometrics, (2007) · Zbl 0651.15001
[20] S. Mounier, H. Zhao, C. Garnier, R. Redon, Copper complexing properties of dissolved organic matter: PARAFAC treatment of fluorescence quenching, Biogeochemistry (August) 2010, doi:10.1007/s10533-010-9486-6.
[21] Paatero, P.: A weighted non-negative least squares algorithm for three-way PARAFAC factor analysis, Chemometrics intell. Lab. syst. 38, No. 2, 223-242 (1997)
[22] Paatero, P.: The multilinear engine–a table-driven, least squares program for solving multi-linear problems, including the n-way parallel factor analysis model, J. comput. Graph. stat. 8, No. 4, 854-888 (1999)
[23] Paatero, P.: Construction and analysis of degenerate PARAFAC models, J. chemometrics 14, No. 3, 285-299 (2000)
[24] Polak, E.: Optimization algorithms and consistent approximations, (1997) · Zbl 0899.90148
[25] Rajih, M.; Comon, P.; Harshman, R. A.: Enhanced line search: a novel method to accelerate PARAFAC, SIAM J. Matrix anal. Appl. 30, No. 3, 1148-1171 (2008) · Zbl 1168.65313 · doi:10.1137/06065577
[26] J.R. Shewchuk, Introduction to the conjugate gradient method without the agonizing pain, Technical Report, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, August 1994.
[27] Smilde, A.; Bro, R.; Geladi, P.: Multi-way analysis with applications in the chemical sciences, (2004)
[28] G. Tomasi, R. Bro, PARAFAC and missing values, Chemometrics Intell. Lab. Syst. (2004) Volume 75, issue 2, February 2005, pp. 163–180.
[29] Tomasi, G.; Bro, R.: A comparison of algorithms for Fitting the PARAFAC model, Comput. stat. Data anal. 50, No. 7, 1700-1734 (2006) · Zbl 1445.62136
[30] Zhang, Q.; Wang, H.; Plemmons, R.; Pauca, P.: Tensors methods for hyperspectral data processing: a space object identification study, J. opt. Soc. am. A 25, No. 12, 3001-3012 (2008)
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.