Fixedpoint algorithms for frequency estimation and structured low rank approximation
(2015) In Applied and Computational Harmonic Analysis Abstract
We develop fixedpoint algorithms for the approximation of structured matrices with rank penalties. In particular we use these fixedpoint algorithms for making approximations by sums of exponentials, i.e., frequency estimation. For the basic formulation of the fixedpoint algorithm we show that it converges to the solution of a related minimization problem, namely the one obtained by replacing the original objective function with its convex envelope and keeping the structured matrix constraint unchanged.It often happens that this solution agrees with the solution to the original minimization problem, and we provide a simple criterion for when this is true. We also provide more general fixedpoint algorithms that can be used to treat... (More)
We develop fixedpoint algorithms for the approximation of structured matrices with rank penalties. In particular we use these fixedpoint algorithms for making approximations by sums of exponentials, i.e., frequency estimation. For the basic formulation of the fixedpoint algorithm we show that it converges to the solution of a related minimization problem, namely the one obtained by replacing the original objective function with its convex envelope and keeping the structured matrix constraint unchanged.It often happens that this solution agrees with the solution to the original minimization problem, and we provide a simple criterion for when this is true. We also provide more general fixedpoint 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 the above mentioned convergence results do not hold 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.
(Less)
 author
 Andersson, Fredrik ^{LU} and Carlsson, Marcus ^{LU}
 organization
 publishing date
 20150401
 type
 Contribution to journal
 publication status
 epub
 subject
 keywords
 Convex envelope, Fenchel conjugate, Fixedpoint algorithms, Frequency estimation, General domain Hankel matrices
 in
 Applied and Computational Harmonic Analysis
 publisher
 Elsevier
 external identifiers

 scopus:85017456635
 ISSN
 10635203
 DOI
 10.1016/j.acha.2017.03.004
 language
 English
 LU publication?
 yes
 id
 e7b51059e9d74fab83c5ef14a57f16e8
 date added to LUP
 20170510 13:38:13
 date last changed
 20170510 13:38:13
@article{e7b51059e9d74fab83c5ef14a57f16e8, abstract = {<p>We develop fixedpoint algorithms for the approximation of structured matrices with rank penalties. In particular we use these fixedpoint algorithms for making approximations by sums of exponentials, i.e., frequency estimation. For the basic formulation of the fixedpoint algorithm we show that it converges to the solution of a related minimization problem, namely the one obtained by replacing the original objective function with its convex envelope and keeping the structured matrix constraint unchanged.It often happens that this solution agrees with the solution to the original minimization problem, and we provide a simple criterion for when this is true. We also provide more general fixedpoint 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 the above mentioned convergence results do not hold 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.</p>}, author = {Andersson, Fredrik and Carlsson, Marcus}, issn = {10635203}, keyword = {Convex envelope,Fenchel conjugate,Fixedpoint algorithms,Frequency estimation,General domain Hankel matrices}, language = {eng}, month = {04}, publisher = {Elsevier}, series = {Applied and Computational Harmonic Analysis}, title = {Fixedpoint algorithms for frequency estimation and structured low rank approximation}, url = {http://dx.doi.org/10.1016/j.acha.2017.03.004}, year = {2015}, }