Search

Graph-based clustering aims to partition the data according to a similarity graph, which has shown impressive performance on various kinds of tasks. The quality of similarity graph largely determines the clustering results, but it is difficult to produce a high-quality one, especially when data contain noises and outliers. To solve this problem, we propose a robust rank constrained sparse learning (RRCSL) method in this article. The $L_{2,1}$ -norm is adopted into the objective function of sparse representation to learn the optimal graph with robustness. To preserve the data structure, we construct an initial graph and search the graph within its neighborhood. By incorporating a rank constraint, the learned graph can be directly used as the cluster indicator, and the final results are obtained without additional postprocessing. In addition, the proposed method cannot only be applied to single-view clustering but also extended to multiview clustering. Plenty of experiments on synthetic and real-world datasets have demonstrated the superiority and robustness of the proposed framework. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel feature selection approach via explicitly addressing the long-standing subspace sparsity issue. Leveraging $\ell _{2,1}$ -norm regularization for feature selection is the major strategy in existing methods, which, however, confronts sparsity limitation and parameter-tuning trouble. To circumvent this problem, employing the $\ell _{2,0}$ -norm constraint to improve the sparsity of the model has gained more attention recently whereas, optimizing the subspace sparsity constraint is still an unsolved problem, which only can acquire an approximate solution and without convergence proof. To address the above challenges, we innovatively propose a novel subspace sparsity discriminative feature selection (S2DFS) method which leverages a subspace sparsity constraint to avoid tuning parameters. In addition, the trace ratio formulated objective function extremely ensures the discriminability of selected features. Most important, an efficient iterative optimization algorithm is presented to explicitly solve the proposed problem with a closed-form solution and strict convergence proof. To the best of our knowledge, such an optimization algorithm of solving the subspace sparsity issue is first proposed in this article, and a general formulation of the optimization algorithm is provided for improving the extensibility and portability of our method. Extensive experiments conducted on several high-dimensional text and image datasets demonstrate that the proposed method outperforms related state-of-the-art methods in pattern classification and image retrieval tasks. [ABSTRACT FROM AUTHOR]

$k$ k -means method using Lloyd heuristic is a traditional clustering method which has played a key role in multiple downstream tasks of machine learning because of its simplicity. However, Lloyd heuristic always finds a bad local minimum, i.e., the bad local minimum makes objective function value not small enough, which limits the performance of $k$ k -means. In this paper, we use coordinate descent (CD) method to solve the problem. First, we show that the $k$ k -means minimization problem can be reformulated as a trace maximization problem, then a simple and efficient coordinate descent scheme is proposed to solve the maximization problem. Two interesting findings through theory are that Lloyd cannot decrease the objective function value of $k$ k -means produced by our CD further, and our proposed method CD to solve $k$ k -means problem can avoid produce empty clusters. In addition, according to the computational complexity analysis, it is verified CD has the same time complexity with original $k$ k -means method. Extensive experiments including statistical hypothesis testing, on several real-world datasets with varying number of clusters, varying number of samples and varying number of dimensions show that CD performs better compared to Lloyd, i.e., lower objective value, better local minimum and fewer iterations. And CD is more robust to initialization than Lloyd whether the initialization strategy is random or initialization of $k$ k -means++. [ABSTRACT FROM AUTHOR]

Dimensionality reduction has attracted much research interest in the past few decades. Existing dimensionality reduction methods like linear discriminant analysis and principal component analysis have achieved promising performance, but the single and linear projection properties limit further improvements of performance. A novel convolutional two-dimensional nonlinear discriminant analysis method is proposed for dimensionality reduction in this article. In order to handle nonlinear data properly, we present a newly designed structure with convolutional neural networks (CNNs) to realize an equivalent objective function with classical two-dimensional linear discriminant analysis (2DLDA) and thus embed the original 2DLDA into an end-to-end network. In this way, the proposed dimensionality reduction network can utilize the nonlinearity of the CNN and benefit from the learning ability. The results of experiment on different image-related applications demonstrate that our method outperforms other comparable approaches, and its effectiveness is proved. [ABSTRACT FROM AUTHOR]

Band selection is one of the most important technique in the reduction of hyperspectral image (HSI). Different from traditional feature selection problem, an important characteristic of it is that there is usually strong correlation between neighboring bands, that is, bands with close indexes. Aiming to fully exploit this prior information, a novel band selection method called optimal neighborhood reconstruction (ONR) is proposed. In ONR, band selection is considered as a combinatorial optimization problem. It evaluates a band combination by assessing its ability to reconstruct the original data, and applies a noise reducer to minimize the influence of noisy bands. Instead of using some approximate algorithms, ONR exploits a recurrence relation that underlies the optimization target to obtain the optimal solution in an efficient way. Besides, we develop a parameter selection approach to automatically determine the parameter of ONR, ensuring it is adaptable to different data sets. In experiments, ONR is compared with some state-of-the-art methods on six HSI data sets. The results demonstrate that ONR is more effective and robust than the others in most of the cases. [ABSTRACT FROM AUTHOR]

