Subspace Clustering: Recent Advances in Algorithms, Theories and Applications

Chun-Guang Li, Chong You, and Guangcan Liu  

Tutorial Abstract

In many real-world applications, we need to deal with high-dimensional datasets, such as images, videos, text, gene expression microarray, and more. Such high-dimensional datasets can often be well approximated by multiple low-dimensional subspaces corresponding to multiple classes or categories. Therefore, the problem, known in the literature as Subspace Clustering, which addresses the task of learning a union of low-rank structures from unlabeled data, has become an indispensable tool for learning from high dimensional data. This problem has many applications, e.g., image representation and compression, motion segmentation, and temporal video segmentation in computer vision; hybrid system identification in control; community clustering in social networks; and genes expression profiles clustering in bioinformatics.
In this tutorial, we will: a) Introduce the representative spectral clustering based subspace clustering methods, the theoretical guarantees, and their representative applications; b) Present the recent advances in scalable subspace clustering methods, the theoretical guarantees, and the representative applications, e.g., image clustering and outliers detections; c) Present the recent advances in low-rankness based methods for learning low-rank structures, the theoretical guarantees, and the representative applications, e.g., saliency detection, music / gene expression array analysis; d) Present the recent advances in optimization algorithms for sparse and low-rank modeling, including the convex optimization, non-convex optimization, and online optimization.

Tutorial Outline

Ø  Introduction to Union of Subspace (5min, Speaker: Chun-Guang Li)
    · Introduction to Multiple Subspaces
    · Problem Statements (Subspace Clustering)
Ø  Subspace Clustering (40 min, Speaker: Chun-Guang Li)
    · Two-Step Modeling for Multiple Subspaces
       i. Self-Expression Model
       ii. Subspace-Preserving Property and Theoretical Guarantees
    · Joint Optimization Modeling for Multiple Subspaces
       i. Structured Subspace Clustering
       ii. Semi-Supervised Setting
       iii. Handle Missing Values
    · Representative Applications
       i. Motion Segmentation / Cancer Subtype Clustering
Ø  Scalable Subspace Clustering (45min, Speaker: Chong You)
    · Representative Methods
       i. Sparse Subspace Clustering by Orthogonal Matching Pursuit (SSC-OMP)ii. Scalable Elastic Net Subspace Clustering (EnSC)
Ø  Theoretical Results
    · Recoverability of SSC-OMP and EnSC
    · Connectivity of EnSC
Ø  Representative Applications
    · Image/Video Segmentation
    · Outlier Detection in a Union of Subspaces
Ø  Low-Rankness based Subspace Clustering (45min, Speaker: Guangcan Liu)
    · Representative Models
       i. Low-Rank Representation (LRR) based Subspace Clustering
       ii. Variants of LRR
    · Analysis on LRR
       i. Closed-form Solutions in Noiseless Case
       ii. Exact Recoverability - Deterministic Analysis
       iii. Exact Recoverability - Probabilistic Analysis
    · Representative Applications
       i. Saliency Detection
       ii. Scene/Music/Genetic Analysis
Ø  Efficient Optimization Algorithms (45min, Speaker: Risheng Liu)
    · Brief review on first order optimization
    · Convex optimization for sparse and low-rank modeling
       i. Accelerated proximal gradient and its variations
       ii. Alternating direction method of multiplier and its variations
    · c) Non-convex optimization for sparse and low-rank modeling
       i. Exact non-convex optimization
       ii. Inexact non-convex optimization
       iii. Deep unrolling for non-convex optimization
    · Online optimization for low-rank modeling

Speaker Interlocution

Chun-Guang Li is an associate professor with the School of Information and Communication Engineering, at Beijing University of Posts and Telecommunications from Dec. 2007. He received his B.E. degree in telecommunication engineering from Jilin University in July 2002, and his Ph.D. degree in signal and information processing from Beijing University of Posts and Telecommunications in Dec. 2007. He visited in the Vision, Dynamics and Learning lab at the Center for Imaging Science in Johns Hopkins University from Dec. 2012 to Nov. 2013, and the Visual Computing group at Microsoft Research Asia from July 2011 to April 2012. His research interests focus on modeling with high dimensional data; including sparse/low-rank modeling, manifold/subspace clustering, matrix completion, semi-supervised learning and their applications in pattern recognition, computer vision, bioinformatics, etc.

Chong You received two B.S. degrees in electrical engineering and in applied mathematics, respectively in 2009, and the M.S. degree in electrical engineering from Peking University, Beijing, China, in 2012. He is currently pursuing the Ph.D. degree with the Department of Electrical and Computer Engineering, Johns Hopkins University. His research interests include large scale and high-dimensional data analysis, sparse signal representation, and computer vision.




Guangcan Liu received the bachelor's degree in mathematics and the Ph.D. degree in computer science and engineering from Shanghai Jiao Tong University, Shanghai, China, in 2004 and 2010, respectively. He was a postdoctoral researcher with the National University of Singapore, Singapore, from 2011 to 2012, the University of Illinois at Urbana-Champaign, Champaign, IL, USA, from 2012 to 2013, Cornell University, Ithaca, NY, USA, from 2013 to 2014, and Rutgers University, Piscataway, NJ, USA, in 2014. Since 2014, he has been a Professor with the School of Information and Control, Nanjing University of Information Science and Technology, Nanjing, China. His research interests touch on the areas of pattern recognition and signal processing. He obtained the National Excellent Youth Fund in 2016 and was designated as the global Highly Cited Researchers in 2017.

Risheng Liu received the BSc and PhD degrees both in mathematics from the Dalian University of Technology in 2007 and 2012, respectively. He was a visiting scholar in the Robotic Institute of Carnegie Mellon University from 2010 to 2012. He served as Hong Kong Scholar Research Fellow at the Hong Kong Polytechnic University from 2016 to 2017. He is currently an associate professor with the Key Laboratory for Ubiquitous Network and Service Software of Liaoning Province, Internal School of Information and Software Technology, Dalian University of Technology. His research interests include machine learning, optimization, computer vision and multimedia. He was a co-recipient of the IEEE ICME Best Student Paper Award in both 2014 and 2015. Two papers were also selected as Finalist of the Best Paper Award in ICME 2017. He is a member of the IEEE and ACM. He is on the Editorial Board of The Visual Computer Journal, IET Image Processing, and Journal of Electronic Imaging.