Scalable Algorithms Using Optimization on Orthogonal Matrix Manifolds

Abstract

Modern machine learning problems in signal processing, computer vision, business, and science often seek to extract interpretable representations from large amounts of raw messy data. Unsupervised learning has broad and versatile uses for dimensionality reduction, exploratory data analysis, predictive modeling, anomaly detection, and more. With large modern datasets, however, many traditional algorithms cannot account for data that contain missing entries, gross outliers, heterogeneous noise, or streaming observations. Furthermore, many classical methods scale poorly when the data dimensions become large. This thesis addresses these challenges and proposes scalable, efficient algorithms using low-dimensional modeling and disciplined convex and nonconvex optimization techniques.

The first work in this thesis addresses a well-studied foreground-background separation problem in computer vision applications. A type of unsupervised learning technique called robust principal component analysis (RPCA) has been shown to have great success on these problems, but only in the setting where the camera is stationary. Video frames captured under certain types of camera motion can be posed as a type of robust matrix completion problem after a geometric registration of the frames. We propose an online algorithm that optimizes over the Grassmannian set of orthogonal subspaces to separate sparse and low-rank components in the data. Our algorithm shows significant computational speedup over the state-of-the-art batch algorithms for processing very high-dimensional registered video data.

The second work fills a gap in the literature for completing missing tensor data using the tensor singular value decomposition. Specifically, we address the case of streaming or online tensor data under this model. Our contribution gives an algorithm with low computational and memory overhead to impute missing entries of multiway data and learn a compressed representation. We show the tensor singular value decomposition admits a type of tensor block term decomposition represented by a product of Grassmannians. Our optimization steps are cheap, parallelizable, and fast, with computational improvements over the state-of-the-art we show on both synthetic and several types of real data.

The third contribution considers when data are corrupted by noise of different variances, or heteroscedastic noise. Modern datasets are increasingly conglomerations of data from heterogeneous sources, but classical methods like principal component analysis (PCA) quickly break down in these scenarios, and little work has addressed this important challenge. Our work not only learns the optimal low-dimensional subspace and factors, but can also estimate the unknown noise variances of the data groups whose membership is known to us. We show our model achieves superior performance compared to PCA and gracefully leverages additional noisy samples. We then derive a heteroscedastic PCA model for streaming data with missing entries and show subspace estimation and tracking improvement compared to state-of-the-art streaming PCA algorithms.

Lastly, this dissertation studies a nonconvex problem on the Stiefel manifold originating from the log-likelihood of heteroscedastic PCA that is uniquely distinct from PCA and not readily solved by the singular value or eigenvalue decompositions. We derive a novel semidefinite relaxation of the problem that has interesting connections to prior work using the Fantope constraint set, we prove a dual certificate to check for global optimality of local solutions, and finally we prove the existence of SDP problems with tight, rank-one solutions and show the result extends to the specific case of heteroscedastic PCA.