Asif, Muhammad Salman.
Primal dual pursuit: a homotopy based algorithm for the Dantzig selector.
Degree: MS, Electrical and Computer Engineering, 2008, Georgia Tech
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.
Advisors/Committee Members: Romberg, Justin (Committee Chair), McClellan, James (Committee Member), Mersereau, Russell (Committee Member).
Subjects/Keywords: Statistical estimation; Random matrices; Convex optimization; Compressed sensing; Sparse signal recovery; Linear programming; LASSO; Model selection; L1 minimization; Dantzig shrinkability; Mathematical optimization; Homotopy theory; Signal processing
to Zotero / EndNote / Reference
APA (6th Edition):
Asif, M. S. (2008). Primal dual pursuit: a homotopy based algorithm for the Dantzig selector. (Masters Thesis). Georgia Tech. Retrieved from http://hdl.handle.net/1853/24693
Chicago Manual of Style (16th Edition):
Asif, Muhammad Salman. “Primal dual pursuit: a homotopy based algorithm for the Dantzig selector.” 2008. Masters Thesis, Georgia Tech. Accessed October 23, 2019.
MLA Handbook (7th Edition):
Asif, Muhammad Salman. “Primal dual pursuit: a homotopy based algorithm for the Dantzig selector.” 2008. Web. 23 Oct 2019.
Asif MS. Primal dual pursuit: a homotopy based algorithm for the Dantzig selector. [Internet] [Masters thesis]. Georgia Tech; 2008. [cited 2019 Oct 23].
Available from: http://hdl.handle.net/1853/24693.
Council of Science Editors:
Asif MS. Primal dual pursuit: a homotopy based algorithm for the Dantzig selector. [Masters Thesis]. Georgia Tech; 2008. Available from: http://hdl.handle.net/1853/24693