Search

High-dimensional data are highly correlative and redundant, making it difficult to explore and analyze. Amount of unsupervised dimensionality reduction (DR) methods has been proposed, in which constructing a neighborhood graph is the primary step of DR methods. However, there exist two problems: 1) the construction of graph is usually separate from the selection of projection direction and 2) the original data are inevitably noisy. In this article, we propose an unsupervised adaptive embedding (UAE) method for DR to solve these challenges, which is a linear graph-embedding method. First, an adaptive allocation method of neighbors is proposed to construct the affinity graph. Second, the construction of affinity graph and calculation of projection matrix are integrated together. It considers the local relationship between samples and global characteristic of high-dimensional data, in which the cleaned data matrix is originally proposed to remove noise in subspace. The relationship between our method and local preserving projections (LPPs) is also explored. Finally, an alternative iteration optimization algorithm is derived to solve our model, the convergence and computational complexity of which are also analyzed. Comprehensive experiments on synthetic and benchmark datasets illustrate the superiority of our method. [ABSTRACT FROM AUTHOR]

The linear discriminant analysis (LDA) method needs to be transformed into another form to acquire an approximate closed-form solution, which could lead to the error between the approximate solution and the true value. Furthermore, the sensitivity of dimensionality reduction (DR) methods to subspace dimensionality cannot be eliminated. In this article, a new formulation of trace ratio LDA (TRLDA) is proposed, which has an optimal solution of LDA. When solving the projection matrix, the TRLDA method given by us is transformed into a quadratic problem with regard to the Stiefel manifold. In addition, we propose a new trace difference problem named optimal dimensionality linear discriminant analysis (ODLDA) to determine the optimal subspace dimension. The nonmonotonicity of ODLDA guarantees the existence of optimal subspace dimensionality. Both the two approaches have achieved efficient DR on several data sets. [ABSTRACT FROM AUTHOR]

Ridge regression is frequently utilized by both supervised learning and semisupervised learning. However, the results cannot obtain the closed-form solution and perform manifold structure when ridge regression is directly applied to semisupervised learning. To address this issue, we propose a novel semisupervised feature selection method under generalized uncorrelated constraint, namely SFS. The generalized uncorrelated constraint equips the framework with the elegant closed-form solution and is introduced to the ridge regression with embedding the manifold structure. The manifold structure and closed-form solution can better save data’s topology information compared to the deep network with gradient descent. Furthermore, the full rank constraint of the projection matrix also avoids the occurrence of excessive row sparsity. The scale factor of the constraint that can be adaptively obtained also provides the subspace constraint more flexibility. Experimental results on data sets validate the superiority of our method to the state-of-the-art semisupervised feature selection methods. [ABSTRACT FROM AUTHOR]

Dimensionality reduction (DR) technique has been frequently used to alleviate information redundancy and reduce computational complexity. Traditional DR methods generally are inability to deal with nonlinear data and have high computational complexity. To cope with the problems, we propose a fast unsupervised projection (FUP) method. The simplified graph of FUP is constructed by samples and representative points, where the number of the representative points selected through iterative optimization is less than that of samples. By generating the presented graph, it is proved that large-scale data can be projected faster in numerous scenarios. Thereafter, the orthogonality FUP (OFUP) method is proposed to ensure the orthogonality of projection matrix. Specifically, the OFUP method is proved to be equivalent to PCA upon certain parameter setting. Experimental results on benchmark data sets show the effectiveness in retaining the essential information. [ABSTRACT FROM AUTHOR]

In this article, we propose a novel feature selection approach, named unsupervised feature selection with constrained $\ell _{2,0}$ -norm (row-sparsity constrained) and optimized graph (RSOGFS), which unifies feature selection and similarity matrix construction into a general framework instead of independently performing the two-stage process; thus, the similarity matrix preserving the local manifold structure of data can be determined adaptively. Unlike those sparse learning-based feature selection methods that can only solve the relaxation or approximation problems by introducing sparsity regularization term into the objective function, the proposed method directly tackles the original $\ell _{2,0}$ -norm constrained problem to achieve group feature selection. Two optimization strategies are provided to solve the original sparse constrained problem. The convergence and approximation guarantees for the new algorithms are rigorously proved, and the computational complexity and parameter determination are theoretically analyzed. Experimental results on real-world data sets show that the proposed method for solving a nonconvex problem is superior to the state of the arts for solving the relaxed or approximate convex problems. [ABSTRACT FROM AUTHOR]

