Solving Large and Dense Eigenvalue Problems that Arise in Physics

摘要

We worked on a fundamental problem of decomposing a signal into a small set ofdecaying complex exponentials. This problem arises in a wide range of disciplines, including nuclear magnetic resonance, speech processing and system identification. We developed a new class of numerical algorithms, and gave a simple, purely linear algebraic proof on why our new approach works. Our class contains two arbitrary matrice F and G. Specific choices of these two matrices result in Prony's and Kung's methods. So all our theoretical results cover the two procedures. This advance is important, for Kung's proof can be difficult to digest. Other choices of F and G give rise to new methods with other desirable characteristics; e.g., our new Hankel QRD method is about ten times faster than Kung's scheme, also known as the Hankel SVD method. Another attraction of the QRD approach is that it is easily updatable to accommodate new data, which is not so for an SVD technique.