TY - GEN
T1 - Iteratively Re-weighted Least Squares minimization
T2 - CISS 2008, 42nd Annual Conference on Information Sciences and Systems
AU - Daubechies, Ingrid
AU - DeVore, Ronald
AU - Fornasier, Massimo
AU - Güntürk, Sinan
PY - 2008
Y1 - 2008
N2 - Given an m × N matrix Φ, with m < N, the system of equations Φx = y is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a "best" solution. One of the oldest is to select the one with minimal l2 norm. It has been shown that in many applications a better choice is the minimal l1 norm solution. This is the case in Compressive Sensing, when sparse solutions are sought. The minimal l1 norm solution can be found by using linear programming; an alternative method is Iterative Re-weighted Least Squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight w, the solution with smallest l2(w) norm; this weight is updated at every iteration step: if x(n) is the solution at step n, then w(n) is defined by wi(n):= 1/|xi(n)|, i = 1,..., N. We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix Φ known as the Restricted Isometry Property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate l1-minimization, the exponenital rate is linear; in adapted versions aimed at 1T-minimization with T <1, we prove faster than linear rate.
AB - Given an m × N matrix Φ, with m < N, the system of equations Φx = y is typically underdetermined and has infinitely many solutions. Various forms of optimization can extract a "best" solution. One of the oldest is to select the one with minimal l2 norm. It has been shown that in many applications a better choice is the minimal l1 norm solution. This is the case in Compressive Sensing, when sparse solutions are sought. The minimal l1 norm solution can be found by using linear programming; an alternative method is Iterative Re-weighted Least Squares (IRLS), which in some cases is numerically faster. The main step of IRLS finds, for a given weight w, the solution with smallest l2(w) norm; this weight is updated at every iteration step: if x(n) is the solution at step n, then w(n) is defined by wi(n):= 1/|xi(n)|, i = 1,..., N. We give a specific recipe for updating weights that avoids technical shortcomings in other approaches, and for which we can prove convergence under certain conditions on the matrix Φ known as the Restricted Isometry Property. We also show that if there is a sparse solution, then the limit of the proposed algorithm is that sparse solution. It is also shown that whenever the solution at a given iteration is sufficiently close to the limit, then the remaining steps of the algorithm converge exponentially fast. In the standard version of the algorithm, designed to emulate l1-minimization, the exponenital rate is linear; in adapted versions aimed at 1T-minimization with T <1, we prove faster than linear rate.
UR - http://www.scopus.com/inward/record.url?scp=52049096603&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=52049096603&partnerID=8YFLogxK
U2 - 10.1109/CISS.2008.4558489
DO - 10.1109/CISS.2008.4558489
M3 - Conference contribution
AN - SCOPUS:52049096603
SN - 9781424422470
T3 - CISS 2008, The 42nd Annual Conference on Information Sciences and Systems
SP - 26
EP - 29
BT - CISS 2008, The 42nd Annual Conference on Information Sciences and Systems
Y2 - 19 March 2008 through 21 March 2008
ER -