Two optimization problems on graphs with applications in locally isometric embedding

In this thesis, we formulate two optimization problems which have found very interesting applications in machine learning areas like locally isometric embedding. Both problems are associated with a graph structure, and by exploiting that we can develop a rich understanding as well as efficient methods for the problems.;The first problem considers designing a fastest mixing Markov process (FMMP) on a connected graph, subject to a linear constraint on the transition rates. We formulate this problem as an eigenvalue optimization problem, which is to maximize the second smallest eigenvalue of the weighted Laplacian. We show that the FMMP problem is a convex optimization problem, which can be expressed as a semidefinite program, and therefore effectively solved numerically. We formulate a dual of the FMMP problem, and show that it has a natural geometric interpretation as a maximum variance unfolding (MVU) problem. The MVU problem is to choose a set of points to be as far apart as possible, measured by their variance, while respecting local distance constraints. It was proposed recently by others as a method for "unfolding" high dimensional data that lies on a low dimensional manifold. We show that the duality connection between the FMMP problem and the MVU problem can shed light on both problems, and allow us to characterize, and in some cases, find optimal solutions. For example, for tree graphs, we show that the FMMP problem can be solved exactly in a finite number of steps. We can also explain why the maximal variance configuration tends to have a low affine dimension and how MVU is related to other existing techniques.;The second problem is the map stitching problem (MSP), which is to stitch together a set of overlapping local maps to form a global map that respects the geometry within each local map. We formulate this problem as a least-squares problem in terms of the orthogonal transformations from the local maps to the global map and their relative displacements. When the graph that describes the overlapping relationship between the local maps is a tree, we show that MSP can be solved in closed form. For general overlapping graphs, we develop a Newton method and a Gauss-Newton method over the orthogonal matrices to solve the problem iteratively. For large scale problems where the overlapping graph is usually sparse, we use a truncated conjugate gradient method to compute approximate search directions. We also show how to apply map stitching at multiple levels if the problem is very large. Finally we show how to apply the map stitching framework to solve some large-scale nonlinear dimensionality reduction and sensor network localization problems.