# Uncovering the limits of uniqueness in sampled Gabor phase retrieval: A
dense set of counterexamples in $L^{2}(\mathbb{R})$

Rima Alaifari  ETH Zürich
Department of Mathematics
Email<EMAIL_ADDRESS>Francesca Bartolucci  TU Delft
Institute of Applied Mathematics
Email<EMAIL_ADDRESS>Matthias Wellershoff  University of Maryland
Department of Mathematics
Email<EMAIL_ADDRESS>
###### Abstract

Sampled Gabor phase retrieval — the problem of recovering a square-integrable
signal from the magnitude of its Gabor transform sampled on a lattice — is a
fundamental problem in signal processing, with important applications in areas
such as imaging and audio processing. Recently, a classification of square-
integrable signals which are not phase retrievable from Gabor measurements on
parallel lines has been presented. This classification was used to exhibit a
family of counterexamples to uniqueness in sampled Gabor phase retrieval.
Here, we show that the set of counterexamples to uniqueness in sampled Gabor
phase retrieval is dense in $L^{2}(\mathbb{R})$, but is not equal to the whole
of $L^{2}(\mathbb{R})$ in general. Overall, our work contributes to a better
understanding of the fundamental limits of sampled Gabor phase retrieval.

###### Index Terms:

Phase retrieval, Gabor transform, sampling result

##  I Introduction

Phase retrieval is a term broadly applied to problems in which information
about complex phase needs to be inferred from data. The origins of phase
retrieval can be traced back to the years 1915 – 1929 when W. H. Bragg and W.
L. Bragg (among others) used X-ray diffraction images of crystals in order to
illuminate their atomic structure [1, 2, 3, 4, 5]. Since then phase retrieval
has found applications in various fields such as crystallography, electron
microscopy and astronomy [6, 7, 8].

Gabor phase retrieval refers to problems in which signals $f\in
L^{2}(\mathbb{R})$ have to be reconstructed from magnitudes of their _Gabor
transform_ ,

$\mathcal{G}f(x,\omega):=2^{1/4}\int_{\mathbb{R}}f(t)\mathrm{e}^{-\pi(t-x)^{2}}\mathrm{e}^{-2\pi\mathrm{i}t\omega}\,\mathrm{d}t,\quad(x,\omega)\in\mathbb{R}^{2}.$

It has been used in a range of audio processing tasks, including the phase
vocoder for time-stretching and pitch-shifting of audio signals [9], as well
as speech enhancement and source separation [10].

In this contribution, we will specifically focus on the _sampled Gabor phase
retrieval_ problem which is the recovery of signals $f$ from the magnitude
measurements $(\lvert\mathcal{G}f(x,\omega)\rvert)_{(x,\omega)\in\Lambda}$
where $\Lambda\subset\mathbb{R}^{2}$ is a lattice111A _lattice_
$\Lambda\subset\mathbb{R}^{2}$ is a discrete subset of the time-frequency
plane that can be written as $L\mathbb{Z}^{k}$ where $L\in\mathbb{R}^{2\times
k}$ is a matrix with linearly independent columns and $k\in\\{1,2\\}$.. We
focus on this sampling problem because magnitude information on the entire
time-frequency plane $\mathbb{R}^{2}$ is not available in practice. Instead,
only a finite number of measurements are stored and inferences are made based
on them. We consider the sampled setup proposed above as a natural and useful
compromise between the fully continuous case, where no sampling occurs, and
the fully discrete case, where the signals are finite-dimensional vectors.

###  I-A Prior arts: Counterexamples to uniqueness in sampled Gabor phase
retrieval

In the following, we will focus on counterexamples to uniqueness in sampled
Gabor phase retrieval; i.e. signals whose Gabor transform magnitudes agree on
a lattice but which are fundamentally different from each other. Before
introducing the concept of a counterexample rigorously, we need to emphasise
that there is one ever-present ambiguity in Gabor phase retrieval: the global
phase ambiguity. Two signals $f,g\in L^{2}(\mathbb{R})$ are said to _agree up
to global phase_ if they are equivalent with respect to the relation

$f\sim g:\iff f=\mathrm{e}^{\mathrm{i}\alpha}g,\mbox{ for some
}\alpha\in\mathbb{R}.$

Notably, $f\sim g$ implies $\lvert\mathcal{G}f\rvert=\lvert\mathcal{G}g\rvert$
such that signals which agree up to global phase cannot be recovered from
Gabor transform magnitudes. With this in mind, we define the set of
counterexamples.

######  Definition I.1 (Counterexamples).

Let $\Lambda\subset\mathbb{R}^{2}$. The _set of counterexamples_ to uniqueness
in Gabor phase retrieval on $\Lambda$ is defined by

$\mathfrak{C}(\Lambda):=\left\\{f\in
L^{2}(\mathbb{R})\,\middle|\,\lvert\mathcal{G}f\rvert=\lvert\mathcal{G}g\rvert\mbox{
on }\Lambda\mbox{ and }f\not\sim g,\right.\\\ \left.\mbox{for some }g\in
L^{2}(\mathbb{R})\right\\}.$

An element $f\in\mathfrak{C}(\Lambda)$ is called a _counterexample_ to
uniqueness in sampled Gabor phase retrieval on $\Lambda$.

Counterexamples to uniqueness in sampled Gabor phase retrieval are interesting
for two reasons. First, they allow us to better understand the fundamental
limits of sampled Gabor phase retrieval, which in turn can guide future
research towards achieving uniqueness. In addition, they offer the opportunity
to explore the potential relationship between uniqueness and stability in
phase retrieval [11].

Let us briefly summarise the recent research on counterexamples in Gabor phase
retrieval. The relationship between the Gabor transform and the Bargmann
transform (which is described in more detail in Section II) allows for the
relation of the Gabor phase retrieval problem to a phase retrieval problem for
entire functions. This was realised in [12, 13]. Then, following these ideas,
a characterisation of all entire functions of exponential-type whose
magnitudes agree on any set of infinitely many equidistant parallel lines was
proven in [14].

Using this characterisation and noting that all lattices are a subset of some
set of infinitely many equidistant parallel lines, it becomes possible to
construct various types of counterexamples. This idea has been applied in [15]
to construct explicit counterexamples to uniqueness in sampled Gabor phase
retrieval on any lattice. (See [14] for a more in-depth explanation.) An
extension of the results in [15] has appeared in [16].

###  I-B Our contributions

In this contribution, we show that the set of counterexamples
$\mathfrak{C}(\Lambda)$ is dense in $L^{2}(\mathbb{R})$ when
$\Lambda\subset\mathbb{R}^{2}$ is a lattice or a set of equidistant parallel
lines. We also show that the Gaussian is _not_ a counterexample for quadratic
lattices, $\Lambda=a\mathbb{Z}^{2}$, with $a\in(0,1)$. Therefore, _the set of
counterexamples is dense but not equal to the whole of $L^{2}(\mathbb{R})$ in
general_. We prove these two results by using the connection between the
Bargmann transform and the Gabor transform as well as some classical results
from complex analysis.

Note that this contribution is a condensed and modified version of the section
on the fragility of uniqueness in sampled Gabor phase retrieval in the larger
manuscript [11]. Apart from a comprehensive treatment of counterexamples, the
larger manuscript also discusses the stability of Gabor phase retrieval as
well as its potential connection with uniqueness in sampled Gabor phase
retrieval. Here, we focus specifically on showing that the counterexamples are
dense.

### Notation

Rotation by $\theta\in\mathbb{R}$ on $\mathbb{R}^{2}$ is denoted by
$\operatorname{R}_{\theta}:\mathbb{R}^{2}\to\mathbb{R}^{2}$; in matrix
notation, we have

$R_{\theta}=\begin{pmatrix}\cos\theta&-\sin\theta\\\
\sin\theta&\cos\theta\end{pmatrix}.$

Translation by $x\in\mathbb{R}$ on $L^{p}(\mathbb{R})$, where
$p\in[1,\infty]$, is denoted by $\operatorname{T}_{x}:L^{p}(\mathbb{R})\to
L^{p}(\mathbb{R})$; i.e.

$\operatorname{T}_{x}f(t)=f(t-x),\qquad t\in\mathbb{R},$

for $f\in L^{p}(\mathbb{R})$. Finally, the normalised Gaussian is denoted by

$\varphi(t)=2^{1/4}\mathrm{e}^{-\pi t^{2}},\qquad t\in\mathbb{R}.$

##  II The relation between the Bargmann and Gabor transform

As mentioned before, we will make use of the well-known connection between the
Bargmann transform and the Gabor transform [17]. The _Fock space_
$\mathcal{F}^{2}(\mathbb{C})$ is the Hilbert space of all entire functions for
which the norm induced by the inner product

$(F,G)_{\mathcal{F}}:=\int_{\mathbb{C}}F(z)\overline{G(z)}\mathrm{e}^{-\pi\lvert
z\rvert^{2}}\,\mathrm{d}z$

is finite. The _Bargmann transform_
$\mathcal{B}:L^{2}(\mathbb{R})\to\mathcal{F}^{2}(\mathbb{C})$,

$\mathcal{B}f(z):=2^{1/4}\int_{\mathbb{R}}f(t)\mathrm{e}^{2\pi tz-\pi
t^{2}-\frac{\pi}{2}z^{2}}\,\mathrm{d}t,\quad z\in\mathbb{C},$

acts as an isomorphism between $L^{2}(\mathbb{R})$ and
$\mathcal{F}^{2}(\mathbb{C})$. It is related to the Gabor transform by the
formula

$\mathcal{G}f(x,-\omega)=\mathrm{e}^{\pi\mathrm{i}x\omega}\mathcal{B}f(x+\mathrm{i}\omega)\mathrm{e}^{-\frac{\pi}{2}(x^{2}+\omega^{2})},$
(1)

for $(x,\omega)\in\mathbb{R}^{2}$. It is the formula above that allows us to
relate the Gabor phase retrieval problem to a phase retrieval problem for
entire functions. We are going to use this relation in the sequel.

##  III The set of counterexamples is dense

