Optimization for High-Dimensional Data Analysis

Graduate Thesis Or Dissertation

Citations

Citeable URL: https://scholar.colorado.edu/concern/graduate_thesis_or_dissertations/dz010q31t

Abstract

As modern datasets continue to grow in size, they are also growing in complexity. Data are more often being recorded using multiple sensors, creating large, multidimensional datasets that are difficult to analyze. In this thesis, we explore methods to accelerate low-rank recovery algorithms for data analysis, with an emphasis on Robust Principal Component Analysis (RPCA). We also develop a tensor-based approach to RPCA that preserves the inherent structure of multidimensional datasets, allowing for improved analysis. Both of our approaches use nuclear-norm regularization with Burer-Monteiro factorization (or higher-order generalizations thereof) to transform convex but expensive programs into non-convex programs that can be solved efficiently. We supplement our non-convex programs with a certificate of optimality that can be used to bound the suboptimality of each iterate. We demonstrate that both of these approaches allow for new applications of RPCA in fields involving multidimensional datasets; for example, we show that our methods can be used for real-time video processing as well as the analysis of fMRI brain-scans. Traditionally, these tasks have been considered too demanding for low-rank recovery algorithms.

Creator