Subspace segmentation, or subspace learning, is a challenging and complicated task in machine learning. This paper builds a primary frame and solid theoretical bases for the minimal subspace segmentation (MSS) of finite samples. The existence and conditional uniqueness of MSS are discussed with conditions generally satisfied in applications. Utilizing weak prior information of MSS, the minimality inspection of segments is further simplified to the prior detection of partitions. The MSS problem is then modeled as a computable optimization problem via the self-expressiveness of samples. A closed form of the representation matrices is first given for the self-expressiveness, and the connection of diagonal blocks is addressed. The MSS model uses a rank restriction on the sum of segment ranks. Theoretically, it can retrieve the minimal sample subspaces that could be heavily intersected. The optimization problem is solved via a basic manifold conjugate gradient algorithm, alternative optimization and hybrid optimization, therein considering solutions to both the primal MSS problem and its pseudo-dual problem. The MSS model is further modified for handling noisy data and solved by an ADMM algorithm. The reported experiments show the strong ability of the MSS method to retrieve minimal sample subspaces that are heavily intersected.

Transferring knowledge from a source domain to a target domain by domain adaptation has been an interesting and challenging problem in many machine learning applications. The key problem is how to match the data distributions of the two heterogeneous domains in a proper way such that they can be treated indifferently for learning. We propose a covariance matching approach DACoM for semi-supervised domain adaptation. The DACoM embeds the original samples into a common latent space linearly such that the covariance mismatch of the two mapped distributions is minimized, and the local geometric structure and discriminative information are preserved simultaneously. The KKT conditions of DACoM model are given as a nonlinear eigenvalue equation. We show that the KKT conditions could at least ensure local optimality. An efficient eigen-updating algorithm is then given for solving the nonlinear eigenvalue problem, whose convergence is guaranteed conditionally. To deal with the case when homogeneous information could only be matched nonlinearly, a kernel version of DACoM is further considered. We also analyze the generalization bound for our domain adaptation approaches. Numerical experiments on simulation datasets and real-world applications are given to comprehensively demonstrate the effectiveness and efficiency of the proposed approach. The experiments show that our method outperforms other existing methods for both homogeneous and heterogeneous domain adaptation.

Representation based methods for subspace learning consist of two stages: Affinity learning and spectral clustering. This letter proposes a feedback strategy to softly combine the two separate stages together by simultaneously optimizing the affinity and spectral projection. The soft feedback strategy can strengthen the required block-diagonal structure of the affinity matrix for most of the existing state-of-art algorithms. Using the feedback strategy, a scalable and projection unified model is given for datasets in large scale. A fast and efficient algorithm is also given to solve this problem, based on active piece-wise sign updating. Experiments are reported to demonstrate the improvement for the existing algorithms and the effectiveness and efficiency of the proposed model on large scale datasets.

Multi-view learning aims to integrate multiple data information from different views to improve the learning performance. The key problem is to handle the unconformities or distortions among view-specific samples or measurements of similarity or dissimilarity. This paper models the view-specific samples as a nonlinear mapping of uniform but latent intact samples for all the views, and the view-specific dissimilarity matrices or similarity matrices are estimated in terms of the uniform latent one. Two methods are then developed for multi-view clustering. One makes use of uniform multidimensional scaling (UMDS) on multi-view dissimilarities or kernels. The other one uses a uniform class assignment (UCA) procedure that optimally extracts the cluster components contained in the view-specific similarity matrices. These two methods result in the same optimization model, subjected to some slightly different constraints. A first-order condition of solutions is given as a nonlinear eigenvalue problem, and a second order condition guarantees local optimality. The nonlinear eigenvalue problem is solved by an iterative algorithm via eigen-space updating, and its convergence is proven. Furthermore, a fast implementation of the algorithm is discussed, which adopts the strategy of restarting subspace extension. Numerical experiments on some real-world data sets provide good support to the proposed methods.

This paper proposes a new model of low-rank matrix factorization that incorporates manifold regularization to the matrix factorization. Superior to the graph-regularized nonnegative matrix factorization, this new regularization model has globally optimal and closed-form solutions. A direct algorithm (for data with small number of points) and an alternate iterative algorithm with inexact inner iteration (for large scale data) are proposed to solve the new model. A convergence analysis establishes the global convergence of the iterative algorithm. The efficiency and precision of the algorithm are demonstrated numerically through applications to six real-world datasets on clustering and classification. Performance comparison with existing algorithms shows the effectiveness of the proposed method for low-rank factorization in general.

