An Efficient Algorithm
for Tensor Principal Component Analysis
via Proximal Linearized Alternating Direction
Method of Multipliers
Linbo Qiao
1,2
, Bofeng Zhang
1
, Lei Zhuang
3
, Jinshu Su
1,2
1
College of Computer, National University of Defense Technology ChangSha 410073, China
2
National Laboratory for Parallel and Distributed Processing, National University of Defense Technology ChangSha 410073, China
3
Department of Statistics, Shanghai University of Finance and Economics,Shanghai 201800 China
1
{qiao.linbo,bfzhang,sjs}@nudt.edu.cn,
3
shirleyshufe@gmail.com
Abstract—In paper, we focus on the computation of the
principal components for a general tensor, known as the ten-
sor principal component analysis (PCA) problem. It has been
proven that the general tensor PCA problem is reducible to
its matricization form when the order is even. Usually it is
considered as low-rank matrix completion problems theoretically.
It is common to consider nuclear norm as a surrogate of the rank
operator since it is the tightest convex lower bound of the rank
operator under certain condition. However, most nuclear norm
minimization based approaches involve numbers of singular value
decomposition (SVD) operations. Given a matrix X ∈ R
m×n
,
the time complexity of SVD operation is O(mn
2
), which brings
prohibitive computational burden to apply these methods in real
applications. However, the problem is non-convex, and the prox-
imal mapping associated with non-convex regularization is not
easy to compute. It is always solved by the Linearized Alternating
Direction Method of Multipliers (LADMM). Despite the success
of LADMM in practice, it remains unknown if LADMM is
convergent in solving such non-convex compositely regularized
optimization. In this paper, we firstly present a detailed conver-
gence analysis of the LADMM algorithm for solving non-convex
compositely regularized optimization with a large class of non-
convex penalties. Furthermore, we propose a new efficient and
scalable algorithm for matrix principal component analysis called
Proximal Linearized Alternating Direction Method of Multipliers
for Principal Component Analysis(PLADMPCA). Different from
traditional matrix factorization methods, PLADMPCA utilizes
the linearization technique to formulate the matrix as an outer
product of vectors, which greatly improves the computational
efficacy compared to matrix factorization method. We empirically
evaluate the proposed algorithm PLADMPCA on synthetic tensor
data with different order. Results have shown that PLADMPCA
have much better computational cost to matrix factorization
based method. At the same time, it outperforms the state-of-art
SVD based matrix completion algorithms by similar or better
reconstruction accuracy with enormous advantages on efficiency.
Index Terms—Tensor; Principal Component Analysis; Proxi-
mal Linearized Alternating Direction Method of Multipliers
I. INTRODUCTION
A tensor is a multidimensional array. More formally, an N-
way or Nth-order tensor is an element in N vector tensor prod-
uct spaces, and each of which has its own coordinate system.
For example, a first-order tensor is a vector, a second-order
tensor is a matrix, and tensors with three or higher-order are
called higher-order tensors. There are two classes of methods
focus on tensor decomposition: the “CP” decomposition[5],
[9] and the Tucker decomposition[26]. Canonical decomposi-
tion(CANDECOMP) is proposed by Carroll and Chang [5] and
parallel factors(PARAFAC) by Harshman [9]. And the “CP”
is the abbreviation of CANDECOMP and PARAFAC.
Principal component analysis (PCA) finds a few linear
combinations of the original variables. It is a powerful tool
to compress data along the direction of maximum variance
with minimum information loss. The PCA plays an important
role in dimension reduction and data analysis related research
areas. Specifically, let ε =(ε
1
, ··· ,ε
m
) be an m-dimensional
random vector, then for a given data matrix M ∈ R
m×n
which
consists of n samples and each sample of the m variables,
finding the principal components which explain the largest
variance of the variables (ε
1
, ··· ,ε
m
) corresponds to the
following optimization problem:
(λ
∗
,x
∗
,y
∗
):=min
λ,x,y
M − λx ⊗ y,
(1)
where λ ∈ R,x∈ R
m
,y ∈ R
n
, and the symbol ⊗ denotes the
outer product of two vectors.
Although the PCA and eigenvalue problem for the matrix
has been well studied in the literature, there is still little
work has been done on the research of PCA for tensors.
Nevertheless, the tensor PCA is of great importance in practice
and has many applications.Similar to its matrix form, the
problem of finding the PC is related to the most variance of
a tensor F, which can be specifically formulated as:
min
x
1
,x
2
,··· ,x
m
F − λx
1
⊗ x
2
⊗···⊗x
m
2
F
,
s.t. λ ∈ R, x
i
=1,i =1, 2, ··· ,m.
(2)
(F
1
⊗F
2
)
i
1
i
2
···i
m
=(F
1
)
i
1
i
2
···i
m
(F
2
)
i
m+1
···i
m+l
.
2016 International Conference on Advanced Cloud and Big Data
978-1-5090-3677-6/16 $31.00 © 2016 IEEE
DOI 10.1109/CBD.2016.14
283