Tensor LRR and Sparse Coding-Based Subspace Clustering

Multi-Attribute Subspace Clustering via Auto-Weighted Tensor Nuclear Norm Minimization

Self-expressiveness based subspace clustering methods have received wide attention for unsupervised learning tasks. However, most existing subspace clustering methods consider data features as a whole and then focus only on one single self-representation. These approaches ignore the intrinsic multi-attribute information embedded in the original data feature and result in one-attribute self-representation. This paper proposes a novel multi-attribute subspace clustering (MASC) model that understands data from multiple attributes. MASC simultaneously learns multiple subspace representations corresponding to each specific attribute by exploiting the intrinsic multi-attribute features drawn from original data. In order to better capture the high-order correlation among multi-attribute representations, we represent them as a tensor in low-rank structure and propose the auto-weighted tensor nuclear norm (AWTNN) as a superior low-rank tensor approximation. Especially, the non-convex AWTNN fully considers the difference between singular values through the implicit and adaptive weights splitting during the AWTNN optimization procedure. We further develop an efficient algorithm to optimize the non-convex and multi-block MASC model and establish the convergence guarantees. A more comprehensive subspace representation can be obtained via aggregating these multi-attribute representations, which can be used to construct a clustering-friendly affinity matrix. Extensive experiments on eight real-world databases reveal that the proposed MASC exhibits superior performance over other subspace clustering methods.

Adaptive Transition Probability Matrix Learning for Multiview Spectral Clustering

Multiview clustering as an important unsupervised method has been gathering a great deal of attention. However, most multiview clustering methods exploit the self-representation property to capture the relationship among data, resulting in high computation cost in calculating the self-representation coefficients. In addition, they usually employ different regularizers to learn the representation tensor or matrix from which a transition probability matrix is constructed in a separate step, such as the one proposed by Wu et al.. Thus, an optimal transition probability matrix cannot be guaranteed. To solve these issues, we propose a unified model for multiview spectral clustering by directly learning an adaptive transition probability matrix (MCA²M), rather than an individual representation matrix of each view. Different from the one proposed by Wu et al., MCA²M utilizes the one-step strategy to directly learn the transition probability matrix under the robust principal component analysis framework. Unlike existing methods using the absolute symmetrization operation to guarantee the nonnegativity and symmetry of the affinity matrix, the transition probability matrix learned from MCA²M is nonnegative and symmetric without any postprocessing. An alternating optimization algorithm is designed based on the efficient alternating direction method of multipliers. Extensive experiments on several real-world databases demonstrate that the proposed method outperforms the state-of-the-art methods.

Two-Dimensional Semi-Nonnegative Matrix Factorization for Clustering

In this paper, we propose a new Semi-Nonnegative Matrix Factorization method for 2-dimensional (2D) data, named TS-NMF. It overcomes the drawback of existing methods that seriously damage the spatial information of the data by converting 2D data to vectors in a preprocessing step. In particular, projection matrices are sought under the guidance of building new data representations, such that the spatial information is retained and projections are enhanced by the goal of clustering, which helps construct optimal projection directions. Moreover, to exploit nonlinear structures of the data, manifold is constructed in the projected subspace, which is adaptively updated according to the projections and less afflicted with noise and outliers of the data and thus more representative in the projected space. Hence, seeking projections, building new data representations, and learning manifold are seamlessly integrated in a single model, which mutually enhance other and lead to a powerful data representation. Comprehensive experimental results verify the effectiveness of TS-NMF in comparison with several state-of-the-art algorithms, which suggests high potential of the proposed method for real world applications.

Smoothness Regularized Multiview Subspace Clustering With Kernel Learning

Multiview subspace clustering has attracted an increasing amount of attention in recent years. However, most of the existing multiview subspace clustering methods assume linear relations between multiview data points when learning the affinity representation by means of the self-expression or fail to preserve the locality property of the original feature space in the learned affinity representation. To address the above issues, in this article, we propose a new multiview subspace clustering method termed smoothness regularized multiview subspace clustering with kernel learning (SMSCK). To capture the nonlinear relations between multiview data points, the proposed model maps the concatenated multiview observations into a high-dimensional kernel space, in which the linear relations reflect the nonlinear relations between multiview data points in the original space. In addition, to explicitly preserve the locality property of the original feature space in the learned affinity representation, the smoothness regularization is deployed in the subspace learning in the kernel space. Theoretical analysis has been provided to ensure that the optimal solution of the proposed model meets the grouping effect. The unique optimal solution of the proposed model can be obtained by an optimization strategy and the theoretical convergence analysis is also conducted. Extensive experiments are conducted on both image and document data sets, and the comparison results with state-of-the-art methods demonstrate the effectiveness of our method.

Tensor Low-Rank Representation for Data Recovery and Clustering

