Super-Resolution of Point Sources via Convex Programming

1 Introduction

• Super-resolution covers reconstructing images from blurred measurements and recovering spectra from truncated time-domain data.The paper focuses on recovering lost fine-scale features without changing the low-pass sensing process.Source: §1 · pp. 1, 3
• Recovering a signal from low-resolution measurements requires structural prior knowledge because otherwise the missing spectrum can be filled arbitrarily.The paper considers signals represented as superpositions of point sources, including spikes and line spectra.Source: §1 · p. 3
• Earlier convex programming established exact recovery at minimum separation 2/fc, while later work established robustness to noise in non-asymptotic regimes [39].Source: §1 · p. 3
• Convex programming recovers point sources at separations above 1.26/fc, using a dual certificate that also extends previous stability results.The paper presents the separation result and dual-certificate proof as central contributions.Source: §1 · p. 3
• The paper adapts its approach to demixing sines and spikes and to super-resolution of multiple signals sharing a common support.For each extension, it proposes a tailored optimization program, discusses solution and optimality conditions, and provides numerical simulations.Source: §1 · p. 3

2.1 Basic model

• The basic model represents a signal as weighted Dirac measures and observes its convolution with a low-pass point-spread function, equivalently its lowest 2fc+1 Fourier coefficients.For line spectra, the measurements correspond to finite time-domain samples.Source: §2.1 · p. 4

2.2 Minimum separation

• When sources cluster too closely relative to the cutoff frequency, low-pass filtering can suppress them, making recovery ill posed even under small data perturbations.The inverse cutoff frequency λc is a fundamental scale; below λc/2, signals can lie nearly in the low-pass operator’s null space.Source: §2.2 · p. 5

2.3 Optimization-based super-resolution

• At minimum separation 1.26λc, total-variation minimization achieves exact recovery; the guarantee extends earlier convex-programming results.The analysis also implies that the recoverable number of sources on the unit interval is proportional to the cutoff frequency.Source: §2.3 · p. 7

2.4 Dual certificate

• A dual certificate proves recovery by interpolating the signal’s signs on its support while remaining strictly below magnitude one off-support.Its structure also identifies harder cases: clustered supports and rapidly varying coefficient signs may defeat bounded low-pass interpolation.Source: §2.4 · pp. 7–8

2.5 Robustness to noise

• The dual-certificate techniques extend noisy-data stability guarantees from minimum separation 2λc to 1.26λc.The construction also sharpens related support-detection and positive-amplitude recovery analyses.Source: §2.5 · p. 9

2.6 Extensions

• The results also lower the minimum-separation requirement to 1.26λc for off-the-grid compressed sensing with random low-pass Fourier samples.The construction further sharpens results for non-uniform splines and applies to piecewise-constant or piecewise-smooth recovery.Source: §2.6 · p. 9

2.7 Implementation

• The infinite-dimensional optimization can be solved exactly through a finite-dimensional semidefinite program, followed by support and amplitude estimation.The procedure extracts candidate support locations from points where the support-locating polynomial has magnitude one.Source: §2.7 · pp. 9–11

2.8 Related work

• Classical MUSIC, Cadzow, and ESPRIT appear comparable in practice, while this work sharpens the earlier 2λc exact-recovery guarantee.Matched-filter methods can degrade under aliasing, and Prony’s method, though exact without noise, can be highly sensitive to perturbations.Source: §2.3 · p. 7, §2.8 · pp. 11–12

3.1.1 Estimation via convex programming; 3.1.2 Implementation

• The demixing program combines the TV norm of the line-spectrum measure with an ℓ1 penalty on spikes, without requiring prior knowledge of either component count.A dual semidefinite program locates spike support where the dual solution reaches η and line-spectrum support where the support-locating polynomial has magnitude one; amplitudes are then estimated from equations.Source: §3.1.1 · p. 14, §3.1 · p. 14, §3.1.2 · pp. 15–16

3.1.3 Theoretical analysis: Dual certificate

• Demixing is uniquely recoverable when a dual certificate interpolates the line-spectrum and spike signs while satisfying the spike constraints.The certificate may be impossible to construct for very clustered line spectra or too many spikes, creating a tradeoff between recoverable sines and spikes.Source: §3.1.3 · p. 16

3.1.4 Numerical results

• Demixing shows a rapid transition between near-always exact recovery and failure; with fixed separation, success allows fewer spikes as the number of sine components grows.For fixed sine count, the separation threshold seems independent of spike count when there are not too many spikes; for fixed spike count, it seems independent of sine count below a limit.Source: §3.1.4 · p. 17, Figure 7 · p. 17

