Skip to main content
SpringerLink
Log in

Tensor principal component analysis via convex optimization

  • Full Length Paper
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

This paper is concerned with the computation of the principal components for a general tensor, known as the tensor principal component analysis (PCA) problem. We show that the general tensor PCA problem is reducible to its special case where the tensor in question is super-symmetric with an even degree. In that case, the tensor can be embedded into a symmetric matrix. We prove that if the tensor is rank-one, then the embedded matrix must be rank-one too, and vice versa. The tensor PCA problem can thus be solved by means of matrix optimization under a rank-one constraint, for which we propose two solution methods: (1) imposing a nuclear norm penalty in the objective to enforce a low-rank solution; (2) relaxing the rank-one constraint by semidefinite programming. Interestingly, our experiments show that both methods can yield a rank-one solution for almost all the randomly generated instances, in which case solving the original tensor PCA problem to optimality. To further cope with the size of the resulting convex optimization models, we propose to use the alternating direction method of multipliers, which reduces significantly the computational efforts. Various extensions of the model are considered as well.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13–51 (1993)

    Article  MathSciNet  Google Scholar 

  2. Bloy, L., Verma, R.: On computing the underlying fiber directions from the diffusion orientation distribution function. In: Metaxas, D., Axel, L., Fichtinger, G., Szekeley, G. (eds.) Medical Image Computing and Computer-Assisted Intervention, MICCAI (2008)

  3. Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1–122 (2011)

    Google Scholar 

  4. Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. 9, 717–772 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  5. Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)

    Article  MATH  Google Scholar 

  6. Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inf. Theory 56(5), 2053–2080 (2009)

    Article  Google Scholar 

  7. Carroll, J.D., Chang, J.J.: Analysis of individual differences in multidimensional scaling via an n-way generalization of “eckart-young” decomposition. Psychometrika 35(3), 283–319 (1970)

    Article  MATH  Google Scholar 

  8. Chandrasekaran, V., Recht, P.A., Parrilo, B., Willsky, A.S.: The convex geometry of linear inverse problems. Found. Comput. Math. 12(6), 805–849 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chen, B.: Optimization with Block Variables: Theory and Applications. PhD thesis, The Chinese Univesrity of Hong Kong (2012)

  10. Chen, B., He, S., Li, Z., Zhang, S.: Maximum block improvement and polynomial optimization. SIAM J. Optim. 22, 87–107 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  11. Comon, P., Golub, G., Lim, L.H., Mourrain, B.: Symmetric tensors and symmetric tensor rank. SIAM J. Matrix Anal. Appl. 30(3), 1254–1279 (2008)

    Article  MathSciNet  Google Scholar 

  12. Donoho, D.: Compressed sensing. IEEE Trans. Inf. Theory 52, 1289–1306 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  13. Douglas, J., Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  14. Eckstein, J.: Splitting Methods for Monotone Operators with Applications to Parallel Optimization. PhD thesis, Massachusetts Institute of Technology (1989)

  15. Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  16. Fortin, M., Glowinski, R.: Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems. North-Holland, Amsterdam (1983)

    MATH  Google Scholar 

  17. Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems. North-Holland, Amsterdam (1983)

    Google Scholar 

  18. Gandy, S., Recht, B., Yamada, I.: Tensor completion and low-n-rank tensor recovery via convex optimization. Inverse Probl. 27(2), 025010 (2011)

    Article  MathSciNet  Google Scholar 

  19. Ghosh, A., Tsigaridas, E., Descoteaux, M., Comon, P., Mourrain, B., Deriche, R.: A polynomial based approach to extract the maxima of an antipodally symmetric spherical function and its application to extract fiber directions from the orientation distribution function in diffusion MRI. In: Computational Diffusion MRI Workshop (CDMRI08), New York (2008)

  20. Glowinski, R., Le Tallec, P.: Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics. SIAM, Philadelphia, PA (1989)

    Book  MATH  Google Scholar 

  21. Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115–1145 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  22. Goldstein, T., Osher, S.: The split Bregman method for L1-regularized problems. SIAM J. Imaging Sci. 2, 323–343 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  23. Grant, M., Boyd, S.: CVX: Matlab Software for Disciplined Convex Programming, version 1.21. http://cvxr.com/cvx, May 2010

  24. Harshman, R.A.: Foundations of the parafac procedure: models and conditions for an “explanatory” multimodal factor analysis. UCLA Working Papers in Phonetics, vol 16, pp. 1–84. http://publish.uwo.ca/~harshman/wppfac0.pdf (1970)

  25. Håstad, J.: Tensor rank is NP-complete. J. Algorithms 11, 644–654 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  26. Henrion, D., Lasserre, J.B., Loefberg, J.: GloptiPoly 3: moments, optimization and semidefinite programming. Optim. Methods Softw. 24, 761–779 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  27. Hilling, J.J., Sudbery, A.: The geometric measure of multipartite entanglement and the singular values of a hypermatrix. J. Math. Phys. 51, 072102 (2010)

    Article  MathSciNet  Google Scholar 

  28. Hitchcock, F.L.: The Expression of a Tensor or a Polyadic as a Sum of Products. J. Math. Phys. 6, 164–189 (1927)

    Google Scholar 

  29. Hitchcock, F.L.: Multiple invariants and generalized rank of a p-way matrix or tensor. J. Math. Phys. 7(1), 39–79 (1927)

    MATH  MathSciNet  Google Scholar 

  30. Hu, S., Qi, L.: Algebraic connectivity of an even uniform hypergraph. J. Comb. Optim. 24(4), 564–579 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  31. Kofidis, E., Regalia, P.A.: On the best rank-\(1\) approximation of higher-order supersymmetric tensors. SIAM J. Matrix Anal. Appl. 23, 863–884 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  32. Kolda, T.G., Bader, B.W.: Tensor decompositions and applications. SIAM Rev. 51, 455–500 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  33. Kolda, T.G., Mayo, J.R.: Shifted power method for computing tensor eigenpairs. SIAM J. Matrix Anal. 32, 1095–1124 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  34. Kruskal, J.B.: Rank, Decomposition, and Uniqueness for 3-way and n-way arrays. In: Multiway Data Analysis, pp. 7–18 (1989)

  35. Lasserre, J.B.: Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  36. Lasserre, J.B.: Polynomials nonnegative on a grid and discrete representations. Trans. Am. Math. Soc. 354, 631–649 (2001)

    Article  MathSciNet  Google Scholar 

  37. Li, W., Ng, M.: Existence and Uniqueness of Stationary Probability Vector of a Transition Probability Tensor. Technical Report. Department of Mathematics, The Hong Kong Baptist University (2011)

  38. Lim, L.H.: Singular values and eigenvalues of tensors: a variational approach. In: Computational Advances in Multi-Sensor Adaptive Processing, 2005 1st IEEE International Workshop on, pp. 129–132. IEEE (2005)

  39. Ling, C., Nie, J., Qi, L., Ye, Y.: Biquadratic optimization over unit spheres and semidefinite programming relaxations. SIAM J. Optim. 20, 1286–1310 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  40. Lions, P.L., Mercier, B.: Splitting algorithms for the sum of two nonlinear operators. SIAM J. Numer. Anal. 16, 964–979 (1979)

    Article  MATH  MathSciNet  Google Scholar 

  41. Liu, J., Musialski, P., Wonka, P., Ye, J.: Tensor completion for estimating missing values in visual data. In: The Twelfth IEEE International Conference on Computer Vision (2009)

  42. Ma, S.: Alternating direction method of multipliers for sparse principal component analysis. J. Oper. Res. Soc. China 1(2), 253–274 (2013)

    Article  MATH  Google Scholar 

  43. Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. Ser. A 128, 321–353 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  44. Mackey, L.: Deflation methods for sparse PCA. In: Advances in Neural Information Processing Systems (NIPS) (2008)

  45. Parrilo, P.A.: Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization. PhD thesis, California Institute of Technology (2000)

  46. Parrilo, P.A.: Semidefinite programming relaxations for semialgebraic problems. Math. Program. Ser. B 96, 293–320 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  47. Peaceman, D.H., Rachford, H.H.: The numerical solution of parabolic elliptic differential equations. SIAM J. Appl. Math. 3, 28–41 (1955)

    Article  MATH  MathSciNet  Google Scholar 

  48. Qi, L.: Eigenvalues of a real supersymmetric tensor. J. Symb. Comput. 40, 1302–1324 (2005)

    Article  MATH  Google Scholar 

  49. Qi, L., Wang, F., Wang, Y.: Z-eigenvalue methods for a global polynomial optimization problem. Math. Program. Ser. A 118, 301–316 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  50. Qi, L., Yu, G., Wu, E.X.: Higher order positive semi-definite diffusion tensor imaging. SIAM J. Imaging Sci. 3(3), 416–433 (2010)

    Google Scholar 

  51. Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52(3), 471–501 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  52. Scheinberg, K., Ma, S., Goldfarb, D.: Sparse inverse covariance selection via alternating linearization methods. In: NIPS (2010)

  53. Tao, M., Yuan, X.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57–81 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  54. Tomioka, R., Suzuki, T., Hayashi, K., Kashima, H.: Statistical performance of convex tensor decomposition. In: Advances in Neural Information Processing Systems (NIPS), p. 137 (2011)

  55. Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49–95 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  56. Wang, H., Ahuja, N.: Compact representation of multidimensional data using tensor rank-one decomposition. In: Proceedings of the Pattern Recognition, 17th International Conference on ICPR (2004)

  57. Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1(3), 248–272 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  58. Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203–230 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  59. Yang, J., Zhang, Y.: Alternating direction algorithms for \(\ell _1\) problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250–278 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  60. Yuan, X.: Alternating direction methods for sparse covariance selection. J. Sci. Comput. 51, 261–273 (2012)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

