Multi-View Matrix Decomposition: A New Scheme for Exploring Discriminative Information

1 Introduction

Many real-world datasets have representations in the form of multiple views, which are collected from different sources or obtained from various feature extractors. For example, in the biological data domain, each human gene is measured by different techniques, such as gene expression, single-nucleotide polymorphism (SNP), and methylation [Cai et al., 2013b]; in the visual data domain, each image/video can be represented by different visual features, such as colour descriptor, local shape descriptor, and spatio-temporal descriptor. These views often provide diverse and complementary information to each other. Combining these information introduced by individual views has recently become very popular, and is expected to enhance the overall performance of a learning task at hand.

∗The corresponding author, wliu.cu@gmail.com.

In the literature, several fusion or combination approaches have been proposed from different perspectives. A naive method is to concatenate the vectors of all views into a new vector, or more generally, to use weights to concatenate them. Such a method is problematic, because it ignores the particular statistical property belonging to an individual view. Kernel-based approaches associate different kernels with different views and combine them either linearly or nonlinearly, among which kernel averaging is a simple and representative method [Bucak et al., 2014]. It is worth noting that such approaches are particularly effective under the assumption that all views are independent of each other.

In contrast, subspace learning methods aim to learn a latent subspace which captures the relevant information shared by all views, and are effective when the views are assumed to be dependent on each other. Canonical Correlation Analysis (CCA) and its variants [Kuss and Graepel, 2003] learn the latent representations shared by all views such that the correlations among the views are maximized. As a version of nonlinear CCA, the shared Gaussian Process Latent Variable Model (sGPLVM) [Shon et al., 2005] builds a common latent space for inferring another view from the observation view. Recently, more methods have been extended to multi-view scenarios. For example, the work of [Quadrianto and Lampert, 2011] constructs embedding projections from multi-view data to produce a shared subspace.

An appealing scheme based on sparse representation has attracted a lot of research interests, which aims to encourage the complementarity by imposing different sparsity constraints on a shared subspace derived from multiple views [Shekhar et al., 2014; Wang et al., 2015]. The used sparsity constraints include ℓ0-norm [Cai et al., 2013b], tree-structured sparsity norm [Bahrampour et al., 2014], and trace-norm [Liu et al., 2015]. Another popular scheme follows the standard pipeline of low-rank matrix recovery [Wright et al., 2009], in which the low-rankness constraint is employed to discover the underlying subspace structures in multi-view data, while the sparsity constraint is used for outlier removal. Cheng et al. [Cheng et al., 2011] imposes ℓ2,1-norm on a concatenated low-rank matrix to associate multiple views. The work of [Guo et al., 2013] captures the dependencies across multiple views via a shared low-rank coefficient matrix. The work of [Xia et al., 2014] learns a shared low-rank transition probability matrix of all views for spectral clustering. Although the aforementioned approaches enjoy satisfactory performance in their specific settings, all of them only focus on the shared component across multiple views while overlook the private component of an individual view. Therefore, the main difficulty of integrating multiple views is how to effectively capture the correlative properties across all views (i.e., shared component), and at the same time exploit the discriminative properties of individual views (i.e., private components).

To address the issues presented above, in this paper we propose a novel multi-view low-rank and sparse matrix decomposition method by robustly utilizing the group-structured prior. Specifically, unlike existing methods, we first concatenate input data from multiple views into a new mixed matrix, so the global structure and the hidden correlations across all the views can be preserved well. We then conduct the low-rank and sparse matrix decomposition in the noisy case, and leverage trace norm and group-structured sparsity norm to promote the low-rankness and sparsity properties of the target matrix, respectively. As such, the shared and private components can be simultaneously captured in both instance and view levels. Since our formulated optimization objective is non-smooth, we develop an algorithm based on Augmented Lagrange Multiplier (ALM) to solve the optimization efficiently. We evaluate our method on six widely used image datasets in classification tasks, and on each dataset we integrate six different types of popular visual features. The experimental results demonstrate that our method consistently outperforms the state-of-the-art classification approaches that use traditional multi-view combinations.

2 Robust Multi-View, Low-Rank, and Sparse Matrix Decomposition

In this section, we introduce the low-rank and sparse matrix decomposition method for integrating diverse and complementary information from multiple views. We first present the concatenation of multi-view input matrices and then describe our framework. Finally, we output an augmented representation by combining shared component and private component, and extend the proposed method to deal with supervised image classification tasks. Given a set of n data instances {xi}ni=1 , the data matrix in the k-th view is X(k) = [x(k) 1 , · · · , x(k) n ] ∈ Rdk×n (k = 1, · · · ,m), where dk denotes the feature dimension of the k-th view.

