  We develop fixed-point algorithms for the approximation of structured
matrices with rank penalties. In particular we use these fixed-point algorithms
for making approximations by sums of exponentials, or frequency estimation. For
the basic formulation of the fixed-point algorithm we show that it converges to
the minimum of the convex envelope of the original objective function along
with its structured matrix constraint. It often happens that this solution
agrees with the solution to the original minimization problem, and we provide a
simple criterium for when this is true. We also provide more general
fixed-point algorithms that can be used to treat the problems of making
weighted approximations by sums of exponentials given equally or unequally
spaced sampling. We apply the method to the case of missing data, although
optimal convergence of the fixed-point algorithm is not guaranteed in this
case. However, it turns out that the method often gives perfect reconstruction
(up to machine precision) in such cases. We also discuss multidimensional
extensions, and illustrate how the proposed algorithms can be used to recover
sums of exponentials in several variables, but when samples are available only
along a curve.
