Advanced

Fixed-point algorithms for frequency estimation and structured low rank approximation

Andersson, Fredrik LU and Carlsson, Marcus LU (2015) In Applied and Computational Harmonic Analysis
Abstract

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, i.e., frequency estimation. For the basic formulation of the fixed-point 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 fixed-point algorithms that can be used to treat... (More)

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, i.e., frequency estimation. For the basic formulation of the fixed-point 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 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 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)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
epub
subject
keywords
Convex envelope, Fenchel conjugate, Fixed-point algorithms, Frequency estimation, General domain Hankel matrices
in
Applied and Computational Harmonic Analysis
publisher
Elsevier
external identifiers
  • scopus:85017456635
ISSN
1063-5203
DOI
10.1016/j.acha.2017.03.004
language
English
LU publication?
yes
id
e7b51059-e9d7-4fab-83c5-ef14a57f16e8
date added to LUP
2017-05-10 13:38:13
date last changed
2017-05-10 13:38:13
@article{e7b51059-e9d7-4fab-83c5-ef14a57f16e8,
  abstract     = {<p>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, i.e., frequency estimation. For the basic formulation of the fixed-point 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 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 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         = {1063-5203},
  keyword      = {Convex envelope,Fenchel conjugate,Fixed-point algorithms,Frequency estimation,General domain Hankel matrices},
  language     = {eng},
  month        = {04},
  publisher    = {Elsevier},
  series       = {Applied and Computational Harmonic Analysis},
  title        = {Fixed-point algorithms for frequency estimation and structured low rank approximation},
  url          = {http://dx.doi.org/10.1016/j.acha.2017.03.004},
  year         = {2015},
}