Comparison between Higher-Order SVD and Third-order Orthogonal Tensor Product Expansion
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:51129", author = "Chiharu Okuma and Jun Murakami and Naoki Yamamoto", title = "Comparison between Higher-Order SVD and Third-order Orthogonal Tensor Product Expansion", 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.", volume = "3", number = "3", pages = "539-7", }