Multi-way or tensor data analysis has attracted increasing attention recently, with many important applications in practice. This article develops a tensor low-rank representation (TLRR) method, which is the first approach that can exactly recover the clean data of intrinsic low-rank structure and accurately cluster them as well, with provable performance guarantees. In particular, for tensor data with arbitrary sparse corruptions, TLRR can exactly recover the clean data under mild conditions; meanwhile TLRR can exactly verify their true origin tensor subspaces and hence cluster them accurately. TLRR objective function can be optimized via efficient convex programing with convergence guarantees. Besides, we provide two simple yet effective dictionary construction methods, the simple TLRR (S-TLRR) and robust TLRR (R-TLRR), to handle slightly and severely corrupted data respectively. Experimental results on two computer vision data analysis tasks, image/video recovery and face clustering, clearly demonstrate the superior performance, efficiency and robustness of our developed method over state-of-the-arts including the popular LRR and SSC methods.

Robust Low-Rank Tensor Recovery with Rectification and Alignment

Low-rank tensor recovery in the presence of sparse but arbitrary errors is an important problem with many practical applications. In this work, we propose a general framework that recovers low-rank tensors, in which the data can be deformed by some unknown transformations and corrupted by arbitrary sparse errors. We give a unified presentation of the surrogate-based formulations that incorporate the features of rectification and alignment simultaneously, and establish worst-case error bounds of the recovered tensor. In this context, the state-of-the-art methods 'RASL' and 'TILT' can be viewed as two special cases of our work, and yet each only performs part of the function of our method. Subsequently, we study the optimization aspects of the problem in detail by deriving two algorithms, one based on the alternating direction method of multipliers (ADMM) and the other based on proximal gradient. We provide convergence guarantees for the latter algorithm, and demonstrate the performance of the former through in-depth simulations. Finally, we present extensive experimental results on public datasets to demonstrate the effectiveness and efficiency of the proposed framework and algorithms.

Robust Structured Graph Clustering

Graph-based clustering methods have achieved remarkable performance by partitioning the data samples into disjoint groups with the similarity graph that characterizes the sample relations. Nevertheless, their learning scheme still suffers from two important problems: 1) the similarity graph directly constructed from the raw features may be unreliable as real-world data always involves adverse noises, outliers, and irrelevant information and 2) most graph-based clustering methods adopt two-step learning strategy that separates the similarity graph construction and clustering into two independent processes. Under such circumstance, the generated graph is unstructured and fixed. It may suffer from a low-quality clustering structure and thus lead to suboptimal clustering performance. To alleviate these limitations, in this article we propose a robust structured graph clustering (RSGC) model. We formulate a novel learning framework to simultaneously learn a robust structured similarity graph and perform clustering. Specifically, the structured graph with proper probabilistic neighborhood assignment is adaptively learned on a robust latent representation that resists the noises and outliers. Furthermore, an explicit rank constraint is imposed on the Laplacian matrix to structurize the graph such that the number of the connected components is exactly equal to the ground-truth cluster number. To solve the challenging objective formulation, we propose to first transform it into an equivalent one that can be tackled more easily. An iterative solution based on the augmented Lagrangian multiplier is then derived to solve the model. In RSGC, the discrete cluster labels can be directly obtained by partitioning the learned similarity graph without reliance on label discretization strategy as most graph-based clustering methods. Experiments on both synthetic and real data sets demonstrate the superiority of the proposed method compared with the state-of-the-art clustering techniques.

Accurate Tensor Completion via Adaptive Low-Rank Representation

Low-rank representation-based approaches that assume low-rank tensors and exploit their low-rank structure with appropriate prior models have underpinned much of the recent progress in tensor completion. However, real tensor data only approximately comply with the low-rank requirement in most cases, viz., the tensor consists of low-rank (e.g., principle part) as well as non-low-rank (e.g., details) structures, which limit the completion accuracy of these approaches. To address this problem, we propose an adaptive low-rank representation model for tensor completion that represents low-rank and non-low-rank structures of a latent tensor separately in a Bayesian framework. Specifically, we reformulate the CANDECOMP/PARAFAC (CP) tensor rank and develop a sparsity-induced prior for the low-rank structure that can be used to determine tensor rank automatically. Then, the non-low-rank structure is modeled using a mixture of Gaussians prior that is shown to be sufficiently flexible and powerful to inform the completion process for a variety of real tensor data. With these two priors, we develop a Bayesian minimum mean-squared error estimate framework for inference. The developed framework can capture the important distinctions between low-rank and non-low-rank structures, thereby enabling more accurate model, and ultimately, completion. For various applications, compared with the state-of-the-art methods, the proposed model yields more accurate completion results.

Robust Subspace Clustering by Cauchy Loss Function

