Estimating Low Dimensional, High-Density Structure

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

Data in high dimensional spaces are now very common. This project will develop methods for analyzing these high dimensional data. Such data may contain hidden structures. For example, clusters (which are small regions with a large number of points) can be stretched out like a string forming a structure called a filament. Scientists in a variety of fields need to locate these objects. It is challenging since the data are often very noisy. This project will develop rigorously justified and computationally efficient methods for extracting such structures. The methods will be applied to a diverse set of problems in astrophysics, seismology, biology, and neuroscience. The project will advance knowledge in several fields including computational geometry, astronomy, machine learning, and statistics. Finding hidden structure is useful for scientific discovery and dimension reduction. Much of the current theory on nonlinear dimension reduction assumes that the hidden structure is a smooth manifold and is very restrictive. The data might be concentrated near a low dimensional but very complicated set, such as a union of intersecting manifolds. Existing algorithms, such as the Subspace Constrained Mean Shift exhibit erratic behavior near intersections. This project will develop improved algorithms for these cases. At the same time, contemporary theory breaks down in these cases and this project will develop new theory to address the aforementioned problem. A complete method (which will be called singular clusters) will be developed for decomposing point clouds of varying dimensions into subsets.