% formatted on 970304 by morris
\documentstyle{article}
\setcounter{page}{29}
\textheight 9.5in
\textwidth 5.75in
\voffset -1in
\hoffset -0.55in
%\documentstyle{llncs}
\begin{document}
\title{Exponential Decomposition}
\author{Frank Luk\\
Rensselaer Polytechnic Institute, USA}
\date{}
\maketitle
We discuss the approximation problem:  
\vskip 2truemm

\hspace{0.5cm} Decompose a signal into a sum of complex exponential sequences. 

\vskip 2truemm

This problem arises in a wide range of signal and image 
processing applications, e.g., directions of arrival,
nuclear magnetic resonance, and image restoration.
Often, physical constraints dictate that these exponential sequences 
must decay and we desire to keep the number of sequences small.
The relation between this problem and the low rank approximation
of a Hankel matrix is well known.  The first technique
for solving the problem goes back to Prony in 1795;
recent contributors include Kung and Cadzow.
In this talk, we propose a novel formulation of the problem
as a matrix pencil involving two closely related Hankel matrices.
For many n-by-n Hankel matrices we explain how this
problem can be solved in $O(n^2)$ operations, thereby providing
a notable improvement over previous algorithms which all require
$O(n^3)$ operations.


\end{document}