In this section, we show that the set of counterexamples
$\mathfrak{C}(\Lambda)$ is dense in $L^{2}(\mathbb{R})$ when
$\Lambda\subset\mathbb{R}^{2}$ is a lattice or a set of equidistant parallel
lines. Our strategy will be to design entire functions
$H^{\pm}_{\delta}\in\mathcal{F}^{2}(\mathbb{C})$ which converge to a constant
as $\delta\to 0$, do not agree up to global phase and still satisfy $\lvert
H^{+}_{\delta}\rvert=\lvert H^{-}_{\delta}\rvert$ on
$\mathbb{R}+\mathrm{i}a\mathbb{Z}$. Once these entire functions have been
designed, we can multiply them with $\mathcal{B}f$ and take the inverse
Bargmann transform in order to get counterexamples on $\mathbb{R}\times
a\mathbb{Z}$ that are close to $f\in L^{2}(\mathbb{R})$.

We design the functions $H^{\pm}_{\delta}\in\mathcal{F}^{2}(\mathbb{C})$ by
modifiying the counterexamples on $\mathbb{R}\times a\mathbb{Z}$,

$h^{\pm}(t):=\varphi(t)\left(\cosh\left(\frac{\pi
t}{a}\right)\pm\mathrm{i}\sinh\left(\frac{\pi t}{a}\right)\right),\quad
t\in\mathbb{R},$

presented in [15]. To accomplish this, we compute the Bargmann transforms of
$h^{\pm}$ which are given by

$z\mapsto\left(1\mp\mathrm{i}+(1\pm\mathrm{i})\mathrm{e}^{\frac{\pi
z}{a}}\right)\mathrm{e}^{-\frac{\pi z}{2a}}$

up to a constant depending on $a$. Next, we note that time-shifting $h^{\pm}$
by $u\in\mathbb{R}$ will produce additional counterexamples on
$\mathbb{R}\times a\mathbb{Z}$ according to the covariance property of the
Gabor transform [17]. For $f\in L^{2}(\mathbb{R})$, it holds that

$\mathcal{B}\operatorname{T}_{u}f(z)=\mathcal{B}f(z-u)\mathrm{e}^{\pi
uz}\mathrm{e}^{-\frac{\pi}{2}u^{2}},\quad z\in\mathbb{C},$

such that the Bargmann transforms of the counterexamples
$\operatorname{T}_{u}h^{\pm}$, with $u=-\tfrac{a}{\pi}\log\delta$, are given
by

$z\mapsto\left(1\mp\mathrm{i}+(1\pm\mathrm{i})\delta\cdot\mathrm{e}^{\frac{\pi
z}{a}}\right)\delta^{-az}\mathrm{e}^{-\frac{\pi z}{2a}}$

up to a constant depending on $a$ and $\delta$. After multiplying by
$\delta^{az}\mathrm{e}^{\frac{\pi z}{2a}}$, it follows that

$z\mapsto 1\mp\mathrm{i}+(1\pm\mathrm{i})\delta\cdot\mathrm{e}^{\frac{\pi
z}{a}}$

are entire functions whose magnitudes agree on
$\mathbb{R}+\mathrm{i}a\mathbb{Z}$ (which do not agree up to global phase) and
we define

$H^{\pm}_{\delta}(z):=1\pm\mathrm{i}\delta\cdot\mathrm{e}^{\tfrac{\pi
z}{a}},\quad z\in\mathbb{C},$ (2)

after multiplying by $(1\pm\mathrm{i})/2$.

######  Theorem III.1.

Let $a>0$. Then, $\mathfrak{C}(\mathbb{R}\times a\mathbb{Z})$ is dense in
$L^{2}(\mathbb{R})$.

###### Proof.

Let $\epsilon>0$ and $f\in L^{2}(\mathbb{R})$. We want to show that there
exist $g^{\pm}\in L^{2}(\mathbb{R})$ which do not agree up to global phase,
are $\epsilon$-close to $f$ in $L^{2}(\mathbb{R})$ and satisfy

$\lvert\mathcal{G}g^{+}\rvert=\lvert\mathcal{G}g^{-}\rvert\mbox{ on
}\mathbb{R}\times a\mathbb{Z}.$

To do so, we note that the monomials

$e_{n}(z):=\left(\frac{\pi^{n}}{n!}\right)^{1/2}z^{n},\qquad
n\in\mathbb{N}_{0},~{}z\in\mathbb{C},$

form an orthonormal basis for the Fock space $\mathcal{F}^{2}(\mathbb{C})$
[17]. Therefore, the space of complex polynomials is dense in
$\mathcal{F}^{2}(\mathbb{C})$ and we can find $P\in\mathbb{C}[z]$ such that

$\left\lVert\mathcal{B}f-P\right\rVert_{\mathcal{F}}<\frac{\epsilon}{2}.$

Let us now consider the entire functions $H^{\pm}_{\delta}$ defined in
equation (2) and note that $G_{\delta}^{\pm}:=H_{\delta}^{\pm}\cdot
P\in\mathcal{F}^{2}(\mathbb{C})$ since $G^{\delta}_{\pm}$ are entire functions
of exponential-type. Hence, we can define the signals
$g^{\pm}_{\delta}:=\mathcal{B}^{-1}G^{\pm}_{\delta}\in L^{2}(\mathbb{R})$. To
establish the desired properties of $g^{\pm}_{\delta}$, we will work with
their Bargmann transforms $G_{\delta}^{\pm}$. First, we note that $\lvert
H^{+}_{\delta}\rvert=\lvert H^{-}_{\delta}\rvert$ on
$\mathbb{R}+\mathrm{i}a\mathbb{Z}$ implies $\lvert G^{+}_{\delta}\rvert=\lvert
G^{-}_{\delta}\rvert$ on $\mathbb{R}+\mathrm{i}a\mathbb{Z}$ and thus
$\lvert\mathcal{G}g^{+}_{\delta}\rvert=\lvert\mathcal{G}g^{-}_{\delta}\rvert$
on $\mathbb{R}\times a\mathbb{Z}$ by equation (1). Secondly, we note that the
entire functions $G^{\pm}_{\delta}$ do not agree up to global phase: indeed,
both entire functions $H^{\pm}_{\delta}$ have infinitely many roots but no
root of $H^{+}_{\delta}$ is a root of $H^{-}_{\delta}$ and vice versa. At the
same time, $P$ is a polynomial and has only finitely many roots. It follows
that $G^{+}_{\delta}$ does have roots which are not roots of $G^{-}_{\delta}$
(and vice versa) and thus $G^{+}_{\delta}\not\sim G^{-}_{\delta}$. By the
linearity of the Bargmann transform, we can conclude that
$g^{+}_{\delta}\not\sim g^{-}_{\delta}$. Finally, we note that the definition
of $H_{\delta}^{\pm}$ in equation (2) directly implies that

$\lVert P-P\cdot H^{\pm}_{\delta}\rVert_{\mathcal{F}}=\delta\lVert z\mapsto
P(z)\cdot\mathrm{e}^{\pi z/a}\rVert_{\mathcal{F}},$

and so there exists a $\delta>0$ depending on $a$, $\epsilon$ and $P$ (which
in turn depends on $f$ and $\epsilon$) such that

$\lVert P-P\cdot H^{\pm}_{\delta}\rVert_{\mathcal{F}}<\frac{\epsilon}{2}.$

We conclude

$\displaystyle\lVert f-g^{\pm}_{\delta}\rVert_{2}$
$\displaystyle=\lVert\mathcal{B}f-H^{\delta}_{\pm}\cdot P\rVert_{\mathcal{F}}$
$\displaystyle\leq\lVert\mathcal{B}f-P\rVert_{\mathcal{F}}+\lVert
P-H^{\delta}_{\pm}\cdot P\rVert_{\mathcal{F}}<\epsilon.$

∎

######  Remark III.2 (Some explanations on the proof).

As $\mathcal{B}f\in\mathcal{F}^{2}(\mathbb{C})$, for $f\in L^{2}(\mathbb{R})$,
we know that $\mathcal{B}f$ is either an entire function of exponential-type
or an entire function of second order. If $\mathcal{B}f$ is of second order,
then its type is either strictly smaller than $\pi/2$ or exactly $\pi/2$. In
most of these cases, it holds that $\mathcal{B}f\cdot
H^{\pm}_{\delta}\in\mathcal{F}^{2}(\mathbb{C})$ and thus we can define

$g^{\pm}_{\delta}:=\mathcal{B}^{-1}\left(\mathcal{B}f\cdot
H^{\pm}_{\delta}\right)\in L^{2}(\mathbb{R}),$

with

$\delta<\frac{\epsilon}{\lVert z\mapsto\mathcal{B}f(z)\mathrm{e}^{\pi
z/a}\rVert_{\mathcal{F}}},$

to obtain counterexamples which are $\epsilon$-close to $f$ in
$L^{2}(\mathbb{R})$. We note that $g^{\pm}_{\delta}$ are small additive
perturbations of our original signals $f$.

Unfortunately, there is one case in which this simple strategy does not work:
the one in which $\mathcal{B}f$ is a second-order entire function of type
$\pi/2$. Indeed, in this case, it is not guaranteed that $\mathcal{B}f\cdot
H^{\pm}_{\delta}$ is in the Fock space. — Two striking examples for why this
can fail can be found in [18]. — As the only situation in which
$\mathcal{B}f\cdot H^{\pm}_{\delta}$ is not in the Fock space occurs when
$\mathcal{B}f$ is exactly of order two and of type $\pi/2$, it seems obvious
that the functions $f$ for which $\mathcal{B}f\cdot
H^{\pm}_{\delta}\in\mathcal{F}^{2}(\mathbb{C})$ holds must be dense in
$L^{2}(\mathbb{R})$. We can prove this by realising that the complex
polynomials are dense in $\mathcal{F}^{2}(\mathbb{C})$.

Theorem III.1 continues to hold for any set of infinitely many equidistant
parallel lines. We can show this by considering the entire functions

$H^{\pm}_{\delta}(z):=1\pm\mathrm{i}\delta\exp\left(\frac{\pi\mathrm{e}^{\mathrm{i}\theta}}{a}\left(z-\overline{\lambda}_{0}\right)\right)$