2.1 Multi-View Input Matrix Concatenation

Different from previous approaches that handle multi-view input matrices X(k) individually, we first concatenate the input data matrices X(k) of each view to construct a new mixed matrix X = [X(1) ; · · · ;X(m) ] ∈ Rd×n , with d = ∑mk=1 dk. Since different views describe different aspects of the same object, the views are intrinsically associated. Thus, the concatenated input matrix has a natural advantage of strengthening the correlation among multiple views, as well as providing a convenient way to explore the complementarity of multiple views both in instance level and view level, which will be detailed in the following subsection.

2.2 ProblemFormulation

Given a single-view input data X(k) , motivated by classical low-rank matrix recovery model [Wright et al., 2009], previous approaches [Guo et al., 2013; Xia et al., 2014] utilize this model to remove outlier from the observation data by decomposing the single-view data matrix X(k) into two different parts: a shared low-rank matrix L and a separately sparse error matrix E(k) . Under fairly general conditions, L can be exactly recovered from X(k) as long as E(k) is sufficiently sparse. Formally, this model can be formulated into:

where γ is a tradeoff parameter. As aforementioned, this model may not be suitable for coping with multi-view problems. The main reason is that this model oversimply decomposes all input matrices into a low-rank matrix shared by all views and an error matrix belonging to each view. In fact, the removed error matrix instead contains discriminative information specific to each individual view, which is useful to boost the performance of a given learning task.

Therefore, in this paper, we simultaneously capture the shared component and private component in a unified matrix decomposition framework. Specifically, we decompose the concatenated input matrix X into three parts, i.e. low-rank matrix L, sparse matrix S and noise matrix E, and then utilize three different regularizations to exploit the underlying relationship among multiple views so as to leverage the correlated information across all views as well as the discriminative information of each view. Hence, we consider the following matrix decomposition problem:

where L, S, E ∈ Rd×n , Z ∈ Rn×n encodes the dependencies among the data instances, B ∈ Rd×d denotes a row transformation matrix that maps the input data into a view space, and non-negative parameters λ1, λ2 are used to balance the effects of the three parts. The trace norm ‖L‖∗ is the convex envelope of the rank of L over the unit ball of the spectral norm, and minimizing the trace norm often induces the desirable low-rank structure in practice. Ω(S) is a regularizer that encourages group-structured sparsity of S. Due to the inherent sparse structures of the real-world data, Ω(S) can be defined as

Here, c is the number of groups, and SGi j is a row vector containing a subset of entries in the row Sj, that is, those specified by the indices in group Gi [Rakotomamonjy et al., 2008].

Based on matrix norm inequality, Eq. (2) can be relaxed to:

In Eq. (4), analogous to low-rank matrix recovery, the matrix Z is equal to the low-rank representation (i.e., shared component) corresponding to the dictionary X. Intuitively, the underlying global structure of the original input matrices is consistent across all views.

Besides the shared component, we need to discover the private component S specific to each view. In Eq. (4), B is a row transformation matrix projecting the input data into view space, upon which the relevance among views can be discovered. Considering the matrix S being group-structured sparse, we instead enforce group-structured sparsity constraint on B by exploiting regularization relaxation, which encourages sharing within a group and discriminativeness among different groups. Meanwhile, sparsity is also forced between different rows so that the discriminative elements in each view are selected. To obtain the private component, the discriminative information in view space should be connected to the data space, mathematically, S = BX.

2.3 Augmented Representation

When the shared component Z and the private component S are learned from Eq. (4), we can derive an augmented multiview representation by directly concatenating them.

Nevertheless, to make the augmented representation more robust and compact, we first learn the low-dimensional shared component ˜ Z ∈ Rp×n for all views by enforcing Principal Component Analysis (PCA) on the learned low-rank representation Z. Then, we can obtain more compact private component ˜ S ∈ Rq×n by filtering out all zero rows in S. The above two procedures still well preserve the inherent properties of Z and S. Therefore, the augmented multi-view representation is denoted as

where R ∈ R(p+q)×n with p+q ≪ d. Subsequently, the augmented representation is feasible to a variety of multi-view learning tasks, such as image classification, clustering, object detection and recognition, etc.

