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

DOI10.1016/J.ACHA.2017.03.004zbMATH Open1475.65043arXiv1601.01242OpenAlexW2963518309MaRDI QIDQ1990967FDOQ1990967

Authors: Fredrik Andersson, Marcus Carlsson 

Publication date: 29 October 2018

Published in: Applied and Computational Harmonic Analysis (Search for Journal in Brave)

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, 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.

Full work available at URL: https://arxiv.org/abs/1601.01242

Recommendations

• Structured low-rank approximation and its applications
• Factorization approach to structured low-rank approximation with applications
• Structured low rank approximation
• Fixed point and Bregman iterative methods for matrix rank minimization
• Structured low-rank approximation with missing data

zbMATH Keywords

Fenchel conjugatefixed-point algorithmsfrequency estimationconvex envelopegeneral domain Hankel matrices

Mathematics Subject Classification ID

Numerical optimization and variational techniques (65K10) Multidimensional problems (41A63) Toeplitz, Cauchy, and related matrices (15B05) Iterative procedures involving nonlinear operators (47J25) Approximation with constraints (41A29)

Cites Work

• Variational Analysis
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Hankel matrix rank minimization with applications to system identification and realization
• On approximation of functions by exponential sums
• Convergence theorems for sequences of nonlinear operators in Banach spaces
• Introduction to spectral analysis
• Matrix pencil method for estimating parameters of exponentially damped/undamped sinusoids in noise
• ANALYTIC PROPERTIES OF SCHMIDT PAIRS FOR A HANKEL OPERATOR AND THE GENERALIZED SCHUR-TAKAGI PROBLEM
• Derivatives of Spectral Functions
• Compressed Sensing Off the Grid
• Toeplitz and Hankel operators on the Paley-Wiener space
• Infinite Hankel matrices and generalized Caratheodory-Fejer and Riesz problems
• Computation of generalized matrix functions
• SYMMETRIC GAUGE FUNCTIONS AND UNITARILY INVARIANT NORMS
• The Asymptotic Behavior of Firmly Nonexpansive Mappings
• Fenchel duality, Fitzpatrick functions and the extension of firmly nonexpansive mappings
• Nonlinear approximation of functions in two dimensions by sums of exponential functions
• Nonlinear approximation of functions in two dimensions by sums of wave packets
• On general domain truncated correlation and convolution operators with finite rank
• A New Frequency Estimation Method for Equally and Unequally Spaced Data
• Sparse approximation of functions using sums of exponentials and AAK theory
• Infinite Hankel matrices and generalized Caratheodory-Fejer and I. Schur problems
• Operator-Lipschitz estimates for the singular value functional calculus
• On generalized matrix functions

Cited In (7)

• Optimal rank-1 Hankel approximation of matrices: Frobenius norm and spectral norm and Cadzow's algorithm
• Structured Frequency Algorithms
• Multichannel frequency estimation with constant amplitude via convex structured low-rank approximation
• On convex envelopes and regularization of non-convex functionals without moving global minima
• SQNR estimation of fixed-point DSP algorithms
• Frequency-limited balanced truncation with low-rank approximations
• Optimal approximation with exponential sums by a maximum likelihood modification of Prony's method

This page was built for publication: Fixed-point algorithms for frequency estimation and structured low rank approximation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1990967)