Optimality guarantees for non-convex low rank matrix recovery problems

Date

2015-08

Authors

White, Christopher Dale

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Low rank matrices lie at the heart of many techniques in scientific computing and machine learning. In this thesis, we examine various scenarios in which we seek to recover an underlying low rank matrix from compressed or noisy measurements. Specifically, we consider the recovery of a rank r positive semidefinite matrix XX[superscript T] āˆˆ R[superscript n x n] from m scalar measurements of the form [mathematic equation] via minimization of the natural lā‚‚ loss function [mathematic equation]; we also analyze the quadratic nonnegative matrix factorization (QNMF) approach to clustering where the matrix to be factorized is the transition matrix for a reversible Markov chain. In all of these instances, the optimization problem we wish to solve has many local optima and is highly non-convex. Instead of analyzing convex relaxations, which tend to be complicated and computationally expensive, we operate directly on the natural non-convex problems and prove both local and global optimality guarantees for a family of algorithms.

Department

Description

text

LCSH Subject Headings

Citation