Back to search

Virginia Commonwealth University

The l1-norm regularized l1-norm best-fit line problem and applications

Abstract

dc:description.abstract

The 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 × 4

Rights

dc:rights
Statement dc:rights
  • © The Author

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
Virginia Commonwealth University
Base URL
scholarscompass.vcu.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Ling, Xiao. The l1-norm regularized l1-norm best-fit line problem and applications. Dissertation thesis, https://doi.org/10.25772/CKKM-8G96