Accession Number:

ADA458509

Title:

Stochastic Search for Signal Processing Algorithm Optimization

Descriptive Note:

Research paper

Corporate Author:

CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

2001-05-01

Pagination or Media Count:

14.0

Abstract:

Many difficult problems can be viewed as search problems. However, given a new task with an embedded search problem, it is challenging to state and find a truly effective search approach. In this paper, the authors address the complex task of signal processing optimization. They first introduce and discuss the complexities of this domain. In general, a single signal processing algorithm can be represented by a very large number of different but mathematically equivalent formulas. Unfortunately, when these formulas are implemented in actual code, their running times differ significantly. Signal processing algorithm optimization aims at finding the fastest formula. The authors present a new approach that successfully solves this problem using an evolutionary stochastic search algorithm, Split Tree Evolution for Efficient Runtimes STEER, to search through the very large space of formulas. They empirically compare STEER against other search methods, including dynamic programming, exhaustive search, and random search, and show that STEER can find faster formulas while still only timing a very small portion of the search space.

Subject Categories:

  • Numerical Mathematics
  • Statistics and Probability
  • Operations Research
  • Radiofrequency Wave Propagation

Distribution Statement:

APPROVED FOR PUBLIC RELEASE