PaperlayerView exact revision on arXiv

Source-linked AI summary

Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization

Yuejie Chi

arXiv:1506.02751v3cs.ITmath.ITmath.OC

TL;DR

When the point spread function is unknown, recovering sparse spike delays and amplitudes from convolution measurements is ill-posed. AtomicLift constrains the point spread function to a known low-dimensional subspace and applies lifting with atomic-norm minimization. Under stated randomness and separation conditions, it guarantees recovery up to scale with sufficiently many samples.

  • Problem

    The paper addresses joint recovery of sparse spike delays and amplitudes when the point spread function in the convolution measurements is unknown.

    Source: §I · p. 1, A. Our Contributions · p. 1

  • Method

    AtomicLift constrains the point spread function to a known low-dimensional subspace, lifts the bilinear problem, and applies atomic-norm minimization to the jointly spectrally sparse signals.

    Source: A. Our Contributions · p. 2

  • Results

    With high probability, under isotropic and incoherent i.i.d. subspace rows and minimum separation 1/M, AtomicLift recovers the spike signal up to scale using N on the order of O(K^2L^2), up to logarithmic factors.

    Source: A. Our Contributions · p. 2

  • Takeaways & Limitations

    The dual solution localizes spikes through peaks of a vector-valued polynomial, and the convex formulation can be implemented by semidefinite programming.

    Source: A. Our Contributions · p. 2, E. Spike Localization · p. 5

    The theory requires O(K^2L^2) samples up to logarithmic factors, while observed phase transitions suggest success at O(KL).

    Source: §V · p. 9

Abstract

from arXiv · show

Neural recordings, returns from radars and sonars, images in astronomy and single-molecule microscopy can be modeled as a linear superposition of a small number of scaled and delayed copies of a band-limited or diffraction-limited point spread function, which is either determined by the nature or designed by the users; in other words, we observe the convolution between a point spread function and a sparse spike signal with unknown amplitudes and delays. While it is of great interest to accurately resolve the spike signal from as few samples as possible, however, when the point spread function is not known a priori, this problem is terribly ill-posed. This paper proposes a convex optimization framework to simultaneously estimate the point spread function as well as the spike signal, by mildly constraining the point spread function to lie in a known low-dimensional subspace. By applying the lifting trick, we obtain an underdetermined linear system of an ensemble of signals with joint spectral sparsity, to which atomic norm minimization is applied. Under mild randomness assumptions of the low-dimensional subspace as well as a separation condition of the spike signal, we prove the proposed algorithm, dubbed as AtomicLift, is guaranteed to recover the spike signal up to a scaling factor as soon as the number of samples is large enough. The extension of AtomicLift to handle noisy measurements is also discussed. Numerical examples are provided to validate the effectiveness of the proposed approaches.

I. INTRODUCTION

Blind spikes deconvolution seeks source delays and amplitudes from convolution measurements when the point spread function is unknown, making joint recovery ill-posed. The paper introduces AtomicLift, which uses lifting and joint spectral sparsity to recover the spike signal and point spread function under stated conditions.

I. INTRODUCTION

  • AtomicLift targets source delays and amplitudes from convolution measurements when the point spread function is unknown, a setting that makes blind deconvolution ill-posed.Applications include radar, sonar, neural recordings, and array signal processing.Source: §I · p. 1

A. Our Contributions

  • Lifting converts the bilinear measurements into a linear system for a rank-one matrix, whose shared spectral support enables atomic-norm recovery without a predefined spike-location grid.The method constrains the point spread function to a known low-dimensional subspace and can be implemented by semidefinite programming.Source: A. Our Contributions · pp. 1–2
  • Under i.i.d. isotropic and incoherent subspace rows and minimum spike separation 1/M, AtomicLift recovers the signal up to scale with high probability for N on the order of O(K^2L^2), up to logarithmic factors.The result assumes no randomness in the spike signal or the point-spread-function orientation.Source: A. Our Contributions · p. 2
  • The proof certifies optimality with a vector-valued dual polynomial, adapting squared Fejer-kernel constructions to the lifting operator.The dual polynomial differs from prior scalar constructions because it is vector-valued and incorporates the special linear operator induced by lifting.Source: A. Our Contributions · p. 2

B. Comparisons with Related Work

  • Earlier subspace-based blind-deconvolution guarantees do not directly fit continuous spike locations, while grid-based sparse recovery can encounter basis mismatch off-grid.Atomic-norm super-resolution work is extended here to the more challenging unknown-PSF setting, for which the authors claim the first provable blind super-resolution algorithm.Source: B. Comparisons with Related Work · p. 2

C. Paper Organization

  • The paper proceeds from problem formulation and AtomicLift guarantees to numerical examples, proofs, and concluding future directions.Source: C. Paper Organization · p. 2

II. ATOMICLIFT FOR BLIND SPARSE SPIKES DECONVOLUTION

  • The method is first presented for noiseless measurements and then extended to the noisy case.Source: §II · p. 3

