Publication

On Perfect Clustering of High Dimension, Low Sample Size Data

Related publications (79)

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Testing Graph Clusterability: Algorithms and Lower Bounds

Mikhail Kapralov, Aidasadat Mousavifar, Ashish Hari Chiplunkar

We consider the problem of testing graph cluster structure: given access to a graph G = (V, E), can we quickly determine whether the graph can be partitioned into a few clusters with good inner conductance, or is far from any such graph? This is a generali ...

IEEE COMPUTER SOC2018

Robust and Efficient Data Clustering with Signal Processing on Graphs

Lionel Jérémie Martin

Data is pervasive in today's world and has actually been for quite some time. With the increasing volume of data to process, there is a need for faster and at least as accurate techniques than what we already have. In particular, the last decade recorded t ...

EPFL2018

Graph-based Methods for Visualization and Clustering

Johann Paratte

The amount of data that we produce and consume is larger than it has been at any point in the history of mankind, and it keeps growing exponentially. All this information, gathered in overwhelming volumes, often comes with two problematic characteristics: ...

EPFL2017

Robust Discriminative Clustering with Sparse Regularizers

Nicolas Henri Bernard Flammarion

Clustering high-dimensional data often requires some form of dimensionality reduction, where clustered variables are separated from "noise-looking" variables. We cast this problem as finding a low-dimensional projection of the data which is well-clustered. ...

2017

On the Structure of Cortical Microcircuits Inferred from Small Sample Sizes

Rodrigo de Campos Perin

The structure in cortical microcircuits deviates from what would be expected in a purely random network, which has been seen as evidence of clustering. To address this issue, we sought to reproduce the nonrandom features of cortical circuits by considering ...

Soc Neuroscience2017

A Bi-Criteria Approximation Algorithm for k-Means

Justin Dean Ward

We consider the classical k-means clustering problem in the setting of bi-criteria approximation, in which an algorithm is allowed to output beta*k > k clusters, and must produce a clustering with cost at most alpha times the to the cost of the optimal set ...

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik2016

Fast Robust PCA on Graphs

Pierre Vandergheynst, Gilles Puy, Nathanaël Perraudin, Nauman Shahid, Vasilis Kalofolias

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the c ...

Ieee-Inst Electrical Electronics Engineers Inc2016

Consistency of Cheeger and Ratio Graph Cuts

Xavier Bresson

This paper establishes the consistency of a family of graph-cut-based algorithms for clustering of data clouds. We consider point clouds obtained as samples of a ground-truth measure. We investigate approaches to clustering based on minimizing objective fu ...

Microtome Publ2016

PCA using graph total variation

Pierre Vandergheynst, Nathanaël Perraudin, Benjamin Ricaud, Nauman Shahid, Vasilis Kalofolias

Mining useful clusters from high dimensional data has received sig- nificant attention of the signal processing and machine learning com- munity in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome th ...

Ieee2016

Clustering of heterogeneous networks with directional flows based on “Snake” similarities

Nikolaos Geroliminis, Mohammadreza Saeedmanesh

Aggregated network level modeling and control of traffic in urban networks have recently gained a lot of interest due to unpredictability of travel behaviors and high complexity of physical modeling in microscopic level. Recent research has shown the exist ...

Elsevier2016