A non-negative representation learning algorithm for selecting neighbors

摘要

A crucial step in many manifold clustering and embedding algorithms involves selecting the neighbors of a data point. In this paper, a non-negative representation learning algorithm is proposed to select the neighbors of a data point, so that they are almost always lying in the tangent space of the manifold at the given query point. This is very important to multi-manifold clustering and manifold embedding. Convex geometry theory states that a data point on a face of a convex polytope can be a convex combination of the vertices of the polytope, and that the non-zero combination scalars correspond to the vertices of the face the point lies on. The intent of this paper is to use points that that are near to a point as the vertices of a convex polytope, and select the vertices on the same face as this point to be the neighbors. Clearly, the point can be a convex combination of its neighbors. We can observe that these neighbors almost always lie in the tangent space of the manifold at the query point and can preserve the local manifold structure well. Based on this basic idea, we construct an objective function. Moreover, an augmented Lagrange multipliers method is proposed for solving it to derive a non-negative representation, and then the neighbors of a data point can be obtained. The result of our neighbor selection algorithm can be used by other clustering methods such as LEM or manifold embedding methods such as LLE. We demonstrate the effectiveness and efficiency of the proposed method through experiments on synthetic data and a real-world problem.