Super-resolution via superset selection and pruning

I. INTRODUCTION

• The target is recovery, or approximation, of a sparse vector from m ≤ n contiguous Fourier measurements.The measurement model uses a partial, short-and-wide Fourier matrix and allows additive noise.Source: §I · p. 1
• Contiguous Fourier measurements permit neighboring nonzero components to be much closer than the Rayleigh limit n/m, but super-resolution can be arbitrarily ill-posed.The introduction contrasts these measurements with randomly drawn measurements in compressed sensing and notes open questions about recovery bounds and suitable algorithms.Source: §I · p. 1
• The superset method combines subspace identification with a removal procedure that tightens the active set.The identification step is described as related to matrix pencil but omits its subsequent eigenvalue computation.Source: §I · p. 1
• The method is claimed to provide perfect recovery for the noiseless ℓ0 problem and to generalize to higher dimensions.The authors also report that it can outperform the matrix pencil method in numerical experiments.Source: §I · p. 1

II. NOISELESS SUBSPACE IDENTIFICATION

• The classical uniqueness result states that x0 is the unique sparsest solution when m ≥ 2|T| and y = Ax0.This result is recalled as background for the recovery procedure.Source: §II · p. 1
• Translation invariance of partial Fourier columns lets the method use translated copies of y in a Hankel matrix to obtain the subspace spanned by the signal atoms.Restrictions to consecutive entries reproduce the same sequence up to an overall scalar; the range of the Hankel matrix is the sought subspace.Source: §II · p. 2
• For L ≥ |T|, the Hankel matrix has rank |T|, providing the subspace used to identify the support.The recovery procedure tests candidate atoms using their angle to the identified subspace.Source: §II · p. 2
• After identifying T, the method obtains the solution by solving the determined system on that support.The resulting procedure is stated to solve the noise-free ℓ0 sparse-recovery problem.Source: §II · p. 2
• When m > 2|T| and |T| + 1 ≤ L ≤ m − |T| − 1, the procedure recovers x0 exactly in the noiseless case.The proof relies on the partial Fourier matrix being full spark.Source: §II · p. 2
• The matrix pencil approach computes rank-reducing numbers through generalized eigenvalues, whereas the superset procedure uses subspace identification followed by support removal.The cited discussion notes that Prony’s method is a matrix-pencil special case when L = |T| and should be avoided in practice if possible due to numerical inferiority.Source: §II · p. 2

III. NOISY SUBSPACE IDENTIFICATION

• When noise is present, the signal range differs from Ran Y, but low-noise cases may still reveal the support through the smallest angles.The pruning step projects the observation onto the candidate range and retains indices only when the angle exceeds a threshold.Source: §III · pp. 2–3
• Under Gaussian noise e ~ N(0, σ^2 I_m), Proposition 4 gives a high-probability singular-value bound for indices in the support.The proposition concerns the singular values of the noisy and noiseless Hankel matrices.Source: §III · p. 2
• The procedure estimates support size with a large constant such as m/2 and assumes the signal dynamic range can be known beforehand.It replaces an unknown noiseless singular value using Weyl’s inequality; the perturbation is described as controllable with high probability.Source: §III · p. 3
• The subspace-identification step returns a set expected to contain the true support, rather than the support itself.A second step removes candidates by testing whether the observation lies in the range after each candidate column is removed.Source: §III · p. 3
• Algorithm 1 implements pruning iteratively, removing one atom at a time and stopping when the removal test no longer meets its threshold.The algorithm then computes a least-squares fit over the remaining candidate support.Source: §III · p. 3

IV. EXPERIMENTAL RESULTS

• 0.075 was the superset method’s ∥bx − x0∥2 for well-separated spikes; ℓ1-minimization tended to form incorrect clusters around the true spikes.The comparison is shown in Fig. 1’s top row.Source: §IV · p. 3, Figure 1 · p. 4
• For a strongly coherent signal with neighboring spike clusters, the superset method was accurate while ℓ1-minimization failed at least on opposite-sign clusters.The example used n = 1000 and m = 120.Source: §IV · p. 3, Figure 1 · p. 4
• At reasonably small noise, the method recovers exactly even when coherence is nearly 1.The experiment varies measurements and noise for two neighboring spikes and reports success frequency over 100 noise realizations.Source: §IV · pp. 3–4
• For a 2-spike signal, matrix pencil is often better, but it loses ground to the superset method in various progressively less sparse cases.The authors note that understanding matrix pencil performance would require a lower bound on typically very small singular values.Source: §IV · p. 4

• The conclusion presents empirical evidence for the superset method’s potential as a viable computational approach to super-resolution.Source: §V · p. 4
• Further theoretical justifications are deferred to later work.Source: §V · p. 4
• Figure 2 compares recovery probability for the superset and matrix pencil methods across noise and coherence levels for 2-, 3-, and 4-sparse signals.Source: Figure 2 · p. 4