Here, we apply our method to supervised image classification. Suppose the data instances are labeled into c classes, yi ∈ Rc is the class label vector of the data instance xi. The class indicator matrix is represented as Y = [y1, · · · , yn] ∈ Rc×n , where Yj,i = 1 if data instance xi belongs to the j-th class, Yj,i = 0 otherwise. In the training phase, the classifier W ∈ R(p+q)×c can be learned by the augmented representation Rtr from the training instances. In the test phase, given test data ˆX and the row transformation matrix B, we can obtain the shared component ˆ Z according to Eq. (4). The private component is written as ˆ S = B ˆX. Therefore, the augmented representation for test data is Rts = [ ˆ Z; ˆ S], the class of an unseen data instance can be determined by arg maxj (W ⊤Rts + b)j , where b is bias vector.

3 Optimization

3.1 Algorithm

The optimization problem (4) is challenging due to the simultaneous low-rank and group-structured sparsity regularizations in the objective function. To address this problem, Algorithm 1 The learning procedure of the proposed method Input: Amulti-view data matrix X.

Output: The learned matrices Z,B.

• 1: Initialize: Z0 = J0 = 0,B0 =K0 = 0, Y1,0 = 0, Y2,0 = 0, µ = µ1 = µ2 = 10-6 , µmax = 106 , ρ = 1.1, and ϵ = 10-8
• 2: while not converge do
• 3: fix the others and update Z according to Eq. (8);
• 4: fix the others and update B according to Eq. (9);
• 5: fix the others and update J according to Eq. (10);
• 6: fix the others and update K according to Eq. (11);
• 7: update the multipliers: Y1 = Y1 + µ1(Z - J), Y2 = Y2 + µ2(B - K);
• 8: update the parameter: µ = min (µmax, ρµ);
• 9: check the convergence condition: ‖X - XZ - BX‖∞ ≤ ϵ, ‖Z - J‖∞ ≤ ϵ, and ‖B - K‖∞ ≤ ϵ;

10: end while

two auxiliary variables are introduced to decouple Z and B [Afonso et al., 2011]. Hence, we reformulate the problem as follows:

The solution to problem (6) is given by ALM, which is implemented by minimizing the following augmented Lagrangian function

where Y1, Y2 are the Lagrangian multipliers, 〈X, Y 〉 = tr(X⊤Y ) is the inner product between two matrices, and µ1, µ2 are two non-negative penalty parameters. Due to the separable structure of the objective function in Eq. (7), the optimization to problem (7) can be carried out on each variable separately with others fixed. The optimization procedure is described in Algorithm 1.

Now, we investigate an update rule for each variable among Z, B, J, K while fixing the other variables. Update Z with the others fixed:

Update B with the others fixed:

Update J with the others fixed:

Update K with the others fixed:

Note that both Eqs. (8) and (9) give closed-form solutions to Z and B, so they achieve global minima in each iteration. Meanwhile, Eq. (10) can be solved via the singular value thresholding (SVT) operator [Cai et al., 2010] which guarantees the rank of J to reduce until convergence. However, due to the group-structured sparsity regularization, Eq. (11) poses a non-smooth and non-trivial optimization problem. To simplify the optimization of Eq. (11), we seek the following alternative formulation by squaring the regularizer Ω(K):

An auxiliary variable τj,i is introduced to make Eq. (12) more tractable, that is,

where ∑j ∑i τj,i = 1, τj,i ≥ 0, ∀j, i. The condition under which the above inequality holds is

Obviously, when Eq. (14) is satisfied, the right-hand side of Eq. (13) takes a minimum, which can be regarded as a further relaxation of Eq. (12). Thus, Eq. (12) can be reformulated as

Based on the above analysis, Eq. (15) can be solved by alternatively optimizing K and τj,i iteratively until convergence. Denote Mw as the w-th column of matrix M. In each iteration, we first fix the values for K and update τj,i according to Eq. (14). Then, we hold the values for τj,i as constant and optimize for K. To minimize K, we take the first order derivative of Eq. (15) with respect to Kw and set it to zero, obtaining

where Π ∈ Rd×d is a diagonal matrix with ∑ci=1 1 τj,i being the j-th element in its diagonal.

The following theorem guarantees the convergence of solving problem (11) in each iteration.

Theorem 1. The objective of Eq. (11) with λ2 ≥ dµ2 2c monotonically decreases in each iteration.

Proof. The solution of Eq. (11) involves alternative optimization of Kw and τj,i.

(2 λ2 µ2 Π)-1 = µ2 2λ2 Π-1 , where Π-1 is a diagonal matrix with the j-th entry on the diagonal being (∑ci=1 1 τj,i )-1 ≤ 1c . Let λ2 ≥ dµ2 2c , then

Suppose that {Y2,w} is a cauchy sequence and µ2 does not grow too fast. Then ∥∥ Y2,w µ2 ∥∥F is bounded with ∥∥ Y ∗ 2,w µ2 ∥∥F, where Y ∗ 2,w is the value of Y2,w after the algorithm halts. Therefore, we have

