Neighborhood Regularized ℓ1-Graph

Abstract

ℓ1-Graph, which learns a sparse graph over the data by sparse representation, has been demonstrated to be effective in clustering especially for high-dimensional data. Although it achieves compelling performance, the sparse graph generated by ℓ1-Graph ignores the geometric information of the data by treating each datum separately. To obtain a sparse graph that is aligned to the underlying manifold structure of the data, we propose the novel Neighborhood Regularized ℓ1-Graph (NRℓ1-Graph). NRℓ1-Graph learns a sparse graph with locally consistent neighborhoods by encouraging nearby data points to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NRℓ1-Graph with theoretical guarantees on convergence and the gap between the suboptimal and globally optimal solution in each coordinate descent step.