Super-Fast algorithm for minimum variance (Capon) spectral estimation

The minimum variance spectral estimator (sometimes referenced as the Capon spectral estimator, or the minimum variance distortion-less response estimator) is a high resolution spectral estimator used extensively in practice as an alternative to the classical squared-magnitude Fourier estimator. In its original form without special algorithms, the one-dimensional formulation requires order p³ computations, in which p is the minimum variance filter size. The current implementation used in practice employs a fast algorithm developed by Musicus, requiring order p² + p log₂(2p) computations. This paper shows discoveries of additional exploitable structure to bring the computational complexity down to p + p log₂(p), creating a superfast algorithm. Furthermore, by exploiting a differential relationship between two quantities in this structure, an approximated version of the proposed algorithm with an even lower computational complexity is derived.