research-article

Robust Subspace Clustering via Tighter Rank Approximation

Authors:

Qiang ChengAuthors Info & Claims

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

Pages 393 - 401

https://doi.org/10.1145/2806416.2806506

Published: 17 October 2015 Publication History

Abstract

Matrix rank minimization problem is in general NP-hard. The nuclear norm is used to substitute the rank function in many recent studies. Nevertheless, the nuclear norm approximation adds all singular values together and the approximation error may depend heavily on the magnitudes of singular values. This might restrict its capability in dealing with many practical problems. In this paper, an arctangent function is used as a tighter approximation to the rank function. We use it on the challenging subspace clustering problem. For this nonconvex minimization problem, we develop an effective optimization procedure based on a type of augmented Lagrange multipliers (ALM) method. Extensive experiments on face clustering and motion segmentation show that the proposed method is effective for rank approximation.

References

[1]

A. Beck and M. Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences, 2(1):183--202, 2009.

Digital Library

[2]

J.-F. Cai, E. J. Candès, and Z. Shen. A singular value thresholding algorithm for matrix completion. SIAM Journal on Optimization, 20(4):1956--1982, 2010.

Digital Library

[3]

E. J. Candès and B. Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 9(6):717--772, 2009.

Digital Library

[4]

E. J. Candès and T. Tao. The power of convex relaxation: Near-optimal matrix completion. Information Theory, IEEE Transactions on, 56(5):2053--2080, 2010.

Digital Library

[5]

G. Chen and G. Lerman. Spectral curvature clustering (scc). International Journal of Computer Vision, 81(3):317--330, 2009.

Digital Library

[6]

F. H. Clarke. Optimization and nonsmooth analysis, volume 5. Siam, 1990.

[7]

E. Elhamifar and R. Vidal. Sparse subspace clustering. In Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on, pages 2790--2797. IEEE, 2009.

[8]

E. Elhamifar and R. Vidal. Clustering disjoint subspaces via sparse representation. In Acoustics Speech and Signal Processing (ICASSP), 2010 IEEE International Conference on, pages 1926--1929. IEEE, 2010.

[9]

E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm, theory, and applications. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 35(11):2765--2781, 2013.

Digital Library

[10]

P. Favaro, R. Vidal, and A. Ravichandran. A closed form solution to robust subspace estimation and clustering. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 1801--1807. IEEE, 2011.

Digital Library

[11]

M. Fazel. Matrix rank minimization with applications. PhD thesis, PhD thesis, Stanford University, 2002.

[12]

P. Gong, J. Ye, and C.-s. Zhang. Multi-stage multi-task feature learning. In Advances in Neural Information Processing Systems, pages 1988--1996, 2012.

Digital Library

[13]

R. Horst and N. V. Thoai. Dc programming: overview. Journal of Optimization Theory and Applications, 103(1):1--43, 1999.

Digital Library

[14]

Y. Hu, D. Zhang, J. Ye, X. Li, and X. He. Fast and accurate matrix completion via truncated nuclear norm regularization. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 35(9):2117--2130, 2013.

Digital Library

[15]

K. Kanatani. Motion segmentation by subspace separation and model selection. In Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, volume 2, pages 586--591, 2001.

[16]

Z. Kang, C. Peng, J. Cheng, and Q. Cheng. Logdet rank minimization with application to subspace clustering. Computational Intelligence and Neuroscience, 2015, 2015.

[17]

F. Lauer and C. Schnorr. Spectral clustering of linear subspaces for motion segmentation. In Computer Vision, 2009 IEEE 12th International Conference on, pages 678--685. IEEE, 2009.

[18]

K.-C. Lee, J. Ho, and D. Kriegman. Acquiring linear subspaces for face recognition under variable lighting. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 27(5):684--698, 2005.

Digital Library

[19]

A. S. Lewis and H. S. Sendov. Nonsmooth analysis of singular values. part i: Theory. Set-Valued Analysis, 13(3):213--241, 2005.

[20]

Z. Lin, R. Liu, and Z. Su. Linearized alternating direction method with adaptive penalty for low-rank representation. In Advances in neural information processing systems, pages 612--620, 2011.

Digital Library

[21]

G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma. Robust recovery of subspace structures by low-rank representation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 35(1):171--184, 2013.

Digital Library

[22]

G. Liu, Z. Lin, and Y. Yu. Robust subspace segmentation by low-rank representation. In Proceedings of the 27th International Conference on Machine Learning (ICML-10), pages 663--670, 2010.

Digital Library

[23]

G. Liu, H. Xu, and S. Yan. Exact subspace segmentation and outlier detection by low-rank representation. In AISTATS, pages 703--711, 2012.

[24]

C. Lu, J. Tang, S. Y. Yan, and Z. Lin. Generalized nonconvex nonsmooth low-rank minimization. In IEEE International Conference on Computer Vision and Pattern Recognition. IEEE, 2014.

Digital Library

[25]

