An Improved Algorithm for Calculation of the Third-order Orthogonal Tensor Product Expansion by Using Singular Value Decomposition

Authors: Chiharu Okuma, Naoki Yamamoto, Jun Murakami

Abstract:

As a method of expanding a higher-order tensor data to tensor products of vectors we have proposed the Third-order Orthogonal Tensor Product Expansion (3OTPE) that did similar expansion as Higher-Order Singular Value Decomposition (HOSVD). In this paper we provide a computation algorithm to improve our previous method, in which SVD is applied to the matrix that constituted by the contraction of original tensor data and one of the expansion vector obtained. The residual of the improved method is smaller than the previous method, truncating the expanding tensor products to the same number of terms. Moreover, the residual is smaller than HOSVD when applying to color image data. It is able to be confirmed that the computing time of improved method is the same as the previous method and considerably better than HOSVD.

Keywords: Singular value decomposition (SVD), higher-orderSVD (HOSVD), outer product expansion, power method.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084169

References:

[1] Chiharu Okuma, Jun Murakami, and Naoki Yamamoto: Comparison between Higher-order SVD and Third-order Orthogonal Tensor Product Expansion, International Journal Electronics, Communications and Computer Engineering, vol.1, no.2, pp.131-137, 2009.
[2] Jun Murakami, Naoki Yamamoto, and Yoshiaki Tadokoro: High-Speed Computation of 3D Tensor Product Expansion by the Power Method, Electronics and Communications in Japan, Part 3, Vol.85, pp.63-72, 2002.
[3] Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle: A Multilinear Singular Value Decomposition, SIAM Journal on Matrix Analysis and Applications, Vol.21, No.4, pp.1253- 1278, 2000.
[4] Manolis G. Vozalis and Konstantinos G. Margaritis: Applying SVD on Generalized Item-based Filtering, International Journal of Computer Science & Applications, Vol.3, Issue 3, pp.27-51, 2006.
[5] Berkant Savas and Lars Eldén: Handwritten Digit Classification using Higher order Singular Value Decomposition, Pattern Recognition, Vol.40, pp.993-1003, 2007.
[6] J.H. Wilkinson: The Algebraic Eigenvalue Problem, Oxford Science Publications, 1965.
[7] Gene Howard Golub, Christian Reinsch; Singular Value Decomposition and Least Squares Solutions, Numerische Mathematik14, pp.403-420, 1970.
[8] Tian bo Deng and Masayuki Kawamata: Design of Two-Dimensional Recursive Digital Filters Based on the Iterative Singular Value Decomposition, Transactions of the Institute of Electronics, Information and Communication Engineers, Vol.E 73, No.6, pp.882-892, 1990.
[9] Makoto Ohki and Masayuki Kawamata: Design of Three-Dimensional Digital Filters Based on the Outer Product Expansion, IEEE Transactions on circuits and Systems, Vol.CAS-37, No.9, pp.1164-1167, 1990.
[10] R. L. Johnston: Numerical Methods, John Wiley & Sons, 1982.
[11] Jamie Hutchinson: Culture Communication, and an Information Age Madonna IEEE Professional Communication Society Newsletter, Volume 45, No 3, pp. 1, 5-7, 2001.
[12] Taro Konda, Masami Takata, Masashi Iwasaki, and Yoshimasa Nakamura: A new singular value decomposition algorithm suited to parallelization and preliminary results, Proceedings of the 2nd IASTED international conference on Advances in computer science and technology, Puerto Vallarta, Mexico, pp.79-84, 2006.