Performance analysis of the approximate dynamic programming algorithm for parameter estimation of superimposed signals

Sze Fong Yau, Yoram Bresler

Research output: Contribution to journalArticle


We consider the classical problem of fitting a model composed of multiple superimposed signals to noisy data using the criteria of maximum likelihood (ML) or subspace fitting, jointly termed generalized subspace fitting (GSF). We analyze a recently proposed approximate dynamic programming algorithm (ADP), which provides a computationally efficient solution to the associated multidimensional multimodal optimization problem. We quantify the error introduced by the approximations in ADP and deviations from the key local interaction signal model (LISMO) modeling assumption in two ways. First, we upper bound the difference between the exact minimum of the GSF criterion and its value at the ADP estimate and compare the ADP with GSF estimates obtained by exhaustive multidimensional search on a fine lattice. Second, motivated by the similar accuracy bounds, we use perturbation analysis to derive approximate expressions for the MSE of the ADP estimates. These various results provide, for the first time, an effective tool to predict the performance of the ADP algorithm for various signal models at nonasymptotic conditions of interest in practical applications. In particular, they demonstrate that for the classical problems of sinusoid retrieval and array processing, ADP performs comparably to exact (but expensive) maximum likelihood (ML) over a wide range of signal-to-noise ratios (SNR's) and is therefore an attractive algorithm.

Original languageEnglish (US)
Pages (from-to)1274-1286
Number of pages13
JournalIEEE Transactions on Signal Processing
Issue number5
StatePublished - May 1 2000


  • Dynamic programming
  • Model fitting
  • Nonlinear regression
  • Optimization
  • Parameter estimation
  • Radar
  • Sensor array processing
  • Sinusoid retrieval
  • Sonar

ASJC Scopus subject areas

  • Electrical and Electronic Engineering
  • Signal Processing

Fingerprint Dive into the research topics of 'Performance analysis of the approximate dynamic programming algorithm for parameter estimation of superimposed signals'. Together they form a unique fingerprint.

  • Cite this