Sparse non-negative tensor factorization using columnwise
coordinate descent
Ji Liu
, Jun Liu, Peter Wonka, Jieping Ye
Department of Computer Science and Engineering, Arizona State University, Tempe, AZ 85287, United States
article info
Article history:
Received 4 September 2009
Received in revised form
5 February 2011
Accepted 28 May 2011
Available online 15 June 2011
Keywords:
Sparse
Non-negative
Tensor factorization
Columnwise coordinate descent
abstract
Many applications in computer vision, biomedical informatics, and graphics deal with data in the
matrix or te nsor form. Non-negative matrix and tensor factorization, which extract data-dependent
non-negative basis functions, have been commonly applied for the analysis of such data for data
compression, visualization, and detection of hidden information (factors). In this paper, we present a
fast and flexible algorithm for sparse non-negative tensor factorization (SNTF) based on column wise
coordinate descent (CCD). Different from the traditional coordinate descent which updates one element
at a time, CCD updates one column vector simultaneously. Our empirical results on higher-mode
images, such as brain MRI images, gene expression images, and hyperspectral images show that the
proposed algorithm is 1–2 orders of magnitude faster than several state-of-the-art algorithms.
& 2011 Elsevier Ltd. All rights reserved.
1. Introduction
Non-negative matrix and tensor factorization (NMF/NTF) aim
to extract data-dependent non-negative basis functions
[13,6,20,27], so that the target data can be expressed by the
linear or multi-linear combination of these non-negative compo-
nents. They have been commonly applied for the analysis of such
data for data compression, visualization, and detection of hidden
information (factors), e.g., in face recognition [24], psychometric
[19] and image analysis [25]. Additionally, the basis can be
constrained to be sparse which typically leads to an even more
meaningful decomposition of the data. As a result, many
researchers focused on sparse non-negative matrix factorization
(SNMF) [13,14,4,9] in the past few years.
A tensor, as a more general ‘‘matrix’’, can be used to express
more complicated intrinsic structures of higher-mode data. Thus,
sparse non-negative tensor factorization (SNTF) is a natural
extension of the SNMF problem. Recently, SNTF began to receive
more attention. It is used in high-mode medical data analysis
[18], psychometric [19], etc. The SNTF problem is not as well
studied as the matrix case. In comparison with SNMF, SNTF has
two additional challenges. First, a tensor usually contains a much
larger data set than a matrix, thus SNMF needs to pay more
attention to computing efficiency than other factors.
The other challenge lies in how to deal with the so-called ‘‘core
tensor’’ in SNMF. Because of the special structure, tensor factor-
ization always contains implicitly or explicitly a core tensor,
which does not exist in matrix factorization. How to efficiently
and effectively deal with it is one key problem in SNTF. We can
either fix it as an identity [18], or incorporate it into the
optimization procedure [17]. The former approach is not flexible
in handling the unbalanced target tensor data, while the latter
one is computationally very expensive, which makes it unsuitable
for large high-mode tensor data.
In this paper, we propose a fast and flexible SNTF algorithm,
which iteratively updates one basis at a time. We employ the idea
of coordinate descent (CD) for the updating. CD has recently been
shown to be very efficient in solving the sparse learning problem
[22]. It updates one element of the basis at a time and the
algorithm cycles through all elements until convergence. The
key to its high efficiency lies in the closed-form solution for each
update. In the proposed algorithm, we identify the independent
groups of elements among different bases, and update at one time
one column vector which consists of elements from all bases,
rather than one element from one group. We call it ‘‘columnwise
coordinate descent’’ (CCD). In addition, we design a flexible way
to deal with the core tensor problem mentioned above. We apply
the proposed algorithms to three types of higher-mode images
such as brain MRI images, gene expression pattern images,
and hyperspectral images. Our experiments show that the
proposed algorithm is 1–2 orders of magnitude faster than several
recent SNMF and SNTF algorithms while achieving the same
objective value.
Contents lists available at ScienceDirect
journal homepage: www.elsevier.com/locate/pr
Pattern Recognition
0031-3203/$ - see front matter & 2011 Elsevier Ltd. All rights reserved.
doi:10.1016/j.patcog.2011.05.015
Corresponding author. Tel.: þ 1 480 965 9932.
E-mail address: ji.liu@asu.edu (J. Liu).
Pattern Recognition 45 (2012) 649–656