Multivariate Super-Resolution without Separation Bakytzhan Kurmanbek and Elina Robeva

2025-05-02 0 0 721.7KB 21 页 10玖币

侵权投诉

Multivariate Super-Resolution without

Separation

Bakytzhan Kurmanbek and Elina Robeva

Department of Mathematics, The University of British Columbia, 1984 Mathematics Rd, Vancouver, BC V6T 1Z2

In this paper we study the high-dimensional super-resolution imaging problem. Here

we are given an image of a number of point sources of light whose locations and in-

tensities are unknown. The image is pixelized and is blurred by a known point-spread

function arising from the imaging device. We encode the unknown point sources and

their intensities via a nonnegative measure and we propose a convex optimization pro-

gram to ﬁnd it. Assuming the device’s point-spread function is componentwise decom-

posable, we show that the optimal solution is the true measure in the noiseless case, and

it approximates the true measure well in the noisy case with respect to the generalized

Wasserstein distance. Our main assumption is that the components of the point-spread

function form a Tchebychev system (T-system) in the noiseless case and a T∗-system

in the noisy case, mild conditions that are satisﬁed by Gaussian point-spread functions.

Our work is a generalization to all dimensions of the work (Eftekhari, Bendory, & Tang,

2021) where the same analysis is carried out in 2 dimensions. We resolve an open prob-

lem posed in (Schiebinger, Robeva, & Recht, 2018) in the case when the point-spread

function decomposes.

Keywords. Super-resolution, Tchebychev systems, Generalized-Wasserstein distance, Exact solu-

tions, Bounds for a recovery error

1. Introduction

In the super-resolution imaging problem we are given the output of an imaging device depicting

often very small or very distant objects. As a result, we observe a pixelized, blurred, and noisy

image, and we aim to recover the true picture by removing the blur and increasing the resolution.

Solving this problem is essential in many applied sciences such as neuroscience (Betzig et al.,

2006; Hess, Girirajan, & Mason, 2006; Rust, Bates, & Zhuang, 2006; Ekanadham, Tranchina, &

Simoncelli, 2011; Evanko, 2009; Tur, Eldar, & Friedman, 2011), geophysics (Khaidukov, Landa,

& Moser, 2004), and astronomy (Puschmann & Kneer, 2005). Knowing the blurring (point-spread)

function is usually crucial in achieving accurate results.

2020 Mathematics Subject Classiﬁcation: 65K10, 15A30

arXiv:2210.09979v1 [math.OC] 18 Oct 2022

Due to the complexity of the super-resolution imaging problem it is difﬁcult to distinguish point

sources of light that are very close to one another. As a result many of the existing methods can be

proved to work only under a minimum separation condition between the point sources of light even

as the amount of noise approaches zero (Bendory, Dekel, & Feuer, 2016; Candès & Fernandez-

Granda, 2014; Morgenshtern & Candès, 2015).

It was ﬁrst shown in the 1-dimensional case (Schiebinger et al., 2018) that if no noise is present,

then no minimum separation condition is required provided that the point-spread function satisﬁes

a Tchebychev system (Karlin & Studden, 1966) condition. This work was simpliﬁed and extended

to the noisy case in (Eftekhari, Tanner, Thompson, Toader, & Tyagi, 2021), and then to the 2-

dimensional and possibly noisy case in (Eftekhari, Bendory, & Tang, 2021). In the present paper

we generalize these results to the case of any dimension both with or without noise.

A lot of the theoretical work on super-resolution imaging uses concepts and techniques from

compressed sensing (Donoho, 2006; Candès, Romberg, & Tao, 2006; Candés & Tao, 2005), by

minimizing total variation over measures (Candès & Fernandez-Granda, 2014; Tang, Bhaskar, Shah,

& Recht, 2013; Fyhn, Dadkhahi, & Duarte, 2013; Demanet, Needell, & Nguyen, 2013; Duval &

Peyré, 2015; Denoyelle, Duval, & Peyré, 2017; Azais, De Castro, & Gamboa, 2015; Bendory et al.,

2016). In this manuscript, assuming that we have Ksource points in the exact image, we show that

(2K+1)dobservations are enough to recover the image. In the noiseless case, we recover the image

exactly, and in the noisy case, we provide an error bound in Generalized-Wasserstein distance.

Mathematical setup

Let µbe a Borel measure supported on Id= [0,1]d. This measure will represent the true image that

we are trying to reconstruct. Given an image represented by the measure µ, an imaging device with

(a known) point-spread function Ψ:Rd→Rconvolves each individual point source of light with

the point-spread function Ψresulting in a new image which, at a point (x1,...,xd)equals (up to a

noise term)

ZId

Ψ(x1−t1,...,xd−td)µ[d(t1,...,td)].

We will later assume that µis a sparse measure, i.e., µ=∑K

k=1akδθk, where θk= (t(k)

1,...,t(k)

d)∈

Rdare the point source locations, and ak>0 are their intensities. In this case, the observed image

at a point (x1,...,xd)equals

