Sparse multivariate analyses via ℓ1-regularized optimization problems solved with Bregman Iterative Techniques

Abstract

In this dissertation we propose Split Bregman algorithms for several multivariate analytic techniques for dimensionality reduction and feature selection including Sparse Principal Components Analysis, Bisparse Singular Value Decomposition (BSSVD) and Bisparse Singular Value Decomposition with an ℓ1-constrained classifier BSSVDℓ1. For each of these problems we construct and solve a new optimization problem using these Bregman iterative techniques. Each of the proposed optimization problems contain one or more ℓ1-regularization terms to enforce sparsity in the solutions. The use of the ℓ1-norm to enforce sparsity is a widely used technique, however, its lack of differentiability makes it more difficult to solve problems including these types of terms. Bregman iterations make these solutions possible without the addition of variables and algorithms such as the Split Bregman algorithm makes additional penalty terms and multiple ℓ1 terms feasible, a trait that is not present in other state of the art algorithms such as the fixed point continuation algorithm. It is also shown empirically to be faster than another iterative solver for total variation image denoising, another ℓ1-regularized problem, in. We also link sparse Principal Components to cluster centers, denoise Hyperspectral Images using the BSSVD, identify and remove ambiguous observations from a classification problem using the algorithm and detect anomalistic subgraphs using Sparse Eigenvectors of the Modularity Matrix.