Source-linked AI summary
Compressed Sensing off the Grid
Gongguo Tang, Badri Narayan Bhaskar, Parikshit Shah, Benjamin Recht
TL;DR
The paper addresses frequency estimation for partially observed mixtures of complex sinusoids when frequencies are continuous rather than grid-constrained. It uses atomic norm minimization with an exact semidefinite-program formulation and shows exact recovery and frequency localization from sufficiently many random samples under frequency separation. The approach resolves basis mismatch for well-separated line spectra, while noise robustness and computational scaling remain open limitations.
Problem
Compressed sensing needs a method for signals with continuous, off-grid frequencies instead of finite discretized dictionaries.
Method
Atomic norm minimization over complex-exponential atoms is reformulated as an exact semidefinite program for recovering missing samples and estimating frequencies.
Results
For well-separated frequencies, roughly O(s log s log n) random samples suffice for exact signal recovery and frequency localization with high probability.
Takeaways & Limitations
The continuous-dictionary approach resolves basis mismatch despite global coherence, provided the true frequencies are sufficiently separated.
Takeaways & Limitations
In noise, exact support recovery cannot be expected because continuous frequencies become unidentifiable; the paper leaves theoretical stability unresolved.
Abstract
from arXiv · showhide
We consider 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]. We propose an atomic norm minimization approach to exactly recover the unobserved samples. We reformulate this atomic norm minimization as an exact semidefinite program. Even with this continuous dictionary, we show that most sampling sets of size O(s log s log n) are sufficient to guarantee the exact frequency estimation with high probability, provided the frequencies are well separated. Numerical experiments are performed to illustrate the effectiveness of the proposed method.
1 Introduction
The paper estimates off-grid sinusoidal frequencies from randomly sampled time-domain data by optimizing over a continuous atomic dictionary. It establishes exact recovery and frequency localization under separation and random-sign conditions, while avoiding discretization-induced basis mismatch.
- Problem: Compressed sensing traditionally uses finite dictionaries, whereas many signals are parameterized by continuous frequencies that may fall between grid points.The paper targets applications including radar, array processing, communication, seismology, and remote sensing.
- Guarantee: With sufficiently separated frequencies, a sparse sum of complex sinusoids can be reconstructed exactly from a small random sample of time observations.The theorem assumes uniformly random sampling, random coefficient signs, and a minimum separation condition, then guarantees recovery and frequency localization with probability at least 1 − δ.
- Method: The method applies atomic norm minimization directly to continuous complex-exponential atoms and reformulates the optimization exactly as a semidefinite program.The atomic norm generalizes ℓ1 sparse recovery and nuclear-norm low-rank recovery, and is computationally tractable here through semidefinite programming.
- Model: The model samples a subset of regularly spaced times from signals whose unknown frequencies lie anywhere in the normalized interval [0, 1].The sampling set is a subset of {0, ..., n − 1}, rather than the full set of regularly spaced samples.
- Resolution: The required random sample count is O(s log s log n), while the frequency separation condition constrains recoverability.For consecutive samples, the required minimum separation is larger by a logarithmic factor; simulations suggest the critical random-sampling separation may be closer to 1/n than the bound with constant 4.
- Implications: The continuous formulation removes the basis-mismatch problem, making local separation between true atoms more important than global dictionary coherence.Frequencies can be localized from the dual solution, or after missing samples are recovered by Prony’s method, matrix pencil methods, or linear prediction.
2 The Atomic Norm and Semidefinite Characterizations
The paper defines an atomic norm for continuous complex-sinusoid atoms and derives an exact semidefinite representation. This formulation enables recovery from partial observations, with exact recovery and frequency localization under random sampling, separation, and phase assumptions.
- The signal is modeled as a positive combination of complex sinusoids with arbitrary frequencies and phases, using atoms indexed by f ∈ [0,1] and φ ∈ [0,2π).
- The atomic norm is the gauge of the convex hull of the continuous atom set and promotes sparse combinations through low-dimensional faces of that hull.
- For complex exponentials, the atomic norm admits an exact semidefinite-program characterization involving a positive semidefinite Toeplitz matrix and a scalar auxiliary variable.
- The Toeplitz decomposition can be computed by root finding or a generalized eigenvalue problem, providing an implementation route for the semidefinite formulation.
- Atomic norm minimization recovers missing samples from observed entries, and its semidefinite program almost always identifies frequencies when measurements are sufficient and frequencies are reasonably well separated.
- Under the theorem’s random-sampling, random-phase, and separation conditions, the true signal is the unique optimizer with probability at least 1 − δ; dual optima can also localize frequencies.
- The dual polynomial identifies frequencies at locations where its modulus equals one, while atomic norm minimization acts as a trace relaxation of rank minimization.
3 Prior Art and Inspirations
Prior approaches primarily use equispaced samples, while this paper extends exact continuous-frequency recovery to undersampled, nonuniform observations through an atomic-norm framework.
- Convex relaxations can exactly recover spectra under frequency-separation conditions, but prior guarantees require separation on the order of the inverse sample count.
- Earlier frequency-estimation methods generally rely on uniform or equispaced time samples.
- The paper extends these ideas to random subsets of regularly spaced samples while retaining continuous-domain frequency recovery.
- Nonuniform sampling enables compressive, sub-Nyquist acquisition and can reduce the number of sensors needed in array-processing applications.
- The authors position the results as connecting compressed sensing with continuous dictionaries and line-spectral estimation with nonuniform sampling.
4 Proof of Theorem 2.3
The proof certifies atomic-norm recovery by constructing a bounded dual polynomial whose coefficients are restricted to the observed sample set. Concentration arguments control the random perturbation and extend the certificate from a grid to the full frequency domain.
- A dual polynomial certifies optimality by interpolating the target frequencies and remaining bounded elsewhere.
- The squared Fejér kernel peaks at one and rapidly decays, making it suitable for constructing coefficients under a frequency-separation condition.
- The random-sampling certificate uses a random kernel whose nonzero coefficients correspond only to observed indices.
- Matrix Bernstein inequality establishes invertibility of the coefficient system with high probability.
- Hoeffding concentration and a union bound control random polynomial perturbations on a finite grid.
- Bernstein’s polynomial inequality extends the grid result to the continuous interval and establishes |Q(f)| < 1 away from the target frequencies.
5 Numerical Experiments
The experiments compare the continuous semidefinite-program approach with discretized basis pursuit across frequency-recovery, accuracy, running-time, and phase-transition settings. SDP generally provides more accurate recovery, while discretization increases BP accuracy at substantial computational cost; frequency separation sharpens recovery transitions.
- Frequency localization: SDP produced the most accurate frequency localization, while increasing BP’s discretization level improved its localization accuracy.The comparison used n=256, s=6, and m=40 uniformly random samples.
- Experimental design: The experiments used three discretization levels and 1,920 valid trials, each configuration repeated 10 times.Trials with ρm≥1 were excluded.
- Accuracy and running time: SDP significantly outperformed BP in numerical accuracy across all tested discretization levels.The performance profiles compare solution accuracy and running time over the experimental configurations.
- Accuracy and running time: At discretization level N=64n, BP reached median accuracy of order 10^-5, while SDP achieved median error of order 10^-9.BP’s median running time at N=64n already exceeded SDP’s.
- Phase transitions: Phase-transition plots encode observed-entry fraction on the x-axis, sparsity fraction on the y-axis, and success rate by color.Red denotes perfect recovery and blue denotes complete failure.
- Phase transitions: Increasing the minimum frequency separation produced a much sharper transition boundary, which approached the ρs=ρm/2 line.With separation marginally above 1/n, failures occurred below the initially expected boundary.
6 Conclusion and Future Work
The method resolves basis mismatch for line spectra and recovers signals from compressed samples when frequencies are well separated. Future work addresses noisy recovery, computational scaling, and extensions beyond continuous frequency models.
- Conclusion: Well-separated frequencies require roughly a number of samples proportional to the number of frequencies, up to polylogarithmic factors.The result holds despite the continuous dictionary lacking incoherence and restricted-isometry conditions.
- Noisy recovery: Exact support recovery cannot be expected with noise because continuous frequencies become un-identifiable under perturbations.The authors leave theoretical stability analysis for future work.
- Noisy recovery: 18 uniform samples recovered a three-frequency signal with bounded ℓ2 noise of ε = 2 in a numerical denoising example.The paper presents this as evidence suggesting stability, not as a verified stability theorem.
- Computation: Modest discretization causes substantial reconstruction error, while fine discretization imposes significant computational burdens.First-order methods tested by the authors did not achieve the precision needed for fine frequency localization.
- Future directions: The authors propose extending semidefinite-characterizable recovery techniques to other continuously parametrized dictionaries, including possible image-manifold models.This direction is intended to clarify which signal classes can be exactly recovered.
A Proof of Theorem 1.1
The proof of Theorem 1.1 translates the observation model to a symmetric index set and constructs a dual polynomial under a minimum frequency-separation condition. Rewriting the resulting guarantee in the original indexing yields the theorem.
- Index transformation: The Bernoulli observation model on {0, …, n − 1} induces a corresponding model on the symmetric set {−2M, …, 2M}.The translated observation set has sampling probability m/n.
- Dual certificate: Under minimum separation Δf ≥ 1/M, the proof invokes the theorem's dual-polynomial construction with high probability.The construction is used to certify optimality after translating back to the original index set.
- Dual certificate: The polynomial Q(f) satisfies the required certificate properties, and rewriting the symmetric result in terms of n completes the theorem.The final step uses Proposition 2.4.
B Proof of Proposition 2.5
The proof characterizes Gram-matrix representations associated with the dual polynomial and establishes rank, complementarity, and strict inequality properties needed for the semidefinite-program solution.
- Gram representations: A nonnegative trigonometric polynomial with s unit-circle zeros admits a positive semidefinite Gram matrix of rank n − s.The construction uses spectral factorization and a maximal-rank representation.
- Gram representations: There are 2^(n−1−s) rank-one representations, obtained by choosing one root from each conjugate pair.The zero structure determines the available spectral-factor choices.
- Optimality: The constructed primal-dual pair is strictly complementary, and the unique primal optimum has the stated atomic decomposition.The argument uses shared range spaces for relative-interior optimal solutions.
- Dual certificate: The dual polynomial satisfies |⟨q, a(f_k, 0)⟩| = 1 at the support frequencies and is strictly less than one elsewhere.This separates the true frequencies from all other frequencies in the dual certificate.
C Proof of Proposition 4.1
The proof of Proposition 4.1 applies a separation assumption and a matrix norm bound to establish invertibility of the relevant matrix.
- Separation assumption: The proof assumes the minimum frequency separation satisfies Δmin ≥ 1/M.This is the condition under which the cited lemma is applied.
- Invertibility argument: The Geršhgorin circle theorem is applied to the symmetric matrix I − D̄ with zero diagonal.The argument uses the matrix infinity norm, defined as the maximum absolute row sum.
- Invertibility argument: Consequently, D̄ is invertible.
D Proof of Lemma 4.4
The proof computes the quantities needed for Lemma 4.3 and establishes the required bounds, including invertibility and an upper bound on σ2.
- The argument begins by computing the quantities required to apply Lemma 4.3.
- M ≥ 4 is used in the proof.
- σ2 is bounded above by 1.3623 using (4.8) and (4.3).
- The proof confirms invertibility of p−1D.
E Proof of Corollary 4.5
The proof derives two inequalities as rearrangements of earlier bounds and concludes by comparing operator norms of a matrix and its submatrices.
- The proof derives two inequalities as rearrangements of a preceding relation.
- One bound is stated on the set E1,τ in terms of ∥¯D−1∥.
- The argument concludes because a matrix’s operator norm dominates the operator norms of all its submatrices.
F Proof of Lemma 4.6
The proof applies Talagrand’s concentration inequality to control the relevant random quantities, using bounds on variance and deviation terms before a union-bound conclusion.
- The proof uses Talagrand’s concentration of measure inequality.
- Lemma F.1 concerns independent Banach-space-valued random variables and a countable family of centered, bounded functions.
- Lemma F.1 defines the variance parameter σ2 and deviation quantity ¯V used in the concentration bound.
- The proof rewrites vℓ(f) − p¯vℓ(f) as vℓ(f) − Evℓ(f) and defines the associated random variables Y ℓ.
- After bounding the required quantities, the proof concludes with a condition involving γ > 0 and an application of the union bound.
G Proof of Lemma 4.8
The proof combines Hoeffding-based concentration, auxiliary bounds, and union bounds to establish the required probabilistic conditions for Lemma 4.8.
- The proof is based on Hoeffding’s inequality for independent random variables on the complex unit circle.
- It analyzes a random inner product involving u, L∗, and vℓ(f) − p¯vℓ(f), then applies Hoeffding’s inequality and union bounds.
- The argument imposes conditions on a, including the case 24s/√m ≥ 1, to control terms below δ.
- The proof combines lower bounds on m and sets τ = 1/4 to obtain a sufficient condition holding with probability at least 1 − 3δ.