Exact and Approximation Algorithms for Sparse PCA

Sparse Principal Component Analysis (SPCA) is designed to enhance the interpretability of traditional Principal Component Analysis (PCA) by optimally selecting a subset of features that comprise the first principal component. Given the NP-hard nature of SPCA, most current approaches resort to approximate solutions, typically achieved through tractable semidefinite programs (SDPs)¬†or¬†heuristic methods. To solve SPCA to … Read more

Fast Multilevel Algorithms for Compressive Principle Component Pursuit

Recovering a low-rank matrix from highly corrupted measurements arises in compressed sensing of structured high-dimensional signals (e.g., videos and hyperspectral images among others). Robust principal component analysis (RPCA), solved via principal component pursuit (PCP), recovers a low-rank matrix from sparse corruptions that are of unknown value and support by decomposing the observation matrix into two … Read more

An Alternating Minimization Method for Matrix Completion Problem

In this paper, we focus on solving matrix completion problem arising from applications in the fields of information theory, statistics, engineering, etc. However, the matrix completion problem involves nonconvex rank constraints which make this type of problem difficult to handle. Traditional approaches use a nuclear norm surrogate to replace the rank constraints. The relaxed model … Read more

Nonsmooth Matrix Valued Functions Defined by Singular Values

A class of matrix valued functions defined by singular values of nonsymmetric matrices is shown to have many properties analogous to matrix valued functions defined by eigenvalues of symmetric matrices. In particular, the (smoothed) matrix valued Fischer-Burmeister function is proved to be strongly semismooth everywhere. This result is also used to show the strong semismoothness … Read more