Michigan State University
Comparative analysis of orthogonal matching pursuit and least angle regression
Abstract
dc:descriptionThe problem of finding a unique and sparse solution for an underdetermined linear system has attracted significant attention in recent years. In this thesis, we compare two popular algorithms that are used for finding sparse solutions of underdetermined linear systems: Orthogonal Matching Pursuit (OMP) and Least Angle Regression (LARS). We provide an in-depth description of both algorithms. Subsequently, we outline the similarities and differences between them. OMP and LARS solve different optimization problems: OMP attempts to find an approximate solution for the L0-norm minimization problem, while LARS solves the L1-norm minimization problem. However, both algorithms depend on an underlying greedy framework. They start from an all-zero solution, and then iteratively construct a sparse solution until some convergence is reached. By reformulating the overall structure and corresponding analytical expressions of OMP and LARS, we show that many of the steps of both algorithms are almost identical. Meanwhile, we highlight the primary differences between the two algorithms. In particular, based on our reformulation, we show that the key difference between these algorithms is how they update the solution vector at each iteration. In addition, we present some of the salient benefits and shortcomings of each algorithm. Moreover, we exploit parallel processing techniques to speedup the convergence of algorithms.
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Hameed, Mazin Abdulrasool
- Contributors dc:contributor
-
- Radha, Hayder
- Aviyente, Selin
- Udpa, Lalita
Subjects
dc:subject × 4Rights
dc:rights- Statement dc:rights
-
- In Copyright
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
-
etd:1711
isbn:9781267309778
isbn:1267309776
oclc:931869286
umi:1509522
local:Hameed_grad.msu_0128N_11024 - OAI record oai:identifier
- https://d.lib.msu.edu/oai?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Ad.lib.msu.edu%3Aetd_1711