Y. Ma, H. Derksen, W. Hong, and J. Wright. Segmentation of multivariate mixed data via lossy data coding and compression. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 29(9):1546--1562, 2007.

Digital Library

[26]

K. Mohan and M. Fazel. Iterative reweighted algorithms for matrix rank minimization. The Journal of Machine Learning Research, 13(1):3441--3473, 2012.

Digital Library

[27]

B. Nasihatkon and R. Hartley. Graph connectivity in sparse subspace clustering. In Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on, pages 2137--2144. IEEE, 2011.

Digital Library

[28]

A. Y. Ng, M. I. Jordan, Y. Weiss, et al. On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2:849--856, 2002.

Digital Library

[29]

F. Nie, H. Huang, and C. H. Ding. Low-rank matrix recovery via efficient schatten p-norm minimization. In AAAI, 2012.

Digital Library

[30]

S. Rao, R. Tron, R. Vidal, and Y. Ma. Motion segmentation in the presence of outlying, incomplete, or corrupted trajectories. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 32(10):1832--1845, 2010.

Digital Library

[31]

B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471--501, 2010.

Digital Library

[32]

B. Recht, W. Xu, and B. Hassibi. Null space conditions and thresholds for rank minimization. Mathematical programming, 127(1):175--202, 2011.

Digital Library

[33]

J. Shi and J. Malik. Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 22(8):888--905, 2000.

Digital Library

[34]

M. Soltanolkotabi, E. J. Candes, et al. A geometric analysis of subspace clustering with outliers. The Annals of Statistics, 40(4):2195--2238, 2012.

[35]

R. Tron and R. Vidal. A benchmark for the comparison of 3-d motion segmentation algorithms. In Computer Vision and Pattern Recognition, 2007. CVPR'07. IEEE Conference on, pages 1--8. IEEE, 2007.

[36]

R. Vidal. A tutorial on subspace clustering. IEEE Signal Processing Magazine, 28(2):52--68, 2010.

[37]

R. Vidal and P. Favaro. Low rank subspace clustering (lrsc). Pattern Recognition Letters, 43:47--61, 2014.

[38]

Y.-X. Wang and H. Xu. Noisy sparse subspace clustering. In Proceedings of The 30th International Conference on Machine Learning, pages 89--97, 2013.

Digital Library

[39]

S. Xiang, X. Tong, and J. Ye. Efficient sparse group feature selection via nonconvex optimization. In Proceedings of the 30th International Conference on Machine Learning (ICML-13), pages 284--292, 2013.

[40]

J. Yan and M. Pollefeys. A general framework for motion segmentation: Independent, articulated, rigid, non-rigid, degenerate and non-degenerate. In Computer Vision--ECCV 2006, pages 94--106. Springer, 2006.

Digital Library

[41]

J. Yang, W. Yin, Y. Zhang, and Y. Wang. A fast algorithm for edge-preserving variational multichannel image restoration. SIAM Journal on Imaging Sciences, 2(2):569--592, 2009.

Digital Library

[42]

Z. Zhang and B. Tu. Nonconvex penalization using laplace exponents and concave conjugates. In Advances in Neural Information Processing Systems, pages 611--619, 2012.

[43]

Y.-B. Zhao. An approximation theory of matrix rank minimization and its application to quadratic equations. Linear Algebra and its Applications, 437(1):77--93, 2012.

Cited By

Zhang HZhao JZhang BGong CQian JYang J(2024) Unified Framework for Faster Clustering via Joint Schatten p -Norm Factorization With Optimal Mean IEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.332771635:3(3012-3026)Online publication date: Mar-2024
https://doi.org/10.1109/TNNLS.2023.3327716
Hu DQu QLiu ZChen WWang Z(2024)Subspace clustering based on latent low-rank representation with transformed Schatten-1 penalty functionKnowledge-Based Systems10.1016/j.knosys.2024.112538304(112538)Online publication date: Nov-2024
https://doi.org/10.1016/j.knosys.2024.112538
Qu QWang ZChen W(2022)Robust Subspace Clustering Based on Latent Low-rank Representation with Weighted Schatten-p Norm MinimizationPRICAI 2022: Trends in Artificial Intelligence10.1007/978-3-031-20862-1_37(504-515)Online publication date: 10-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20862-1_37
Show More Cited By

Index Terms

Robust Subspace Clustering via Tighter Rank Approximation
1. Computing methodologies
  1. Machine learning
    1. Learning paradigms
      1. Unsupervised learning
        Cluster analysis

Recommendations

Schatten-q regularizer constrained low rank subspace clustering model

In the global low rank spectral subspace clustering model, the rank minimization problem is relaxed as Nuclear Norm Minimization (NNM) problem. This relaxation is widely used due to its convexity. However, in recent years, the non-convex regularization ...
Subspace clustering based on latent low rank representation with Frobenius norm minimization

