Comparison between Higher-Order SVD and Third-order Orthogonal Tensor Product Expansion

Authors: Chiharu Okuma, Jun Murakami, Naoki Yamamoto

Abstract:

In digital signal processing it is important to approximate multi-dimensional data by the method called rank reduction, in which we reduce the rank of multi-dimensional data from higher to lower. For 2-dimennsional data, singular value decomposition (SVD) is one of the most known rank reduction techniques. Additional, outer product expansion expanded from SVD was proposed and implemented for multi-dimensional data, which has been widely applied to image processing and pattern recognition. However, the multi-dimensional outer product expansion has behavior of great computation complex and has not orthogonally between the expansion terms. Therefore we have proposed an alterative method, Third-order Orthogonal Tensor Product Expansion short for 3-OTPE. 3-OTPE uses the power method instead of nonlinear optimization method for decreasing at computing time. At the same time the group of B. D. Lathauwer proposed Higher-Order SVD (HOSVD) that is also developed with SVD extensions for multi-dimensional data. 3-OTPE and HOSVD are similarly on the rank reduction of multi-dimensional data. Using these two methods we can obtain computation results respectively, some ones are the same while some ones are slight different. In this paper, we compare 3-OTPE to HOSVD in accuracy of calculation and computing time of resolution, and clarify the difference between these two methods.

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

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

References:

[1] 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.
[2] 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.
[3] Takahiro Saitoh, Takashi Komatsu, Hiroshi Harashima, and Hiroshi Miyakawa: Still Picture Coding by Multi-Dimensional Outer Product Expansion (in Japanese), Transactions of the Institute of Electronics, Information and Communication Engineers, Vol.J68-B, No.4, pp.547-548, 1985.
[4] 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.
[5] Chiharu Okuma, Jun Murakami, and Naoki Yamamoto: Calculation of 3-D Nonnegative Outer Product Expansion by the Power Method and Its Application to Digital Signal Processing, Proceeding of 12th International Symposium on Artificial Life and Robotics, GS14-4, 2007.
[6] 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.
[7] Berkant Savas and Lars Eldén: Handwritten Digit Classification using Higher order Singular Value Decomposition, Pattern Recognition, Vol.40, pp.993-1003, 2007.
[8] 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.
[9] Lieven De Lathauwer, Bart De Moor, and Joos Vandewalle: On the Best Rank-1 And Rank-(R1,R2, ... ,RN) Approximation Of Higher-Order Tensors, SIAM Journal on Matrix Analysis and Applications., Vol.21, No4, pp.1324-1342,2000.
[10] William H. Press, William T. Vetterling, Saul A. Teukolsky, and Brian P. Flannery: Numerical Recipes in C, Cambridge University Press, 1988.
[11] Michael W. Berry, Susan T. Dumais, and Gavin W. O-Brien: Using Linear Algebra for Intelligent Information Retrieval, SIAM Review, Vol.37, No.4, pp.573-595, 1995.