∑

k=1

akΨ(x1−t(k)

1,...,xd−t(k)

d).

We will also assume that the point-spread function Ψlies in the tensor product model, i.e.,

Ψ(ξ1,··· ,ξd) = ψ(1)(ξ1)···ψ(d)(ξd),(1.1)

where ψ(1),...,ψ(d)are continuous real-valued functions on I.

This is a widely used model in imaging as noted in (Eftekhari, Bendory, & Tang, 2021) which

studies the 2-dimensional case and assumes the 2-dimensional point-spread function satisﬁes (1.1).

It is also often the case that the functions ψ(j)are copies of a function ψ.

Suppose that the image we observe is of size M×···×M(dtimes) with coordinates {yi1,···,id}M

ij=1

measured on an M× ··· × M(dtimes) grid {x(1)

1,...,x(1)

M} × ··· × {x(d)

1,...,x(d)

M}, which can be

thought of as consisting of the pixels. Then,

yi1,···,id≈ZIdψ(1)(x(1)

i1−t1)···ψ(d)(x(d)

id−td)µ[d(t1,··· ,td)],(1.2)

where we have noted the possibility of noise being present. For notational convenience, we denote

ψ(i)

m(ti) = ψ(i)(x(i)

mi−ti)

for every i∈[d]and m∈[M]. More speciﬁcally, we will assume that

∑

i1,···,id=1yi1,···,id−ZIdψ(1)

i1(t1)···ψ(d)

id(td)µ[d(t1,··· ,td)]

2≤δ2(1.3)

where δ≥0 reﬂects an additive noise model.

We may rewrite (1.3) more compactly as



y−ZIdψ(1)

[M](t1)⊗ · ·· ⊗ ψ(d)

[M](td)µ[d(t1,··· ,td)]



F≤δ(1.4)

where k · kFstands for the Frobenious norm (of a tensor), and ψ(j)

[M](tj) = (ψ(j)

1(tj),...,ψ(j)

M(tj))T.

Summary of results

To recover µ, we propose to use the convex feasibility program

Find a nonnegative Borel measure µon Idsuch that



y−ZIdψ(1)

[M](t1)⊗ · ·· ⊗ ψ(d)

[M](td)µ[d(t1,··· ,td)]



F≤δ0(1.5)

for some δ0≥δ. Note that this program is grid-free and has no regularity other than the non-

negativity of the Borel measure compared to other methods where the measure’s total variation is

assumed to be constant (Candès & Fernandez-Granda, 2014; Tang et al., 2013; Fyhn et al., 2013).

The dual program to the program (1.5) can be used to ﬁnd the unknown point sources and their

amplitudes. When there is no noise, i.e., δ0=0, we show that the solution of (1.5) is exact and

unique under certain conditions for the component functions of the point spread function. In the

presence of noise, i.e. δ>0, we show that the solution of program (1.5) well approximates the true

measure, by showing an upper bound for the recovery error.

We generalize the main results obtained in (Eftekhari, Bendory, & Tang, 2021) from 2 to higher

dimensions. We address the noiseless case in Section 2. We show in Theorem 2.2 that if the true

measure µconsists of Kpoint sources, then the unique solution of program (1.5) is the true measure

µ. Here we assume that the translates of the component-wise functions ψ(j)form Tchebychev sys-

tems and that M≥2K+1, where our observations y∈(RM)Nd. Moreover, no minimum separation

between the point sources is required, and, therefore, program (1.5) recovers correct solution no

matter how close to each other the point sources may be.

We address the noisy case in Section 3. We assume the true measure is an arbitrary measure

µsupported on Idand the noise level is δ>0. Theorem 3.7 then shows that if the translates of

the component-wise functions form T∗-systems, and given enough observations, the solution of

program (1.5) well-approximates the true image measure in Generalized-Wasserstein distance. We

use two auxiliary Lemmas 3.8 and 3.9, which utilize the existence of dual certiﬁcates Qand Q0, to

bound the errors away from the support and near the support. The existence of such dual certiﬁcates

shown in Propositions 3.11 and 3.12 is a generalization to all dimensions of Propositions 21 and

22 in (Eftekhari, Bendory, & Tang, 2021) which address this problem in 2 dimensions. We give an

upper bound on the recovery error in terms of the noise level and the minimum separation between

the points sources (see Theorem 3.7).

The T-system and T∗-system assumptions have already been shown to hold for translated copies

of Gaussian functions (Eftekhari, Bendory, & Tang, 2021; Eftekhari, Tanner, et al., 2021). There-

fore, all of our results hold for Gaussian point spread functions that satisfy the decomposability

criterion (1.1).

The proofs of all theorems, lemmas, and propositions can be found in the appendices.

2. The noiseless case

Let µbe a nonnegative atomic measure

µ=

∑

k=1

akδθk,ak>0

with K≥1 impulses located at Θ={θk}K

k=1⊂interior(Id)with positive amplitudes {ak}K

k=1, where