A. Problem Formulation

  • The measurements contain an unavoidable scaling ambiguity, so recovery targets the point spread function and spike locations with amplitudes only up to a common scale.The spikes are modeled as delayed, scaled Dirac functions; normalized delays are sampled at a rate sufficient for unique identification when 2M ≥ BmaxTmax.Source: A. Problem Formulation · p. 3

B. AtomicLift

AtomicLift lifts blind deconvolution into linear measurements of a jointly spectrally sparse matrix and recovers it by atomic-norm minimization. Under random-subspace and spike-separation conditions, it recovers the signal and PSF up to scaling with high probability.

B. AtomicLift

  • Constraining g=Bh with known B turns the blind problem into linear measurements of the lifted matrix Z⋆=xh^T.The lifted matrix yields x and g up to scaling through its left and right singular vectors.Source: B. AtomicLift · p. 3
  • AtomicLift recovers the lifted ensemble by minimizing its atomic norm subject to the measurements, exploiting shared sinusoidal frequencies across its columns.The atomic norm has an equivalent semidefinite-programming characterization that can be computed with off-the-shelf solvers.Source: B. AtomicLift · pp. 3–4

C. Performance Guarantee of AtomicLift

  • The guarantee assumes i.i.d. subspace rows with isotropy and incoherence; isotropy implies average spectral flatness, while the analysis limits incoherence to the deterministic setting.The incoherence framework can be extended to stochastic sub-Gaussian or sub-exponential distributions, but the paper leaves that extension outside its analysis.Source: C. Performance Guarantee of AtomicLift · p. 4
  • With M≥64, i.i.d. subspace rows satisfying isotropy and incoherence, and Δ≥1/M, AtomicLift recovers Z⋆ with probability at least 1−δ.Source: C. Performance Guarantee of AtomicLift · p. 4
  • The spike signal may be deterministic with arbitrary amplitudes and orientation in the subspace, provided its separation is at least 1/M.This separation matches the condition for known-PSF total-variation recovery, while AtomicLift’s guarantee is probabilistic.Source: C. Performance Guarantee of AtomicLift · p. 4
  • The guarantee requires M on the order of O(K^2L^2) up to logarithmic factors; for fixed L, it simplifies to M/log^2 M ≳ O(K^2).The paper notes that blind spike deconvolution therefore requires more measurements.Source: C. Performance Guarantee of AtomicLift · p. 4

D. AtomicLift for noisy data

AtomicLift adapts its measurement constraint to bounded noise and localizes spikes through peaks of a dual-polynomial score. Experiments examine recovery as sample, spike, and subspace dimensions vary, while noisy data still require model-order estimation.

D. AtomicLift for noisy data

  • The noisy model treats frequency-domain samples as contaminated by additive noise bounded in 2-norm, and modifies AtomicLift's measurement constraint accordingly.The experiment models the additive noise as independent complex Gaussian samples.Source: D. AtomicLift for noisy data · p. 4, §III · p. 5
  • For noisy measurements, the algorithm imposes a constraint matched to the noise level, but the dual polynomial overestimates source count and still requires model-order estimation.The noisy example uses K = 6, N = 64, L = 3, and SNR = 15 dB.Source: D. AtomicLift for noisy data · p. 4, §III · p. 5, Figure 3 · p. 6

E. Spike Localization

  • Spike locations are identified by peaks of the 2-norm of the dual-polynomial score Q(τ).The dual problems supply the solution used to form Q(τ).Source: E. Spike Localization · p. 5

III. NUMERICAL EXPERIMENTS

  • With a known PSF, deconvolution yields a time-domain signal different from the observed convolution, whereas AtomicLift's dual polynomial demonstrates exact spike localization in the noiseless illustration.The setup uses K = 6 spikes and minimum separation Δ ≥ 1/N.Source: §III · p. 5
  • AtomicLift succeeds experimentally when N ≳ O(KL), while randomly placed spikes without the separation condition produce a less sharp phase transition.The phase-transition experiments use a normalized error threshold of 10^-3; the comparison uses separated versus randomly generated locations.Source: §III · p. 5

IV. PROOF OF MAIN THEOREM

The proof establishes exact recovery by constructing a vector-valued dual polynomial that meets the conditions for a valid dual certificate. Its coefficients are chosen through a linear system built from squared Fejér-kernel terms and their derivatives.

IV. PROOF OF MAIN THEOREM

  • AtomicLift's solution is exact if a vector-valued dual polynomial satisfies the required certificate conditions, so the proof constructs such a polynomial.The paper identifies this as a sufficient condition for unique optimality of the solution to (9).Source: §IV · p. 6

A. Construction of the dual polynomial

B. Invertibility of Γ

The proof establishes that Γ is invertible when it is sufficiently close to its expectation, using concentration and a bound on the corresponding deterministic matrix. This makes the coefficient system in the dual-polynomial construction solvable.

B. Invertibility of Γ

  • The expectation Γ̄ equals Φ ⊗ I_L, and the proof invokes a separation-conditioned invertibility result for Φ.The cited lemma assumes Δ ≥ 1/M.Source: B. Invertibility of Γ · p. 7
  • When ∥Γ − Γ̄∥ ≤ χ for 0 < χ < 0.6376, Γ is invertible on the stated event.The event has probability at least 1 − δ when the bound in (24) holds.Source: B. Invertibility of Γ · p. 7
  • The proof uses the perturbation event to establish invertibility of Γ before parameterizing the dual polynomial.The resulting inverse bound is tied to the bound on Φ^-1.Source: B. Invertibility of Γ · p. 7