3.2 Point sources with a common support; 3.2.1 Estimation via convex programming

• For signals sharing a support, the method processes their low-pass measurements jointly to exploit amplitude diversity rather than estimating each support separately.This setting is motivated by fluorescence microscopy and sparse-channel estimation.Source: §3.2 · p. 17, §3.2.1 · p. 18

3.2.1 Estimation via convex programming

• The continuous ℓ1/ℓ2-based gTV objective favors a sparse common support and can jointly recover signals that are challenging to super-resolve individually.For point-source signals, the gTV norm reduces to the ℓ1/ℓ2 norm of the amplitude matrix.Source: §3.2.1 · p. 18

3.2.2 Implementation

• The common-support implementation uses an SDP-derived support-locating polynomial; in the example, individual TV polynomials miss spikes and produce false positives.The example uses three signals, 15 sources, cutoff frequency 40, and minimum separation 0.7λc.Source: Figure 8 · p. 19, §3.2.2 · p. 20

3.2.3 Theoretical analysis: Dual certificate; 3.2.4 Numerical results

• For common-support recovery, the dual certificate gives uniqueness, and simulations show the critical separation decreases as the number of signals increases, saturating at λc/2.For amplitudes in general position, the authors suggest interpolation may become easier with more signals; the simulations confirm decreasing separation thresholds.Source: §3.2.4 · p. 21, §3.2.3 · p. 21

4 Proof of Proposition 2.3

• A product of differently band-limited Dirichlet kernels gives faster tail decay, while incorporating the kernel derivative makes the interpolating polynomial’s magnitude locally extremal at support points.The construction addresses both off-support magnitude control and the need to keep the polynomial from exceeding one near the support.Source: §4 · pp. 22–23

4.2 Proof of Lemma 4.1

• Lemma 4.1 establishes interpolation coefficient vectors satisfying the construction’s equations under Theorem 2.2’s hypotheses.The proof uses matrix invertibility to ensure the coefficient vectors are well defined.Source: §4 · p. 24, §4.2 · p. 27

4.3 Proof of Lemma 4.2

• Near each support point, Lemma 4.2 bounds |q(t)| strictly below 1 up to 0.288316 λc and establishes the local quadratic bound.The proof uses grid-evaluated bounds on |q|² and its second derivative.Source: §4 · p. 24, §4.3 · p. 30, Figure 12 · p. 30

4.1 Bounds on the interpolation kernel

• Sharp bounds on the interpolation kernel and its derivatives provide the estimates used in the subsequent lemmas.The section gives near-origin bounds and weaker, decreasing bounds away from the origin.Source: §4.1 · p. 25

4.4 Proof of Lemma 4.3

• From 0.288316 to τmin/2, the grid-evaluated bound (4.17) remains strictly below 1, extending off-support control beyond the local interval.Figure 13 evaluates the bound on a grid with step size 10^-6.Source: §4 · p. 24, Figure 13 · p. 31

5 Conclusion and future research

• The paper characterizes convex-programming super-resolution for one-dimensional point sources separated by a minimum distance.The authors describe the characterization as reasonably tight.Source: §5 · p. 32
• The work also derives optimization-based algorithms for demixing sines and spikes and for super-resolving point sources with a common support.The authors identify theoretical guarantees for both models as an open direction, using appropriate dual certificates.Source: §5 · p. 32
• Applying the optimization programs in real applications will require efficient algorithms for large-scale datasets.The conclusion also identifies two-dimensional signals and supports with some clustering as directions for further study.Source: §5 · p. 32

A.1 Proof of Proposition 2.4

• Fejér-Riesz factorization supplies a polynomial factor for the nonnegative trigonometric polynomial used in the certificate.The proof first obtains nonnegativity from the bound on the polynomial norm.Source: §A.1 · p. 36
• Setting Λ = CC* + c̃c̃* makes Λ and Λ − CC* positive semidefinite and yields T*(Λ) = e1.The proof uses these properties to complete the certificate construction.Source: §A.1 · p. 37

A.2 Proof of Lemma 3.1

• Minimizing the Lagrangian gives dual feasibility constraints |(F*n c)(t)| ≤ 1 and ||c||∞ ≤ η; maximizing the remaining expression yields the dual problem.The Lagrangian includes the total-variation and weighted ℓ1 costs with the data constraint.Source: §A.2 · p. 37

• The feasible set contains the origin in its interior, so it is nonempty.Source: §A.3 · p. 37
• The interior-point condition allows the proof to invoke generalized Slater strong duality.Source: §A.3 · p. 37
• Hölder’s inequality together with the constraints on ĉ yields the stated result.Source: §A.3 · p. 37

