TY - JOUR

T1 - Tensor principal component analysis via convex optimization

AU - Jiang, Bo

AU - Ma, Shiqian

AU - Zhang, Shuzhong

N1 - Publisher Copyright:
© 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
Copyright:
Copyright 2015 Elsevier B.V., All rights reserved.

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

KW - Low rank

KW - Nuclear norm

KW - Principal component analysis

KW - Semidefinite programming relaxation

KW - Tensor

UR - http://www.scopus.com/inward/record.url?scp=84925290954&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84925290954&partnerID=8YFLogxK

U2 - 10.1007/s10107-014-0774-0

DO - 10.1007/s10107-014-0774-0

M3 - Article

AN - SCOPUS:84925290954

VL - 150

SP - 423

EP - 457

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

IS - 2

ER -