Convex optimization is one of the most robust tools for automated data analysis. It has widespread applications in fields such as machine learning, computer vision, combinatorial optimization and scientific computing. However, the rapidly increasing volume and complexity of data that needs to be processed often renders general-purpose algorithms unusable.

This thesis aims to address this issue through development of very fast algorithms for core convex optimization problems, with a focus on graphs. To this end, we:

• Develop nearly optimal algorithms for the Fermat-Weber (geometric median) problem, a fundamental task in robust estimation and clustering.
• Investigate how to approximate massive amounts of high-dimensional data in a restrictive streaming setting, achieving optimal tradeoffs.
• Develop the fastest algorithm for solving linear systems on undirected graphs. This is achieved through improved clustering algorithms and better understanding of the interplay between combinatorial and numerical aspects of previous approaches.
• Show the existence of clustering and oblivious routing algorithms for a broad family of directed graphs, in hopes of advancing the search for faster maximum flow algorithms.

202 pages

Thesis Committee:
Gary L. Miller (Chair)
Anupam Gupta
Daniel Sleator
Shang-Hua Teng (University of Southern California)

Frank Pfenning, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Return to: SCS Technical Report Collection
School of Computer Science

This page maintained by [email protected]