Since Y2,w µ2 is bounded and Bw monotonically decreases, ‖Kw‖F also monotonically decreases in each iteration.

Without loss of generality, we can suppose ∑dj=1 ∑ci=1 ∥∥KGi j ∥∥2 ≥ 1. According to Eq. (14),

Since ‖Kw‖F decreases in each iteration, ∥∥KGi j ∥∥2 also decreases. Given 0 ≤ |τj,i| ≤ 1, we know that the value of τj,i monotonically decreases. Since each iteration converges, the convergence of optimizing the objective in Eq. (11) is ensured.

3.2 Complexity Analysis

The complexity of the proposed algorithm (see Algorithm 1) includes four parts, where each part accounts for the optimization with respect to a single variable among Z, B, J, K, respectively. Firstly, the update of Z consists of some matrix multiplication and inversion, leading to a complexity of O(n3 ). The update of B also has a similar complexity. The SVD is implemented when solving J, which usually induces a computational cost of O(n3 ). Suppose the number of inner iterations for updating K is t, then the corresponding time complexity is O(2n3 t). The computational cost for updating Y1, Y2 and µ can be eliminated since they are relatively smaller than that of the others.

Apparently, the computational cost of Algorithm 1 is dominated by the calculation of J. For a maximal number of outer iteration T (step 2 to step 10), the complexity of Algorithm 1 can thus be approximated by O(Tn3 ).

4 Experiments

In this section, we evaluate the performance of our method on six benchmark datasets: Caltech101 [Fei-Fei et al., 2007], NUS-WIDE [Chua et al., 2009], Handwritten numeral [Frank and Asuncion, 2010], Animal with attributes [Lampert et al., 2009], Scene-15 [Lazebnik et al., 2006].

Caltech101 dataset is an object recognition dataset containing 8677 images, belonging to 101 categories. Following [Cai et al., 2013a], we choose widely used 7 and 20 classes to construct two datasets, i.e. Caltech7 and Caltech20, in which there are 1474 images and 2386 images, respectively. In order to obtain the different views, we extract GIST [Oliva and Torralba, 2001] with dimension 512, CENTRIST [Wu and Rehg, 2008] with dimension 1302, LBP [Ojala et al., 2002] with dimension 256, histogram of oriented gradient (HOG) with dimension 576, SIFT-SPM [Lazebnik et al., 2006] with dimension 1000, color histogram (CH) with dimension 64.

NUS-WIDE dataset contains 30000 images and 31 classes. We use six published features to do multi-view classification, which contains 225 dimension block-wise color moments (CM), 64 dimension CH, 144 dimension color correlogram (CoRR), 128 dimension wavelet texture (WT), 73 dimension edge distribution (EDH), and 500 dimension SIFT BoW feature.

Handwritten numerals (HW) dataset consists of 2000 data instances for 0 to 9 ten digit classes. We use six published features to represent multiple views. Specifically, these features include 76 Fourier coefficients of the character shapes (FOU), 216 profile correlations (FAC), 64 Karhunenlove coefficients (KAR), 240 pixel averages in 2×3 windows (PIX), 47 Zernike moment (ZER), and 6 morphological features (MOR).

Animal with attributes (AWA) dataset contains 50 classes, 30475 instances. We use all the published features for all the images, that is, 2688 dimension color histogram (CQ), 2000 dimension local self-similarity (LSS), 252 dimension pyramidHOG (PHOG), 2000 dimension SIFT, 2000 dimension colorSIFT, and 2000 dimension SURF.

Scene-15 dataset consists of 15 classes, 3000 images, mainly stemming from the COREL collection, personal photographs and Google image search. We extract the same six visual features from each image as Caltech101 dataset.

4.1 Experimental Setup

To demonstrate the advantage of our proposed method, we compare the proposed method against several representative approaches: (1) Single View (SV): Using the single-view feature to verify the classification performance, where Type 1 to Type 6 represent six different features belonging to the corresponding datasets, respectively. (2) Direct Concatenation (DC-SVM): Concatenating features of all views in a straightforward way, and then performing classification by SVM directly on the concatenated feature. (3) SimpleMKL: Constructing a kernel for each view, and then learning a linear combination of the different kernels in SVM [Rakotomamonjy et al., 2008]. (4) SMML: Integrating multiple views by imposing joint structured sparsity regularizations [Wang et al., 2013]. (5) I2SCA: CCA-based multiview supervised feature learning [Jing et al., 2014]. (6) MTSRC: Tree-structured sparse model for multi-view classification [Bahrampour et al., 2014]. (7) lrMMC: Low-rank multiview matrix completion method [Liu et al., 2015].