Subspace clustering is a problem of exploring the low-dimensional subspaces of high-dimensional data. State-of-the-art approaches are designed by following the model of spectral clustering-based method. These methods pay much attention to learn the representation matrix to construct a suitable similarity matrix and overlook the influence of the noise term on subspace clustering. However, the real data are always contaminated by the noise and the noise usually has a complicated statistical distribution. To alleviate this problem, in this paper, we propose a subspace clustering method based on Cauchy loss function (CLF). Particularly, it uses CLF to penalize the noise term for suppressing the large noise mixed in the real data. This is due to that the CLF's influence function has an upper bound that can alleviate the influence of a single sample, especially the sample with a large noise, on estimating the residuals. Furthermore, we theoretically prove the grouping effect of our proposed method, which means that highly correlated data can be grouped together. Finally, experimental results on five real data sets reveal that our proposed method outperforms several representative clustering methods.

Tensor Based Multiscale Low Rank Decomposition for Hyperspectral Images Dimensionality Reduction

Dimensionality reduction is an essential and important issue in hyperspectral image processing. With the advantages of preserving the spatial neighborhood information and the global structure information, tensor analysis and low rank representation have been widely considered in this field and yielded satisfactory performance. In available tensor- and low rank-based methods, how to construct appropriate tensor samples and determine the optimal rank of hyperspectral images along each mode are still challenging issues. To address these drawbacks, an unsupervised tensor-based multiscale low rank decomposition (T-MLRD) method for hyperspectral images dimensionality reduction is proposed in this paper. By regarding the raw cube hyperspectral image as the only tensor sample, T-MLRD needs no labeled samples and avoids the processing of constructing tensor samples. In addition, a novel multiscale low rank estimating method is proposed to obtain the optimal rank along each mode of hyperspectral image which avoids the complicated rank computing. Finally, the multiscale low rank feature representation is fused to achieve dimensionality reduction. Experimental results on real hyperspectral datasets demonstrate the superiority of the proposed method over several state-of-the-art approaches.

Online Robust Low-Rank Tensor Modeling for Streaming Data Analysis

Tensor data (i.e., the data having multiple dimensions) are quickly growing in scale in many practical applications, which poses new challenges for data modeling and analysis approaches, such as high-order relations of large complexity, gross noise, and varying data scale. Existing low-rank data analysis methods, which are effective at analyzing matrix data, may fail in the regime of tensor data due to these challenges. A robust and scalable low-rank tensor modeling method is heavily desired. In this paper, we develop an online robust low-rank tensor modeling (ORLTM) method to address these challenges. The ORLTM method leverages the high-order correlations among all tensor modes to model an intrinsic low-rank structure of streaming tensor data online and can effectively analyze data residing in a mixture of multiple subspaces by virtue of dictionary learning. ORLTM consumes a very limited memory space that remains constant regardless of the increase of tensor data size, which facilitates processing tensor data at a large scale. More concretely, it models each mode unfolding of streaming tensor data using the bilinear formulation of tensor nuclear norms. With this reformulation, ORLTM employs a stochastic optimization algorithm to learn the tensor low-rank structure alternatively for online updating. To capture the final tensors, ORLTM uses an average pooling operation on folded tensors in all modes. We also provide the analysis regarding computational complexity, memory cost, and convergence. Moreover, we extend ORLTM to the image alignment scenario by incorporating the geometrical transformations and linearizing the constraints. Extensive empirical studies on synthetic database and three practical vision tasks, including video background subtraction, image alignment, and visual tracking, have demonstrated the superiority of the proposed method.

A Fast and Accurate Matrix Completion Method Based on QR Decomposition and L2,1 -Norm Minimization

Low-rank matrix completion aims to recover matrices with missing entries and has attracted considerable attention from machine learning researchers. Most of the existing methods, such as weighted nuclear-norm-minimization-based methods and Qatar Riyal (QR)-decomposition-based methods, cannot provide both convergence accuracy and convergence speed. To investigate a fast and accurate completion method, an iterative QR-decomposition-based method is proposed for computing an approximate singular value decomposition. This method can compute the largest singular values of a matrix by iterative QR decomposition. Then, under the framework of matrix trifactorization, a method for computing an approximate SVD based on QR decomposition (CSVD-QR)-based L_2,1 -norm minimization method (LNM-QR) is proposed for fast matrix completion. Theoretical analysis shows that this QR-decomposition-based method can obtain the same optimal solution as a nuclear norm minimization method, i.e., the L_2,1 -norm of a submatrix can converge to its nuclear norm. Consequently, an LNM-QR-based iteratively reweighted L_2,1 -norm minimization method (IRLNM-QR) is proposed to improve the accuracy of LNM-QR. Theoretical analysis shows that IRLNM-QR is as accurate as an iteratively reweighted nuclear norm minimization method, which is much more accurate than the traditional QR-decomposition-based matrix completion methods. Experimental results obtained on both synthetic and real-world visual data sets show that our methods are much faster and more accurate than the state-of-the-art methods.

