Events Calendar

PhD Defense - Shay Deutsch

Title: Learning the Geometric Structure of High Dimensional Data using the Tensor Voting Graph

Location: SAL 322

Time: 2:30pm - 4:30pm, May 6th, 2016

PhD Candidate: Shay Deutsch

Committee members:

Prof. Gerard Medioni (Chair)
Prof. Aiichiro Nakano
Prof. Antonio Ortega (Outside Member)

Abstract:
This study addresses a range of fundamental problems in unsupervised manifold learning. Given a set of noisy points in a high dimensional space that lie near one or more possibly intersecting smooth manifolds, different challenges include learning the local geometric structure at each point, geodesic distance estimation, and clustering. These problems are ubiquitous in unsupervised manifold learning, and many applications in computer vision as well as other scientific applications would benefit from a principled approach to these problems.
In the first part of this thesis we present a hybrid local-global method that leverages the algorithmic capabilities of the Tensor Voting framework. However, unlike Tensor Voting, which can learn complex structures reliably only locally, our method is capable of reliably inferring the global structure of complex manifolds using a unique graph construction called the Tensor Voting Graph (TVG). This graph provides an efficient tool to perform the desired global manifold learning tasks such as geodesic distance estimation and clustering on complex manifolds, thus overcoming one of one of the main limitations of Tensor Voting as a strictly local approach. Moreover, we propose to explicitly and directly resolve the ambiguities near the intersections with a novel algorithm, which uses the TVG and the positions of the points near the manifold intersections.
In the second part of this thesis we propose a new framework for manifold denoising based processing in the graph Fourier frequency domain, derived from the spectral decomposition of the discrete graph Laplacian. The suggested approach, called MFD, uses the Spectral Graph Wavelet transform in order to perform non-iterative denoising directly in the graph frequency domain. To the best of our knowledge, MFD is the first attempt to use graph signal processing tools for manifold denoising on unstructured domains. We provide theoretical justification for our Manifold Frequency Denoising approach on unstructured graphs and demonstrate that for smooth manifolds the coordinate signals also exhibit smoothness. This is first demonstrated in the case of noiseless observations, by proving that manifolds with smoother characteristics creates more energy in the lower frequencies. Moreover, it is shown that higher frequency wavelet coefficients decay in a way that depends on the smoothness properties of the manifold, which is explicitly tied to the curvature properties. We then provide an analysis for the case of noisy points and a noisy graph, establishing results which tie the noisy graph Laplacian to the noiseless graph Laplacian characteristics, induced by the smoothness manifold properties and the graph construction properties.
Finally, the last part of this research merges the Manifold Frequency Denoising and the Tensor Voting Graph methods into a uniform framework, which allows us to denoise and analyze a general class of noisy manifolds with singularities also in the presence of outliers. We demonstrate that the limitation of the Spectral Graph Wavelets in its flexibility to analyze certain classes of graph signals can be overcome for manifolds with singularities using certain graph construction and regularization methods. This allows us to take into account global smoothness characteristics without over-smoothing in the manifold discontinuations (which correspond to high frequency bands of the Spectral Graph Wavelets), and moreover is robust to a large amount of outliers.

Location: Henry Salvatori Computer Science Center (SAL) - 322

Audiences: Everyone Is Invited

Contact: Lizsl De Leon