go-v.orgdoi

Scalable Algorithms Using Optimization on Orthogonal Matrix Manifolds

Kyle Gilman · Deep Blue (University of Michigan) · 2022

  • DOI 10.7302/6830
  • Publisher University of Michigan
  • Type dissertation
  • Issued 2022

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

Deep Blue (University of Michigan) · University of Michigan · dissertation · 2022

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.

Open the resolved locator · 10.7302/6830

Metadata licence: OpenAlex metadata (CC0)

Registry
OpenAlex DOI index + API
Fetched
2026-11-19 21:43 UTC
Cache state
not cached yet (bulk-index+openalex)
Locator
https://hdl.handle.net/2027.42/175616
Metadata licence
OpenAlex metadata (CC0)
Scope
Metadata as returned by the resolver; abstracts are never generated here.