article

Graph optimization for dimensionality reduction with sparsity constraints

Authors:

Lishan QiaoAuthors Info & Claims

Pattern Recognition, Volume 45, Issue 3

Pages 1205 - 1210

https://doi.org/10.1016/j.patcog.2011.08.015

Published: 01 March 2012 Publication History

Abstract

Graph-based dimensionality reduction (DR) methods play an increasingly important role in many machine learning and pattern recognition applications. In this paper, we propose a novel graph-based learning scheme to conduct Graph Optimization for Dimensionality Reduction with Sparsity Constraints (GODRSC). Different from most of graph-based DR methods where graphs are generally constructed in advance, GODRSC aims to simultaneously seek a graph and a projection matrix preserving such a graph in one unified framework, resulting in an automatically updated graph. Moreover, by applying an l"1 regularizer, a sparse graph is achieved, which models the ''locality'' structure of data and contains natural discriminating information. Finally, extensive experiments on several publicly available UCI and face databases verify the feasibility and effectiveness of the proposed method.

References

[1]

Yan, S.C., Xu, D., Zhang, B.Y., Zhang, H.J., Yang, Q. and Lin, S., Graph embedding and extensions: a general framework for dimensionality reduction. IEEE Transactions on Pattern Analysis and Machine Intelligence. v29 i1. 40-51.

Digital Library

[2]

Tenenbaum, J.B., Silva, V. and Langford, J., A global geometric framework for nonlinear dimensionality reduction. Science. v290 i5500. 2319-2323.

[3]

Roweis, S.T. and Saul, L.K., Nonlinear dimensionality reduction by locally linear embedding. Science. v290 i5500. 2323-2326.

[4]

Belkin, M. and Niyogi, P., Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation. v15 i6. 1373-1396.

[5]

X.F. He, P. Niyogi, Locality preserving projections, in: Neural Information Processing Systems (NIPS), 2003.

[6]

W. Liu, S.-F. Chang, Robust multi-class transductive learning with graphs, in: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2009.

[7]

T. Jebara, J. Wang, S. Chang, Graph construction and b-matching for semi-supervised learning, in: International Conference on Machine Learning (ICML), 2009.

[8]

C. Cortes, M. Mohri, On transductive regression, in: Neural Information Processing Systems (NIPS), 2007.

[9]

M. Maier, U. Luxburg, Influence of graph construction on graph-based clustering measures, in: Neural Information Processing Systems (NIPS), 2008.

[10]

X. Zhu, Semi-supervised Learning Literature Survey, Technical Report, 2008.

[11]

Zhang, L., Qiao, L. and Chen, S., Graph-optimized locality preserving projections. Pattern Recognition. v43 i6. 1993-2002.

[12]

Qiao, L.S., Chen, S.C. and Tan, X.Y., Sparsity preserving projections with applications to face recognition. Pattern Recognition. v43 i1. 331-341.

[13]

Wright, J., Yang, A.Y., Ganesh, A., Sastry, S.S. and Ma, Y., Robust face recognition via sparse representation. IEEE Transactions on Pattern Analysis and Machine Intelligence. v31 i2. 210-227.

[14]

S. Yan, H. Wang, Semi-supervised learning by sparse representation, in: SIAM International Conference on Data Mining (SDM), 2009.

[15]

X.F. He, D. Cai, S.C. Yan, H.J. Zhang, Neighborhood preserving embedding, in: IEEE International Conference on Computer Vision (ICCV), 2005.

[16]

H. Wang, S.C. Yan, D. Xu, X.O. Tang, T. Huang, Trace ratio vs. ratio trace for dimensionality reduction, in: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2007.

[17]

Guo, Y., Li, S., Yang, J., Shu, T. and Wu, L., A generalized Foley-Sammon transform based on generalized fisher discrimimant criterion and its application to face recognition. Pattern Recognition Letters. v24 i1-3. 147-158.

[18]

Jia, Y., Nie, F. and Zhang, C., Trace ratio problem revisited. IEEE Transactions on Neural Networks. v20 i4. 729-735.

[19]

Hesterberg, T., Choi, N.H., Meier, L. and Fraley, C., Least angle and l1 penalized regression: a review. Statistics Surveys. v2. 61-93.

[20]

Liu, J., Ye, J. and Jin, R., Sparse learning with euclidean projection onto l1 ball. Journal of Machine Learning Research.

[21]

J. Liu, S. Ji, J. Ye, SLEP: sparse learning with efficient projections, 2009.

[22]

Nie, F., Xiang, S., Jia, Y. and Zhang, C., Semi-supervised orthogonal discriminant analysis via label propagation. Pattern Recognition. v42. 2615-2627.

[23]

Tseng, P., Convergence of a block coordinate descent method for nondifferentiable minimization. Journal of Optimization Theory and Applications. v109 i3. 475-494.

[24]

Qiao, L.S., Chen, S.C. and Tan, X.Y., Sparsity preserving discriminant analysis for single training image face recognition. Pattern Recognition Letters. v31 i5. 422-429.

[25]

Martinez, A.M. and Kak, A.C., PCA versus LDA. IEEE Transactions on Pattern Analysis and Machine Intelligence. v23 i2. 228-233.

[26]

Lee, K.C., Ho, J. and Kriegman, D.J., Acquiring linear subspaces for face recognition under variable lighting. IEEE Transactions on Pattern Analysis and Machine Intelligence. v27 i5. 684-698.

