### Abstract

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 l_{2} norm. It has been shown that in many applications a better choice is the minimal l_{1} norm solution. This is the case in Compressive Sensing, when sparse solutions are sought. The minimal l_{1} 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 l_{2}(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 w_{i}^{(n)}:= 1/|x_{i}^{(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 l_{1}-minimization, the exponenital rate is linear; in adapted versions aimed at 1_{T}-minimization with T <1, we prove faster than linear rate.

Original language | English (US) |
---|---|

Title of host publication | CISS 2008, The 42nd Annual Conference on Information Sciences and Systems |

Pages | 26-29 |

Number of pages | 4 |

DOIs | |

State | Published - 2008 |

Event | CISS 2008, 42nd Annual Conference on Information Sciences and Systems - Princeton, NJ, United States Duration: Mar 19 2008 → Mar 21 2008 |

### Publication series

Name | CISS 2008, The 42nd Annual Conference on Information Sciences and Systems |
---|

### Other

Other | CISS 2008, 42nd Annual Conference on Information Sciences and Systems |
---|---|

Country | United States |

City | Princeton, NJ |

Period | 3/19/08 → 3/21/08 |

### ASJC Scopus subject areas

- Computer Science Applications
- Information Systems
- Control and Systems Engineering

## Fingerprint Dive into the research topics of 'Iteratively Re-weighted Least Squares minimization: Proof of faster than linear rate for sparse recovery'. Together they form a unique fingerprint.

## Cite this

*CISS 2008, The 42nd Annual Conference on Information Sciences and Systems*(pp. 26-29). [4558489] (CISS 2008, The 42nd Annual Conference on Information Sciences and Systems). https://doi.org/10.1109/CISS.2008.4558489