L1-NORM TENSOR DATA ANALYSIS: THEORY AND ALGORITHMS

Background: Modern datasets are collected across diverse sensing modalities and are naturally stored and processed in the form of N-way arrays, also known as tensors. Tucker tensor decomposition is a standard method for the analysis and compression of tensor data. Tucker finds a plethora of applications across fields of science and engineering, such as communications, data analytics, machine intelligence, pattern recognition, and computer vision. From an algorithmic standpoint, Tucker is typically implemented by means of the Higher-Order Singular-Value Decomposition (HOSVD) algorithm, or the Higher-Order Orthogonal Iterations (HOOI) algorithm.

Motivation: Conventional Tucker decomposition tries to minimize the L2-norm of the residual-error in the low-rank approximated tensor that derives by multi-way projection of the original tensor onto the spans of N sought-after orthonormal bases –or, equivalently, Tucker tries to maximize the L2-norm of this multi-way projection. Due to its reliance to the L2-norm, whether it is implemented by means of HOSVD or HOOI, Tucker decomposition has been shown to be very sensitive against faulty entries within the processed tensor. This outlier sensitivity of Tucker is often attributed to its L2/Frobenius norm based formulation.

Contributions: In this line of research, we set theoretical foundations and develop algorithms for reliable L1-norm based tensor analysis. Our contributions are as follows. We present generalized L1-Tucker decomposition for N-way tensors. For the special case of (N=3)-way tensors, we show that rank-1 L1-Tucker2 can be cast to combinatorial optimization and, therefore, solved exactly. Moreover, for N=3, we propose two algorithms that approximate the solution to general rank Tucker2 decomposition efficiently; one that follows an alternating-maximization approach and another that conducts optimal single bit-flips and employs a subspace deflation approach. Thereafter, we consider general N-way tensors and develop and propose two new algorithmic frameworks for the solution of L1-Tucker/L1-Tucker2, namely L1-norm Higher-Order SVD (L1-HOSVD) and L1-norm Higher-Order Orthogonal Iterations (L1-HOOI). We provide complete convergence analysis for L1-HOOI, as well as complexity analysis for L1-HOSVD and L1-HOOI. Finally, we develop a dynamic L1-Tucker solver, appropriate for streaming tensor measurements which is capable of (i) identifying/suppressing outliers on-the-fly and (ii) dynamically updating the decomposition when a change in the underlying structure of the data occurs. We conduct extensive numerical studies on both synthetic and real-world tensor datasets. Our studies illustrate that L1-Tucker/L1-Tucker2 solvers (1) attain similar (high) performance to that of standard Tucker solvers when the data are nominal/clean and (2) exhibit sturdy resistance against outliers in the processed tensor while significantly outperforming standard Tucker solvers when outliers appear in the processed tensor.


Related Media

Related Publications

  • J4] D. G. Chachlakis, M. Dhanaraj, A. Prater-Bennette, and P. P. Markopoulos, Dynamic L1-norm Tucker Tensor Decomposition. (submitted; under review)
    Preprint @ TechRxiv

  • [J2] D. G. Chachlakis, A. Prater-Bennette, and P. P. Markopoulos, L1-norm Tucker Tensor Decomposition, IEEE Access, November 2019.
    Preprint @ arXiv, IEEE Xplore, Python Codes

  • [J1] P. P. Markopoulos, D. G. Chachlakis, and E. E. Papalexakis, The exact solution to rank-1 L1-norm TUCKER2 decomposition, IEEE Signal Processing Letters, April 2018. Preprint @ arXiv, IEEE Xplore, Python Codes

  • [C14] D. G. Chachlakis, A. Prater-Bennette, and P. P. Markopoulos, L1-norm higher-order orthogonal iterations for robust tensor analysis, in Proceedings 2020 IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE ICASSP 2020), Barcelona, Spain, May 2020.
    IEEE Xplore, Python Codes

  • [C11] K. Tountas, D. G. Chachlakis, P. P. Markopoulos, D. A. Pados, Iteratively Re-weighted L1-norm PCA of Tensor Data, in Proceedings IEEE Asilomar Conference on Signals, Systems, and Computers (IEEE ACSSC 2019), Pacific Grove, CA, November 2019.
    IEEE Xplore

  • [C9] D. G. Chachlakis, M. Dhanaraj, A. Prater-Bennette, and P. P. Markopoulos, Options for multimodal classification based on L1-TUCKER decomposition, in Proceedings SPIE Defense and Commercial Sensing (SPIE DCS 2019), Baltimore, MD, April 2019.
    SPIE Digital Library

  • [C8] P. P. Markopoulos, D. G. Chachlakis, and A. Prater-Bennette, L1-norm Higher-Order Singular-Value Decomposition, in Proceedings IEEE Global Conference on Signal and Information Processing (IEEE GlobalSIP 2018), Anaheim, CA, November 2018.
    IEEE Xplore, Python Codes

  • [C5] D. G. Chachlakis and P. P. Markopoulos, Novel algorithms for exact and efficient L1-norm-based TUCKER2 decomposition, in Proceedings IEEE International Conference on Acoustics, Speech, and Signal Processing (IEEE ICASSP 2018), Calgary, Canada, April 2018.
    IEEE Xplore

  • [C4] D. G. Chachlakis and P. P. Markopoulos, Robust decomposition of 3-way tensors based on L1-norm, in Proceedings SPIE Defense and Commercial Sensing (SPIE DCS 2018), Orlando, FL, April 2018.
    SPIE Digital Library

Collaborator Acknowledgements