[27]

Cai, D., He, X.F., Han, J.W. and Zhang, H.J., Orthogonal laplacianfaces for face recognition. IEEE Transactions on Image Processing. v15 i11. 3608-3614.

Cited By

Niu FZhao XGuo JShi MLiu XLiu B(2023)Fast and Robust Unsupervised Dimensionality Reduction with Adaptive Bipartite GraphsKnowledge-Based Systems10.1016/j.knosys.2023.110680276:COnline publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110680
Zhao XNie FYu WLi X(2023)Fast neighborhood reconstruction with adaptive weights learningKnowledge-Based Systems10.1016/j.knosys.2022.110082259:COnline publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110082
Yang ZWang JLi QYi JLiu XNie F(2022)Graph optimization for unsupervised dimensionality reduction with probabilistic neighborsApplied Intelligence10.1007/s10489-022-03534-z53:2(2348-2361)Online publication date: 7-May-2022
https://dl.acm.org/doi/10.1007/s10489-022-03534-z
Show More Cited By

Graph optimization for dimensionality reduction with sparsity constraints
1. Computing methodologies

Recommendations

Discriminative globality and locality preserving graph embedding for dimensionality reduction
Highlights
- Propose the DGLPGE method.
- Design new local and global graph constructions.
Abstract
Graph embedding in dimensionality reduction has attracted much attention in the high-dimensional data analysis. Graph construction in graph embedding plays an important role in the quality of dimensionality reduction. However, the ...
Face recognition using discriminant sparsity neighborhood preserving embedding

In this paper, we propose an effective supervised dimensionality reduction technique, namely discriminant sparsity neighborhood preserving embedding (DSNPE), for face recognition. DSNPE constructs graph and corresponding edge weights simultaneously ...
Sparsity induced locality preserving projection approaches for dimensionality reduction

We consider the problem of sparse subspace learning for data classification and face recognition. New approaches called lα-regularization-based sparse locality preserving projection (α-SLPP) and structural sparse locality preserving projection (SSLPP) ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Pattern Recognition

Pattern Recognition Volume 45, Issue 3

March, 2012

317 pages

ISSN:0031-3203

Issue’s Table of Contents

Copyright © Elsevier Ltd © 2011.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 March 2012

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

30
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Niu FZhao XGuo JShi MLiu XLiu B(2023)Fast and Robust Unsupervised Dimensionality Reduction with Adaptive Bipartite GraphsKnowledge-Based Systems10.1016/j.knosys.2023.110680276:COnline publication date: 27-Sep-2023
https://dl.acm.org/doi/10.1016/j.knosys.2023.110680
Zhao XNie FYu WLi X(2023)Fast neighborhood reconstruction with adaptive weights learningKnowledge-Based Systems10.1016/j.knosys.2022.110082259:COnline publication date: 10-Jan-2023
https://dl.acm.org/doi/10.1016/j.knosys.2022.110082
Yang ZWang JLi QYi JLiu XNie F(2022)Graph optimization for unsupervised dimensionality reduction with probabilistic neighborsApplied Intelligence10.1007/s10489-022-03534-z53:2(2348-2361)Online publication date: 7-May-2022
https://dl.acm.org/doi/10.1007/s10489-022-03534-z
Du HWang YZhang FZhou Y(2020)Low-Rank Discriminative Adaptive Graph Preserving Subspace LearningNeural Processing Letters10.1007/s11063-020-10340-652:3(2127-2149)Online publication date: 4-Sep-2020
https://dl.acm.org/doi/10.1007/s11063-020-10340-6
Yi YWang JZhou WFang YKong JLu Y(2019)Joint graph optimization and projection learning for dimensionality reductionPattern Recognition10.1016/j.patcog.2019.03.02492:C(258-273)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1016/j.patcog.2019.03.024
Yuan MFeng DShi YLiu W(2019)Dimensionality reduction by collaborative preserving Fisher discriminant analysisNeurocomputing10.1016/j.neucom.2019.05.014356:C(228-243)Online publication date: 3-Sep-2019
https://dl.acm.org/doi/10.1016/j.neucom.2019.05.014
Yang BLi Q(2019)Local binary pattern-based discriminant graph construction for dimensionality reduction with application to face recognitionMultimedia Tools and Applications10.1007/s11042-019-7518-378:16(22445-22462)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s11042-019-7518-3
Moujahid ADornaika FRuichek YHammoudi K(2019)Towards semantic segmentation of orthophoto images using graph-based community identificationNeural Computing and Applications10.1007/s00521-017-3056-y31:2(1155-1163)Online publication date: 1-Feb-2019
https://dl.acm.org/doi/10.1007/s00521-017-3056-y
Zhang DHe JZhao Y(2018)Kernel Sparse Representation Based Dimensionality Reduction with Applications to Image ClassificationProceedings of the 3rd International Conference on Intelligent Information Processing10.1145/3232116.3232132(95-100)Online publication date: 19-May-2018
https://dl.acm.org/doi/10.1145/3232116.3232132
Qiao LZhang LChen SShen D(2018)Data-driven graph construction and graph learningNeurocomputing10.1016/j.neucom.2018.05.084312:C(336-351)Online publication date: 27-Oct-2018
https://dl.acm.org/doi/10.1016/j.neucom.2018.05.084
Show More Cited By

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents