The Exact Solution to Rank-1 L1-norm TUCKER2 Decomposition
This provides a robust decomposition method for outlier-corrupted tensor data, but it is incremental as it builds on existing L1-norm and TUCKER2 concepts.
The paper tackled the problem of rank-1 L1-norm TUCKER2 decomposition for 3-way tensors, proving it is equivalent to combinatorial optimization and deriving the first exact algorithms with exponential and polynomial costs, and showed that L1-TUCKER2 outperforms several existing methods in tensor approximation for outlier-corrupted data.
We study rank-1 {L1-norm-based TUCKER2} (L1-TUCKER2) decomposition of 3-way tensors, treated as a collection of $N$ $D \times M$ matrices that are to be jointly decomposed. Our contributions are as follows. i) We prove that the problem is equivalent to combinatorial optimization over $N$ antipodal-binary variables. ii) We derive the first two algorithms in the literature for its exact solution. The first algorithm has cost exponential in $N$; the second one has cost polynomial in $N$ (under a mild assumption). Our algorithms are accompanied by formal complexity analysis. iii) We conduct numerical studies to compare the performance of exact L1-TUCKER2 (proposed) with standard HOSVD, HOOI, GLRAM, PCA, L1-PCA, and TPCA-L1. Our studies show that L1-TUCKER2 outperforms (in tensor approximation) all the above counterparts when the processed data are outlier corrupted.