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

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.