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.
Read