A.4 Proof of Lemma 3.3

• The proof considers an arbitrary solution distinct from the target that satisfies the optimization constraints.This sets up the uniqueness argument.Source: §A.4 · p. 38

A.4.1 Proof of Lemma A.1

• The Fourier matrix indexed by T is full rank because it is a submatrix of a Vandermonde matrix, supporting the conclusion that x′ = x and s′ = s.The proof concludes equality of both components.Source: §A.4.1 · pp. 38–39

A.5 Proof of Lemma 3.4

• Minimizing the Lagrangian over X̃ gives a finite lower bound only under the stated constraints; there the minimum occurs at X̃ = 0, and maximizing over C yields the dual problem.The passage identifies C as the dual variable.Source: §A.5 · p. 39

A.6 Proof of Lemma 3.5

• The proof invokes strong duality under a generalized Slater condition and uses a lemma based on Cauchy–Schwarz to establish the stated result.The lemma rules out equality if any rowwise inner product is strictly below the corresponding norm.Source: §A.6 · pp. 39–40

A.7 Proof of Lemma 3.6

• A certificate Q with norm at most one on T and strictly below one on Tᶜ makes any nonzero off-support perturbation increase the group-TV bound, while ⟨Q, X⟩ = ||X||gTV.The argument uses separability of the gTV norm to compare the supported and off-support components.Source: §A.7 · p. 41
• Injectivity of measurements on T follows from a full-rank Vandermonde submatrix, so a perturbation vanishing off T must also vanish on T.Together these conditions complete the uniqueness proof.Source: §A.7 · p. 41

B.1 Upper and lower bounds near the origin in Lemma 4.4

• τ₀(0.247) = 0.9112, τ₀(0.339) = 0.6615, and τ₀(0.414) = 0.5401 mark interval splits for the bounds near the origin.The intervals depend on γ₀.Source: §B.1 · p. 42
• τ₃(0.247) = 0.4614, τ₃(0.339) = 0.2346, and τ₃(0.414) = 0.3051 are reported for the derivative-bound intervals.The appendix gives upper and lower bounds on K and its derivatives near the origin.Source: §B.1 · pp. 43–44

B.2 Bounds on the tail of the kernel in Lemma 4.6

• Bounds for γ = [0.247, 0.339, 0.414]ᵀ are plotted in Figure 15.The figure caption identifies non-increasing upper bounds on |Kγ| and its derivatives.Source: §B.2 · p. 46

C.1 Proof of Lemma 4.4

• For 0 < γ₀ < 1 and f_c ≥ f_min, the proof derives local bounds on Kγ and its derivatives using trigonometric identities and Taylor expansions.It also controls deviations from grid values using Bernstein’s inequality for trigonometric polynomials.Source: §C.1 · pp. 48, 49, 51, 52
• The first-, second-, and third-derivative bounds are extended from the local interval using the stated identities and inequalities.For the third derivative, the passage specifies one interval up to τ₃(γ₀) and obtains the remaining bounds by combining the displayed estimates.Source: §C.1 · pp. 49, 51

C.2 Proof of Lemma 4.6

• The tail inequalities establish bounds that decrease in τ under the condition stated in Lemma 4.6.The proof combines the inequalities with (C.19) and notes the f_min ≥ 10³ condition.Source: §C.2 · p. 52

C.3 Proof of Lemma 4.7

• Grid-based maximization bounds kernel contributions across the allowed source locations by covering an interval with an equispaced grid of separation ϵ.The bound applies to source locations within (j + 4)Δ_min; more distant locations are handled using Lemma 4.6.Source: §C.3 · p. 53
• The proof uses sharper kernel or derivative bounds for terms 1–20, then applies a coarser bound for terms 21–400.The minimum-separation condition supplies the distance bound used for the more distant terms.Source: §C.3 · p. 53
• Lemma C.2 considers derivative orders ℓ = 0, 1, 2, 3 for fc ≥ 10^3 and 80/fc ≤ |t| ≤ 1/2, with γ = [0.247, 0.339, 0.414]ᵀ.Source: §C.3 · p. 53

C.4 Proof of Lemma C.2

• For large t, the proof of Lemma C.2 uses a lower bound on the sine function and combines it with bounds on the kernel and its derivatives.The proof sets p := 3, while noting that the lemma also holds when convolving a different number of Dirichlet kernels.Source: §C.4 · p. 54

C.5 Proof of Lemma 4.9

• The C.5 proof applies the fundamental theorem of calculus over ϵ-sized intervals under assumptions on F and bound (C.27).The argument considers t and t′ in adjacent intervals indexed by integers k and j.Source: §C.5 · p. 55