Fast Tensor Principal Component Analysis via Proximal Alternating Direction Method with Vectorized Technique

Download Download as PDF (Size:355KB)  HTML   XML  PP. 77-86  
DOI: 10.4236/am.2017.81007    312 Downloads   404 Views  

ABSTRACT

This paper studies the problem of tensor principal component analysis (PCA). Usually the tensor PCA is viewed as a low-rank matrix completion problem via matrix factorization technique, and nuclear norm is used as a convex approximation of the rank operator under mild condition. However, most nuclear norm minimization approaches are based on SVD operations. Given a matrix , the time complexity of SVD operation is O(mn2), which brings prohibitive computational complexity in large-scale problems. In this paper, an efficient and scalable algorithm for tensor principal component analysis is proposed which is called Linearized Alternating Direction Method with Vectorized technique for Tensor Principal Component Analysis (LADMVTPCA). Different from traditional matrix factorization methods, LADMVTPCA utilizes the vectorized technique to formulate the tensor as an outer product of vectors, which greatly improves the computational efficacy compared to matrix factorization method. In the experiment part, synthetic tensor data with different orders are used to empirically evaluate the proposed algorithm LADMVTPCA. Results have shown that LADMVTPCA outperforms matrix factorization based method.

Cite this paper

Fan, H. , Kuang, G. and Qiao, L. (2017) Fast Tensor Principal Component Analysis via Proximal Alternating Direction Method with Vectorized Technique. Applied Mathematics, 8, 77-86. doi: 10.4236/am.2017.81007.

References

[1] Kolda, T.G. and Bader, B.W. (2009) Tensor Decompositions and Applications. SIAM Review, 51, 455-500.
https://doi.org/10.1137/07070111X
[2] Wang, H. and Ahuja, N. (2004) Compact Representation of Multidimensional Data Using Tensor Rank-One Decomposition. Proceedings of the 17th International Conference on Pattern Recognition, ICPR 2004, Cambridge, 26-26 August 2004, 104-107.
[3] Huang, F., Niranjan, U., Hakeem, M.U. and Anandkumar, A. (2013) Fast Detection of Overlapping Communities via Online Tensor Methods. arXiv:1309.0787
[4] Qi, L., Yu, G. and Wu, E.X. (2010) Higher Order Positive Semidefinite Diffusion Tensor Imaging. SIAM Journal on Imaging Sciences, 3, 416-433.
https://doi.org/10.1137/090755138
[5] Jiang, B., Ma, S. and Zhang, S. (2014) Tensor Principal Component Analysis via Convex Optimization. Mathematical Programming, 1-35.
[6] Hitchcock, F.L. (1927) The Expression of a Tensor or a Polyadic as a Sum of Products. Journal of Mathematics and Physics, 6, 164-189.
[7] Kofidis, E. and Regalia, P.A. (2002) On the Best Rank-1 Approximation of Higher-Order Supersymmetric Tensors. SIAM Journal on Matrix Analysis and Applications, 23, 863-884.
https://doi.org/10.1137/S0895479801387413
[8] Kolda, T.G. and Mayo, J.R. (2011) Shifted Power Method for Computing Tensor Eigenpairs. SIAM Journal on Matrix Analysis and Applications, 32, 1095-1124.
https://doi.org/10.1137/100801482
[9] Qi, L. (2005) Eigenvalues of a Real Supersymmetric Tensor. Journal of Symbolic Computation, 40, 1302-1324.
https://doi.org/10.1016/j.jsc.2005.05.007
[10] Mackey, L.W. (2009) Deflation Methods for Sparse PCA. Advances in Neural Information Processing Systems, 21, 1017-1024.
[11] Lim, L.H. (2005) Singular Values and Eigenvalues of Tensors: A Variational Approach. IEEE International Workshop on Computational Advances in Multi-Sensor Adaptive Processing, Puerto Vallarta, Mexico, 13-15 December 2005, 129-132.
[12] Zhong, L.W. and Kwok, J.T. (2013) Fast Stochastic Alternating Direction Method of Multipliers. Proceedings of the 30th International Conference on Machine Learning, Atlanta, Georgia, 2013.
[13] Zhao, P.l., Yang, J.W., Zhang, T. and Li, P. (2013) Adaptive Stochastic Alternating Direction Method of Multipliers. arXiv:1312.4564
[14] Magnússon, S., Weeraddana, P.C., Rabbat, M.G. and Fischione, C. (2014) On the Convergence of Alternating Direction Lagrangian Methods for Nonconvex Structured Optimization Problems. arXiv:1409.8033 [math.OC]
[15] Hong, M.Y., Luo, Z.-Q. and Razaviyayn, M. (2015) Convergence Analysis of Alternating Direction Method of Multipliers for a Family of Nonconvex Problems. 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), Brisbane, 19-24 April 2015, 3836-3840.
https://doi.org/10.1109/ICASSP.2015.7178689
[16] Yang, J. and Yuan, X. (2013) Linearized Augmented Lagrangian and Alternating Direction Methods for Nuclear Norm Minimization. Mathematics of Computation, 820, 301-329.

  
comments powered by Disqus

Copyright © 2017 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.