and realising that the corresponding signals $g^{\pm}_{\delta}\in
L^{2}(\mathbb{R})$ satisfy

$\lvert\mathcal{G}g^{+}_{\delta}\rvert=\lvert\mathcal{G}g^{-}_{\delta}\rvert\mbox{
on }\operatorname{R}_{\theta}\left(\mathbb{R}\times
a\mathbb{Z}\right)+\lambda_{0},$

where $a>0$, $\lambda_{0}\in\mathbb{R}^{2}\simeq\mathbb{C}$. The statement for
general lattices follows from the same consideration because all lattices are
subsets of some set of infinitely many equidistant parallel lines. We
therefore arrive at the following result.

######  Theorem III.3.

Let $\Lambda\subset\mathbb{R}^{2}$ be a set of equidistant parallel lines or a
lattice. Then, $\mathfrak{C}(\Lambda)$ is dense in $L^{2}(\mathbb{R})$.

To illustrate our main results, we construct counterexamples that are close to
the Hermite functions and plot their spectrograms.

######  Example III.4.

Consider the $n$-th Hermite function $H_{n}\in L^{2}(\mathbb{R})$ given by

$\mathcal{B}H_{n}(z)=e_{n}(z)=\left(\frac{\pi^{n}}{n!}\right)^{1/2}z^{n},\qquad
z\in\mathbb{C}.$

By equation (1), the Gabor transform of the Hermite function is

$\displaystyle\mathcal{G}H_{n}(x,\omega)$
$\displaystyle=\mathrm{e}^{-\pi\mathrm{i}x\omega}\mathcal{B}H_{n}(x-\mathrm{i}\omega)\mathrm{e}^{-\frac{\pi}{2}\left(x^{2}+\omega^{2}\right)}$
$\displaystyle=\left(\frac{\pi^{n}}{n!}\right)^{1/2}\mathrm{e}^{-\pi\mathrm{i}x\omega}\left(x-\mathrm{i}\omega\right)^{n}\mathrm{e}^{-\frac{\pi}{2}\left(x^{2}+\omega^{2}\right)},$

for $(x,\omega)\in\mathbb{R}^{2}$. If we plot the magnitude of the above (for
$n=5$), we obtain Figure 1a. Next, we want to find counterexamples which are
close to $H_{n}$. According to Remark III.2, we can define
$g^{+}_{\delta}:=\mathcal{B}^{-1}(\mathcal{B}H_{n}\cdot H^{+}_{\delta})$. Let
us visualise the spectrogram of $g^{+}_{\delta}$, i.e.

$\mathcal{G}g^{+}_{\delta}(x,\omega)=\mathcal{G}H_{n}(x,\omega)\cdot
H^{+}_{\delta}(x-\mathrm{i}\omega),\quad(x,\omega)\in\mathbb{R}^{2},$

in Figure 1b (for $n=5$, $a=\tfrac{1}{4}$ and
$\delta=\tfrac{1}{50}\exp(-10\pi)$).

(a) $\lvert\mathcal{G}H_{5}\rvert$

(b) $\lvert\mathcal{G}g_{\delta}^{+}\rvert$, for
$\delta=\tfrac{1}{50}\exp(-10\pi)$.

Figure 1: The Gabor magnitude of the fifth Hermite function (Figure 1a) and of
a counterexample $g_{\delta}^{+}$ to sampled Gabor phase retrieval on
$\mathbb{R}\times\tfrac{1}{4}\mathbb{Z}$ (Figure 1b).

##  IV The Gaussian is not a counterexample

Finally, we can show that the Gaussian is not a counterexample on
$a\mathbb{Z}^{2}$ if $a\in(0,1)$. Specifically, we prove the following result.

######  Theorem IV.1.

Let $0<a<1$ and $f\in L^{2}(\mathbb{R})$ be such that

$\lvert\mathcal{G}f(x,\omega)\rvert^{2}=\lvert\mathcal{G}\varphi(x,\omega)\rvert^{2},\qquad(x,\omega)\in
a\mathbb{Z}^{2}.$

Then, there exists an $\alpha\in\mathbb{R}$ such that
$f=\mathrm{e}^{\mathrm{i}\alpha}\varphi$.

Since the Bargmann transform of the Gaussian is one, equation (1) implies that
the theorem above is equivalent to the following lemma.

######  Lemma IV.2.

Let $0<a<1$ and let $F\in\mathcal{F}^{2}(\mathbb{C})$ be such that

$\lvert F(z)\rvert=1=\lvert\mathcal{B}\varphi(z)\rvert,\qquad z\in
a\mathbb{Z}+\mathrm{i}a\mathbb{Z}.$

Then, there exists an $\alpha\in\mathbb{R}$ such that
$F=\mathrm{e}^{\mathrm{i}\alpha}$.

The intuition for the proof of this lemma comes from the maximum modulus
principle: we note that we are considering a second order entire function $F$
which is bounded on all lattice points; this suggests that $F$ should be
constant in the entire complex plane as long as the lattice is dense enough.
This intuition is indeed correct, as evidenced by the following result
independently discovered by V. G. Iyer [19] and A. Pfluger [20].

######  Theorem IV.3.

Let $h$ be an entire function such that

$\limsup_{r\to\infty}\frac{\log M_{h}(r)}{r^{2}}<\frac{\pi}{2},$

where $M_{h}(r):=\max_{\lvert z\rvert=r}\lvert h(z)\rvert$. If there exists a
constant $\kappa>0$ such that

$\lvert h(m+\mathrm{i}n)\rvert\leq\kappa,\qquad m,n\in\mathbb{Z},$

then $h$ is constant.

###### Proof of Lemma IV.2.

Consider the function $h(z):=F(az)$, for $z\in\mathbb{C}$. It holds that

$\lvert h(z)\rvert=\lvert F(az)\rvert\leq\lVert
F\rVert_{\mathcal{F}}\cdot\mathrm{e}^{\frac{\pi}{2}\lvert az\rvert^{2}}=\lVert
F\rVert_{\mathcal{F}}\cdot\mathrm{e}^{\frac{\pi a^{2}}{2}\lvert z\rvert^{2}},$

for $z\in\mathbb{C}$, such that

$\displaystyle\limsup_{r\to\infty}\frac{\log M_{h}(r)}{r^{2}}$
$\displaystyle\leq\limsup_{r\to\infty}\left(\frac{\log\lVert
F\rVert_{\mathcal{F}}}{r^{2}}+\frac{\pi a^{2}}{2}\right)$
$\displaystyle=\frac{\pi a^{2}}{2}<\frac{\pi}{2}.$

Additionally,

$\lvert h(m+\mathrm{i}n)\rvert=\lvert F(am+\mathrm{i}an)\rvert=1,\qquad
m,n\in\mathbb{Z},$

holds such that the assumptions of Theorem IV.3 are met and we can conclude
that $h$ is constant. As $\lvert h(0)\rvert=1$, it follows that there must
exist an $\alpha\in\mathbb{R}$ such that $h=\mathrm{e}^{\mathrm{i}\alpha}$
which implies $F=\mathrm{e}^{\mathrm{i}\alpha}$. ∎

We have therefore shown that the set of counterexamples is not equal to the
whole of $L^{2}(\mathbb{R})$ when $\Lambda$ is a sufficiently dense quadratic
lattice.

######  Remark IV.4.

A natural confusion that might arise in connection with Theorem IV.1 is in how
far it is different from the result in [21] on shift-invariant spaces with
Gaussian generator $V_{\beta}^{1}(\varphi)$. While Theorem IV.1 implies that
the Gaussian can be distinguished from all other functions in
$L^{2}(\mathbb{R})$ based on its sampled Gabor magnitude measurements, the
result in [21] only implies that it can be distinguished from the functions in
$V_{\beta}^{1}(\varphi)\subset L^{2}(\mathbb{R})$.

## Acknowledgements

The authors would like to extend their heartfelt thanks to Stefan
Steinerberger for his insightful discussions and acknowledge funding through
the SNSF grant 200021_184698.