The performance of graph-based feature selection methods relies heavily on the quality of the construction of the similarity matrix. However, most of the graphs on these methods are initially fixed, where few of them are constrained. Once the graph is determined, it will remain constant in the whole optimization process. In other words, in case that the graph constructed on the raw data is not appropriate, it will drag down the entire algorithm. Aiming to tackle this defect, a novel unsupervised feature selection via adaptive graph learning and constraint (EGCFS) is proposed to select the uncorrelated yet discriminative features by exploiting the embedded graph learning and constraint. The adaptive graph learning method incorporates the structure of the similarity matrix into the optimization process, which not only learns the graph structure adaptively but also obtains the closed-form solution of the graph coefficient. Special graph constraint is embedded with the feature selection process to connect nearer data points with larger probability. The idea of maximizing between-class scatter matrix and the adaptive graph structure is integrated into a uniform framework to obtain excellent structural performance. Moreover, the proposed embedded graph constraint not only performs with manifold structure but also validates the link between graph-based approach and $k$ -means from a unique perspective. Experiments on several benchmark data sets verify the effectiveness and superiority of the proposed method. [ABSTRACT FROM AUTHOR]

Data clustering is a fundamental problem in the field of machine learning. Among the numerous clustering techniques, matrix factorization-based methods have achieved impressive performances because they are able to provide a compact and interpretable representation of the input data. However, most of the existing works assume that each class has a global centroid, which does not hold for data with complicated structures. Besides, they cannot guarantee that the sample is associated with the nearest centroid. In this work, we present a concept factorization with the local centroids (CFLCs) approach for data clustering. The proposed model has the following advantages: 1) the samples from the same class are allowed to connect with multiple local centroids such that the manifold structure is captured; 2) the pairwise relationship between the samples and centroids is modeled to produce a reasonable label assignment; and 3) the clustering problem is formulated as a bipartite graph partitioning task, and an efficient algorithm is designed for optimization. Experiments on several data sets validate the effectiveness of the CFLC model and demonstrate its superior performance over the state of the arts. [ABSTRACT FROM AUTHOR]

Graph-based technique is widely used in projection, clustering, and classification tasks. In this article, we propose a novel and solid framework, named unsupervised projection with graph optimization (UPGO), for both dimensionality reduction and clustering. Different from the existing algorithms which treat graph construction and projection learning as two separate steps, UPGO unifies graph construction and projection learning into a general framework. It learns the graph similarity matrix adaptively based on the relationships among the low-dimensional representations. A constraint is introduced to the Laplacian matrix to learn a structured graph which contains the clustering structure, from which the clustering results can be obtained directly without requiring any postprocessing. The structured graph achieves the ideal neighbors assignment, based on which an optimal low-dimensional subspace can be learned. Moreover, we generalize UPGO to tackle the semisupervised case, namely semisupervised projection with graph optimization (SPGO), a framework for both dimensionality reduction and classification. An efficient algorithm is derived to optimize the proposed frameworks. We provide theoretical analysis about convergence analysis, computational complexity, and parameter determination. Experimental results on real-world data sets show the effectiveness of the proposed frameworks compared with the state-of-the-art algorithms. Results also confirm the generality of the proposed frameworks. [ABSTRACT FROM AUTHOR]

Feature representation learning, an emerging topic in recent years, has achieved great progress. Powerful learned features can lead to excellent classification accuracy. In this article, a selective and robust feature representation framework with a supervised constraint (SRSC) is presented. SRSC seeks a selective, robust, and discriminative subspace by transforming the original feature space into the category space. Particularly, we add a selective constraint to the transformation matrix (or classifier parameter) that can select discriminative dimensions of the input samples. Moreover, a supervised regularization is tailored to further enhance the discriminability of the subspace. To relax the hard zero-one label matrix in the category space, an additional error term is also incorporated into the framework, which can lead to a more robust transformation matrix. SRSC is formulated as a constrained least square learning (feature transforming) problem. For the SRSC problem, an inexact augmented Lagrange multiplier method (ALM) is utilized to solve it. Extensive experiments on several benchmark data sets adequately demonstrate the effectiveness and superiority of the proposed method. The proposed SRSC approach has achieved better performances than the compared counterpart methods. [ABSTRACT FROM AUTHOR]

