Back to search

Michigan State University

Comparative analysis of orthogonal matching pursuit and least angle regression

Abstract

dc:description

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

Rights

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

Chain of custody

source
Harvested from
Michigan State University
Base URL
d.lib.msu.edu/oai
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Hameed, Mazin Abdulrasool. Comparative analysis of orthogonal matching pursuit and least angle regression. 2012. https://doi.org/doi:10.25335/3sdp-zs58