In Pursuit Of Novelty: A Decentralized Approach To Subspace Clustering

Keywords

Data sketching; Decentralized design; Randomization; Subspace clustering

Abstract

This paper considers the subspace clustering problem in a decentralized setting. The core algorithm finds directions of novelty in the span of the data to identify the membership of a collection of distributed data points. The low rank structure of the full M1 × M2 data matrix D is exploited to substantially reduce the processing and communication overhead. Two decentralized designs are presented. In the first design, each agent/sensor sends a compressed version of its data vector to a central processing unit, which applies the clustering algorithm to the compressed data vectors. In the second design, only a small random subset of the agents send their compressed data vectors to the central unit and the clustering algorithm is applied to the sampled compressed data vectors. It is shown that the gain in communication overhead of the first and second decentralized designs relative to the centralized solution is of order O(M1/r) and O(M1M2/r2+M2), respectively, where r is the rank of D.

Publication Date

2-10-2017

Publication Title

54th Annual Allerton Conference on Communication, Control, and Computing, Allerton 2016

Number of Pages

447-451

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/ALLERTON.2016.7852265

Socpus ID

85015221688 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85015221688

This document is currently not available here.

Share

COinS