Skip to main content
SpringerLink
Log in

Low rank approximation with sparse integration of multiple manifolds for data representation

  • Published:
Applied Intelligence Aims and scope Submit manuscript

Abstract

Manifold regularized techniques have been extensively exploited in unsupervised learning like matrix factorization whose performance is heavily affected by the underlying graph regularization. However, there exist no principled ways to select reasonable graphs under the matrix decomposition setting, particularly in multiple heterogeneous graph sources. In this paper, we deal with the issue of searching for the optimal linear combination space of multiple graphs under the low rank matrix approximation model. Specifically, efficient projection onto the probabilistic simplex is utilized to optimize the coefficient vector of graphs, resulting in the sparse pattern of coefficients. This attractive property of sparsity can be interpreted as a criterion for selecting graphs, i.e., identifying the most discriminative graphs and removing the noisy or irrelevant graphs, so as to boost the low rank decomposition performance. Experimental results over diverse popular image and web document corpora corroborate the effectiveness of our new model in terms of clusterings.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7

Similar content being viewed by others

Notes

  1. http://www.stanford.edu/group/SOL/software/lsqr.html

  2. http://cvxr.com/cvx/

  3. http://users.isy.liu.se/johanl/yalmip/

  4. Both Coil-20 and MNIST can be found at http://www.cad.zju.edu.cn/home/dengcai/Data/MLData.html. The USPS database is downloaded from http://www.cs.nyu.edu/~roweis/data.html.

  5. Both TDT2 and Reuters-21578 are available at http://www.cad.zju.edu.cn/home/dengcai/Data/TextData.html. CiteSeer and Cora can be downloaded from http://www.cs.umd.edu/%7Esen/lbc-proj/LBC.html. Besides, BBC and BBC sport can be accessed under http://mlg.ucd.ie/datasets/bbc.html.