The problem of subspace clustering which refers to segmenting a collection of data samples approximately drawn from a union of linear subspaces is considered in this paper. Among existing subspace clustering algorithms, low rank representation (LRR) ...
Robust Sparse and Low-rank Subspace Clustering with Log-based Nonconvex Approximations
ICBDT '22: Proceedings of the 5th International Conference on Big Data Technologies

In this paper, we propose a new subspace clustering method that learns a simultaneous low-rank and sparse representation matrix from data. Other than using the nuclear and ℓ1 norms, nonconvex low-rank and sparse approximations are adopted to more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CIKM '15: Proceedings of the 24th ACM International on Conference on Information and Knowledge Management

October 2015

1998 pages

ISBN:9781450337946

DOI:10.1145/2806416

General Chairs:
James Bailey
The University of Melbourne
,
Alistair Moffat
The University of Melbourne
,
Program Chairs:
Charu C. Aggarwal
IBM
,
Maarten de Rijke
University of Amsterdam
,
Ravi Kumar
Google
,
Vanessa Murdock
Microsoft
,
Timos Sellis
RMIT University
,
Jeffrey Xu Yu
Chinese University of Hong Kong

Copyright © 2015 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 October 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

US National Science Foundation

Conference

CIKM'15

Sponsor:

CIKM'15: 24th ACM International Conference on Information and Knowledge Management

October 18 - 23, 2015

Melbourne, Australia

Acceptance Rates

CIKM '15 Paper Acceptance Rate 165 of 646 submissions, 26%;

Overall Acceptance Rate 1,861 of 8,427 submissions, 22%

Upcoming Conference

CIKM '25

Sponsor:
sigir
sigir

The 34th ACM International Conference on Information and Knowledge Management

November 10 - 14, 2025

Seoul , Republic of Korea

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

17
Total Citations
View Citations
494
Total Downloads

Downloads (Last 12 months)14
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang HZhao JZhang BGong CQian JYang J(2024) Unified Framework for Faster Clustering via Joint Schatten p -Norm Factorization With Optimal Mean IEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2023.332771635:3(3012-3026)Online publication date: Mar-2024
https://doi.org/10.1109/TNNLS.2023.3327716
Hu DQu QLiu ZChen WWang Z(2024)Subspace clustering based on latent low-rank representation with transformed Schatten-1 penalty functionKnowledge-Based Systems10.1016/j.knosys.2024.112538304(112538)Online publication date: Nov-2024
https://doi.org/10.1016/j.knosys.2024.112538
Qu QWang ZChen W(2022)Robust Subspace Clustering Based on Latent Low-rank Representation with Weighted Schatten-p Norm MinimizationPRICAI 2022: Trends in Artificial Intelligence10.1007/978-3-031-20862-1_37(504-515)Online publication date: 10-Nov-2022
https://dl.acm.org/doi/10.1007/978-3-031-20862-1_37
Zhu WPeng BChen CDemartini GZuccon GCulpepper JHuang ZTong H(2021)Self-Supervised Embedding for Subspace ClusteringProceedings of the 30th ACM International Conference on Information & Knowledge Management10.1145/3459637.3482178(3687-3691)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3459637.3482178
Wu FLi YLi CWu Y(2021)A Fast Tensor Completion Method Based on Tensor QR Decomposition and Tensor Nuclear Norm MinimizationIEEE Transactions on Computational Imaging10.1109/TCI.2021.31309777(1267-1277)Online publication date: 2021
https://doi.org/10.1109/TCI.2021.3130977
Liu QDavoine FYang JCui YJin ZHan F(2019)A Fast and Accurate Matrix Completion Method Based on QR Decomposition and $L_{2,1}$ -Norm MinimizationIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2018.285195730:3(803-817)Online publication date: Mar-2019
https://doi.org/10.1109/TNNLS.2018.2851957
Zhou FWu YDai YWang PNi K(2019)Graph-Regularized Laplace Approximation for Detecting Small Infrared Target Against Complex BackgroundsIEEE Access10.1109/ACCESS.2019.29255637(85354-85371)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2925563
Shi CHuang ZWan LXiong T(2019)Low-Rank Tensor Completion Based on Log-Det Rank Approximation and Matrix FactorizationJournal of Scientific Computing10.1007/s10915-019-01009-x80:3(1888-1912)Online publication date: 1-Sep-2019
https://dl.acm.org/doi/10.1007/s10915-019-01009-x
Zhang XGao YLan LGuo XHuang XLuo Z(2018)Low-Rank Matrix Recovery via Continuation-Based Approximate Low-Rank MinimizationPRICAI 2018: Trends in Artificial Intelligence10.1007/978-3-319-97304-3_43(559-573)Online publication date: 27-Jul-2018
https://doi.org/10.1007/978-3-319-97304-3_43
Peng CKang ZXu FChen YCheng Q(2017)Image Projection Ridge Regression for Subspace ClusteringIEEE Signal Processing Letters10.1109/LSP.2017.270085224:7(991-995)Online publication date: Jul-2017
https://doi.org/10.1109/LSP.2017.2700852
Show More Cited By

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten