Fixed-point algorithms for frequency estimation and structured low rank approximation
(2019) In Applied and Computational Harmonic Analysis 46(1). p.40-65- 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)
- author
- Andersson, Fredrik LU and Carlsson, Marcus LU
- organization
- publishing date
- 2019-01
- type
- Contribution to journal
- publication status
- published
- subject
- keywords
- Convex envelope, Fenchel conjugate, Fixed-point algorithms, Frequency estimation, General domain Hankel matrices
- in
- Applied and Computational Harmonic Analysis
- volume
- 46
- issue
- 1
- pages
- 40 - 65
- publisher
- Elsevier
- external identifiers
-
- scopus:85048737587
- 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
- 2022-04-24 23:41:37
@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}},
keywords = {{Convex envelope; Fenchel conjugate; Fixed-point algorithms; Frequency estimation; General domain Hankel matrices}},
language = {{eng}},
number = {{1}},
pages = {{40--65}},
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}},
doi = {{10.1016/j.acha.2017.03.004}},
volume = {{46}},
year = {{2019}},
}