Dimensionality reduction is a critical technology in the domain of pattern recognition, and linear discriminant analysis (LDA) is one of the most popular supervised dimensionality reduction methods. However, whenever its distance criterion of objective function uses $L_{2}-norm$, it is sensitive to outliers. In this paper, we propose a new formulation of linear discriminant analysis via joint $L_{2,1}-norm$ minimization on objective function to induce robustness, so as to efficiently alleviate the influence of outliers and improve the robustness of proposed method. An efficient iterative algorithm is proposed to solve the optimization problem and proved to be convergent. Extensive experiments are performed on an artificial data set, on UCI data sets and on four face data sets, which sufficiently demonstrates the efficiency of comparing to other methods and robustness to outliers of our approach.
24 December 2019 in IEEE Transactions on Pattern Analysis and Machine Intelligence
Linear Discriminant Analysis (LDA) is one of the most successful supervised dimensionality reduction methods and has been widely used in many real-world applications. However, the ${l}_{2}$ -norm is employed as the distance measure in objective of LDA, which is sensitive to outliers. Many previous works improve the robustness of LDA by using L1-norm distance. However, the robustness against outliers is limited and the solver of L1-norm are mostly based on greedy search strategy, which is time-consuming and easy to get stuck in a local optimum. In this paper, we propose a novel robust LDA measured by ${l}_{2,1}$ -norm to learn robust discriminative projections. Since the proposed model needs to minimize and maximize (minmax) ${l}_{2,1}$ -norm terms simultaneously, it is challenging to solve. As a result, we first systematically derive an efficient iterative optimization algorithm to solve a general ratio minimization problem, and rigorously prove its convergence. More importantly, an efficient non-greedy iterative re-weighted optimization algorithm is developed based on preceding approach for solving proposed ${l}_{2,1}$ -norm minmax problem. Besides, an optimal weighted mean mechanism is driven according to designed objective and solver, which can be applied to other approach for robustness improvement. Extensive experimental results on several real-world datasets show the effectiveness of proposed method.
In this article, we propose a novel feature selection approach via explicitly addressing the long-standing subspace sparsity issue. Leveraging ℓ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 ℓ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 (S²DFS) 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.
Due to the multimodality of non-Gaussian data, traditional globality-preserved dimensionality reduction (DR) methods, such as linear discriminant analysis (LDA) and principal component analysis (PCA) are difficult to deal with. In this paper, we present a novel local DR framework via auto-optimized graph embedding to extract the intrinsic submanifold structure of multimodal data. Specifically, the proposed model seeks to learn an embedding space which can preserve the local neighborhood structure by constructing a k-nearest neighbors (kNNs) graph on data points. Different than previous works, our model employs the l₀-norm constraint and binary constraint on the similarity matrix to impose that there only be a k nonzero value in each row of the similarity matrix, which can ensure the k-connectivity in graph. More important, as the high-dimensional data probably contains some noises and redundant features, calculating the similarity matrix in the original space by using a kernel function is inaccurate. As a result, a mechanism of an auto-optimized graph is derived in the proposed model. Concretely, we learn the embedding space and similarity matrix simultaneously. In other words, the selection of neighbors is automatically executed in the optimal subspace rather than in the original space when the algorithm reaches convergence, which can alleviate the affect of noises and improve the robustness of the proposed model. In addition, four supervised and semisupervised local DR methods are derived by the proposed framework which can extract the discriminative features while preserving the submanifold structure of data. Last but not least, since two variables need to be optimized simultaneously in the proposed methods, and the constraints on the similarity matrix are difficult to satisfy, which is an NP-hard problem. Consequently, an efficient iterative optimization algorithm is introduced to solve the proposed problems. Extensive experiments conducted on synthetic data and several real-world datasets have demonstrated the advantages of the proposed methods in robustness and recognition accuracy.
3 February 2020 in ACM Transactions on Knowledge Discovery From Data
Dimensionality reduction plays a significant role in high-dimensional data processing, and Linear Discriminant Analysis (LDA) is a widely used supervised dimensionality reduction approach. However, a major drawback of LDA is that it is incapable of extracting the local structure information, which is crucial for handling multimodal data. In this article, we propose a novel supervised dimensionality reduction method named Adaptive Local Linear Discriminant Analysis (ALLDA), which adaptively learns a k -nearest neighbors graph from data themselves to extract the local connectivity of data. Furthermore, the original high-dimensional data usually contains noisy and redundant features, which has a negative impact on the evaluation of neighborships and degrades the subsequent classification performance. To address this issue, our method learns the similarity matrix and updates the subspace simultaneously so that the neighborships can be evaluated in the optimal subspaces where the noises have been removed. Through the optimal graph embedding, the underlying sub-manifolds of data in intra-class can be extracted precisely. Meanwhile, an efficient iterative optimization algorithm is proposed to solve the minimization problem. Promising experimental results on synthetic and real-world datasets are provided to evaluate the effectiveness of proposed method.