×

Total variation based tensor decomposition for multi-dimensional data with time dimension. (English) Zbl 1349.65141

Summary: We study tensors with time dimension which arises in many scientific and engineering applications such as time series gene expression analysis and video analysis. In these applications, we are interested in determining a set of components interacting closely and consistently together over a period of time. The main aim of this paper is to develop a numerical method to compute such constrained CANDECOMP/PARAFAC (CP) decompositions. We make use of the total variation regularization to constrain the time dimension factor in the decomposition in order to obtain a piecewise constant function with respect to time points. The components of the other dimensions corresponding to these time points are closely related. For example, in time series gene expression analysis, a set of genes may regulate a biological process together during a specific time period; in video analysis, a set of image pixels may refer to a foreground object in the video frames. We employ ADMM to solve the resulting optimization problem, and study its convergence. Numerical examples on synthetic and real data sets are used to demonstrate that the proposed total variation based CP decomposition model can provide more accurate and interesting results.

MSC:

65F22 Ill-posedness and regularization problems in numerical linear algebra
15A69 Multilinear algebra, tensor calculus

Software:

EDISA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] De Lathauwer, A multilinear singular value decomposition, SIAM Journal on Matrix Analysis and Applications 21 (4) pp 1253– (2000) · Zbl 0962.15005
[2] Kolda, Tensor decompositions and applications, SIAM Review 51 pp 455– (2009) · Zbl 1173.65029
[3] Hitchcock, Multilple invariants and generalized rank of a p-way matrix or tensor, Journal of Mathematical Physics 7 pp 39– (1927) · JFM 53.0097.01
[4] Hitchcock, The expression of a tensor or a polyadic as a sum of products, Journal of Mathematical Physics 6 pp 164– (1927) · JFM 53.0095.01
[5] Cattell, Parallel proportional profiles and other principles for determining the choice of factors by rotation, Psychometrika 9 (4) pp 267– (1944)
[6] Carroll, Analysis of individual differences in multidimensional scaling via an N-way generalization of Eckart-Young decomposition, Psychometrika 35 (3) pp 283– (1970) · Zbl 0202.19101
[7] Harshman, Foundations of the PARAFAC procedure: models and conditions for an explanatory multi-modal factor analysis, UCLA Working Papers in Phonetics 16 pp 1– (1970)
[8] Möcks, Topographic components model for event-related potentials and some biophysical considerations, IEEE Transactions on Biomedical Engineering 35 pp 482– (1988)
[9] De Lathauwer, Tensor-based techniques for the blind separation of DS-CDMA signal, Signal Processing 87 (2) pp 322– (2007) · Zbl 1186.94413
[10] Sidiropoulos, Khatri-Rao space-time codes, IEEE Transactions on Signal Processing 50 pp 2396– (2002) · Zbl 1369.94449
[11] Shashua A Levin A Linear image coding for regression and classification using the tensor-rank principle Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition Kauai, HI, USA, 2001 42 49
[12] Acar, Proceedings of the IEEE International Conference on Intelligence and Security Informatics pp 256– (2005)
[13] Acar, Proceedings of the IEEE International Conference on Intelligence and Security Informatics pp 213– (2006)
[14] Bader, Survey of Text Mining II, in: Discussion Tracking in Enron Email Using PARAFAC (2008)
[15] Furukawa, EGRW02: Proceedings of the 13th Eurographics Workshop on Rendering pp 257– (2002)
[16] Faber, Recent developments in CANDECOMP/ PARAFAC algorithms: a critical review, Chemometrics and Intelligent Laboratory Systems 65 pp 119– (2003)
[17] Golub, Matrix Computations (1996)
[18] Acar, A scalable optimization approach for fitting canonical tensor decompositions, Journal of Chemometrics 25 (2) pp 67– (2011)
[19] De Sterck, A nonlinear GMRES optimization algorithm for canonical tensor decomposition, SIAM Journal on Scientific Computing 34 (3) pp A1351– (2012) · Zbl 1253.15035
[20] De Silva, Tensor rank and the ill-posedness of the best low-rank approximation problem, SIAM Journal on Matrix Analysis and Applications 30 pp 1084– (2008) · Zbl 1167.14038
[21] Lim, Nonnegative approximations of nonnegative tensors, Journal of Chemometrics 23 pp 432– (2009)
[22] Supper, EDISA: extracting biclusters from multiple time-series of gene expression profiles, BMC Bioinformatics 8 pp 334– (2007) · Zbl 05326261
[23] Li X Ng M Ye Y HAR: hub, authority and relevance scores in multi-relational data for query search SIAM International Conference on Data Mining CA 2012 141 152
[24] Li, MultiComm: finding local community structure in multi-dimensional networks, IEEE Transactions on Knowledge and Data Engineering 26 pp 929– (2014)
[25] Ng, Multi-view foreground segmentation via fourth order tensor learning, Inverse Problems and Imaging 7 pp 885– (2013) · Zbl 1273.15011
[26] Rudin, Nonlinear total variation based noise removal algorithms, Physica D: Nonlinear Phenomena 60 pp 259– (1992) · Zbl 0780.49028
[27] Nesterov, Introductory Lectures on Convex Optimization: A Basic Course (2004) · Zbl 1086.90045
[28] Van Rijsbergen CJ Information Retrieval Butterworth London
[29] Dennis, David: database for annotation, visualization, and integrated discovery, Genome Biology 4 (5) pp 3– (2003)
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.