# Sparse non-negative super-resolution — simplified and stabilised

Eftekhari, A
Tanner, J
Thompson, A
Tyagi, H

13 August 2019

## Journal:

Applied and Computational Harmonic Analysis

## Last Updated:

2020-01-21T17:15:05.82+00:00

## DOI:

10.1016/j.acha.2019.08.004

## abstract:

<p style="text-align:justify;"> The convolution of a discrete measure,$<mi is="true">x</mi><mo is="true" linebreak="goodbreak" linebreakstyle="after">=</mo><msubsup is="true"><mrow is="true"><mo is="true">∑</mo></mrow><mrow is="true"><mi is="true">i</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">=</mo><mn is="true">1</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msubsup><msub is="true"><mrow is="true"><mi is="true">a</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><msub is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><msub is="true"><mrow is="true"><mi is="true">t</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub></mrow></msub>$ , with a local window function,$<mi is="true">ϕ</mi><mo is="true" stretchy="false">(</mo><mi is="true">s</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><mi is="true">t</mi><mo is="true" stretchy="false">)</mo>$, is a common model for a measurement device whose resolution is substantially lower than that of the objects being observed. Super-resolution concerns localising the point sources $<msubsup is="true"><mrow is="true"><mo is="true" stretchy="false">{</mo><msub is="true"><mrow is="true"><mi is="true">a</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">t</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true" stretchy="false">}</mo></mrow><mrow is="true"><mi is="true">i</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">=</mo><mn is="true">1</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msubsup>$ with an accuracy beyond the essential support of $<mi is="true">ϕ</mi><mo is="true" stretchy="false">(</mo><mi is="true">s</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><mi is="true">t</mi><mo is="true" stretchy="false">)</mo>$, typically from m samples $<mi is="true">y</mi><mo is="true" stretchy="false">(</mo><msub is="true"><mrow is="true"><mi is="true">s</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow></msub><mo is="true" stretchy="false">)</mo><mo is="true" linebreak="goodbreak" linebreakstyle="after">=</mo><msubsup is="true"><mrow is="true"><mo is="true">∑</mo></mrow><mrow is="true"><mi is="true">i</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">=</mo><mn is="true">1</mn></mrow><mrow is="true"><mi is="true">k</mi></mrow></msubsup><msub is="true"><mrow is="true"><mi is="true">a</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mi is="true">ϕ</mi><mo is="true" stretchy="false">(</mo><msub is="true"><mrow is="true"><mi is="true">s</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow></msub><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><msub is="true"><mrow is="true"><mi is="true">t</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true" stretchy="false">)</mo><mo is="true" linebreak="goodbreak" linebreakstyle="after">+</mo><msub is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow></msub>$, where $<msub is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow></msub>$ indicates an inexactness in the sample value. We consider the setting of x being non-negative and seek to characterise all non-negative measures approximately consistent with the samples. We first show that x is the unique non-negative measure consistent with the samples provided the samples are exact, i.e. $<msub is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow></msub><mo is="true" linebreak="goodbreak" linebreakstyle="after">=</mo><mn is="true">0</mn>$, $<mi is="true">m</mi><mo is="true">≥</mo><mn is="true">2</mn><mi is="true">k</mi><mo is="true" linebreak="goodbreak" linebreakstyle="after">+</mo><mn is="true">1</mn>$ samples are available, and $<mi is="true">ϕ</mi><mo is="true" stretchy="false">(</mo><mi is="true">s</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><mi is="true">t</mi><mo is="true" stretchy="false">)</mo>$ generates a Chebyshev system. This is independent of how close the sample locations are and does not rely on any regulariser beyond non-negativity; as such, it extends and clarifies the work by Schiebinger et al. in [1] and De Castro et al. in [2], who achieve the same results but require a total variation regulariser, which we show is unnecessary.<br/> Moreover, we characterise non-negative solutions $<mover accent="true" is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mo is="true" stretchy="false">ˆ</mo></mrow></mover>$ consistent with the samples within the bound $<msubsup is="true"><mrow is="true"><mo is="true">∑</mo></mrow><mrow is="true"><mi is="true">j</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">=</mo><mn is="true">1</mn></mrow><mrow is="true"><mi is="true">m</mi></mrow></msubsup><msubsup is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mi is="true">j</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msubsup><mo is="true">≤</mo><msup is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mn is="true">2</mn></mrow></msup>$. Any such non-negative measure is within $<mi is="true" mathvariant="script">O</mi><mo is="true" stretchy="false">(</mo><msup is="true"><mrow is="true"><mi is="true">δ</mi></mrow><mrow is="true"><mn is="true">1</mn><mo is="true" stretchy="false">/</mo><mn is="true">7</mn></mrow></msup><mo is="true" stretchy="false">)</mo>$ of the discrete measure x generating the samples in the generalised Wasserstein distance. Similarly, we show using somewhat different techniques that the integrals of $<mover accent="true" is="true"><mrow is="true"><mi is="true">x</mi></mrow><mrow is="true"><mo is="true" stretchy="false">ˆ</mo></mrow></mover>$ and x over $<mo is="true" stretchy="false">(</mo><msub is="true"><mrow is="true"><mi is="true">t</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><mi is="true">ϵ</mi><mo is="true">,</mo><msub is="true"><mrow is="true"><mi is="true">t</mi></mrow><mrow is="true"><mi is="true">i</mi></mrow></msub><mo is="true" linebreak="badbreak" linebreakstyle="after">+</mo><mi is="true">ϵ</mi><mo is="true" stretchy="false">)</mo>$ are similarly close, converging to one another as ϵ and δ approach zero. We also show how to make these general results, for windows that form a Chebyshev system, precise for the case of $<mi is="true">ϕ</mi><mo is="true" stretchy="false">(</mo><mi is="true">s</mi><mo is="true" linebreak="badbreak" linebreakstyle="after">−</mo><mi is="true">t</mi><mo is="true" stretchy="false">)</mo>$ being a Gaussian window. The main innovation of these results is that non-negativity alone is sufficient to localise point sources beyond the essential sensor resolution and that, while regularisers such as total variation might be particularly effective, they are not required in the non-negative setting. </p>

1039749

Not Submitted

Journal Article