### Abstract

We present two «fast» approaches to the NP-hard problem of computing a maximally sparse approximate solution to linear inverse problems, also known as the best subset selection. The first approach, a heuristic, is an iterative algorithm globally convergent to sparse elements of any given convex, compact S/spl sub/R/sup mx/. We demonstrate its effectiveness in bandlimited extrapolation and in sparse filter design. The second approach is a polynomial-time greedy sequential backward elimination algorithm. We show that if A has full column rank and /spl epsiv/ is small enough, then the algorithm will find the sparsest x satisfying /spl par/Ax-b/spl par//spl les//spl epsiv/, if such exists.

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

Title of host publication | Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998 |

Pages | 1877-1880 |

Number of pages | 4 |

DOIs | |

State | Published - Dec 1 1998 |

Event | 1998 23rd IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998 - Seattle, WA, United States Duration: May 12 1998 → May 15 1998 |

### Publication series

Name | ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings |
---|---|

Volume | 3 |

ISSN (Print) | 1520-6149 |

### Other

Other | 1998 23rd IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998 |
---|---|

Country | United States |

City | Seattle, WA |

Period | 5/12/98 → 5/15/98 |

### ASJC Scopus subject areas

- Software
- Signal Processing
- Electrical and Electronic Engineering

## Fingerprint Dive into the research topics of 'Fast optimal and suboptimal algorithms for sparse solutions to linear inverse problems'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 1998*(pp. 1877-1880). [681830] (ICASSP, IEEE International Conference on Acoustics, Speech and Signal Processing - Proceedings; Vol. 3). https://doi.org/10.1109/ICASSP.1998.681830