Virginia Commonwealth University
The l1-norm regularized l1-norm best-fit line problem and applications
Abstract
dc:description.abstractThe best-fit subspace or low-rank approximation of a data matrix revolvesaround the norm approximation technique. l2-norm criterion is probably the mostwidely used norm for fitting subspaces. As the computational power increases, thel1-norm analogue has recently gained attention from the academic community. It iswidely agreed that the l1 norm is insensitive to outliers, compared to its l2 variant.Because of the polyhedral structure interrelated with linear programming (LP),the l0 norm is commonly relaxed into the l1-norm problem to induce sparsity inmodels. In this work, we examine the role of the l1-norm approximation in severaldomains. Our focus is on the underlying characterization of the l1-norm subspace,the parallel implementation of the algorithm, and its applications in the field ofcomputer vision.Chapter 2 develops a sparse and outlier insensitive method to fit a one-dimensional subspace that can be used as a replacement for eigenvector methods such as principal component analysis. The method is insensitive to outlier observations by formulating procedures as optimization problems that seek the best-fit line according to the l1 norm. It is also capable of producing sparse principal components with an additional penalty term to take sparseness into account.Our algorithm has a worst-case time complexity of O(m2nlogn). This chapteralso presents the results of the implementation of this algorithm in the paralleland heterogeneous environment of NVIDIA CUDA and discusses the behavior ofthe algorithm in various settings. Our goal is to demonstrate the scalability andefficiency of our new approach.Chapter 3 proposes an image denoising approach based on an l1-norm best-fitline algorithm. The denoising process is expressed as a best-fit subspace estima-tion problem, where the best-fit subspaces are derived in a l1-norm minimizationframework. This new approach is competitive with existing approaches in termsof objective error metrics and visual fidelity and has the advantage that it can beimplemented in parallel for large-scale applications. Numerical experiments illus-trate that the technique can be successfully applied to the classical case of additiveGaussian noise. The performance of our approach is experimentally verified on avariety of images and noise levels.Chapter 4 describes a method for denoising data using kernel principal com-ponent analysis (KPCA) that is able to recover preimages of the intrinsic variablesin the feature space using a single line search along the gradient descent directionof its squared projection error. This method combines a projection-free preimageestimation algorithm with an l1-norm kernel PCA (KPCA). Those two stages pro-vide distinct advantages to other KPCA preimage methods in the sense that it isinsensitive to outliers and computationally efficient. The method can enhance theresults of a range of unsupervised learning tasks such as denoising, clustering, anddimensionality reduction. Numerical experiments in the Amsterdam Library of Object Images demonstrate that the proposed method performs better in terms of mean squared error than the l2-norm analogue as well as on toy synthetic data.The proposed method is applied to different data sets and the performances arereported.
Degree
thesis:*- Name thesis:degree_name
- Doctor of Philosophy
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Systems Modeling and Analysis
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Ling, Xiao
- Contributors dc:contributor
-
- Paul Brooks
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- © The Author
Identifiers
dc:identifier.*- Identifier
- https://scholarscompass.vcu.edu/etd/6972