Manifold learning algorithms seek to find a low-dimensional parameterization of high-dimensional data. They heavily rely on the notion of what can be considered as local, how accurately the manifold can be approximated locally, and, last but not least, how the local structures can be patched together to produce the global parameterization. In this paper, we develop algorithms that address two key issues in manifold learning: 1) the adaptive selection of the local neighborhood sizes when imposing a connectivity structure on the given set of high-dimensional data points and 2) the adaptive bias reduction in the local low-dimensional embedding by accounting for the variations in the curvature of the manifold as well as its interplay with the sampling density of the data set. We demonstrate the effectiveness of our methods for improving the performance of manifold learning algorithms using both synthetic and real-world data sets.

Given a finite number of data points sampled from a low-dimensional manifold embedded in a high dimensional space together with the parameter vectors for a subset of the data points, we need to determine the parameter vectors for the rest of the data points. This problem is known as semi-supervised manifold learning, and in this paper we propose methods to handle this problem by solving certain eigenvalue-problems. Our proposed methods address two key issues in semi-supervised manifold learning: 1) fitting of the local affine geometric structures, and 2) preserving the global manifold structures embodied in the overlapping neighborhoods around each data points. We augment the alignment matrix of local tangent space alignment (LTSA) with the orthogonal projection based on the known parameter vectors, giving rise to the eigenvalue problem that characterizes the semi-supervised manifold learning problem. We also discuss the roles of different types of neighborhoods and their influence on the learning process. We illustrate the performance of the proposed methods using both synthetic data sets as well as data sets arising from applications in video annotations.

The locally linear embedding (LLE) is improved by introducing multiple linearly independent local weight vectors for each neighborhood. We characterize the reconstruction weights and show the existence of the linearly independent weight vectors at each neighborhood. The modified locally linear embedding (MLLE) proposed in this paper is much stable. It can retrieve the ideal embedding if MLLE is applied on data points sampled from an isometric manifold. MLLE is also compared with the local tangent space alignment (LTSA). Numerical examples are given that show the improvement and efficiency of MLLE.

The recent Maximum Weighted Likelihood (MWL) [18], [19] has provided a general learning paradigm for density-mixture model selection and learning, in which weight design, however, is a key issue. This paper will therefore explore such a design, and through which a heuristic extended Expectation-Maximization (X-EM) algorithm is presented accordingly. Unlike the EM algorithm [1], the X-EM algorithm is able to perform model selection by fading the redundant components out from a density mixture, meanwhile estimating the model parameters appropriately. The numerical simulations demonstrate the efficacy of our algorithm.

Local manifold learning methods produce a collection of overlapping local coordinate systems from a given set of sample points. Alignment is the process to stitch those local systems together to produce a global coordinate system and is done through the computation of the eigensubspace of a so-called alignment matrix. In this paper, we present an analysis of the eigenstructure of the alignment matrix giving both necessary and sufficient conditions under which the null space of the alignment matrix recovers the global coordinate system. We also show by analyzing examples that the gap in the spectrum of the alignment matrix is proportional to the size of the overlap of the local coordinate systems. Our results pave the way for gaining better understanding of the performance of local manifold learning methods.

We propose a fast manifold learning algorithm based on the methodology of domain decomposition. Starting with the set of sample points partitioned into two subdomains, we develop the solution of the interface problem that can glue the embeddings on the two subdomains into an embedding on the whole domain. We provide a detailed analysis to assess the errors produced by the gluing process using matrix perturbation theory. Numerical examples are given to illustrate the efficiency and effectiveness of the proposed methods.

Recently, there have been several advances in the machine learning and pattern recognition communities for developing manifold learning algo- rithms to construct nonlinear low-dimensional manifolds from sample data points embedded in high-dimensional spaces. In this paper, we de- velop algorithms that address two key issues in manifold learning: 1) the adaptive selection of the neighborhood sizes; and 2) better fitting the local geometric structure to account for the variations in the curvature of the manifold and its interplay with the sampling density of the data set. We also illustrate the effectiveness of our methods on some synthetic data sets.