CaltechAUTHORS
  A Caltech Library Service

Similarity clustering in the presence of outliers: Exact recovery via convex program

Korlakai Vinayak, Ramya and Hassibi, Babak (2016) Similarity clustering in the presence of outliers: Exact recovery via convex program. In: 2016 IEEE International Symposium on Information Theory (ISIT). IEEE , Piscataway, NJ, pp. 91-95. ISBN 978-1-5090-1807-9. https://resolver.caltech.edu/CaltechAUTHORS:20160823-111539026

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160823-111539026

Abstract

We study the problem of clustering a set of data points based on their similarity matrix, each entry of which represents the similarity between the corresponding pair of points. We propose a convex-optimization-based algorithm for clustering using the similarity matrix, which has provable recovery guarantees. It needs no prior knowledge of the number of clusters and it behaves in a robust way in the presence of outliers and noise. Using a generative stochastic model for the similarity matrix (which can be thought of as a generalization of the classical Stochastic Block Model) we obtain precise bounds (not orderwise) on the sizes of the clusters, the number of outliers, the noise variance, separation between the mean similarities inside and outside the clusters and the values of the regularization parameter that guarantee the exact recovery of the clusters with high probability. The theoretical findings are corroborated with extensive evidence from simulations.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/ISIT.2016.7541267 DOIArticle
http://ieeexplore.ieee.org/document/7541267/?arnumber=7541267PublisherArticle
ORCID:
AuthorORCID
Korlakai Vinayak, Ramya0000-0003-0248-9551
Additional Information:© 2016 IEEE. This work was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund. and by King Abdullah University of Science and Technology.
Funders:
Funding AgencyGrant Number
NSFCNS-0932428
NSFCCF-1018927
NSFCCF-1423663
NSFCCF-1409204
Qualcomm Inc.UNSPECIFIED
JPL Director's Discretionary FundUNSPECIFIED
Caltech President’s FundUNSPECIFIED
King Abdullah University of Science and Technology (KAUST)UNSPECIFIED
Record Number:CaltechAUTHORS:20160823-111539026
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20160823-111539026
Official Citation:R. K. Vinayak and B. Hassibi, "Similarity clustering in the presence of outliers: Exact recovery via convex program," 2016 IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, 2016, pp. 91-95. doi: 10.1109/ISIT.2016.7541267 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7541267&isnumber=7541040
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:69851
Collection:CaltechAUTHORS
Deposited By: Tony Diaz
Deposited On:23 Aug 2016 18:24
Last Modified:03 Oct 2019 10:25

Repository Staff Only: item control page