References

  1. Cai D, He X, Han J, Huang T (2011) Graph regularized nonnegative matrix factorization for data representation. IEEE Trans Pattern Anal Mach Intell 33(8):1548–1560

    Article  Google Scholar 

  2. Cai X, Nie F, Cai W, Huang H (2013) Heterogeneous image features integration via multi-modal semi-supervised learning model. In: ICCV

  3. Chen Y, Zhang J, Cai D, Liu W, He X (2013) Nonnegative local coordinate factorization for image representation. IEEE Trans Image Process 22(3):969–979

    Article  MathSciNet  Google Scholar 

  4. Cheng J, Leng C, Li P, Wang M, Lu H (2014) Semi-supervised multi-graph hashing for scalable similarity search. Comput Vis Image Underst 124(0):12–21

    Article  Google Scholar 

  5. Ding C, Li T, Jordan M (2010) Convex and semi-nonnegative matrix factorizations. IEEE Trans Pattern Anal Mach Intell 32(1):45–55

    Article  Google Scholar 

  6. Duchi J, Shalev-Shwartz S, Singer Y, Chandra T (2008) Efficient projections onto the ℓ 1-ball for learning in high dimensions. In: ICML

  7. Gower JC, Dijksterhuis GB (2004) Procrustes problems. Oxford statistical science, vol 30. Oxford University Press, USA

  8. Karasuyama M, Mamitsuka H (2013) Multiple graph label propagation by sparse integration. IEEE Trans Neural Netw Learn Syst 24(12):1999–2012

    Article  Google Scholar 

  9. Kim M (2013) Accelerated max-margin multiple kernel learning. Appl Intell 38(1):45–57

    Article  Google Scholar 

  10. Kuang D, Park H, Ding C H Q (2012) Symmetric nonnegative matrix factorization for graph clustering. In: SDM

  11. Li P, Bu J, Chen C, He Z, Cai D (2013) Relational multimanifold coclustering. IEEE Trans Cybern PP(99):1–11

    Google Scholar 

  12. Li W J, Yeung D Y (2009) Relation regularized matrix factorization. In: IJCAI

  13. Liu H, Wu Z, Li X, Cai D, Huang T (2012) Constrained nonnegative matrix factorization for image representation. IEEE Trans Pattern Anal Mach Intell 34(7):1299–1311

    Article  Google Scholar 

  14. Liu W, He J, Chang S F (2010) Large graph construction for scalable semi-supervised learning. In: ICML

  15. Liu W, Wang J, Chang S F (2012) Robust and scalable graph-based semisupervised learning. Proc IEEE 100(9):2624–2638

    Article  Google Scholar 

  16. Liu W, Wang J, Ji R, Jiang Y G, Chang S F (2012) Supervised hashing with kernels. In: CVPR

  17. Liu X, He J, Lang B (2014) Multiple feature kernel hashing for large-scale visual search. Pattern Recog 47(2):748–757

    Article  Google Scholar 

  18. Lu Z, Peng Y (2013) Exhaustive and efficient constraint propagation: a graph-based learning approach and its applications. Int J Comput Vis 103(3):306–325

    Article  MATH  MathSciNet  Google Scholar 

  19. Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416

    Article  MathSciNet  Google Scholar 

  20. Nesterov Y (2003) Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers

  21. Saad Y (2003) Iterative methods for sparse linear systems, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia

    Book  MATH  Google Scholar 

  22. Shu X, Gao Y, Lu H (2012) Efficient linear discriminant analysis with locality preserving for face recognition. Pattern Recog 45(5):1892–1898

    Article  MATH  Google Scholar 

  23. Wang JJY, Bensmail H, Gao X (2013) Multiple graph regularized nonnegative matrix factorization. Pattern Recog 46(10): 2840–2847

    Article  Google Scholar 

  24. Wang JY, Bensmail H, Gao X (2012) Multiple graph regularized protein domain ranking. BMC Bioinformatics 13(1):1–11

    Article  MATH  Google Scholar 

  25. Wang M, Hua XS, Hong R, Tang J, Qi GJ, Song Y (2009) Unified video annotation via multigraph learning. IEEE Trans Circ Syst Video Technol 19(5):733–746

    Article  Google Scholar 

  26. Wang M, Li H, Tao D, Lu K, Wu X (2012) Multimodal graph-based reranking for web image search. IEEE Trans Image Process 21(11):4649–4661

    Article  MathSciNet  Google Scholar 

  27. Xu B, Bu J, Chen C, Wang C, Cai D, He X (2014) EMR: a scalable graph-based ranking model for content-based image retrieval. IEEE Trans Knowl Data Eng 99 (PrePrints)

  28. Xu C, Tao D, Geng B, Yang L, Hua X S (2012) Ensemble manifold regularization. IEEE Trans Pattern Anal Mach Intell 34(6):1227–1233

    Article  Google Scholar 

  29. Yang YB, Li YN, Pan LY, Li N, He GN (2013) Image retrieval based on augmented relational graph representation. Appl Intell 38(4):489–501

    Article  Google Scholar 

  30. Zhang D, Zhou Z H, Chen S (2007) Semi-supervised dimensionality reduction. In: SDM

  31. Zhang Z, Zhao K (2013) Low-rank matrix approximation with manifold regularization. IEEE Trans Pattern Anal Mach Intell 35(7):1717–1729

    Article  Google Scholar 

Download references

Acknowledgments

The authors would like to thank the anonymous referees for their constructive suggestions and comments. The third author was partially supported by the Research Funds of Shanghai Municipal Science and Technology Commission Grant 12511502902 and the National Natural Science Foundation of China Grant 61375053.

Author information

Authors and Affiliations

  1. Department of Computer Science, City University of Hong Kong, Kowloon, Hong Kong

    Liang Tao & Horace H. S. Ip

  2. Department of Computer Science and Technology, Shanghai University of Finance and Economics, Shanghai, 200433, China

    Yinglin Wang

  3. Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, 200240, China

    Liang Tao & Yinglin Wang

  4. College of Information Science and Technology, Nanjing Agricultural University, Nanjing, 210095, China

    Xin Shu

Authors
  1. Liang Tao
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Horace H. S. Ip
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yinglin Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Xin Shu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Liang Tao.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tao, L., Ip, H.H.S., Wang, Y. et al. Low rank approximation with sparse integration of multiple manifolds for data representation. Appl Intell 42, 430–446 (2015). https://doi.org/10.1007/s10489-014-0600-7

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10489-014-0600-7

Keywords

Search

Navigation