Guaranteed Blind Sparse Spikes Deconvolution via Lifting and Convex Optimization

Abstract

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.

References in corpus (5)

• Self-Calibration and Biconvex Compressive Sensing
• Super-resolution on the Sphere using Convex Optimization
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models
• Identifiability in Blind Deconvolution with Subspace or Sparsity Constraints
• Stable Separation and Super-Resolution of Mixture Models

Cited by in corpus (32)

• An overview of low-rank matrix recovery from incomplete observations
• Implicit Regularization in Nonconvex Statistical Estimation: Gradient Descent Converges Linearly for Phase Retrieval, Matrix Completion, and Blind Deconvolution
• Harnessing Sparsity over the Continuum: Atomic Norm Minimization for Super Resolution
• A New Atomic Norm for DOA Estimation With Gain-Phase Errors
• Gridless DOA Estimation with Multiple Frequencies
• Interference Removal for Radar/Communication Co-existence: the Random Scattering Case
• Blind Image Deblurring with Unknown Kernel Size and Substantial Noise
• Mathematical Theory of Atomic Norm Denoising In Blind Two-Dimensional Super-Resolution (Extended Version)
• Blind Deconvolution Meets Blind Demixing: Algorithms and Performance Bounds
• Two-Dimensional Super-Resolution via Convex Relaxation
• A convex variational model for learning convolutional image atoms from incomplete data
• Simultaneous Sparse Recovery and Blind Demodulation
• Blind Goal-Oriented Massive Access for Future Wireless Networks
• Autocorrelation analysis for cryo-EM with sparsity constraints: Improved sample complexity and projection-based algorithms
• Compressed Super-Resolution of Positive Sources
• Blind Super-resolution of Point Sources via Projected Gradient Descent
• Blind Two-Dimensional Super Resolution in Multiple Input Single Output Linear Systems
• Structured Local Optima in Sparse Blind Deconvolution
• Support Recovery for Sparse Signals with Unknown Non-stationary Modulation
• Timely and Painless Breakups: Off-the-grid Blind Message Recovery and Users' Demixing
• Sensor Calibration for Off-the-Grid Spectral Estimation
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Short-and-Sparse Deconvolution -- A Geometric Approach
• Convex and Nonconvex Optimization Are Both Minimax-Optimal for Noisy Blind Deconvolution under Random Designs
• Multichannel Sparse Blind Deconvolution on the Sphere
• Super-Resolution of Complex Exponentials from Modulations with Unknown Waveforms
• On the Sample Complexity of Super-Resolution Radar
• On the Global Geometry of Sphere-Constrained Sparse Blind Deconvolution
• Atomic Norm Denoising for Complex Exponentials with Unknown Waveform Modulations
• Signal Reconstruction using Blind Super-resolution with Arbitrary Sampling
• A Non-Convex Optimization Technique for Sparse Blind Deconvolution -- Initialization Aspects and Error Reduction Properties
• Fast and Accurate Amplitude Demodulation of Wideband Signals