Back to search

Georgia Institute of Technology

Primal dual pursuit: a homotopy based algorithm for the Dantzig selector

Abstract

dc:description.abstract

Consider the following system model y = Ax + e, where x is n-dimensional sparse signal, y is the measurement vector in a much lower dimension m, A is the measurement matrix and e is the error in our measurements. The Dantzig selector estimates x by solving the following optimization problem minimize || x ||₁ subject to || A'(Ax - y) ||∞ ≤ ε, (DS). This is a convex program and can be recast into a linear program and solved using any modern optimization method e.g., interior point methods. We propose a fast and efficient scheme for solving the Dantzig Selector (DS), which we call "Primal-Dual pursuit". This algorithm can be thought of as a "primal-dual homotopy" approach to solve the Dantzig selector (DS). It computes the solution to (DS) for a range of successively relaxed problems, by starting with a large artificial ε and moving towards the desired value. Our algorithm iteratively updates the primal and dual supports as ε reduces to the desired value, which gives final solution. The homotopy path solution of (DS) takes with varying ε is piecewise linear. At some critical values of ε in this path, either some new elements enter the support of the signal or some existing elements leave the support. We derive the optimality and feasibility conditions which are used to update the solutions at these critical points. We also present a detailed analysis of primal-dual pursuit for sparse signals in noiseless case. We show that if our signal is S-sparse, then we can find all its S elements in exactly S steps using about "S² log n" random measurements, with very high probability.

Degree

thesis:*
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2008

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Asif, Muhammad Salman
Advisor dc:contributor.advisor
  • Romberg, Justin
Committee members dc:contributor.committeemember
  • McClellan, James
  • Mersereau, Russell

Subjects

dc:subject × 13

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/24693

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Asif, Muhammad Salman. Primal dual pursuit: a homotopy based algorithm for the Dantzig selector. Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24693