For large-scale image retrieval task, a hashing technique has attracted extensive attention due to its efficient computing and applying. By using the hashing technique in image retrieval, it is crucial to generate discrete hash codes and preserve the neighborhood ranking information simultaneously. However, both related steps are treated independently in most of the existing deep hashing methods, which lead to the loss of key category-level information in the discretization process and the decrease in discriminative ranking relationship. In order to generate discrete hash codes with notable discriminative information, we integrate the discretization process and the ranking process into one architecture. Motivated by this idea, a novel ranking optimization discrete hashing (RODH) method is proposed, which directly generates discrete hash codes (e.g., +1/−1) from raw images by balancing the effective category-level information of discretization and the discrimination of ranking information. The proposed method integrates convolutional neural network, discrete hash function learning, and ranking function optimizing into a unified framework. Meanwhile, a novel loss function based on label information and mean average precision (MAP) is proposed to preserve the label consistency and optimize the ranking information of hash codes simultaneously. Experimental results on four benchmark data sets demonstrate that RODH can achieve superior performance over the state-of-the-art hashing methods. [ABSTRACT FROM AUTHOR]

Unsupervised feature selection is fundamentally important for processing unlabeled high-dimensional data, and several methods have been proposed on this topic. Most existing embedded unsupervised methods just emphasize the data structure in the input space, which may contain large noise. Therefore, they are limited to perceive the discriminative information implied within the low-dimensional manifold. In addition, these methods always involve several parameters to be tuned, which is time-consuming. In this paper, we present a self-tuned discrimination-aware (STDA) approach for unsupervised feature selection. The main contributions of this paper are threefold: 1) it adopts the advantage of discriminant analysis technique to select the valuable features; 2) it learns the local data structure adaptively in the discriminative subspace to alleviate the effect of data noise; and 3) it performs feature selection and clustering simultaneously with an efficient optimization strategy, and saves the additional efforts to tune parameters. Experimental results on a toy data set and various real-world benchmarks justify the effectiveness of STDA on both feature selection and data clustering, and demonstrate its promising performance against the state of the arts. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

Unsupervised feature selection always occupies a key position as a preprocessing in the tasks of classification or clustering due to the existence of extra essential features within high-dimensional data. Although lots of efforts have been made, the existing methods neglect to consider the redundancy of features, and thus select redundant features. In this brief, by virtue of a generalized uncorrelated constraint, we present an improved sparse regression model [generalized uncorrelated regression model (GURM)] for seeking the uncorrelated yet discriminative features. Benefited from this, the structure of data is kept in the Stiefel manifold, which avoids the potential trivial solution triggered by a conventional ridge regression model. Besides that, the uncorrelated constraint equips the model with the closed-form solution. In addition, we also incorporate a graph regularization term based on the principle of maximum entropy into the GURM model (URAFS), so as to embed the local geometric structure of data into the manifold learning. An efficient algorithm is designed to perform URAFS by virtue of the existing generalized powered iteration method. Extensive experiments on eight benchmark data sets among seven state-of-the-art methods on the task of clustering are conducted to verify the effectiveness and superiority of the proposed method. [ABSTRACT FROM AUTHOR]

In this paper, we propose a unified model called flexible affinity matrix learning (FAML) for unsupervised and semisupervised classification by exploiting both the relationship among data and the clustering structure simultaneously. To capture the relationship among data, we exploit the self-expressiveness property of data to learn a structured matrix in which the structures are induced by different norms. A rank constraint is imposed on the Laplacian matrix of the desired affinity matrix, so that the connected components of data are exactly equal to the cluster number. Thus, the clustering structure is explicit in the learned affinity matrix. By making the estimated affinity matrix approximate the structured matrix during the learning procedure, FAML allows the affinity matrix itself to be adaptively adjusted such that the learned affinity matrix can well capture both the relationship among data and the clustering structure. Thus, FAML has the potential to perform better than other related methods. We derive optimization algorithms to solve the corresponding problems. Extensive unsupervised and semisupervised classification experiments on both synthetic data and real-world benchmark data sets show that the proposed FAML consistently outperforms the state-of-the-art methods. [ABSTRACT FROM AUTHOR]

Spectral clustering has been widely used in various aspects, especially the machine learning fields. Clustering with similarity matrix and low-dimensional representation of data is the main reason of its promising performance shown in spectral clustering. However, such similarity matrix and low-dimensional representation directly derived from input data may not always hold when the data are high dimensional and has complex distribution. First, the similarity matrix simply based on the distance measurement might not be suitable for all kinds of data. Second, the low-dimensional representation might not be able to reflect the manifold structure of the original data. In this brief, we propose a novel linear space embedded clustering method, which uses adaptive neighbors to address the above-mentioned problems. Linearity regularization is used to make the data representation a linear embedded spectral. We also use adaptive neighbors to optimize the similarity matrix and clustering results simultaneously. Extensive experimental results show promising performance compared with the other state-of-the-art algorithms. [ABSTRACT FROM AUTHOR]

