Scalable subspace clustering

clustering
big data
randomized algorithms
Clustering large, high-dimensional datasets that lie near a union of low-dimensional subspaces, using random sketching, sampling and distributed computation.

Overview

Many high-dimensional datasets, such as images of faces under varying lighting or trajectories of moving objects, lie close to a union of low-dimensional subspaces. Subspace clustering groups the data according to the subspace each point belongs to. Standard subspace clustering algorithms, however, scale poorly with the number of data points.

Scatter plot of points in three colors, each arranged along a different line through the origin.

Points drawn from three one-dimensional subspaces; subspace clustering recovers which subspace each point came from.

Approach

This project reduces the cost of clustering large datasets through random sketching, random sampling with validation or consensus, and distributed processing. It also covers data streams with missing entries and multi-way (tensor) data.

Related work with collaborators develops efficient updates of matrix and tensor decompositions for streaming data, including online canonical correlation analysis and updates of the multilinear SVD.

Key papers

  1. P. A. Traganitis and G. B. Giannakis, “Sketched Subspace Clustering,” IEEE Transactions on Signal Processing, vol. 66, no. 7, pp. 1663–1675, 2018. arXiv · MATLAB code
  2. P. A. Traganitis, K. Slavakis and G. B. Giannakis, “Sketch and Validate for Big Data Clustering,” IEEE Journal of Selected Topics in Signal Processing, vol. 9, no. 4, pp. 678–690, 2015. arXiv
  3. P. A. Traganitis and G. B. Giannakis, “Distributed Sketched Subspace Clustering for Large-Scale Data,” Proc. of CAMSAP, 2017. (Invited)
  4. P. A. Traganitis and G. B. Giannakis, “PARAFAC-based Multilinear Subspace Clustering for Tensor Data,” Proc. of GlobalSIP, Washington, DC, 2016.
  5. P. A. Traganitis and G. B. Giannakis, “Efficient Subspace Clustering of Large-scale Data Streams with Misses,” Proc. of CISS, Princeton, NJ, 2016.
  6. V. Kalantzis, P. A. Traganitis and C. I. Kanatsoulis, “Online Canonical Correlation Analysis via Rayleigh-Ritz Projections,” Proc. of Asilomar Conf. on Signals, Systems, and Computers, 2024.
  7. V. Kalantzis and P. A. Traganitis, “Rayleigh-Ritz Based Updates of the Multilinear Singular Value Decomposition,” Proc. of Asilomar Conf. on Signals, Systems, and Computers, 2023.