Super-resolution is generally referred to as the task of recovering fine details from coarse information. Motivated by applications such as single-molecule imaging, radar imaging, etc., we consider parameter estimation of complex exponentials from their modulations with unknown waveforms, allowing for non-stationary blind super-resolution. This problem, however, is ill-posed since both the parameters associated with the complex exponentials and the modulating waveforms are unknown. To alleviate this, we assume that the unknown waveforms live in a common low-dimensional subspace. Using a lifting trick, we recast the blind super-resolution problem as a structured low-rank matrix recovery problem. Atomic norm minimization is then used to enforce the structured low-rankness, and is reformulated as a semidefinite program that is solvable in polynomial time. We show that, up to scaling ambiguities, exact recovery of both of the complex exponential parameters and the unknown waveforms is possible when the waveform subspace is random and the number of measurements is proportional to the number of degrees of freedom in the problem. Numerical simulations support our theoretical findings, showing that non-stationary blind super-resolution using atomic norm minimization is possible.
Recovering structured models (e.g., sparse or group-sparse vectors, low-rank matrices) given a few linear observations have been well-studied recently. In various applications in signal processing and machine learning, the model of interest is structured in several ways, for example, a matrix that is simultaneously sparse and low rank. Often norms that promote the individual structures are known, and allow for recovery using an orderwise optimal number of measurements (e.g., @math norm for sparsity, nuclear norm for matrix rank). Hence, it is reasonable to minimize a combination of such norms. We show that, surprisingly, using multiobjective optimization with these norms can do no better, orderwise, than exploiting only one of the structures, thus revealing a fundamental limitation in sample complexity. This result suggests that to fully exploit the multiple structures, we need an entirely new convex relaxation. Further, specializing our results to the case of sparse and low-rank matrices, we show that a nonconvex formulation recovers the model from very few measurements (on the order of the degrees of freedom), whereas the convex problem combining the @math and nuclear norms requires many more measurements, illustrating a gap between the performance of the convex and nonconvex recovery problems. Our framework applies to arbitrary structure-inducing norms as well as to a wide range of measurement ensembles. This allows us to give sample complexity bounds for problems such as sparse phase retrieval and low-rank tensor completion.