Compressed Super-Resolution I: Maximal Rank Sum-of-Squares
share
Let μ(t) = ∑_τ∈ Sα_τδ(t-τ) denote an |S|-atomic measure defined on [0,1], satisfying min_τ≠τ'|τ - τ'|≥ |S|· n^-1. Let η(θ) = ∑_τ∈ S a_τ D_n(θ - τ) + b_τ D'_n(θ - τ), denote the polynomial obtained from the Dirichlet kernel D_n(θ) = 1/n+1∑_|k|≤ n e^2π i k θ and its derivative by solving the system {η(τ) = 1, η'(τ) = 0, ∀τ∈ S}. We provide evidence that for sufficiently large n, Δ> |S|^2 n^-1, the non negative polynomial 1 - |η(θ)|^2 which vanishes at the atoms τ∈ S, and is bounded by 1 everywhere else on the [0,1] interval, can be written as a sum-of-squares with associated Gram matrix of rank n-|S|. Unlike previous work, our approach does not rely on the Fejer-Riesz Theorem, which prevents developing intuition on the Gram matrix, but requires instead a lower bound on the singular values of a (truncated) large (O(1e10)) matrix. Despite the memory requirements which currently prevent dealing with such a matrix efficiently, we show how such lower bounds can be derived through Power iterations and convolutions with special functions for sizes up to O(1e7). We also provide numerical simulations suggesting that the spectrum remains approximately constant with the truncation size as soon as this size is larger than 100.
READ FULL TEXT