## References

  * [1] W. H. Bragg, “Bakerian lecture: X-rays and crystal structure,” _Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character_ , vol. 215, pp. 253–274, 1915, https://www.jstor.org/stable/91108.
  * [2] W. L. Bragg, “The determination of parameters in crystal structures by means of Fourier series,” _Proceedings of the Royal Society of London. Series A, Containing Papers of a Mathematical and Physical Character_ , vol. 123, no. 792, pp. 537–559, 1929, https://doi.org/10.1098/rspa.1929.0083.
  * [3] J. M. Robertson, “X-ray analysis and application of Fourier series methods to molecular structures,” _Reports on Progress in Physics_ , vol. 4, no. 1, pp. 332–367, January 1937, https://doi.org/10.1088/0034-4885/4/1/324.
  * [4] W. L. Bragg, “The Rutherford memorial lecture, 1960 — the development of X-ray analysis,” _Proceedings of the Royal Society of London. Series A. Mathematical and Physical Sciences_ , vol. 262, no. 1309, pp. 145–158, 1961, https://doi.org/10.1098/rspa.1961.0109.
  * [5] D. Sayre, “X-ray crystallography: The past and present of the phase problem,” _Structural Chemistry_ , vol. 13, no. 1, pp. 81–96, February 2002, https://doi.org/10.1023/A:1013477415486.
  * [6] J. R. Fienup, “Phase retrieval algorithms: A comparison,” _Applied Optics_ , vol. 21, no. 15, pp. 2758–2769, August 1982, https://doi.org/10.1364/AO.21.002758.
  * [7] J. C. Dainty and J. R. Fienup, _Phase retrieval and image reconstruction for astronomy_ , 1st ed. Academic Press, March 1987, ch. 7, pp. 231–275.
  * [8] Y. Shechtman, Y. C. Eldar, O. Cohen, H. N. Chapman, J. Miao, and M. Segev, “Phase retrieval with application to optical imaging: A contemporary overview,” _IEEE Signal Processing Magazine_ , vol. 32, no. 3, pp. 87–109, May 2015, https://doi.org/10.1109/MSP.2014.2352673.
  * [9] Z. Průša and N. Holighaus, “Phase vocoder done right,” in _2017 25th European Signal Processing Conference (EUSIPCO)_. Kos, Greece: IEEE, August 2017, pp. 976–980, https://doi.org/10.23919/EUSIPCO.2017.8081353.
  * [10] R. Abdelmalek, Z. Mnasri, and F. Benzarti, “Audio signal reconstruction using phase retrieval: Implementation and evaluation,” _Multimedia Tools and Applications_ , vol. 81, no. 11, pp. 15 919–15 946, May 2022, https://doi.org/10.1007/s11042-022-12421-1.
  * [11] R. Alaifari, F. Bartolucci, S. Steinerberger, and M. Wellershoff, “On the connection between uniqueness from samples and stability in Gabor phase retrieval,” arXiv:2205.07013 [math.FA], May 2022, https://doi.org/10.48550/arXiv.2205.07013.
  * [12] J. N. Mc Donald, “Phase retrieval and magnitude retrieval of entire functions,” _Journal of Fourier Analysis and Applications_ , vol. 10, no. 3, pp. 259–267, May 2004, https://doi.org/10.1007/s00041-004-0973-9.
  * [13] P. Jaming, “Uniqueness results in an extension of Pauli’s phase retrieval problem,” _Applied and Computational Harmonic Analysis_ , vol. 37, no. 3, pp. 413–441, November 2014, https://doi.org/10.1016/j.acha.2014.01.003.
  * [14] M. Wellershoff, “Phase retrieval of entire functions and its implications for Gabor phase retrieval,” arXiv:2202.03733 [math.CV], February 2022, https://doi.org/10.48550/arXiv.2202.03733.
  * [15] R. Alaifari and M. Wellershoff, “Phase retrieval from sampled Gabor transform magnitudes: Counterexamples,” _Journal of Fourier Analysis and Applications_ , vol. 28, no. 1, pp. 1–9, December 2021, https://doi.org/10.1007/s00041-021-09901-7.
  * [16] P. Grohs and L. Liehr, “On foundational discretization barriers in STFT phase retrieval,” _Journal of Fourier Analysis and Applications_ , vol. 28, no. 2, pp. 1–39, April 2022, https://doi.org/10.1007/s00041-022-09935-5.
  * [17] K. Gröchenig, _Foundations of Time-Frequency Analysis_ , 1st ed., ser. Applied and Numerical Harmonic Analysis (ANHA). Boston, MA: Birkhäuser, December 2000, https://doi.org/10.1007/978-1-4612-0003-1.
  * [18] C. Bénéteau, B. J. Carswell, and S. Kouchekian, “Extremal problems in the Fock space,” _Computational Methods and Function Theory_ , vol. 10, no. 1, pp. 189–206, June 2010, https://doi.org/10.1007/BF03321762.
  * [19] V. G. Iyer, “A note on integral functions of order 2 bounded at the lattice points,” _Journal of the London Mathematical Society_ , vol. s1-11, no. 4, pp. 247–249, October 1936, https://doi.org/10.1112/jlms/s1-11.4.247.
  * [20] A. Pfluger, “On analytic functions bounded at the lattice points,” _Proceedings of the London Mathematical Society_ , vol. s2-42, no. 1, pp. 305–315, 1937, https://doi.org/10.1112/plms/s2-42.1.305.
  * [21] P. Grohs and L. Liehr, “Injectivity of Gabor phase retrieval from lattice measurements,” _Applied and Computational Harmonic Analysis_ , vol. 62, pp. 173–193, January 2023, https://doi.org/10.1016/j.acha.2022.09.001.


# Ballistic deposition with memory:
a new universality class of surface growth with a new scaling law

Ahmed Roman1 Ruomin Zhu4 Ilya Nemenman1,2,3 1Physics Department, Emory
University, Atlanta, Georgia, USA
2 Biology Department, Emory University, Atlanta, Georgia, USA
3 Initiative for Theory and Modeling of Living Systems, Emory University,
Atlanta, Georgia, USA
2 School of Physics, The University of Sydney, Sydney, NSW, Australia

(September 3, 2024)

###### Abstract

Motivated by recent experimental studies in microbiology, we suggest a
modification of the classic ballistic deposition model of surface growth,
where memory of a deposition at a site induces more depositions at that site
or its neighbors. By studying the statistics of surfaces in this model, we
obtain three independent critical exponents: the growth exponent $\beta=5/4$,
the roughening exponent $\alpha=2$, and the new (size) exponent $\gamma=1/2$.
The model requires a modification to the Family-Vicsek scaling, resulting in
the dynamical exponent $z=\frac{\alpha+\gamma}{\beta}=2$. This modified
scaling collapses the surface width vs time curves for various lattice sizes.
This is a previously unobserved universality class of surface growth that
could describe surface properties of a wide range of natural systems.

Suggested keywords

††preprint: AAPM/123-QED

Introduction. Interface growth, and its ensuing roughening, is a paradigmatic
nonequilibrium statistical physics process, with applications to many domains
of physics Barabási and Stanley (1995). Analytical, computational, and
experimental studies have shown that the statistics of interface roughness in
such processes usually is characterized by one of three well-known
universality classes: Poisson, Edwards-Wilkinson (EW), and Kardar-Parisi-Zhang
(KPZ) Family (1986); Kardar  _et al._ (1986). In the first, interface heights
at every point are uncorrelated. In the second, peaks in the interface are
smoothed through diffusion. Finally, in the third, nearby sites in the
interface help each other grow, resulting in a nonlinear amplification of
fluctuations. Competition between the smoothing and the nonlinearity leads to
the interface roughness that increases with time and eventually saturates at a
system-size dependent value.

More concretely, we denote the height of a 1-d interface at point $x$ at time
$t$ by $h(x,t)$. Then the standard deviation of the interface height defines
the interface roughness

$w(L,t)=\langle(h(x,t)-\langle h(x,t)\rangle_{L})^{2}\rangle_{L}^{1/2},$ (1)

and the average here is over a domain of size $L$. Such growth processes are
generally characterized by three critical exponents: $\beta$, the growth
exponent, which measures how the roughness grows with time; $\alpha$, the
roughness exponent, which parameterizes the dependence of the roughness of the
saturated interface on the system size, and $z$, the dynamical exponent, which
relates the time at which the width of the interface stops growing to the
system size. The three exponents are related by the celebrated Family-Vicsek
dynamical scaling Family and Vicsek (1985)

