Compressed Sensing Off the Grid

By Gongguo Tang, Badri Narayan Bhaskar, Parikshit M. Shah, B. Recht. IEEE Transactions on Information Theory, 2012

1,150 citations recorded by the source corpus.

This paper investigates the problem of estimating the frequency components of a mixture of s complex sinusoids from a random subset of n regularly spaced samples. Unlike previous work in compressed sensing, the frequencies are not assumed to lie on a grid, but can assume any values in the normalized frequency domain [0, 1]. An atomic norm minimization approach is proposed to exactly recover the unobserved samples and identify the unknown frequencies, which is then reformulated as an exact semidefinite program. Even with this continuous dictionary, it is shown that O(slog s log n) random samples are sufficient to guarantee exact frequency localization with high probability, provided the frequencies are well separated. Extensive numerical experiments are performed to illustrate the effectiveness of the proposed method.

Subfields: Biomedical Engineering, Computational Mechanics, Signal Processing

View Paper: https://www.semanticscholar.org/paper/f29c7f5fd1125b445bffa4bb43da0cd908ba3a1d

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biomedical Engineering

1. Lihua Xie
2. Zai Yang
3. Marco F. Duarte
4. Joan Bruna
5. C. Freeman
6. Richard Baraniuk
7. Jian Li
8. P. Stoica

In Computational Mechanics

1. Lihua Xie
2. Zai Yang
3. Jian Li
4. P. Stoica
5. Marco F. Duarte
6. Gongguo Tang
7. Yuejie Chi
8. Badri Narayan Bhaskar

In Signal Processing

1. Lihua Xie
2. Zai Yang
3. Jian Li
4. P. Stoica
5. Joan Bruna
6. C. Freeman
7. Gongguo Tang
8. Badri Narayan Bhaskar

Citations in the corpus

• On Gridless Sparse Methods for Line Spectral Estimation From Complete and Incomplete Data (2014, methodology): “In the presence of missing data, the noiseless case is studied in [30], [31] via atomic norm minimization with exact recovery proven under some technical assumptions.”
• Nonconvex Optimization Meets Low-Rank Matrix Factorization: An Overview (2018, background): “robust PCA [159] low-rank projection + thresholding [25] [7, 8, 213, 214] GD + thresholding [64, 215] alternating minimization [216] spectrum estimation — projected GD [217] [218, 219]”
• Topology and Geometry of Half-Rectified Network Optimization (2016, methodology): “For simplicity, we continue to use Wi and x in the following.”
• Spectral compressive sensing (2013, background): “A very recent contributions in the direction of optimization-based approaches shows promising results [73].”
• Direction-of-Arrival Estimation for Coprime Array via Virtual Array Interpolation (2018, background): “We would like to emphasize the striking differences between the virtual domain atoms and those in the physical domain [32]–[34].”
• Sparse Methods for Direction-of-Arrival Estimation (2016, methodology): “,K from y based on the data model in (225) is also referred to as continuous or infinite-dimensional compressed sensing, which extends compressed sensing from the discrete to the continuous setting [127, 154, 174].”
• Enabling Joint Communication and Radar Sensing in Mobile Networks—A Survey (2020, methodology): “Compressive Sensing (Off-grid) such as atomic norm minimization [112], [178], [179] Flexible and do not require consecutive samples.”
• MIMO Radar for Advanced Driver-Assistance Systems and Autonomous Driving: Advantages and Challenges (2020, neutral): “solution invalid [78].”
• Atomic Norm Denoising With Applications to Line Spectral Estimation (2012, methodology): “This frequency localization technique is later extended in [27] to the random undersampling case to yield a compressive sensing scheme that is robust to basis mismatch.”
• Multibeam for Joint Communication and Radar Sensing Using Steerable Analog Antenna Arrays (2018, methodology): “There exist some techniques dealing with off-grid models, such as the perturbation approach [21] and atomic norms [22], but they are currently limited to lowdimension (≤2) problems, and also have respective constrains on the parameter estimation range and the minimum separation of the parameter valu”
• Topology and Geometry of Deep Rectified Network Optimization Landscapes (2016, methodology): “For that purpose, we start with a characterization of the oracle loss, and for simplicity let us assume Y ∈ R and let us first consider the case with a single hidden layer and `1 regularization: R(θ) = ‖θ‖1.”