Title: Dimension Detection via Slivers

Speaker:  Man-Kwun Chiu
HKUST


Date: Friday  March 6, 2009
Time 11:00-11:50
Venue: Room 3464, HKUST

Abstract: 
A lot of data has very high extrinsic dimension.  For example, a
collection of 64X64 black and white images can be viewed as a
point set P in 4096-dimensional space.  When the images are related, it
is often postulated that P lives on a manifold M  of much
lower dimension.  The dimension detection problem is to compute the
dimension of M given a set P of point samples drawn from
M. Knowing the manifold dimension helps in reconstructing the
manifold and embedding the manifold in the parameter space.

We present a novel approach to estimate the dimension m of an unknown
manifold M in d-dimensional real space with positive reach from a set of
point samples P in M.  It works by analyzing the shape of
simplices formed by point samples.  Suppose that M  is drawn from
M according to a Poisson process with an unknown parameter
$\lambda$.  Let k be some fixed positive integer.  When $\lambda$ is
large enough, we prove that the dimension can be correctly output in
$O(kd|P|^{1 + 1/k})$ time with probability greater than $1 - 2^{-k}$.  We
experimented with a practical variant and showed that its performance is
competitive with several previous methods.