We would like to thank the co-editor and the anonymous referees for their helpful comments, and Fei Wang and Yiju Wang for sharing with us their codes of Z-eigenvalue methods.

Author information

Authors and Affiliations

  1. Research Center for Management Science and Data Analytics, School of Information Management and Engineering, Shanghai University of Finance and Economics, Shanghai , 200433, China

    Bo Jiang

  2. Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, NT, Hong Kong

    Shiqian Ma

  3. Department of Industrial and Systems Engineering, University of Minnesota, Minneapolis, MN , 55455, USA

    Shuzhong Zhang

Authors
  1. Bo Jiang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Shiqian Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Shuzhong Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shiqian Ma.

Additional information

Shiqian Ma: Research of this author was supported in part by a Direct Grant of the Chinese University of Hong Kong (Project ID: 4055016) and the Hong Kong Research Grants Council (RGC) Early Career Scheme (ECS) (Project ID: CUHK 439513). Shuzhong Zhang: Research of this author was supported in part by the National Science Foundation under Grant Number CMMI-1161242. Bo Jiang: Research of this author was supported in part by the National Science Foundation under Grant Number CMMI-1161242.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jiang, B., Ma, S. & Zhang, S. Tensor principal component analysis via convex optimization. Math. Program. 150, 423–457 (2015). https://doi.org/10.1007/s10107-014-0774-0

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-014-0774-0

Keywords

Mathematics Subject Classification (2010)

Search

Navigation