Geometric manifold approximation using locally linear approximations

The design and analysis of methods in signal processing is greatly impacted by the model being selected to represent the signals of interest. For many decades, the most popular geometric models in signal processing have been the subspace and the union-of-subspaces signal models. However, there are classes of signals that are not well-represented by either the subspace or the union-of-subspaces model, but are manifested in a low-dimensional non-linear manifold embedded in a high-dimensional ambient space. Though a lot of work has been done on low-dimensional embedding of manifold sampled data, few works address the problem of approximating the manifold geometry in the ambient space. There is value in capturing the geometric variations of a non-linear manifold in the ambient space, as shown in this work. In this work, the local linearity of a manifold is exploited to address the problem of approximating the geometric structure of a non-linear non-intersecting manifold using a union of tangent planes (affine subspaces). The number of approximating tangent planes adapts with the varying manifold curvature such that the manifold geometry is always well approximated within a given accuracy. Also, the local linearity of the manifold is exploited to subsample the manifold data before using it to learn the manifold geometry, with negligible loss of approximation accuracy. Owing to this subsampling feature, the proposed approach shows more than a $100$-times decrease in the learning time when compared to state-of-the-art manifold learning algorithms, while achieving similar approximation accuracy. Because the approximating tangent planes extend indefinitely in space, the data encoding problem becomes complicated in the aforementioned learning approach. Thus, in the second half of the thesis, the manifold approximation problem is reformulated such that the geometry is approximated using a union of tangent patches, instead of tangent planes. Then, the data encoding problem is formulated as a series of convex optimization problems, and an efficient solution is proposed to solve each of the convex problems. Last, the value of capturing manifold geometry is demonstrated by showing the denoising performance of our proposed framework on both synthetic and real data.M.S.Includes bibliographical referencesby Talal Ahme