Advanced search options

Advanced Search Options 🞨

Browse by author name (“Author name starts with…”).

Find ETDs with:

in
/  
in
/  
in
/  
in

Written in Published in Earliest date Latest date

Sorted by

Results per page:

You searched for subject:(Dantzig shrinkability). One record found.

Search Limiters

Last 2 Years | English Only

No search limiters apply to these results.

▼ Search Limiters


Georgia Tech

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

Record DetailsSimilar RecordsGoogle PlusoneFacebookTwitterCiteULikeMendeleyreddit

APA · Chicago · MLA · Vancouver · CSE | Export to Zotero / EndNote / Reference Manager

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. http://hdl.handle.net/1853/24693.

MLA Handbook (7th Edition):

Asif, Muhammad Salman. “Primal dual pursuit: a homotopy based algorithm for the Dantzig selector.” 2008. Web. 23 Oct 2019.

Vancouver:

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

.