The existing unsupervised feature extraction methods frequently explore low-redundant features by an uncorrelated constraint. However, the constrained models might incur trivial solutions, due to the singularity of scatter matrix triggered by high-dimensional data. In this paper, we propose a regularized regression model with a generalized uncorrelated constraint for feature selection, which leads to three merits: 1) exploring the low-redundant and discriminative features; 2) avoiding the trivial solutions and 3) simplifying the optimization. Besides that, the local cluster structure is achieved via a novel constrained spectral analysis for the unsupervised learning, where Must-Links and Cannot-Links are transformed into a intrinsic graph and a penalty graph respectively, rather than incorporated into a mixed affinity graph. Accordingly, a discriminative and uncorrelated feature selection with constrained spectral analysis (DUCFS) is proposed with adopting $\sigma $ -norm regularization for interpolating between F-norm and $\ell _{2,1}$ -norm. Due to the flexible gradient and global differentiability, our model converges fast. Extensive experiments on benchmark datasets among several state-of-the-art approaches verify the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Non-negative Matrix Factorization (NMF) has been one of the most popular clustering techniques in machine leaning, and involves various real-world applications. Most existing works perform matrix factorization on high-dimensional data directly. However, the intrinsic data structure is always hidden within the low-dimensional subspace. And, the redundant features within the input space may affect the final result adversely. In this paper, a new unsupervised matrix factorization method, Discrimination-aware Projected Matrix Factorization (DPMF), is proposed for data clustering. The main contributions are threefold: (1) The linear discriminant analysis is jointly incorporated into the unsupervised matrix factorization framework, so the clustering can be accomplished in the discriminant subspace. (2) The manifold regularization is introduced to perceive the geometric information, and the ${\ell _{2,1}}$ ℓ 2 , 1 -norm is utilized to improve the robustness. (3) An efficient optimization algorithm is designed to solve the proposed problem with proved convergence. Experimental results on one toy dataset and eight real-world benchmarks show the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

This paper addresses two fundamental problems: 1) learning discriminative model parameters and 2) avoiding over-fitting, which often occurs in regression-based classification tasks. We formulate these two problems in terms of relaxing both the strict binary label matrix and graph regularization term into more flexible forms so that the margins between different classes are enlarged as much as possible and the problem of over-fitting is avoided to some extent. This task is accomplished by the proposed double relaxed regression (DRR) method. The convex problem of DRR is solved efficiently with an iterative procedure. Extensive experiments on synthetic and real world image data sets demonstrate the effectiveness of the proposed method in terms of both classification accuracy and running time. [ABSTRACT FROM AUTHOR]

2-D linear discriminant analysis (2DLDA) has been widely used in pattern recognition and image classification. 2DLDA selects discriminative features from the up and left corner of images. However, 2DLDA uses the Frobenius norm (F-norm), which is sensitive to noise or outliers in data, as a metric. In this paper, we propose a novel framework, called horizontal and vertical nuclear norm-based 2DLDA (HVNN-2DLDA) for image representation. In the proposed framework, HVNN-2DLDA methods (i.e., HNN-2DLDA and VNN-2DLDA) are proposed, and both use the nuclear norm as a criterion. The nuclear norm can provide more structure and global information for the reconstruction of noisy images. HNN-2DLDA and VNN-2DLDA represent images in the row and column directions, respectively. In addition, by combining the row and column directions, we propose a bilateral nuclear norm-based 2DLDA method called BNN-2DLDA. The advantage of BNN-2DLDA over HNN-2DLDA and VNN-2DLDA is that an image sample can be represented by both the row and the column directions instead of only the row or column direction. HVNN-2DLDA learns a set of local optimal projection vectors by maximizing the ratio of the nuclear norm of the between-class scatter matrix and the nuclear norm of the within-class scatter matrix. To verify the robustness and recognition performance in image classification of HVNN-2DLDA, six public image databases are used for experiments. The experimental results demonstrate the effectiveness and the feasibility of the proposed framework. [ABSTRACT FROM AUTHOR]

In this paper, we study Stochastic Composite Optimization (SCO) for sparse learning that aims to learn a sparse solution from a composite function. Most of the recent SCO algorithms have already reached the optimal expected convergence rate \mathcal O(1/\lambda T) , but they often fail to deliver sparse solutions at the end either due to the limited sparsity regularization during stochastic optimization (SO) or due to the limitation in online-to-batch conversion. Even when the objective function is strongly convex, their high probability bounds can only attain \mathcal O(\sqrt\log (1/\delta)/T) with $\delta$ is the failure probability, which is much worse than the expected convergence rate. To address these limitations, we propose a simple yet effective two-phase Stochastic Composite Optimization scheme by adding a novel powerful sparse online-to-batch conversion to the general Stochastic Optimization algorithms. We further develop three concrete algorithms, OptimalSL, LastSL and AverageSL, directly under our scheme to prove the effectiveness of the proposed scheme. Both the theoretical analysis and the experiment results show that our methods can really outperform the existing methods at the ability of sparse learning and at the meantime we can improve the high probability bound to approximately \mathcal {O}(\log (\log (T)/\delta)/\lambda T) . [ABSTRACT FROM AUTHOR]