C. Certifying (18b)

To certify the dual polynomial away from spike locations, the proof bounds it first on a grid and then extends the bounds across the unit interval. Combining these controls completes the dual-certificate argument for Theorem 1.

C. Certifying (18b)

  • The proof establishes uniform boundedness on grid Υgrid, extends that bound to all τ ∈ [0, 1), and finally shows ∥Q(τ)∥2 < 1 for every τ ∈ [0, 1]\T.Source: C. Certifying (18b) · p. 8
  • The grid bounds and their extension to the unit interval are combined to establish the required event with probability at least 1 − δ.The stated result holds when the associated sample-size condition is met.Source: C. Certifying (18b) · p. 9
  • The proof separates points near each spike from the rest of the interval when establishing boundedness.Each neighborhood has radius ρc/M, with ρc = 0.08245.Source: C. Certifying (18b) · p. 9
  • With Q(τ) verified as a valid dual certificate, the proof concludes Theorem 1.Source: C. Certifying (18b) · p. 9

V. CONCLUSIONS

AtomicLift uses a lifted atomic-norm formulation with the PSF constrained to a known low-dimensional subspace, and under mild conditions it recovers the spike signal and PSF up to scaling. The conclusion also identifies measurement efficiency and unused rank-one structure as directions for improvement.

  • Under mild conditions, AtomicLift provably recovers the spike signal and PSF up to a scaling ambiguity when enough measurements are available.The framework lifts the bilinear problem and minimizes the atomic norm of a jointly spectrally sparse ensemble, constraining the PSF to a known low-dimensional subspace.Source: §V · p. 9
  • Phase transitions suggest success at O(KL) measurements, versus the O(K^2L^2) guarantee up to logarithmic factors; the required count also exceeds the O(K + L) degrees of freedom.The authors suggest additional randomness assumptions on the spike signal could improve the guarantee.Source: §V · p. 9
  • AtomicLift does not exploit the rank-one property of Z⋆, motivating non-convex algorithms as a future direction.The authors point to recent work by Lee et al. as potentially informative.Source: §V · p. 9

APPENDIX A PROOF OF PROPOSITION 1

These appendix excerpts establish optimality and uniqueness in Proposition 1 and outline concentration-inequality arguments used in later proofs. The supplied proof passages provide only fragments of those later arguments.

APPENDIX A PROOF OF PROPOSITION 1

  • Strong duality establishes primal and dual optimality, and the proof concludes that the optimal solution of (9) is unique.For solutions with the same support set, the proof uses independence of the atoms in that set to establish coincidence.Source: Appendix A · pp. 9–10

APPENDIX B PROOF OF PROPOSITION 2

  • The Proposition 2 proof applies non-commutative Bernstein’s inequality, using the bound max_n |s_n| ≤ 1 and the incoherence property of F.The excerpt also invokes ∥Φ∥ ≤ 1.3623.Source: Appendix B · p. 10

APPENDIX C PROOF OF LEMMA 4

  • The Lemma 4 proof invokes Talagrand’s concentration inequality and concludes its bound for some constant c > 0.The cited inequality is stated for independent random variables taking values in a Banach space.Source: Appendix C · pp. 10–11

APPENDIX D PROOF OF LEMMA 5

The proof excerpt uses a union bound to control a probability term and completes the argument by combining lower bounds on M.

  • The proof bounds its first probability term by δ after applying the union bound and removing the conditional probability.Source: Appendix D · p. 11
  • The proof sets χ = 1/4 and completes by combining lower bounds on M and absorbing constants.Source: Appendix D · p. 11

APPENDIX E PROOF OF LEMMA 6

The supplied proof excerpts invoke a grid approximation and a Bernstein polynomial inequality in the Lemma 7 argument.

APPENDIX F PROOF OF LEMMA 7

  • Using Bernstein’s polynomial inequality, one can choose a grid of size 3CM^4/epsilon so that every τ in [0, 1] has a grid point within epsilon/(3CM^4), provided M satisfies (31).Source: Appendix F · pp. 11–12

APPENDIX G PROOF OF LEMMA 8

Lemma 10 bounds the magnitude of Q̄ away from the spike locations and controls its first and second derivatives near them; the second-derivative bound is identified as new.

  • For Δ≥1/M, Lemma 10 gives |Q̄(τ)|<0.99992 on Tfar and κ²|Q̄′′(τ)|<1.7068 and κ|Q̄′(τ)|<0.4346 on Tnear.Source: Appendix G · p. 12
  • The bound κ²|Q̄′′(τ)|<1.7068 is new and follows by rewriting [3, equation (2.27)] to bound κ²|Q̄′′R(τ)|.Source: Appendix G · p. 12
  • The proof uses a sufficiently small numerical ε and completes the sample-complexity check by retaining only the dominating terms.Source: Appendix G · p. 12
Loading 1506.02751v3…