As for semisupervised learning, both label information and side information serve as pivotal indicators for the classification. Nonetheless, most of related research works utilize either label information or side information instead of exploiting both of them simultaneously. To address the referred defect, we propose a graph-based semisupervised learning (GSL) problem according to both given label information and side information. To solve the GSL problem efficiently, two novel self-weighted strategies are proposed based on solving associated equivalent counterparts of a GSL problem, which can be widely applied to a spectrum of biobjective optimizations. Different from a conventional technique to amalgamate must-link and cannot-link into a single similarity for convenient optimization, we derive a new parameter-free similarity, upon which intrinsic graph and penalty graph can be separately developed. Consequently, a novel semisupervised classification algorithm can be summarized correspondingly with a theoretical analysis. [ABSTRACT FROM AUTHOR]

This paper examines a matrix-regularized multiple kernel learning (MKL) technique based on a notion of $(r,~p)$ norms. For the problem of learning a linear combination in the support vector machine-based framework, model complexity is typically controlled using various regularization strategies on the combined kernel weights. Recent research has developed a generalized $\ell _{p}$ -norm MKL framework with tunable variable $p$ ($p\ge 1$) to support controlled intrinsic sparsity. Unfortunately, this “1-D” vector $\ell _{p}$ -norm hardly exploits potentially useful information on how the base kernels “interact.” To allow for higher order kernel-pair relationships, we extend the “1-D” vector $\ell _{p}$ -MKL to the “2-D” matrix $(r,~p)$ norms ($1\le r,~p<\infty $). We develop a new formulation and an efficient optimization strategy for $(r,~p)$ -MKL with guaranteed convergence. A theoretical analysis and experiments on seven UCI data sets shed light on the superiority of $(r,~p)$ -MKL over $\ell _{p}$ -MKL in various scenarios. [ABSTRACT FROM AUTHOR]

In this brief, a novel self-weighted orthogonal linear discriminant analysis (SOLDA) problem is proposed, and a self-weighted supervised discriminative feature selection (SSD-FS) method is derived by introducing sparsity-inducing regularization to the proposed SOLDA problem. By using the row-sparse projection, the proposed SSD-FS method is superior to multiple sparse feature selection approaches, which can overly suppress the nonzero rows such that the associated features are insufficient for selection. More specifically, the orthogonal constraint ensures the minimal number of selectable features for the proposed SSD-FS method. In addition, the proposed feature selection method is able to harness the discriminant power such that the discriminative features are selected. Consequently, the effectiveness of the proposed SSD-FS method is validated theoretically and experimentally. [ABSTRACT FROM AUTHOR]

The amount of matrix data has increased rapidly nowadays. How to classify matrix data efficiently is an important issue. In this paper, by discovering the shortages of 2-D linear discriminant analysis and 2-D logistic regression, a novel 2-D framework named rank- $k$ 2-D multinomial logistic regression (2DMLR-RK) is proposed. The 2DMLR-RK is designed for a multiclass matrix classification problem. In the proposed framework, each category is modeled by a left projection matrix and a right projection matrix with rank $k$. The left projection matrices capture the row information of matrix data, and the right projection matrices acquire the column information. We identify the parameter $k$ plays the role of balancing the capacity of learning and generalization of the 2DMLR-RK. In addition, we develop an effective framework for solving the proposed nonconvex optimization problem. The convergence, initialization, and computational complexity are discussed. Extensive experiments on various types of data sets are conducted. Comparing with 1-D methods, 2DMLR-RK not only achieves a better classification accuracy, but also costs less computation time. Comparing with other state-of-the-art 2-D methods, the 2DMLR-RK achieves a better performance for matrix data classification. [ABSTRACT FROM AUTHOR]

Image matting is generally modeled as a space transform from the color space to the alpha space. By estimating the alpha factor of the model, the foreground of an image can be extracted. However, there is some dimensional information redundancy in the alpha space. It usually leads to the misjudgments of some pixels near the boundary between the foreground and the background. In this paper, a manifold matting framework named Patch Alignment Manifold Matting is proposed for image matting. In particular, we first propose a part modeling of color space in the local image patch. We then perform whole alignment optimization for approximating the alpha results using subspace reconstructing error. Furthermore, we utilize Nesterov’s algorithm to solve the optimization problem. Finally, we apply some manifold learning methods in the framework, and obtain several image matting methods, such as named ISOMAP matting and its derived Cascade ISOMAP matting. The experimental results reveal that the manifold matting framework and its two examples are effective when compared with several representative matting methods. [ABSTRACT FROM AUTHOR]

