Compressed Super-Resolution I: Maximal Rank Sum-of-Squares

Let $μ (t) = \sum_{τ \in S} α_{τ} δ (t - τ)$ denote an $∣ S ∣$ -atomic measure defined on $[0, 1]$ , satisfying $\min_{\tau\neq \tau’}|\tau

\tau’|\geq |S|\cdot n^{-1} $. L e t$ \eta(\theta) = \sum_{\tau\in S} a_\tau D_n(\theta - \tau) + b_\tau D’n(\theta - \tau)$, denote the polynomial obtained from the Dirichlet kernel $D_n(\theta) = \frac{1}{n+1}\sum{|k|\leq n} e^{2\pi i k \theta} $a n d i t s d e r i v a t i v e b y s o l v i n g t h e s y s t e m$ \left{\eta(\tau) = 1, \eta’(\tau) = 0,; \forall \tau \in S\right}$. We provide evidence that for sufficiently large $n$ , $Δ > ∣ S ∣^{2} n^{- 1}$ , the non negative polynomial $1 - ∣ η (θ) ∣^{2}$ which vanishes at the atoms $τ \in 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 (1 e 10)$ ) 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 (1 e 7)$ . 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$ .

Let $μ (t) = \sum_{τ \in S} α_{τ} δ (t - τ)$ denote an $∣ S ∣$ -atomic measure defined on $[0, 1]$ , satisfying $\min_{\tau\neq \tau’}|\tau

\tau’|\geq |S|\cdot n^{-1} $. L e t$ \eta(\theta) = \sum_{\tau\in S} a_\tau D_n(\theta - \tau) + b_\tau D’n(\theta - \tau)$, denote the polynomial obtained from the Dirichlet kernel $D_n(\theta) = \frac{1}{n+1}\sum{|k|\leq n} e^{2\pi i k \theta} $a n d i t s d e r i v a t i v e b y s o l v i n g t h e s y s t e m$ \left{\eta(\tau) = 1, \eta’(\tau) = 0,; \forall \tau \in S\right}$. We provide evidence that for sufficiently large $n$ , $Δ > ∣ S ∣^{2} n^{- 1}$ , the non negative polynomial $1 - ∣ η (θ) ∣^{2}$ which vanishes at the atoms $τ \in 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 (1 e 10)$ ) 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 (1 e 7)$ . 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$ .

文献摘要