$\displaystyle w(L,t)$ $\displaystyle\sim
L^{\alpha}f(t/L^{z}),\quad\mbox{with}$ (2) $\displaystyle f(u)$
$\displaystyle\propto\bigg{\\{}\begin{array}[]{ll}u^{\beta}&u\ll 1\\\ 1&u\gg
1\end{array},$ (5)

which results in $z=\alpha/\beta$.

Figure 1: Changes in height and propensity in one time step. The left panel
(a) shows the deposition of particle $A$ at step $N$ into site three. The site
number increases from left to right. The sites 1-5 have propensities
$\pi_{1},\cdots,\pi_{5}$ respectively. Panel (b) indicates the final position
of particle $A$ at step $N+1$ as an overhang of column two. The propensities
of site three and its two nearest neighbors become one while other site
propensities are reduced by factor $r$. Figure 2:  Examples of the BDM
interfaces. In the top row, the deposition height vs. space coordinate is
shown for each deposition as a black dot. Different columns are for different
values of $r$. The blue curves show the surface height as a function of the
spatial coordinate for different number of depositions, from $N=2000$ (light
blue), to $N=10000$ (dark blue). The bottom row shows the propensity, encoded
by color, as a function of space and time.

What unites all of these cases is that there is no memory or inertia in the
interface growth – deposition is Markovian in time. This is a reasonable
assumption when the interface is built by or from stateless agents. However,
when the agents are more complex, such as when they are living cells with a
multitude of internal states, such memory-less assumption should be
questioned. For example, in cyclic AMP signaling in Dictyostelium discoideum,
which is a classic biological model of collective signaling, collective
motility, and development, a spreading wave of cyclic AMP activates a cell,
but only if the temporal derivative of the cyclic AMP concentration is
positive and large Wang  _et al._ (2012). In another example, an action
potential propagates in a bacterial film only if a concentration of a
previously secreted extracellular potassium has not yet decayed through
diffusion Prindle  _et al._ (2015); Martinez-Corral  _et al._ (2018). All such
processes possess memory: the interface at a certain point can grow, but only
if it grew here recently. Theory of such interface growth processes with
memory is not yet established. In particular, we do not know the relevant
critical exponents, how many different universality classes there are, and
whether the Family-Viscek scaling is satisfied in such settings.

Here we develop a model of Ballistic Deposition with Memory (BDM), one of
likely many possible extensions of the traditional memoryless surface growth
processes, which is inspired by the microbiological systems mentioned above.
We derive the critical exponents, and verify them numerically. We show that
the process falls into a new universality class with a new scaling law and a
new scaling relation. The KPZ universality class is an unstable fixed point in
the BDM dynamics. Finally, we discuss the effect of varying memory duration,
and show that the standard KPZ interfaces are achieved in a particular limit
of the memory parameters.

Model formulation. We consider the deposition of particles on a one-
dimensional substrate of length $L$. Each site $i$ has a propensity value
$0\leq\pi_{i}(N)\leq 1$, which determines the probability that the site will
receive a particle deposition at step $N$. Initially, all sites are equally
likely to receive a deposition; i.e., $\pi_{i}(0)=1$ for all $i$. However,
unlike in the ballistic deposition model, if a site $j$ receives a deposition,
then the propensity at that site and its nearest neighbors is set to one,
while the propensity of all other sites is reduced by a factor $r$, thus
reducing the probability of receiving a deposition if no deposition has
happened for a long time:

$\pi_{i}(N+1)=\begin{cases}1&j-1\leq i\leq j+1\\\
r\pi_{i}(N)&\text{otherwise.}\end{cases}$ (6)

Overall, the probability to receive the deposition at site $i$ at the $N$th
deposition event is

$\mathcal{P}[i,N]=\frac{\pi_{i}(N)}{\sum_{i=1}^{L}\pi_{i}(N)}.$ (7)

Figure 3: (Left) The saturation width of the BDM interface as a function of
the system length $L$. The scaling $L^{\alpha}$, where $\alpha$ is the
roughening exponent, obtained from simulation, is shown. (Middle) The scaling
of $w/t^{\beta}$ in the growth regime as function of the system size is
$L^{\gamma}$; $t(N)$ is defined as in Eq. (11). The fitted scaling with the
size exponent $\gamma=0.54\approx 0.5$ is also plotted. (Right) The growth
exponent $\beta$ as a function of the system size $L$. The black dash-dotted
line at $\beta=5/4$ is the theoretical prediction, in agreement with
simulations once finite size effects become negligible. The value $r=0.5$ is
used for all subplots.

At step $N$, the height of the interface at site $i$ is $h(i,N)$, with
$h(i,0)=0$. After a site $i$ is randomly selected for the deposition according
to Eq. (7), its height increases from $h(i,N)$ to

$h(i,N+1)=\max\\{h(i-1,N),h(i,N)+1,h(i+1,N)\\},$ (8)

allowing for overhangs, as in the traditional Ballistic Deposition, cf. Fig.
1. We model the process with periodic boundary conditions, $h(L+1,N)=h(1,N)$.
The dynamics of the surface and the propensity are shown in Fig. 2 for various
values of $r$. For low values of $r$, a single propensity finger moves
randomly, causing the deposition sites to follow a random walk, and overhangs
form every time the random walk reverts. In the intermediate $r$ regime,
multiple propensity fingers move randomly, merge and split. These fingers
deposit particles that form shapes, reminiscent of the Diffusion Limited
Aggregation Witten and Sander (1983), though whether the similarity is more
than qualitative is unclear. For values of $r\approx 1$, many deposition
fingers merge into a deposition front, whose fluctuation is KPZ-like (as we
will discuss later), but with chasms that have a much lower height, and whose
frequency gets lower as $r\to 1$.

A random walker. We start with the fast propensity decay limit, defined as
$r\ll 1/L$ (see Appendix for details). Here the probability that any site $j$
receives a deposition at step $N+1$ given that a non-neighboring site $i$
received a deposition at step $N$ is

$\begin{split}\sum_{\begin{subarray}{c}j\not\in\\{i-1,i,i+1\\}\\\ 1\leq j\leq
L\end{subarray}}\mathcal{P}[j,N+1|i,N]&=\sum_{\begin{subarray}{c}j\not\in\\{i-1,i,i+1\\}\\\
1\leq j\leq L\end{subarray}}\frac{\pi_{j}(N)}{\sum_{k=1}^{L}\pi_{k}(N)}\\\
&<\frac{Lr}{3}\ll\frac{1}{3},\end{split}$ (9)

where we used the bounds
$\sum_{k=1}^{L}\pi_{i}(N)>\sum_{k\in\\{i-1,i,i+1\\}}\pi_{k}(N)=3$ and
$\sum_{\begin{subarray}{c}j\not\in\\{i-1,i,i+1\\}\\\ 1\leq j\leq
L\end{subarray}}\pi_{j}(N)<(L-3)r<Lr$ to bound the denominator and numerator,
respectively. Therefore, the location $x_{N}$ of the deposition after $N$
steps is well approximated by a 1-d random walker.

Determining the unit of time. Up until now, we did not make an explicit
distinction between time and $N$, the number of particles deposited, so that
$t\sim N$. This is in contrast to classical models of surface growth, such as
ballistic deposition or KPZ, where the time is defined in the units of the
mean number of deposited layers, $t\sim N/L$. Adopting the traditional
definition would imply that, for small $r$, in one time unit, one deposits $L$
particles on $\sqrt{L}$ sites. The flux per unit time at those $\sqrt{L}$
sites would then be $\sim\sqrt{L}$, which is infinite in the thermodynamic
limit, $L\rightarrow\infty$. Here we show that, to avoid this pathology,
$t\propto N$ is the only acceptable choice.

We begin by defining the space-averaged propensity
$\pi(N)=\frac{1}{L}\sum_{i=1}^{L}\pi_{i}(N)$, which can be decomposed into two
different contributions. At step $N-1$, $L-3$ sites do not receive a
deposition and are not neighbors of the deposition site. The total propensity
of those sites at step $N$ is $(L-3)r\pi(N-1)$. The total propensity of the
site that receives a deposition and its two neighbors is three. Thus we obtain
the recursion relation for $\pi(N)$

$\pi(N)=\frac{1}{L}\big{[}(L-3)r\pi(N-1)+3\big{]}.$ (10)

The solution of Eq. (10) (see Appendix) has a characteristic time scale of
$N_{1/e}=\frac{1}{\ln\frac{L}{(L-3)r}}\approx\frac{1}{\ln\frac{1}{r}}$
depositions, approaching a steady state space-averaged propensity
$\pi_{*}=3(L-(L-3)r)^{-1}.$ In the limit $N\gg N_{1/e}$, there are
$\mathcal{O}(L\pi_{*})$ sites whose probability of receiving a deposition is
$\mathcal{O}(1/L\pi_{*})$ (see Appendix), while all other sites have
probability zero of receiving a deposition. This implies that the effective
lattice length is $L\pi_{*}$ and motivates a definition of time as

$t=\eta\frac{N}{L\pi_{*}}=\eta\left(\frac{1}{3}-\frac{L-3}{3L}r\right)N$ (11)

for any constant $\eta$. In all figures and equations, we define time as in
Eq. (11) with $\eta=1$.

Dynamical exponents. After $N$ depositions, the deposited particles span
$\mathcal{O}(\sqrt{N})$ lattice sites and the random walker has performed
$\mathcal{O}(N)$ reversals, with each reversal increasing the height by 1.
Thus the average height of the interface is $\langle h(N)\rangle\sim
c_{1}\cdot 0\cdot\frac{L-\sqrt{N}}{L}+c_{2}\cdot
N\cdot\frac{\sqrt{N}}{L}\sim\frac{N^{3/2}}{L}=\lambda_{r,L}^{3/2}t^{3/2}/L$
while the mean squared height is $\langle h(N)^{2}\rangle\sim c_{3}\cdot
0^{2}\cdot\frac{L-\sqrt{N}}{L}+c_{4}\cdot
N^{2}\cdot\frac{\sqrt{N}}{L}\sim\frac{N^{5/2}}{L}=\lambda_{r,L}^{5/2}t^{5/2}/L$
for $\lambda_{r,L}=1/(L\pi^{*})$ and some constants $c_{1},\cdots,c_{4}$. The
resulting mean width of the interface becomes

$w(L,t)\sim\left(\lambda_{r,L}^{5/2}\frac{t^{5/2}}{L}-\delta\lambda_{r,L}^{3/4}\frac{t^{3/4}}{L^{2}}\right)^{1/2}$
(12)

for some constant $\delta$.

In the regime where $\sqrt{N}\ll L$ (i.e., the random walker has yet to span
the system), the width of the interface grows with time (the growth regime),
and its value is dominated by the first term in Eq. (12):

$w(L,t)\sim\lambda_{r,L}^{5/4}t^{5/4}/\sqrt{L}\propto t^{\beta}L^{-\gamma}.$
(13)

This determines the size exponent $\gamma=1/2$ and growth exponent
$\beta=5/4$, which are in excellent agreement with simulation values, cf. Fig.
3, despite finite size effects, and even with $r$ outside the regime $r\ll
1/L$.

In the regime where $\sqrt{N}\gtrsim\mathcal{O}(L)$, the random walker has
spanned the lattice, and the surface roughness saturates at

$w_{\rm{sat}}\sim N^{5/4}/\sqrt{L}\sim(L^{2})^{5/4}/\sqrt{L}=L^{2},$ (14)

This determines the roughness exponent $\alpha=2$, which agrees with the
simulations, Fig. 3.

Figure 4: Interface width $w$ as a function of time for $r=0.5$ and systems of
different lengths, $L$. The time axis is scaled by $L^{z}=L^{2}$, and the
width axis is scaled by $L^{\alpha}=L^{2}$, which achieves collapse of all
curves. The data come from averaging over $20$ independent runs for all $L$
except $L=6400$, which used $5$ independent runs. The inset shows the bare
width as a function of the bare time.

Dynamical scaling relation and the scaling law. Since the growth and
saturation regimes cross at some time $t_{c}$, it follows from Eqs. (13) and
(14) that $\lambda_{r,L}^{-\beta}L^{-\gamma}t_{c}^{\beta}\sim L^{\alpha}$. The
relation
$t_{c}\sim\lambda_{r,L}L^{\frac{\alpha+\gamma}{\beta}}=\lambda_{r,L}L^{z}$
determines the scaling law $z=\frac{\alpha+\gamma}{\beta}=2$ in our model.
Note that $\lambda_{r,L}$ has a weak dependence on $L$ such that for $L\gg 1$
it is essentially independent of $L$. The scaling relation becomes

$w(L,t)\sim L^{\alpha}f(t/L^{\frac{\alpha+\gamma}{\beta}})$ (15)

with $f$ defined as in the Family-Vicsek scalingFamily and Vicsek (1985).
Indeed, plotting $w/L^{\alpha}$ against $t/L^{\frac{\alpha+\gamma}{\beta}}$,
as in Fig. 4, collapses the width vs time curves plotted for various lattice
lengths $L$ in the inset of Fig. 4. From this, we conclude that there are
three independent exponents $\alpha,\beta$ and $\gamma$ that fix the dynamic
exponent $z$.

As a newly arriving particle sticks to the surface following Eq. (8), its
height is either the same or larger than that of its neighbors. This
introduces correlations between neighboring sites. The ensuing height
fluctuations spread laterally since particles deposited at nearby sites must
have an equal or larger height. This correlation length $\xi_{||}$ can only
grow up to the substrate length, i.e., $\xi_{||}\sim L$ for $t\gg t_{c}.$
Replacing $L$ by $\xi_{||}$ in $t_{c}\sim\lambda_{r,L}L^{z}$, we find that
$\xi_{||}\sim\lambda_{r,L}^{-1/z}t_{c}^{1/z}$ for $t\gg t_{c}.$ Since
$\xi_{||}\sim N^{1/2}$ for $t\ll t_{c}$, we see that
$\xi_{||}\sim\lambda_{r,L}^{-1/z}t^{1/z}$ holds for $t\ll t_{c}$ as well.

Varying the memory time scale. As $r$ increases, so does the total size of the
randomly moving propensity fingers $L\pi_{*}=\lambda_{r,L}^{-1}$. Increasing
$r$ also decreases linearly the time to saturation $t_{c}$, cf. Fig. 5. In the
limit of $r=1$, the KPZ exponents as seen in Fig. 5 and the standard
definition of time $t=N/L$ are recovered. For most of the $r\in[0,1]$ domain,
the surface fluctuations are in the new universality class and are not in the
KPZ class, cf. Fig. 5. At early times, the Poisson regime dominates the growth
with a characteristic scale $t^{1/2}$ followed by the KPZ growth with a scale
$t^{1/3}$ (effectively, $r\sim 1$) within a moving finger of finite width, and
eventual transition to fluctuations with a scale of $t^{5/4}$ (effectively,
$r<1$). For finite $L$, this transition occurs at $r^{*}(L)<1$. However, in
the thermodynamics limit $L\rightarrow\infty$, the transition value
$r^{*}(L)\rightarrow 1$ because the random depositions would cover only a
finite part of the lattice. This implies that the KPZ class is an unstable
point of the dynamics that occurs only at $r=1$ if $L$ is infinite.

Figure 5: Interface width $w$ as a function of time for system size $L=10^{3}$
and different propensity decay constants $r$. The growth exponent changes from
the KPZ value of $\beta=1/3$ to BDM value $\beta=5/4$ as the propensity decay
rate $r$ deviates from $r=1$. For $r=1$ and for very small time, the width
exhibits the Poisson scaling with $\beta=1/2$.

Conclusion. We numerically and analytically studied a model of surface growth
with memory. Introduction of memory breaks the temporal locality of the
deposition process, so that deposition at the current time is dependent on the
history of prior deposition events. This leads to emergence of a new size
exponent $\gamma$, which captures the random walk nature of the deposition
process at long times, and to changes in the values of the growth exponent
($\beta=5/4$) and the roughening exponent ($\alpha=2$). These exponent result
in a new scaling law $z=\frac{\alpha+\gamma}{\beta}=2$, which generalized the
classical scaling law $z=\alpha/\beta$. In other words, BDM is a surface
growth process that does not belong to the KPZ universality class.

In the standard KPZ and EW universality classes, there is no correlation in
the deposition process, so that the position of the next deposition is
independent from the positions of all past depositions. By including the
propensity, we introduce such correlations. The ensuing universality class
differs from the KPZ and the EW classes, and from their various well-known
modifications Medina  _et al._ (1989); Das Sarma and Tamborenea (1991); Wolf
and Villain (1990); Rácz  _et al._ (1991); Sun  _et al._ (1989); Lai and Das
Sarma (1991); Villain (1991). This is because our novel class changes the
dimensionality of the dynamics by introducing additional dynamical variables
$\pi$ in addition to $h$.

While our model was inspired by biological systems, it is unclear if the
discovered universality class is relevant to them. In order to verify this, it
is necessary to explore large spatiotemporal scales that are beyond the
typical scales probed in current experiments. For the Dictyostelium discoideum
system, tracking the front of the AMP waves on time scales of hours and
colonies with radii of order a meter might be necessary to test our predicted
exponents. We hope that such experiments will provide exciting new insights in
interface growth phenomena.

###### Acknowledgements.

IN thanks Mehran Kardar and Fereydoon Family for useful discussions. This work
was supported in part by NSF Grants No. 2010524, 2014173, and by the Simons
Foundation.

## References

  * Barabási and Stanley (1995) A. L. Barabási and H. E. Stanley,  _Fractal Concepts in Surface Growth_ (Cambridge University Press, Cambridge, 1995).
  * Family (1986) F. Family, Journal of Physics A: Mathematical and General 19, L441 (1986).
  * Kardar  _et al._ (1986) M. Kardar, G. Parisi, and Y.-C. Zhang, Physical Review Letters 56, 889 (1986).
  * Family and Vicsek (1985) F. Family and T. Vicsek, Journal of Physics A: Mathematical and General 18, L75 (1985).
  * Wang  _et al._ (2012) C. J. Wang, A. Bergmann, B. Lin, K. Kim, and A. Levchenko, Science Signaling 5, ra17 (2012).
  * Prindle  _et al._ (2015) A. Prindle, J. Liu, M. Asally, S. Ly, J. Garcia-Ojalvo, and G. Suel, Nature 527, 59 (2015).
  * Martinez-Corral  _et al._ (2018) R. Martinez-Corral, J. Liu, G. M. Süel, and J. Garcia-Ojalvo, Proceedings of the National Academy of Sciences 115, E8333 (2018).
  * Witten and Sander (1983) T. Witten and L. Sander, Phys Rev B 27, 5686 (1983).
  * Medina  _et al._ (1989) E. Medina, T. Hwa, M. Kardar, and Y.-C. Zhang, Physical Review A 39, 3053 (1989).
  * Das Sarma and Tamborenea (1991) S. Das Sarma and P. Tamborenea, Physical Review Letters 66, 325 (1991).
  * Wolf and Villain (1990) D. E. Wolf and J. Villain, Europhysics Letters (EPL) 13, 389 (1990).
  * Rácz  _et al._ (1991) Z. Rácz, M. Siegert, D. Liu, and M. Plischke, Physical Review A 43, 5275 (1991).
  * Sun  _et al._ (1989) T. Sun, H. Guo, and M. Grant, Physical Review A 40, 6763 (1989).
  * Lai and Das Sarma (1991) Z. W. Lai and S. Das Sarma, Physical Review Letters 66, 2348 (1991).
  * Villain (1991) J. Villain, J. Phys. I France 1, 19 (1991).

## Appendix

Solving the propensity recursion relation. Multiplying the recursion relation
Eq. (10) by the summing factor $(\frac{L-3}{L}r)^{-N-1}$ and summing from
$n=0$ to $n=N-1$, we obtain a telescoping sum, which evaluates to

$\pi(N)=\pi(0)\left(\frac{L-3}{L}r\right)^{N-1}+\frac{3}{L}\sum_{n=0}^{N-1}\left(\frac{L-3}{L}r\right)^{n}.$
(16)

Rewriting the first term of the above expression and the result of the
remaining geometric sum in the exponential form yields

$\pi(N)=\left(\frac{L}{(L-3)r}-\frac{3}{L-(L-3)r}\right)e^{-N\ln\left(\frac{L}{(L-3)r}\right)}\\\
+\frac{3}{L-(L-3)r}.$ (17)

From the first term, we obtain the propensity decay time scale

$N_{1/e}=\frac{1}{\ln\left(\frac{L}{(L-3)r}\right)}\approx\frac{1}{\ln\left(\frac{1}{r}\right)},\;\mbox{for
}L\gg 1.$ (18)

Thus $\pi(N)$ exponentially decays to

$\pi_{*}=\frac{3}{L-(L-3)r}$ (19)

on the time scale $\mathcal{O}(N_{1/e})$. In the limit $r\rightarrow 1$ and
$L\gg 1$, the time scale $N_{1/e}\rightarrow\infty$. That is, the propensity
remains at the fixed value of $\pi\approx 1$ and no decay occurs, consistent
with the regular Ballistic Deposition process.

Computing deposition probabilities. From Eq. (7), we deduce that if site $j$
receives a deposition at step $N$, then the probability that site $i$ will
receive a deposition is

$\displaystyle\mathcal{P}[i,N+1]$
$\displaystyle=\frac{\pi_{i}(N+1)}{\sum_{i=1}^{L}\pi_{i}(N+1)}=\frac{\pi_{i}(N+1)}{L\pi(N+1)}$
(20)
$\displaystyle\approx\bigg{\\{}\begin{array}[]{ll}\frac{1}{(L-3)r\pi(N)+3},&\text{for}\;j-1\leq
i\leq j+1\\\ \frac{r\pi(N)}{(L-3)r\pi(N)+3},&\text{otherwise.}\end{array}$
(23)

However, for $N\gg\frac{1}{\ln(1/r)}$, the propensity
$\pi(N)\approx\pi_{*}=\frac{3}{L-(L-3)r}$ and the probability of a deposition
at site $i$ becomes

$\mathcal{P}[i,N+1]\approx\bigg{\\{}\begin{array}[]{ll}\frac{1}{3}-\frac{L-3}{3L}r,&\text{for}\;j-1\leq
i\leq j+1\\\ \frac{r}{L},&\text{otherwise.}\end{array}$ (24)

As a check, we see that the probability that any site receives a deposition is
one

$\sum_{i=1}^{L}\mathcal{P}[i,N+1]=(L-3)\frac{r}{L}+3\left(\frac{1}{3}-\frac{L-3}{3L}r\right)=1.$

Furthermore, using Eq. (24), we see that

$\sum_{\begin{subarray}{c}j\not\in\\{i-1,i,i+1\\}\\\ 1\leq j\leq
L\end{subarray}}\mathcal{P}[j,N+1|i,N]=\frac{L-3}{L}r\approx r\ll 1$ (25)

for $r\ll 1$. Therefore, the position $x_{N}$ of the deposition at step $N$
follows an unbiased random walk in this regime.

Expanding the random walk regime. The steady state propensity $\pi_{*}$ in
practice is not spread out over the entire lattice. Instead
$L\pi_{*}=3(1-\frac{L-3}{L}r)^{-1}$ sites have propensity almost one, and the
rest of the lattice has zero propensity. This motivates the definition of time
as $t=\eta\frac{N}{L\pi_{*}}$ shown in Eq. (11) in the main text. In the limit
$L\pi_{*}\ll L$, the propensity process is made of multiple fingers of
cumulative size $L\pi_{*}$, which all are performing random walks. These
fingers dynamically merge and split as particles are deposited randomly. This
has the effect that, outside these fingers, the probability of a deposition is
zero and hence our dynamical exponents will hold in the significantly larger
regime $L\pi_{*}\ll L$ or, equivalently, $\frac{3}{1-r}\ll L.$

Extracting exponents from data. To estimate the growth exponent $\beta$, we
compute the mean width $\langle w(N)\rangle=\frac{1}{n}\sum_{i=1}^{n}w_{i}(N)$
of $n$ realizations of width $\\{w_{1}(N),\cdots,w_{n}(N)\\}$ obtained from
$n$ realizations of the height $\\{h_{1}(N),\cdots,h_{n}(N)\\}$ according to
Eq. (1). To ensure that the estimated value of the growth exponent remains in
the growth regime and is unaffected by cross-over effects, we limit the range
of time used in the estimation to $N\in[3\cdot 10^{2},3\cdot 10^{4}]$.
According to Eqs. 13 and 14, the mean width in the growth regime is $\langle
w(N)\rangle\sim L^{-\gamma}N^{\beta}$. Therefore, linear regression obtains
the slopes $\beta$ and $\gamma$ of the plane $\ln w(N)=\beta\ln N-\gamma\ln
L+k$ when regressed against $\ln N$ and $\ln L$ respectively. The slopes
obtain values of $\beta\approx 1.25\pm 0.03$ and $\gamma\approx 0.54\pm 0.09$.

To determine the size of the fluctuations around the estimated value of
$\beta$ for a fixed substrate length $L$, we use the covariance matrix
$\Sigma_{\beta,\Delta}$ of the parameters $\beta$ and $\Delta=-\gamma\ln L+k$.
The covariance matrix is $\Sigma_{\beta,\Delta}\approx
R^{-1}(R^{-1})^{T}\frac{|\vec{e_{res}}|^{2}}{df}$ where $R$ is the triangular
factor from a $QR$ decomposition of the Vandermonde matrix of $\ln(N)$,
$\vec{e_{res}}$ is the vector of residuals between the data and the fitting
line, and $df=2$ is the number of degrees of freedom. The quantity
$(\Sigma_{\beta,\Delta})_{\beta,\beta}^{1/2}$ provides the standard deviation
on $\beta$. A similar procedure is followed when we regress on $-\gamma\ln
L+k$ against $\ln L$ to find $\gamma$ and its standard deviation.

To determine the roughening exponent $\alpha$, we note that $\langle
w(t)\rangle\sim L^{\alpha}$ in the saturated regime. To avoid a bias in the
estimate of $\alpha$ due to the transition from growth to saturation, we limit
the time range used in the estimate to $N\in I_{L}=[2L^{2},10L^{2}]$ for
lattice length $L$. For a fixed lattice length $L$, the width in the
saturation regime fluctuates over the interval $I_{L}$. In this regime, the
mean width is obtained from the relation $\langle
w_{\rm{sat}}\rangle_{I_{L}}=\frac{1}{|I_{L}|}\sum_{N\in I_{L}}\langle
w(N)\rangle$, where $|I_{L}|$ is the length of the interval $I_{L}$ used for
the estimate of $w_{sat}$ of the lattice of length $L$. Using linear
regression, the value of the slope of the line $\ln\langle
w_{\rm{sat}}\rangle=\alpha\ln L+\lambda$ gives $\alpha\approx 2.0\pm 0.18$ as
seen in Fig. 3, in agreement with the value of $\alpha$ obtained analytically.


# SEMI-SUPERVISED LEARNING FOR HYPERSPECTRAL IMAGES BY NON PARAMETRICALLY
PREDICTING VIEW ASSIGNMENTCRediT

###### Abstract

Hyperspectral image (HSI) classification is gaining a lot of momentum in
present time because of high inherent spectral information within the images.
However, these images suffer from the problem of curse of dimensionality and
usually require a large number samples for tasks such as classification,
especially in supervised setting. Recently, to effectively train the deep
learning models with minimal labelled samples, the unlabeled samples are also
being leveraged in self-supervised and semi-supervised setting. In this work,
we leverage the idea of semi-supervised learning to assist the discriminative
self-supervised pretraining of the models. The proposed method takes different
augmented views of the unlabeled samples as input and assigns them the same
pseudo-label corresponding to the labelled sample from the downstream task. We
train our model on two HSI datasets, namely Houston dataset (from data fusion
contest, 2013) and Pavia university dataset, and show that the proposed
approach performs better than self-supervised approach and supervised
training.

Index Terms—  Hyperspectral images, self-supervised learning, semi-supervised
learning

##  1 Introduction

With the innovation in the sensing technologies, we are continuously
witnessing the increase in the amount of data being collected in the remote
sensing domain. The domain of hyperspectral imaging in particular has been
under significant progress with images being generated of high spectral and
spatial resolution. However, the acquisition of humongous data leads to the
challenges of data processing. With the current technology, most of the data
processing task, specifically on a larger scale, are religiously handled using
algorithms from deep learning (DL). Even though DL techniques have shown to
perform brilliantly with the big data, most of the applications, specifically
those from supervised learning require large number of annotated samples.
Since data annotations depend on manual interference, it becomes necessary to
come up with the techniques that rely on limited samples for a decent
performance. Self-supervised and semi-supervised learning have shown to be
efficient learning paradigms for such limited label learning, where the models
are trained by leveraging the information inherent in the unlabeled data.

Fig. 1: The figure shows the schematic of the PAWS model for semi-supervised
pretraining. From the HSI, we obtain the unlabelled overlapping patches for
anchor and positive sets. These patches pass through the augmentation function
$g(\phi)$ to get the augmented representations. The augmented anchor and
positive samples are sent through the encoder $f(\theta)$ to obtain the
embedding $\hat{z}_{U}^{A}$ and $\hat{z}_{U}^{P}$. Similarly, for the labelled
sample, the embedding $z_{L}$ is obtained. $\hat{z}_{U}^{A}$ and
$\hat{z}_{U}^{P}$ are compared with $z_{L}$ using a non-parametric classifier
$C_{NP}$. The pseudo-label probabilities obtained after classification are
then compared using the cross-entropy loss on which the model is trained.

Recently, several works pertaining to self-supervised learning have been
studied with regards to hyperspectral image classification. One of the pioneer
works in the self-supervised learning domain is presented in [1], where the
authors propose a generative SSL based approach for HSI classification. Here,
the network is initially pretrained as an autoencoder to reconstruct the
original 3D HSI patch. The encoder part of the pretrained model is then used
for classification of HSI samples. [2] proposed a method for self-supervised
learning in HSI classification. Their method was inspired from Barlow Twins
method of SSL, where the pre-training happens by minimising the distance
between the cross-correlation matrix between the embedding of the two
augmented views and the ideal correlation matrix of HSI samples. Similarly,
[3] presented a work leveraging the idea of bootstrap your own latent (BYOL)
in HSI classification. Additionally, they introduced the idea of random
occlusion for augmentation in multiple views.

Most of the works mentioned above purely relied on the idea of self-supervised
learning only. However, it was proposed in [4] that an additional guiding
information could be provided for pretraining by leveraging the training
samples that would be anyways available in the groundtruth. Their work
focussed on minimising a consistency loss between the pseudo-labels
corresponding to the different augmented views, that are assigned with respect
to the labelled samples from the groundtruth (where, they termed their
approach as PAWS). Based on the aforementioned concept, we take an opportunity
to build on the idea of semi-supervised learning for HSI classification, in
the current research work. Our contributions are as follows:

  * •

We extend the idea of PAWS in the domain of hyperspectral image
classification, where we show its performance compared to supervised and self-
supervised algorithms.

  * •

We evaluate our approach on Houston 2013 dataset in different settings (with
and without data augmentations) to showcase its performance.

##  2 Methodology

Let $\mathcal{X}\in\mathbb{R}^{M\times N\times B}$ represent the hyperspectral
image with $M$, $N$ and $B$ the number of rows, columns and channels
respectively. $\mathbf{x}_{U}^{j}\in\mathbb{R}^{p\times p\times B}$ represent
the unlabelled samples, while $\mathbf{x}^{i}_{L}\in\mathbb{R}^{p\times
p\times B}$ represent the labelled samples, with the labels of the central
pixel assigned to each sample. Here, $p$ represents the spatial dimension of
the sample. Let $y^{i}_{L}\in\mathcal{Y}_{L}$ represent the labels associated
with the training samples. Here, $i\in\\{1,2,...N_{L}\\}$ and
$j\in\\{1,2,...N_{U}\\}$, where $N_{L}$ and $N_{U}$ is the number of labelled
and unlabelled samples respectively. The training process is divided in two
stages, namely pretraining and classification, that are discussed in the
subsequent sections. The schematic of the proposed approach is presented in
Fig. 1.

###  2.1 Pretraining

This section explains the semi-supervised pretraining of the proposed PAWS
model. Let $(x^{i})^{A}_{U}\in\mathbb{R}^{p\times p\times B}$ denote the
anchor view and $(x^{i})^{P}_{U}\in\mathbb{R}^{p\times p\times B}$ denote the
positive view, (which spatially overlap). The two views are passed through a
non-trainable probabilistic augmentation function $g(\phi)$ to obtain
respective augmented views as $(\hat{x}^{i})^{A}_{U}$ and
$(\hat{x}^{i})^{P}_{U}$. Here, $\phi$ is the probability vector to choose the
respective augmentation. Let $f(\theta)$ denote the encoder that maps the
given hyperspectral patch to the hidden representation
($f(\theta):\mathbb{R}^{p\times p\times B}\xrightarrow{}\mathbb{R}^{d}$). We
have used two kinds of encoders for the experimets. One of them is derived
from a WideResNet [5] architecture with input layer changed to accommodate
hyperspectral data. The other encoder is a fully convolutional framework with
the initial layer being a 3D convolution layer and the later layers followed
by three depthwise separable convolution layers, thus resulting in the $d$
dimensional vectors $(\hat{z}^{i})^{A}_{U}$ and $(\hat{z}^{i})^{P}_{U}$.
Simultaneously, for a labelled sample $(x^{j})_{L}\in\mathbb{R}^{p\times
p\times B}$ (acquired from labelled support set), we get the representation
$(z^{j})_{L}$.

The support representation $(z^{i})_{L}$ is then compared with the anchor and
positive representations $(\hat{x}^{i})^{A}_{U}$ and $(\hat{x}^{i})^{P}_{U}$
using a cosine similarity based non-parametric soft nearest neighbour (SNN)
classifier [6] ($C_{NP}$), given as:

$(\hat{p}^{j})^{A}=C_{NP}({z^{j}_{U},\mathbf{z}_{L}})=\sigma_{\tau}((z^{j})^{A}_{U}\mathbf{z}^{T}_{L})\mathcal{Y}_{L}$
(1)

Similarly, $(\hat{p}^{j})^{P}$ can be calculated as well. Here, $\sigma$ is
the softmax activation and $\tau(>0)$ is the temperature. The calculated
probabilities are then sharpened to avoid representation collapse and get
confident predictions. The sharpening function is denoted as:

$[\rho(\hat{p}^{j})]^{k}=\frac{([p^{j}]_{k})^{\frac{1}{T}}}{\sum_{t=1}^{K}([p^{t}]_{k})^{\frac{1}{T}}}$
(2)

Here $k\in\\{1,2,...,K\\}$, where $K$ is the number of classes. For training
the model, we simultaneously consider two cross entropy loss terms between
$(\hat{p}^{j})^{P}$ and $(\hat{p}^{j})^{A}$. Additionally, an auto-entropy
based regularizer derived from the average sharpened predictions is included.
This is to ensure that the average prediction is close to the the mean
distribution. The final loss is written as:

$\mathcal{L}_{SSL}=\frac{1}{2n}\sum_{i=1}^{n}(\mathcal{E}(\rho((\hat{p}^{j})^{A}),(\hat{p}^{j})^{P})+\mathcal{E}(\rho((\hat{p}^{j})^{P}),(\hat{p}^{j})^{A}))-\mathcal{E}(\bar{p})$
(3)

Here, $\mathcal{E}$ denotes the entropy function, while $\bar{p}$ is the
average probability of the predictions, given as:

$\bar{p}=\frac{1}{2n}\sum_{i=1}^{n}(\rho((\hat{p}^{j})^{P}),\rho((\hat{p}^{j})^{A}))$
(4)

In the cross entropy loss, while training, the gradients are not calculated
with respect to the sharpened targets.

###  2.2 Classification

After pretraining, the model is evaluated for the task of landuse/land cover
classification. We have applied three techniques as classification benchmarks:

  1. 1.

Linear layer: A fully connected layer is appended over the existing model. The
weights of the pretrained model are frozen, while only the weights of the
final layer are modified using training samples. The model is then evaluated
on the test samples.

  2. 2.

Fine tuning: It is also akin to the previous classifier, but instead of
freezing the weights, all the weights are simultaneously modified using
training samples. The model is then evaluated on the test samples. The
schematic of linear classification and finetuning can be seen in Fig. 2.

  3. 3.

Soft nearest neighbor (SNN) classifier: Here, the trained model simply acts as
a feature extractor without further downstream optimization. Both training and
test samples are passed through the pretrained model. The test samples are
then compared with the training samples using a cosine similarity based
classifier (such as classifier $C_{NP}$).

Fig. 2: Schematic of linear classification and finetuning after PAWS based
pretraining.

##  3 EXPERIMENTS AND RESULTS

###  3.1 Datasets

We have considered the following two datasets for our experiments:

Houston dataset: This dataset is from data fusion contest, $2013$. The spatial
extent of the HSI is $349$ $\times$ $1905$ and is composed of $144$ bands. The
dataset consists of $2832$ training samples and $12197$ test samples,
distributed over $15$ land use/land cover classes. For our experiments, we
have selected $100$ samples per class from the training samples as support set
(overall $1500$ patches). For the anchor and positive points, we have sampled
out $71416$. The HSI and the corresponding groundtruth are presented in Fig. 3
[7].

Pavia University dataset: The hyperspectral image has the dimensions $610$
$\times$ $340$ $\times$ $103$, while the number of labelled samples is
$42776$. For the anchor and positive points, we have sampled out $99000$
points, while the support set and test set are formed of $900$ ($100$ per
class) and $41876$ points respectively, with the patch size of $9$. The HSI
and the corresponding groundtruth are presented in Fig. 4 [2].

In both the datasets, the anchor and positive patches overlap by $67$%.

Fig. 3: Houston 2013 dataset. False colour composite (Left). Groundtruth
(Right)

Fig. 4: Pavia University dataset. False colour composite (Left). Groundtruth
(Right)

###  3.2 Training protocols

All the deep learning models use LARS optimizer [8] for pretraining stage.
During classification, with linear layer as well as with fine tuning,
stochastic gradient descent optimizer is used. In the experiments, the values
of temperatures $\tau$ (in softmax) and $T$ (during sharpening) are fixed to
$0.25$ and $0.10$ respectively. The number of epochs are fixed to 50 for the
model pretraining, linear classification as well as finetuning. For every
unlabeled sample, following augmentations have been applied:

  1. 1.

Spectral: Random channel swapping, random channel dropping, channel intensity
suppression, random channel averaging for a fixed number of channels

  2. 2.

Spatial: Flipping (horizontal, vertical and mirror), random cropping, random
rotation

  3. 3.

Spectral-spatial: Pixel vector removal, noise introduction across channels and
spatial dimension

###  3.3 Results and Discussions

The results are provided in Tables 1 and 2 for Houston 13 and Pavia university
datasets respectively. For Houston 13 dataset, a custom CNN is used, while the
results of Pavia University dataset have been presented when trained on
WideResNet. Column 1 indicates the model specifics. Column 2 denotes if
augmentations have been applied. Column 3 represents the choice of classifier
for downstream land cover classification, and corresponding overall accuracy
values are listed in Column 4. It is visible that the proposed semi-supervised
approach performs better than the supervised approach, both in the linear
layer setting as well as fine tuning setting. The method also performs better
than one of the recently attempted self-supervised approach based on Barlow
Twins loss. As baseline benchmark, SNN classification performance surpasses
when the classifier is trained on features extracted from the pretrained model
using our proposed approach. From Table 2, it is also visible, that the
accuracy on supervised classification is relatively much lower than the other
models. This could be attributed to the large number of parameters in
WideResNet in comparison to the custom CNN model. Best performances are
highlighted in bold.

Table 1: Accuracy analysis for the proposed semi-supervised PAWS model on Houston 2013 dataset. Encoder | Augmentations | Classifier | Accuracy
---|---|---|---
CNN | No | Supervised | 79.10%
Barlow Twins [2] | Yes | Fine Tune | 77.14%
None | No | Linear | 64.21%
PAWS trained | Yes | Linear | 80.92%
PAWS trained | Yes | Fine Tune |  83.12%
None | No | SNN | 32.63%
Untrained | No | SNN | 34.28%
PAWS trained | Yes | SNN |  75.31%
Table 2: Accuracy analysis for the proposed semi-supervised PAWS model on Pavia University dataset. Encoder | Augmentations | Classifier | Accuracy
---|---|---|---
CNN | No | Supervised | 21.38%
Barlow Twins [2] | Yes | Linear | 82.44%
None | No | Linear | 74.12%
PAWS trained | Yes | Linear |  83.64%
None | No | SNN | 50.12%
Untrained | No | SNN | 46.33%
PAWS trained | Yes | SNN |  70.34%

##  4 Conclusions

In this paper, we apply the method of semi-supervised learning (based on PAWS
approach) for hyperspectral image classification. Our method leverages the
labelled samples (available in the downstream task) to effectively guide the
self-supervised pretraining process before the classification. We observe that
the proposed model outperforms the supervised as well as self-supervised
classification task, both in parametric and non-parametric settings. Motivated
by our findings, we plan to extend our experiments to large-scale missions
such as DLR’s EnMAP satellite launched in April 2021 and recently moved into
the operational phase.

## Acknowledgement

This project is supported by the German Federal Ministry of Education and
Research (BMBF) in the framework of the International Future AI lab “AI4EO –
Artificial Intelligence for Earth Observation: Reasoning, Uncertainties,
Ethics and Beyond” (grant number: 01DD20001). Additionally, this work is also
supported by the Helmholtz Association through the Framework of HelmholtzAI,
grant ID: ZT-I-PF- 5-01 – Local Unit Munich Unit @Aeronautics, Space and
Transport (MASTr).

## References

  * [1] Lichao Mou, Pedram Ghamisi, and Xiao Xiang Zhu,  “Unsupervised spectral–spatial feature learning via deep residual conv–deconv network for hyperspectral image classification,”  IEEE Transactions on Geoscience and Remote Sensing, vol. 56, no. 1, pp. 391–406, 2017.
  * [2] Nassim Ait Ali Braham, Lichao Mou, Jocelyn Chanussot, Julien Mairal, and Xiao Xiang Zhu,  “Self supervised learning for few shot hyperspectral image classification,”  in IGARSS 2022-2022 IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2022, pp. 267–270.
  * [3] Jinhui Li, Xiaorun Li, Zeyu Cao, and Liaoying Zhao,  “ROBYOL: Random-occlusion-based BYOL for hyperspectral image classification,”  IEEE Geoscience and Remote Sensing Letters, vol. 19, pp. 1–5, 2022\.
  * [4] Mahmoud Assran, Mathilde Caron, Ishan Misra, Piotr Bojanowski, Armand Joulin, Nicolas Ballas, and Michael Rabbat,  “Semi-supervised learning of visual features by non-parametrically predicting view assignments with support samples,”  in Proceedings of the IEEE/CVF International Conference on Computer Vision, 2021, pp. 8443–8452.
  * [5] Sergey Zagoruyko and Nikos Komodakis,  “Wide residual networks,”  arXiv preprint arXiv:1605.07146, 2016.
  * [6] Ruslan Salakhutdinov and Geoff Hinton,  “Learning a nonlinear embedding by preserving class neighbourhood structure,”  in Artificial intelligence and statistics. PMLR, 2007, pp. 412–419.
  * [7] Rupak Bose, Shivam Pande, and Biplab Banerjee,  “Two headed dragons: Multimodal fusion and cross modal transactions,”  in 2021 IEEE International Conference on Image Processing (ICIP). IEEE, 2021, pp. 2893–2897.
  * [8] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh,  “Large batch optimization for deep learning: Training BERT in 76 minutes,”  arXiv preprint arXiv:1904.00962, 2019.