Maximum likelihood parameter estimation and subspace fitting of superimposed signals by dynamic programming - An approximate method

Sze Fong Yau, Yoram Bresler

Research output: Contribution to journalArticle


The problem of fitting a model composed of a number of superimposed signals to noisy data using the criteria of maximum likelihood (ML) and subspace fitting is considered. Using a Local Interaction Signal Model, established through a study of the Cramér-Rao bound for the estimation accuracy, an approximate dynamic programming algorithm (ADP) for signal parameter estimation is proposed. It yields estimates close to the global maximum of the ML or subspace fitting criteria with a computational cost only linear in the number of signals, rather than exponential as in the case of exhaustive search. The ADP algorithm improves on our previously proposed Basic Dynamic Programming (BDP) and Robust Exact Dynamic Programming (REDP) algorithms by further reducing the computational requirements and by being applicable to the multiple snapshot scenario, at the cost of slightly reduced accuracy. For example, for m sinusoids the computation is reduced from O(mq6) in BDP and REDP to O(mq2), where q is the number of grid points per dimension for the parameter search, which determines the resolution of frequency. Like the BDP and REDP, the ADP algorithm is adapted to determine the number of signals, and is applicable to arbitrary signal sampling or sensor array geometry. The ADP estimates converge almost surely to their noiseless values with increasing number of snapshots. Computer simulation results of several examples are presented.

Original languageEnglish (US)
Pages (from-to)283-298
Number of pages16
JournalSignal Processing
Issue number3
StatePublished - Dec 1992



  • array processing
  • nonlinear programming
  • Nonlinear regression
  • parameter estimation
  • sinusoids retrieval

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this