Newtonized Orthogonal Matching Pursuit: Frequency Estimation over the Continuum

Abstract

We propose a fast sequential algorithm for the fundamental problem of estimating frequencies and amplitudes of a noisy mixture of sinusoids. The algorithm is a natural generalization of Orthogonal Matching Pursuit (OMP) to the continuum using Newton refinements, and hence is termed Newtonized OMP (NOMP). Each iteration consists of two phases: detection of a new sinusoid, and sequential Newton refinements of the parameters of already detected sinusoids. The refinements play a critical role in two ways: (1) sidestepping the potential basis mismatch from discretizing a continuous parameter space, (2) providing feedback for locally refining parameters estimated in previous iterations. We characterize convergence, and provide a Constant False Alarm Rate (CFAR) based termination criterion. By benchmarking against the Cramer Rao Bound, we show that NOMP achieves near-optimal performance under a variety of conditions. We compare the performance of NOMP with classical algorithms such as MUSIC and more recent Atomic norm Soft Thresholding (AST) and Lasso algorithms, both in terms of frequency estimation accuracy and run time.

Submitted to IEEE Transactions on Signal Processing (TSP)

References in corpus (4)

• Pathwise coordinate optimization
• Coordinate descent algorithms for lasso penalized regression
• Approximation and learning by greedy algorithms
• Orthogonal Matching Pursuit with Replacement

Cited by in corpus (36)

• Integrated Sensing and Communication with Massive MIMO: A Unified Tensor Approach for Channel and Target Parameter Estimation
• Compressive channel estimation and tracking for large arrays in mm wave picocells
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• TRICE: A Channel Estimation Framework for RIS-Aided Millimeter-Wave MIMO Systems
• Study of dynamics in post-transient flows using Koopman mode decomposition
• A Block Sparsity Based Estimator for mmWave Massive MIMO Channels with Beam Squint
• Fast Beam Alignment for Millimeter Wave Communications: A Sparse Encoding and Phaseless Decoding Approach
• Compressive Initial Access and Beamforming Training for Millimeter-Wave Cellular Systems
• Design of Large Effective Apertures for Millimeter Wave Systems using a Sparse Array of Subarrays
• Efficient IoT Devices Localization Through Wi-Fi CSI Feature Fusion and Anomaly Detection
• A Time-of-Flight Imaging System Based on Resonant Photoelastic Modulation
• Variational Inference of Structured Line Spectra Exploiting Group-Sparsity
• A New Path Division Multiple Access for the Massive MIMO-OTFS Networks
• Multi-sensor Spatial Association using Joint Range-Doppler Features
• Communication and Localization with Extremely Large Lens Antenna Array
• A Coordinate Descent Approach to Atomic Norm Denoising
• Spatial Wideband Channel Estimation for MmWave Massive MIMO Systems with Hybrid Architectures and Low-Resolution ADCs
• Efficient Downlink Channel Reconstruction for FDD Multi-Antenna Systems
• Fast Antenna and Beam Switching Method for mmWave Handsets with Hand Blockage
• Expectation Propagation based Line Spectral Estimation
• Integrated Communication and Localization in mmWave Systems
• Channel Estimation for Extremely Large-Scale Massive MIMO Systems
• Grid-less Variational Bayesian Inference of Line Spectral from Quantized Samples
• Labeling Multipath via Reconfigurable Intelligent Surface
• Deep Learning Based FDD Non-Stationary Massive MIMO Downlink Channel Reconstruction
• Asymmetrical Uplink and Downlink Transceivers in Massive MIMO Systems
• Networked Collaborative Sensing using Multi-domain Measurements: Architectures, Performance Limits and Algorithms
• FDD Massive MIMO Based on Efficient Downlink Channel Reconstruction
• Gridless Line Spectral Estimation with Multiple Measurement Vector via Variational Bayesian Inference
• Cubic NK-SVD: An Algorithm for Designing Parametric Dictionary in Frequency Estimation
• Gridless Channel Estimation for MmWave Hybrid Massive MIMO Systems with Low-Resolution ADCs
• Enabling Plug-and-Play and Crowdsourcing SLAM in Wireless Communication Systems
• Compressed Sensing Constant Modulus Constrained Projection Matrix Design and High-Resolution DoA Estimation Methods
• A Two-stage Approach to Estimate CFO and Channel with One-bit ADCs
• Newtonalized Orthogonal Matching Pursuit for Linear Frequency Modulated Pulse Frequency Agile Radar
• A Method with Lower-than-ML Threshold for Frequency Estimation of Multiple Sinusoids