We consider the problem of image representation from the perspective of statistical design. Recent studies have shown that images are possibly sampled from a low dimensional manifold despite of the fact that the ambient space is usually very high dimensional. Learning low dimensional image representations is crucial for many image processing tasks such as recognition and retrieval. Most of the existing approaches for learning low dimensional representations, such as principal component analysis (PCA) and locality preserving projections (LPP), aim at discovering the geometrical or discriminant structures in the data. In this paper, we take a different perspective from statistical experimental design, and propose a novel dimensionality reduction algorithm called A-Optimal Projection (AOP). AOP is based on a linear regression model. Specifically, AOP finds the optimal basis functions so that the expected prediction error of the regression model can be minimized if the new representations are used for training the model. Experimental results suggest that the proposed approach provides a better representation and achieves higher accuracy in image retrieval. [ABSTRACT FROM PUBLISHER]

In image analysis, the images are often represented by multiple visual features (also known as multiview features), that aim to better interpret them for achieving remarkable performance of the learning. Since the processes of feature extraction on each view are separated, the multiple visual features of images may include overlap, noise, and redundancy. Thus, learning with all the derived views of the data could decrease the effectiveness. To address this, this paper simultaneously conducts a hierarchical feature selection and a multiview multilabel (MVML) learning for multiview image classification, via embedding a proposed a new block-row regularizer into the MVML framework. The block-row regularizer concatenating a Frobenius norm ( F -norm) regularizer and an \boldsymbol \ell \textbf {2,1} -norm regularizer is designed to conduct a hierarchical feature selection, in which the F -norm regularizer is used to conduct a high-level feature selection for selecting the informative views (i.e., discarding the uninformative views) and the \boldsymbol \ell \textbf {2,1} -norm regularizer is then used to conduct a low-level feature selection on the informative views. The rationale of the use of a block-row regularizer is to avoid the issue of the over-fitting (via the block-row regularizer), to remove redundant views and to preserve the natural group structures of data (via the F -norm regularizer), and to remove noisy features (the \boldsymbol \ell \textbf {2,1} -norm regularizer), respectively. We further devise a computationally efficient algorithm to optimize the derived objective function and also theoretically prove the convergence of the proposed optimization method. Finally, the results on real image datasets show that the proposed method outperforms two baseline algorithms and three state-of-the-art algorithms in terms of classification performance. [ABSTRACT FROM PUBLISHER]

Hashing methods are effective in generating compact binary signatures for images and videos. This paper addresses an important open issue in the literature, i.e., how to learn compact hash codes by enhancing the complementarity among different hash functions. Most of prior studies solve this problem either by adopting time-consuming sequential learning algorithms or by generating the hash functions which are subject to some deliberately-designed constraints (e.g., enforcing hash functions orthogonal to one another). We analyze the drawbacks of past works and propose a new solution to this problem. Our idea is to decompose the feature space into a subspace shared by all hash functions and its complementary subspace. On one hand, the shared subspace, corresponding to the common structure across different hash functions, conveys most relevant information for the hashing task. Similar to data de-noising, irrelevant information is explicitly suppressed during hash function generation. On the other hand, in case that the complementary subspace also contains useful information for specific hash functions, the final form of our proposed hashing scheme is a compromise between these two kinds of subspaces. To make hash functions not only preserve the local neighborhood structure but also capture the global cluster distribution of the whole data, an objective function incorporating spectral embedding loss, binary quantization loss, and shared subspace contribution is introduced to guide the hash function learning. We propose an efficient alternating optimization method to simultaneously learn both the shared structure and the hash functions. Experimental results on three well-known benchmarks CIFAR-10, NUS-WIDE, and a-TRECVID demonstrate that our approach significantly outperforms state-of-the-art hashing methods. [ABSTRACT FROM PUBLISHER]

We propose a new graph based hashing method called spectral embedded hashing (SEH) for large-scale image retrieval. We first introduce a new regularizer into the objective function of the recent work spectral hashing to control the mismatch between the resultant hamming embedding and the low-dimensional data representation, which is obtained by using a linear regression function. This linear regression function can be employed to effectively handle the out-of-sample data, and the introduction of the new regularizer makes SEH better cope with the data sampled from a nonlinear manifold. Considering that SEH cannot efficiently cope with the high dimensional data, we further extend SEH to kernel SEH (KSEH) to improve the efficiency and effectiveness, in which a nonlinear regression function can also be employed to obtain the low dimensional data representation. We also develop a new method to efficiently solve the approximate solution for the eigenvalue decomposition problem in SEH and KSEH. Moreover, we show that some existing hashing methods are special cases of our KSEH. Our comprehensive experiments on CIFAR, Tiny-580K, NUS-WIDE, and Caltech-256 datasets clearly demonstrate the effectiveness of our methods. [ABSTRACT FROM PUBLISHER]