Repository logo
 

Sparse multivariate analyses via ℓ1-regularized optimization problems solved with Bregman iterative techniques

Date

2012

Authors

Rohrbacker, Nicholas, author
Kirby, Michael, advisor
Peterson, Christopher, committee member
Liu, Jiangguo, committee member
Ben-Hur, Asa, committee member

Journal Title

Journal ISSN

Volume Title

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.

Description

Rights Access

Subject

convex optimization
modularity
sparse PCA
bisparse singular value cecomposition
Split Bregman
support vector machine

Citation

Associated Publications