Neighborhood regularized ℓ1-graph

Yingzhen Yang, Jiashi Feng, Jiahui Yu, Jianchao Yang, Pushmeet Kohli, Thomas S. Huang

Research output: Contribution to conferencePaper

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 sparse representation for 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 sparse graph with locally consistent neighborhood by encouraging nearby data to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NRℓ1-Graph with theoretical guarantee on the convergence and the gap between the suboptimal solution and the globally optimal solution in each step of the coordinate descent, which is essential for the overall optimization of NRℓ1-Graph. Its provable accelerated version, NRℓ1-Graph by Random Projection (NRℓ1-Graph-RP) that employs randomized data matrix decomposition, is also presented to improve the efficiency of the optimization of NRℓ1-Graph. Experimental results on various real data sets demonstrate the effectiveness of both NRℓ1-Graph and NRℓ1- Graph-RP.-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 sparse representation for 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 sparse graph with locally consistent neighborhood by encouraging nearby data to have similar neighbors in the constructed sparse graph. We present the optimization algorithm of NRℓ1-Graph with theoretical guarantee on the convergence and the gap between the suboptimal solution and the globally optimal solution in each step of the coordinate descent, which is essential for the overall optimization of NRℓ1-Graph. Its provable accelerated version, NRℓ1-Graph by Random Projection (NRℓ1-Graph-RP) that employs randomized data matrix decomposition, is also presented to improve the efficiency of the optimization of NRℓ1-Graph. Experimental results on various real data sets demonstrate the effectiveness of both NRℓ1-Graph and NRℓ1- Graph-RP.

Original languageEnglish (US)
StatePublished - Jan 1 2017
Event33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017 - Sydney, Australia
Duration: Aug 11 2017Aug 15 2017

Other

Other33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017
CountryAustralia
CitySydney
Period8/11/178/15/17

    Fingerprint

ASJC Scopus subject areas

  • Artificial Intelligence

Cite this

Yang, Y., Feng, J., Yu, J., Yang, J., Kohli, P., & Huang, T. S. (2017). Neighborhood regularized ℓ1-graph. Paper presented at 33rd Conference on Uncertainty in Artificial Intelligence, UAI 2017, Sydney, Australia.