Multiview Subspace Clustering via Tensorial t-Product Representation

The ubiquitous information from multiple-view data, as well as the complementary information among different views, is usually beneficial for various tasks, for example, clustering, classification, denoising, and so on. Multiview subspace clustering is based on the fact that multiview data are generated from a latent subspace. To recover the underlying subspace structure, a successful approach adopted recently has been sparse and/or low-rank subspace clustering. Despite the fact that existing subspace clustering approaches may numerically handle multiview data, by exploring all possible pairwise correlation within views, high-order statistics that can only be captured by simultaneously utilizing all views are often overlooked. As a consequence, the clustering performance of the multiview data is compromised. To address this issue, in this paper, a novel multiview clustering method is proposed by using t-product in the third-order tensor space. First, we propose a novel tensor construction method to organize multiview tensorial data, to which the tensor-tensor product can be applied. Second, based on the circular convolution operation, multiview data can be effectively represented by a t-linear combination with sparse and low-rank penalty using "self-expressiveness." Our extensive experimental results on face, object, digital image, and text data demonstrate that the proposed method outperforms the state-of-the-art methods for a range of criteria.

Incomplete-Data Oriented Multiview Dimension Reduction via Sparse Low-Rank Representation

For dimension reduction on multiview data, most of the previous studies implicitly take an assumption that all samples are completed in all views. Nevertheless, this assumption could often be violated in real applications due to the presence of noise, limited access to data, equipment malfunction, and so on. Most of the previous methods will cease to work when missing values in one or multiple views occur, thus an incomplete-data oriented dimension reduction becomes an important issue. To this end, we mathematically formulate the above-mentioned issue as sparse low-rank representation through multiview subspace (SRRS) learning to impute missing values, by jointly measuring intraview relations (via sparse low-rank representation) and interview relations (through common subspace representation). Moreover, by exploiting various subspace priors in the proposed SRRS formulation, we develop three novel dimension reduction methods for incomplete multiview data: 1) multiview subspace learning via graph embedding; 2) multiview subspace learning via structured sparsity; and 3) sparse multiview feature selection via rank minimization. For each of them, the objective function and the algorithm to solve the resulting optimization problem are elaborated, respectively. We perform extensive experiments to investigate their performance on three types of tasks including data recovery, clustering, and classification. Both two toy examples (i.e., Swiss roll and -curve) and four real-world data sets (i.e., face images, multisource news, multicamera activity, and multimodality neuroimaging data) are systematically tested. As demonstrated, our methods achieve the performance superior to that of the state-of-the-art comparable methods. Also, the results clearly show the advantage of integrating the sparsity and low-rankness over using each of them separately.

Probabilistic Low-Rank Multitask Learning

In this paper, we consider the problem of learning multiple related tasks simultaneously with the goal of improving the generalization performance of individual tasks. The key challenge is to effectively exploit the shared information across multiple tasks as well as preserve the discriminative information for each individual task. To address this, we propose a novel probabilistic model for multitask learning (MTL) that can automatically balance between low-rank and sparsity constraints. The former assumes a low-rank structure of the underlying predictive hypothesis space to explicitly capture the relationship of different tasks and the latter learns the incoherent sparse patterns private to each task. We derive and perform inference via variational Bayesian methods. Experimental results on both regression and classification tasks on real-world applications demonstrate the effectiveness of the proposed method in dealing with the MTL problems.

Self-Taught Low-Rank Coding for Visual Learning

The lack of labeled data presents a common challenge in many computer vision and machine learning tasks. Semisupervised learning and transfer learning methods have been developed to tackle this challenge by utilizing auxiliary samples from the same domain or from a different domain, respectively. Self-taught learning, which is a special type of transfer learning, has fewer restrictions on the choice of auxiliary data. It has shown promising performance in visual learning. However, existing self-taught learning methods usually ignore the structure information in data. In this paper, we focus on building a self-taught coding framework, which can effectively utilize the rich low-level pattern information abstracted from the auxiliary domain, in order to characterize the high-level structural information in the target domain. By leveraging a high quality dictionary learned across auxiliary and target domains, the proposed approach learns expressive codings for the samples in the target domain. Since many types of visual data have been proven to contain subspace structures, a low-rank constraint is introduced into the coding objective to better characterize the structure of the given target set. The proposed representation learning framework is called self-taught low-rank (S-Low) coding, which can be formulated as a nonconvex rank-minimization and dictionary learning problem. We devise an efficient majorization-minimization augmented Lagrange multiplier algorithm to solve it. Based on the proposed S-Low coding mechanism, both unsupervised and supervised visual learning algorithms are derived. Extensive experiments on five benchmark data sets demonstrate the effectiveness of our approach.