Abstract：In graph-based machine learning algorithms, the construction of the graph representing the data structure is the key issue. In this paper, a non-negative and sparse graph construction algorithm based on split Bregman method is presented. A weight matrix is learned by solving an equality formulation of the sparse representation through split Bregman method. In the weight matrix, each data sample can be represented by a non-negative linear combination of other samples. The constructed graph of the proposed algorithm can capture the linear relationship between data samples. Experimental results under semi-supervised learning framework demonstrate that the proposed algorithm can capture the latent structure information of data well.
[1] Zhu X J, Ghahramani Z B, Lafferty J. Semi-supervised Learning Using Gaussian Fields and Harmonic Functions // Proc of the 20th International Conference on Machine Learning. Washington, USA, 2003: 912-919 [2] Zhou D Y, Bousquet O, Lal T N, et al. Learning with Local and Global Consistency[EB/OL].[2014-02-25]. http://papers.nips.cc/paper/2506-learning-with-local-and-global-consistency.pdf [3] Roweis S T, Saul L K. Nonlinear Dimensionality Reduction by Locally Linear Embedding. Science, 2000, 290(5500): 2323-2326 [4] Yan S C, Wang H. Semi-supervised Learning by Sparse Representation // Proc of the SIAM International Conference on Data Mining. Sparks, USA, 2009: 792-801 [5] Cheng B, Yang J C, Yan S C, et al. Learning with l1-Graph for Image Analysis. IEEE Trans on Image Processing, 2010, 19(4): 858-866 [6] Zhuang L S, Gao H Y, Lin Z C, et al. Non-negative Low Rank and Sparse Graph for Semi-supervised Learning // Proc of the IEEE Conference on Computer Vision and Pattern Recognition. Providence, USA, 2012: 2328-2335 [7] Liu G C, Lin Z C, Yu Y. Robust Subspace Segmentation by Low-Rank Representation // Proc of the 27th International Conference on Machine Learning. Haifa, Israel, 2010: 663-670 [8] Szlam A, Guo Z H, Osher S. A Split Bregman Method for Non-ne-gative Sparsity Penalized Least Squares with Applications to Hyperspectral Demixing // Proc of the 17th IEEE International Conference on Image Processing. Hong Kong, China, 2010: 1917-1920 [9] Yin W T, Osher S, Goldfarb D, et al. Bregman Iterative Algorithms for l1-Minimization with Applications to Compressed Sensing. SIAM Journal on Imaging Sciences, 2008, 1(1): 143-168 [10] Osher S, Mao Y, Dong B, et al. Fast Linearized Bregman Iteration for Compressive Sensing and Sparse Denoising. Communications in Mathematical Sciences, 2010, 8(1): 93-111 [11] Goldstein T, Osher S. The Split Bregman Method for l1-Regula-rized Problems. SIAM Journal on Imaging Sciences, 2009, 2(2): 323-343
2015, Vol. 28 