Besides, to further demonstrate the superior performance of the proposed method, we derive three variants of the proposed method. First, in Eq. (4), we enforce ℓ1-norm to constrain the sparse matrix S. We denote it as "Our method (ℓ1norm)". Second, we use ℓ2,1-norm to constrain the sparse matrix S. We denote this degenerate version of the proposed method as "Our method (ℓ2,1-norm)". Finally, the full version of the proposed method by Eq. (4) is operated and named as "Our method".

To quantitatively measure the performance of the compared methods, we use accuracy to measure the classification performances. Since we mainly investigate the multi-view supervised classification problem, hence the labels of training samples are known. For each dataset, we randomly choose 30% of the data for training, and the rest for testing. All reported experimental results are averaged over 10 runs with random initializations.

In all the experiments, we implement standard 5-fold crossvalidation and report the average results. Specifically, the parameters λ1 and λ2 in Eq. (4) are finely tuned by searching the grid of {10-3 , 10-2 , · · · , 102 , 103}, and then the best values are chosen based on validation performance. For SVM

classifier, we use Gaussian kernel as the kernel matrix for each method, which is defined as K(xi, xj ) = exp(-σ||xi - xj||2 ). The standard deviation σ is tuned in the same range used as our method. The tradeoff parameter C of SVM is selected from the range {0.01, 0.1, 1, 10, 100, 1000}. We use LIBSVM 1 software package to implement SVM in all our experiments.

4.2 Classification Results

The classification results of the compared methods on all considered datasets are reported in Table 1. The confusion matrices of Caltech7, Caltech20 and Handwritten numerals are shown in Figure 1. First of all, in order to verify multi-view combination power of our method, we compare classification performances between using all the views and using only one view. It is obvious that single-view feature may perform better on some of the datasets while perform poorly on the other datasets. For example, the classification accuracy of HOG on Caltech7 is 88.29%, while on the Caltech20, the accuracy is only 31.46%. Meanwhile, for each dataset, some features are more effective than the others. Hence, it is nearly impossible for a single feature to perform best on all datasets. To better utilize the diversity and complementarity of multiple views, the naive approach is to directly concatenate multiple features together. However, as shown in Table 1, the performance of this method is not better than the single feature. For instance, on the NUS-WIDE dataset, the classification accuracy of DCSVM is only 13.31%, compared to 15.21% achieved by the CM feature alone. The reason is that direct feature concatenation may not promote the complementarity of multiple views. Instead, some feature may even introduce noise to other features, deteriorating the whole performance.

As shown in Table 1, more sophisticated multi-view combination methods are compared. Although these approaches all achieve significant performance gains on the six datasets, about 10%∼12% improvement compared with the naive method. However, most of these methods only focus on the shared component across multiple views. Comparatively, our proposed method achieves the best results on all six datasets, and outperforms the previous best results nearly by 7% on average. It is mainly because that our method simultaneously consider the shared component and the private component, which is beneficial to boosting the classification performance.

1 http://www.csie.ntu.edu.tw/∼cjlin/libsvm/

5 Conclusions

In this paper, we proposed a novel multi-view, low-rank, and sparse matrix decomposition scheme which can robustly integrate diverse yet complementary information from multiple views. Different from traditional approaches, we decomposed a concatenated input matrix into three parts including the low-rank, sparse, and noisy parts, and imposed particular constraints on them. In the presented unified optimization framework, on one hand the low-rankness regularizer was leveraged to capture the shared component across all views in the instance level; on the other hand the group-structured sparsity regularizer was employed to extract the private component from each view in the view level. The final multi-view fusion was conducted by combining the learned shared and private components. The experimental results on six popular image classification datasets demonstrated that our proposed method consistently achieves superior performance over the state-of-the-arts.

In future work, we plan to extend our multi-view matrix decomposition method to work under semi-supervised settings like [Liu et al., 2010; 2012a]. To make our method scalable to massive heterogeneous datasets, we intend to draw on the storage and computational merits of learning based datadependent hashing techniques [Liu et al., 2011; 2012b; 2014; Shen et al., 2015], and develop new hashing schemes to cater for large-scale multi-view matrix decomposition.

Acknowledgements This work is supported by National High Technology Research and Development Program of China (2013AA01A602), Program for New Century Excellent Talents in University (NCET-12-0917), National Natural Science Foundation of China (No. 61125204 and No. 61472304), and Australian Research Council Projects (FT130101457, DP-140102164, and LP-140100569).