Cut Improvement and Clustering Using Compressive Sensing

April 16, 2020
3:00
Zoom
Speaker: Daniel McKenzie
Host: Lenore Cowen

Abstract

Abstract: A joint work with Ming-Jun Lai.

Let G = (V, E) be a (possibly weighted) graph. Typically, the clustering problem refers to decomposing V into disjoint subsets C1, . . . , Ck such that each Ca has many internal edges and few external edges. However when n := |V | and k are large, finding all k clusters can be computationally wasteful and undesirable. In this talk we study two refinements of the clustering problem:

  1. Local Clustering: Given a small set of seed vertices, gamma, such that gamma is a proper subset of Ca, find or approximate Ca.
  2. Cut Improvement: Given an approximation omega, such that omega is approximately Ca, refine omega to an even better approximation of Ca.

In particular, we introduce a novel algorithm based on techniques from the signal processing field of compressive sensing which is able to solve both problems. We shall show that this algorithm, which we call ClusterPursuit, exhibits strong performance in theory and in practice.

You are invited to a Zoom meeting. When: Apr 16, 2020 03:00 PM Eastern Time (US and Canada)

Register in advance for this meeting: https://tufts.zoom.us/meeting/register/vpUpceytqT4vhFFutlvgWmEnOzrOSlL0pw

After registering, you will receive a confirmation email containing information about joining the meeting.