In image classification, feature combination is often used to combine the merits of multiple complementary features and improve the classification accuracy compared with one single feature. Existing feature combination algorithms, e.g., multiple kernel learning, usually determine the weights of features based on the optimization with respect to some classifier-dependent objective function. These algorithms are often computationally expensive, and in some cases are found to perform no better than simple baselines. In this paper, we solve the feature combination problem from a totally different perspective. Our algorithm is based on the simple idea of combining only base kernels suitable to be combined. Since the very aim of feature combination is to obtain the highest possible classification accuracy, we measure the combination suitableness of two base kernels by the maximum possible cross-validation accuracy of their combined kernel. By regarding the pairwise suitableness as the kernel adjacency, we obtain a weighted graph of all base kernels and find that the base kernels suitable to be combined correspond to a cluster in the graph. We then use the dominant sets algorithm to find the cluster and determine the weights of base kernels automatically. In this way, we transform the kernel combination problem into a clustering one. Our algorithm can be implemented in parallel easily and the running time can be adjusted based on available memory to a large extent. In experiments on several data sets, our algorithm generates comparable classification accuracy with the state of the art. [ABSTRACT FROM AUTHOR]

In this paper, we mainly focus on how to achieve the translated subspace representation for each class, which could simultaneously indicate the distribution of the associated class and the differences from its complementary classes. By virtue of the reconstruction problem, the class-specific subspace classifier (CSSC) problem could be represented as a series of biobjective optimization problems, which minimize and maximize the reconstruction errors of the related class and its complementary classes, respectively. Besides, the regularization term is specifically introduced to ensure the whole system’s stability. Accordingly, a regularized class-specific subspace classifier (RCSSC) method can be further proposed based on solving a general quadratic ratio problem. The proposed RCSSC method consistently converges to the global optimal subspace and translation under the variations of the regularization parameter. Furthermore, the proposed RCSSC method could be extended to the unregularized case, which is known as unregularized CSSC (UCSSC) method via orthogonal decomposition technique. As a result, the effectiveness and the superiority of both proposed RCSSC and UCSSC methods can be verified analytically and experimentally. [ABSTRACT FROM PUBLISHER]

Visual feature learning, which aims to construct an effective feature representation for visual data, has a wide range of applications in computer vision. It is often posed as a problem of nonnegative matrix factorization (NMF), which constructs a linear representation for the data. Although NMF is typically parallelized for efficiency, traditional parallelization methods suffer from either an expensive computation or a high runtime memory usage. To alleviate this problem, we propose a parallel NMF method called alternating least square block decomposition (ALSD), which efficiently solves a set of conditionally independent optimization subproblems based on a highly parallelized fine-grained grid-based blockwise matrix decomposition. By assigning each block optimization subproblem to an individual computing node, ALSD can be effectively implemented in a MapReduce-based Hadoop framework. In order to cope with dynamically varying visual data, we further present an incremental version of ALSD, which is able to incrementally update the NMF solution with a low computational cost. Experimental results demonstrate the efficiency and scalability of the proposed methods as well as their applications to image clustering and image retrieval. [ABSTRACT FROM PUBLISHER]

Face sketch–photo synthesis plays an important role in law enforcement and digital entertainment. Most of the existing methods only use pixel intensities as the feature. Since face images can be described using features from multiple aspects, this paper presents a novel multiple representations-based face sketch–photo-synthesis method that adaptively combines multiple representations to represent an image patch. In particular, it combines multiple features from face images processed using multiple filters and deploys Markov networks to exploit the interacting relationships between the neighboring image patches. The proposed framework could be solved using an alternating optimization strategy and it normally converges in only five outer iterations in the experiments. Our experimental results on the Chinese University of Hong Kong (CUHK) face sketch database, celebrity photos, CUHK Face Sketch FERET Database, IIIT-D Viewed Sketch Database, and forensic sketches demonstrate the effectiveness of our method for face sketch–photo synthesis. In addition, cross-database and database-dependent style-synthesis evaluations demonstrate the generalizability of this novel method and suggest promising solutions for face identification in forensic science. [ABSTRACT FROM PUBLISHER]