θk= (t(k)

1,...,t(k)

d)∈Rd. Consider the case where there is no imaging noise (δ=0). In this case,

we collect noise-free measurements

y=ZIdψ(1)

[M](t1)···ψ(d)

[M](td)µ[d(t1,··· ,td)] ∈(RM)Nd.

To understand when solving program (1.5) with δ0=0 successfully recovers the true measure µ,

recall the concept of a T-system (Karlin & Studden, 1966):

Deﬁnition 2.1. Several real-valued and continuous functions {φj}m

j=1form a Tchebychev system

(or T-system) on the interval Iif the m×mmatrix [φj(τi)]m

i,j=1is nonsingular for any increasing

sequence {τi}m

i=1⊂I.

Many sets of functions, such as the monomials 1,t,t2,...,tm−1as well as shifted translates of

Gaussian functions, are known to form Tsystems. Given a T-system {φm}M

m=1, any linear combi-

nation of the elements ∑m

i=1biφiis often called a "polynomial", and, like real polynomials of degree

m−1, it has at most m−1 zeros on the real line. We will use some of the properties of T-systems

to form a dual polynomial certiﬁcate for our program (1.5), which will be a linear combination

of shiften copies of the point-spread function. The dual polynomial certiﬁcate will be the unique

solution of the dual program to (1.5) and will correspond to the unique solution to the original

program (1.5). The construction of a dual certiﬁcate is a classical technique used in compressed

sensing (Candès et al., 2006; Fuchs, 2005).

Theorem 2.2 (Noiseless measurements).Let µbe a K-sparse nonnegative measure supported on

interior(Id). Let also M ≥2K+1, and suppose that the functions {ψ(i)

mi}M

mi=1form a T-system on I

for every i =1,...,d. Lastly, consider the image y ∈(RM)Ndof the measure µin (1.4) with noise

level δ=0. Then, µis the unique solution of program (1.5) with δ0=0.

In other words, given at least (2K+1)dsamples from an image consisting of Kpoint sources,

program (1.5) recovers the Kpoint sources exactly. Here, we require the component-wise func-

tions {ψ(i)

mi}M

mi=1to form a T-system for every i=1,...,d. Lemmas 2.3 and 2.4 below establish

Theorem 2.2. Their proofs are located in Appendices A and B, respectively.

Lemma 2.3 (Uniqueness of the measure).Let µbe a K-sparse nonnegative atomic measure sup-

ported on Θ⊂interior(Id). Then, µis the unique solution of program (1.5) with δ0=0if

• the Md×K matrix [ψ(1)

i1(t(k)

1)···ψ(d)

id(t(k)

d)]i1,···,id=M,k=K

i1,···,id,k=1has full rank, and

• there exist real coefﬁcients {bi1,···,id}M

i1,···,id=1and a polynomial

Q(t1,··· ,td) =

∑

i1,···,id=1

bi1,···,idψ(1)

i1(t1)···ψ(d)

id(td)

such that Q is nonnegative on interior(Id)and vanishes only on Θ.

Our next lemma establishes the second one of the above conditions, namely the existence of a

dual polynomial certiﬁcate for our program.

Lemma 2.4 (Existence of a dual polynomial certiﬁcate).Let µbe a K-sparse non-negative atomic

measure supported on interior(Id). For M ≥2K+1, suppose that {ψ(i)

mi}M

mi=1form a T-system on I

for i =1,...,d. Then the dual certiﬁcate Q in Lemma 2.3 exists.

Combining these two lemmas, we see that the true sparse measure µis the unique solution to our

optimization problem, which proves Theorem 2.2.

3. The noisy case

In this section, we present our generalized results for the noisy case. Since the measure in this case,

might not be atomic, we use atomic measures to approximate both true measure and the solution of

program (1.5). We use the Generalized-Wasserstein distance for the recovery error. Before stating

the main Theorem 3.7, we introduce several necessary concepts.

Deﬁnition 3.1 (Separation).For an atomic measure µsupported on Θ={θk}K

k=1={(t(1)

k,...,t(d)

k)})K

k=1,

let sep(µ)denote the minimum separation between all impulses in µand the boundary of Id. That

is, sep(µ), is the largest number vsuch that

v≤ |t(i)

k−t(i)

l|,∀k6=l;k,l∈[K],i∈[d]

v≤ |t(i)

k−0|,v≤ |t(i)

k−1| ∀ i∈[d],k∈[K].

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

MultivariateSuper-ResolutionwithoutSeparationBakytzhanKurmanbekandElinaRobevaDepartmentofMathematics,TheUniversityofBritishColumbia,1984MathematicsRd,Vancouver,BCV6T1Z2Inthispaperwestudythehigh-dimensionalsuper-resolutionimagingproblem.Herewearegivenanimageofanumberofpointsourcesoflightwhoselocation...

展开>> 收起<<

Multivariate Super-Resolution without Separation Bakytzhan Kurmanbek and Elina Robeva.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Multivariate Super-Resolution without Separation Bakytzhan Kurmanbek and Elina Robeva

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: