# Approximating Multi-Dimensional and Multiband Signals

Yuhan Li, Tianyao Huang∗, Yimin Liu and Xiqin Wang This work was supported by
the National Natural Science Foundation of China under Grants 62171259. T.
Huang is with the School of Computer and Communication Engineering, University
of Science and Technology Beijing, Beijing, China. Y. Liu, Xiqin Wang, and Y.
Li are with the EE Department, Tsinghua University, Beijing, China.
∗Correspondence<EMAIL_ADDRESS>
###### Abstract

We study the problem of representing a discrete tensor that comes from finite
uniform samplings of a multi-dimensional and multiband analog signal.
Particularly, we consider two typical cases in which the shape of the subbands
is cubic or parallelepipedic. For the cubic case, by examining the spectrum of
its corresponding time- and band-limited operators, we obtain a low-
dimensional optimal dictionary to represent the original tensor. We further
prove that the optimal dictionary can be approximated by the famous discrete
prolate spheroidal sequences (DPSSs) with certain modulation, leading to an
efficient constructing method. For the parallelepipedic case, we show that
there also exists a low-dimensional dictionary to represent the original
tensor. We present rigorous proof that the numbers of atoms in both
dictionaries are approximately equal to the dot of the total number of
samplings and the total volume of the subbands. Our derivations are mainly
focused on the 2-dimensional (2-D) scenarios but can be naturally extended to
high dimensions.

###### Index Terms:

Multi-dimensional signals, multiband signals, discrete prolate spheroidal
sequences, eigenvalues

##  I Introduction

A fundamental problem in signal processing is to represent or approximate the
signal with a few atoms from a certain dictionary [1]. Such a representation
or approximation benefits many tasks including reconstruction [2], denoising
[3], and classification [4]. The Fourier basis is a prevalent choice for
signal representation, as it often captures signals efficiently due to the
majority of their Fourier coefficients being negligible or null [5]. However,
the Fourier basis is not always the optimal choice for some natural signals,
especially the multiband signal, encompassing multiple bands with non-
negligible bandwidth.

Multiband signals have been widely concerned in communication [6, 7] and radar
[8, 9] applications. The multiband signals possess a special structure in the
frequency domain, whose spectral support set is constrained to certain
continuous intervals [10, 6], that is, there is no energy or information
outside these frequency intervals. These intervals are called bands. Besides,
when there is only one interval, the multiband signals degrade to a band-
limited signal.

For band-limited signals, some works have managed to achieve optimal
approximation using prolate spheroidal wave functions (PSWFs) [11, 12, 13] for
in the continuous scenarios and DPSSs [14, 15, 16] as well as periodic
discrete prolate spheroidal sequences (PDPSSs) [17, 18] in the discrete
scenarios. These functions stem from the eigenvectors of the corresponding
time- and band-limiting operators or covariance matrices [17]. The
distribution of their eigenvalues performs a sharp phase transition from 1 to
0, that is, most eigenvalues cluster to 1 or 0. The number of the non-zero
eigenvalues is roughly equal to the product of the number of samplings and the
proportion of the supporting set. Such a property leads to a natural low-
dimension dictionary or basis to approximate the original band-limited signal
and thus inspires wide applications [1]. The analysis of DPSSs is extended to
multiband signals in [1], which shows that the multiband signals hold similar
distributions of eigenvalues as the band-limited signals. The low-dimension
dictionary for the multiband signals can be approximated by the dictionaries
from different band-limited signals with certain frequency modulations.

Yet, these works focus on the 1-dimensional (1-D) signal and lack discussions
on multi-dimensional signals. Here, we mean the domain of the signals is
“multi-dimensional” rather than the range, e.g. a vector is 1-D and a matrix
is 2-D in the context of our framework. The multi-dimensional signals often
occur in array signal processing, image processing, and other practical
scenarios [6, 19]. These signals are distributed across multi-dimensional
frequency domains, and exhibit complicated coupling relationships among these
domains, rendering their analysis notably challenging. Most works [20, 21]
consider a specific distribution and tend to find a near-optimal sampling
method. The work [19] extends the results from [22] to obtain an oblivious
sampling method for the Fourier-constrained multi-dimensional signal. Such a
method may fall sub-optimal for a specially structured signal like the
multiband signal.

In this paper, we focus on the multi-dimensional multiband signals.
Particularly, we mainly consider two typical cases where the uni-band is cubic
or parallelepipedic, respectively. The first cubic case is prevalent in radar
signal processing scenarios [9, 23], wherein the processing typically involves
discretizing the signal domain into grid points. Each grid point encapsulates
the signals within its spatial cubic block. The second case is encountered in
spatiotemporal adaptive processing [24]. We primarily discuss scenarios in the
more common two-dimensional setting, with the conclusion naturally extending
to higher dimensions.

Our contribution can be concluded as follows

  * •

For the multi-dimensional multiband signal whose subbands are cubic, we
investigate its “covariance matrix”, analyze the distribution of its
eigenvalues, and give the number of atoms enough to approximate the original
signal in the sense of mean squared error (MSE). Strict proofs are provided.

  * •

We show that such a multi-dimensional multiband dictionary formed by the
optimal atoms can be approximated with modulated base-band DPSSs. The base-
band ones can be constructed more easily, enhancing the practical value.

  * •

For the multi-dimensional multiband signal whose subbands are parallelepipeds,
we theoretically analyze its “covariance matrix” and show it possesses
clustering property in the distribution of eigenvalues, which is almost the
same as those with cubic subbands.

We remark that our work is greatly inspired by [1], which focuses on the
unidimensional multiband signal. However, it is not trivial to extrapolate
their findings to multi-dimensional scenarios as the complicated geometry of
the subbands should be considered. This extension is challenging not only
because it increases the computational complexity within the proof process,
but also because it addresses the inter-dimensional coupling relationships for
parallelepipedic subbands.

The remaining chapters are arranged as follows. In Section II, we introduce
the model of one-dimensional multiband signals and existing theoretical
results. Then in Section III, we extend the one-dimensional model to multi-
dimensional multiband signals and present the notations. Section IV-A provides
our theoretical results concerning the properties of multi-dimensional
multiband signals. The final section summarizes the entire paper.

In this paper, boldface letters like $\bm{x}$ and $\bm{B}$, except $\bm{W}$,
are employed to denote tensors (including vectors and matrices). We utilize
$\bm{W}$, $\mathbb{W}$, and $\mathbb{W}^{\Diamond}$, along with their
superscript or subscript variations, to indicate regions in the Fourier
domain. The denotations $\|\bm{W}\|$, $\|\mathbb{W}\|$, and
$\|\mathbb{W}^{\Diamond}\|$ represent the Lebesgue measure of the regions. The
Frobenius norm of a tensor, denoted as $\|\cdot\|_{F}$, is indeed defined as
the square root of the sum of the squares of all its elements.

##  II Preliminaries on 1-D Multiband Signal

In this part, we first present the mathematical formulation of 1-D multiband
signals. Subsequently, in order from simple to complex, we briefly review some
important properties of band-limited, band-pass, and multiband signals from
[1]. The band-limited and band-pass signals can be considered as special,
simpler forms of multiband signals.

To begin with, given an 1-D multiband analog signal $x(t)$, whose supporting
set on the frequency domain is defined as

$\mathbb{F}=\bigcup_{i=0}^{J-1}[F_{i}-B_{i}/2,F_{i}+B_{i}/2].$ (1)

Uniformly sampling the signal in the time interval $[0,NT_{s})$ with sampling
period $T_{s}$, we obtain a length-$N$ vector $\bm{x}$. Here, we assume that
the sampling period $T_{s}$ satisfies the minimum Nyquist sampling rate. The
sampled vector $\bm{x}$ also has a multiband structure as

$\bm{x}[n]=\int_{\mathbb{W}}\tilde{x}(f)e^{j2\pi
fn}\text{d}f,n=0,1,\dots,N-1,$ (2)

where the supporting set $\mathbb{W}$ is defined as

$\displaystyle\mathbb{W}=T_{s}\mathbb{F}$
$\displaystyle=\bigcup_{i=0}^{J-1}[T_{s}F_{i}-T_{s}B_{i}/2,F_{i}+T_{s}B_{i}/2]$
$\displaystyle=\bigcup_{i=0}^{J-1}[f_{j}-W_{j},f_{j}+W_{j}]\subset[-\frac{1}{2},\frac{1}{2}].$
(3)

The weight function
$\tilde{x}(f)=\frac{1}{T_{s}}X(\frac{f}{T_{s}}),|f|\leq\frac{1}{2}$, where
$X()$ is the expression of the Fourier transform of $x(t)$.

Existing works [1, 9] show that such finite-length multiband vector $\bm{x}$
has a certain structure that it can be approximated by a linear combination of
entries in a low-dimensional dictionary. It is assumed that $x(t)$ is a
stationary stochastic signal and its power spectrum after sampling is

$S_{xx}(f)=\left\\{\begin{aligned} &1,\ \ f\in\mathbb{W},\\\ &0,\ \
{\text{else}}.\end{aligned}\right.$ (4)

The covariance matrix $\bm{B}_{N,\mathbb{W}}$ of $\bm{x}$ is calculated as

$\displaystyle\bm{B}_{N,\mathbb{W}}[m,n]$
$\displaystyle=\int_{-\frac{1}{2}}^{\frac{1}{2}}S_{xx}(f)e^{j2\pi
f(m-n)}\text{d}f$ $\displaystyle=\int_{\mathbb{W}}e^{j2\pi f(m-n)}\text{d}f$
$\displaystyle=\sum_{i=0}^{J-1}e^{j2\pi f_{i}(m-n)}\frac{\sin(2\pi
W_{i}(m-n))}{\pi(m-n)}.$ (5)

A natural method to approximate $\bm{x}$ is performing principal component
analysis on the covariance matrix $\bm{B}_{N,\mathbb{W}}$.

###  II-A Band-limited Signal

Before dealing with the relatively complicated matrix $\bm{B}_{N,\mathbb{W}}$,
we consider a simple case where $\mathbb{W}=[-W,W],0<W<\frac{1}{2}$, i.e. the
signal $x(t)$ is a band-limited signal. We use the symbol $\bm{B}_{N,W}$ to
represent the covariance matrix in this simplified case. The
eigendecomposition of matrix $\bm{B}_{N,W}$ is

$\bm{B}_{N,W}=\bm{S}_{N,W}\bm{\Lambda}_{N,W}\bm{S}^{H}_{N,W},$ (6)

where the $l$-th column of $\bm{S}_{N,W}$ is the well-known DPSS vector
$\bm{s}^{(l)}_{N,W}$, and $\bm{\Lambda}_{N,W}$ is a diagonal matrix with the
$l$-th diagonal element being the $l$-th eigenvalue $\lambda_{N,W}^{(l)}$. The
eigenvalues have a clustering property as the following lemma states.

######  Lemma 1.

([16, 14]) 1\. Fixing $\epsilon\in(0,1)$, there exist constants
$C_{1}(W,\epsilon)$, $C_{2}(W,\epsilon)$ and integers $N_{1}(W,\epsilon)$ that

$\displaystyle 1-\lambda_{N,W}^{(l)}\leq
C_{1}(W,\epsilon)e^{-C_{2}(W,\epsilon)N},$ (7) $\displaystyle\forall
l\leq\lfloor 2NW(1-\epsilon)\rfloor$

for all $N\geq N_{1}(W,\epsilon)$.

2\. Fixing $\epsilon\in(0,\frac{1}{2W}-1)$, there exist constants
$C_{3}(W,\epsilon)$, $C_{4}(W,\epsilon)$ and integers $N_{2}(W,\epsilon)$ that

$\displaystyle\lambda_{N,W}^{(l)}\leq
C_{3}(W,\epsilon)e^{-C_{4}(W,\epsilon)N},$ (8) $\displaystyle\forall
l\geq\lceil 2NW(1+\epsilon)\rceil$

for all $N\geq N_{2}(W,\epsilon)$.

This lemma shows that there are approximately $2NW$ eigenvalues close to 1 and
the rest are close to 0. Consequently, one can use the first $2NW$
eigenvectors to construct a sparse approximate representation of $\bm{x}$.

###  II-B Band-pass Signal

Further, we consider the band-pass signal whose supporting set in the
frequency domain is $[f_{c}-W,f_{c}+W]$. The covariance matrix
$\bm{B}_{N,[-W+f_{c},W+f_{c}]}$ of such a signal can be viewed as
$\bm{B}_{N,W}$ with a frequency modulation, that is
$\bm{B}_{N,[-W+f_{c},W+f_{c}]}=\bm{E}_{f_{c}}\bm{B}_{N,W}\bm{E}_{f_{c}}^{H}$.
The modulation factor $\bm{E}_{f_{c}}$ is a diagonal matrix defined as

$\bm{E}_{f_{c}}[m,n]=\left\\{\begin{aligned} &e^{j2\pi f_{c}m},\ \ m=n,\\\
&0,\ \ m\neq n.\end{aligned}\right.$ (9)

From the special structure, it can be verified that

$\bm{B}_{N,[-W+f_{c},W+f_{c}]}=\bm{E}_{f_{c}}\bm{S}_{N,W}\bm{\Lambda}_{N,W}(\bm{E}_{f_{c}}\bm{S}_{N,W})^{H}.$
(10)

Therefore, $(\lambda_{N,W}^{(l)},\bm{E}_{f_{c}}\bm{s}_{N,W}^{(l)})$ is a pair
of eigenvalue and eigenvector of $\bm{B}_{N,[-W+f_{c},W+f_{c}]}$. Thus, its
eigenvalues have the same clustering property as Lemma 1 states.

###  II-C Multiband Signal

Though the above conclusions depict the clustering property of eigenvalues and
show the way to approximate band-limited and band-pass signals, the extension
to multiband signals is still hard. Based on a series of mathematical
techniques, [1] proves that $\bm{B}_{N,\mathbb{W}}$ also has a cluttering
phenomenon in its distribution of eigenvalues. The result is recited as
follows.

######  Theorem 2.

([1, Theorem 3.4]) Let $\mathbb{W}\subset[-\frac{1}{2},\frac{1}{2}]$ be formed
by $J$ disjoint intervals. 1\. Fix $\epsilon\in(0,1)$, there exist constants
$\hat{C}_{1}(\mathbb{W},\epsilon)$, $\hat{C}_{2}(\mathbb{W},\epsilon)$ and
integers $\hat{N}_{1}(\mathbb{W},\epsilon)$ that

$\displaystyle
1-\lambda_{N,\mathbb{W}}^{(l)}\leq\hat{C}_{1}(\mathbb{W},\epsilon)N^{2}e^{-\hat{C}_{2}(\mathbb{W},\epsilon)N},$
(11) $\displaystyle\forall l\leq J-1+\sum_{i}\lfloor
2NW_{i}(1-\epsilon)\rfloor$

for all $N\geq\hat{N}_{1}(\mathbb{W},\epsilon)$.

2\. Fix $\epsilon\in(0,\frac{1}{|\mathbb{W}|}-1)$, there exist constants
$\hat{C}_{3}(\mathbb{W},\epsilon)$, $\hat{C}_{4}(\mathbb{W},\epsilon)$ and
integers $\hat{N}_{2}(\mathbb{W},\epsilon)$ that

$\displaystyle\lambda_{N,\mathbb{W}}^{(l)}\leq\hat{C}_{3}(\mathbb{W},\epsilon)e^{-\hat{C}_{4}(\mathbb{W},\epsilon)N},$
(12) $\displaystyle\forall l\geq\sum_{i}\lceil 2NW_{i}(1+\epsilon)\rceil$

for all $N\geq\hat{N}_{2}(\mathbb{W},\epsilon)$.

Figure 1 offers an example of the above theorems. We consider an 1-D multiband
signal whose power spectrum is shown in Figure 1(a). The power spectrum
density is 1 in intervals $[-0.15,-0.05]$ and $[0.15,0.25]$, and is 0 in other
regions. Thus, the total measure $\|\mathbb{W}\|$ is $0.2$. Sample $N=256$
points evenly at intervals of 1 on this signal, and we can compute the
covariance matrix of the 256 samplings as (5). Figure 1(b) presents the
distribution of the eigenvalues of the covariance matrix. As stated in Theorem
2, about $N\|\mathbb{W}\|$ eigenvectors have eigenvalues near 1 while the
others have eigenvalues near 0.

(a) Power spectrum (b) The distribution of the eigenvalues

Figure 1: An example of 1-D multiband signal, whose energy is located in two
disjoint intervals on the frequency range $[=0.15,-0.05]$ and $[0.15,0.25]$.

Similarly, this theorem indicates that about $N\|\mathbb{W}\|$ fixed vectors
is enough to give an approximation for multiband signals whose supporting set
is $\mathbb{W}$.

##  III Multi-dimensional Multiband Signal

In this part, we formulate our problem in multi-dimensional cases, paving the
way for our theoretical analysis in the following sections. Different from 1-D
cases, the subbands in multi-dimensional cases have different shapes, among
which we concentrate on the cubic and parallelepipedic scenarios. Different
shapes with multi-dimensions increase the difficulty of analysis and symbolic
expression. Therefore, instead of directly investigating the covariance
matrix, we define a band and index-limited linear operator following [1] and
consider the eigenvalues of the operator, which are the same as those of the
covariance matrix.

We firstly focus on the $d$-dimensional signals $x(\bm{t})$ with cubic
subbands, which can be formulated by

$x(\bm{t})=\int_{\mathbb{F}}X(\bm{F})e^{j2\pi\left<\bm{F},\bm{t}\right>}\text{d}\bm{F},$
(13)

where the frequency vector $\bm{F}$ and the union of $J$ bands $\mathbb{F}$ is
given by

$\displaystyle\bm{F}$
$\displaystyle=\left[F^{[0]},F^{[1]},\cdots,F^{[d-1]}\right]^{T},$ (14)
$\displaystyle\mathbb{F}$
$\displaystyle=\bigcup_{i=0}^{J-1}\left[F^{[0]}_{i}-B^{[0]}_{i},F^{[0]}_{i}+B^{[0]}_{i}\right]\times\left[F^{[1]}_{i}-B^{[1]}_{i},F^{[1]}_{i}+B^{[1]}_{i}\right]$
$\displaystyle\times\cdots\times\left[F^{[n-1]}_{i}-B^{[n-1]}_{i},F^{[n-1]}_{i}+B^{[n-1]}_{i}\right]$
$\displaystyle=\bigcup_{i=0}^{J-1}\left[\bm{F}_{i}-\bm{B}_{i},\bm{F}_{i}+\bm{B}_{i}\right].$
(15)

Then let $\bm{x}$ denote the vector obtained by uniformly sampling $x(\bm{t})$
which satisfies the Nyquist sampling rate in each dimension with periods
$\bm{T}_{s}$. With $\mathcal{N}$ denoting
$\bigtimes_{i=0}^{d}\\{0,1,\dots,N_{i}-1\\}$, the sampled signal $\bm{x}$ is
given by

$\bm{x}[\bm{n}]=\int_{\mathbb{W}}\tilde{x}(\bm{f})e^{j2\pi\left<\bm{f},\bm{n}\right>}\text{d}\bm{f},\bm{n}\in\mathcal{N},$
(16)

where $\tilde{x}(\bm{f})$ is the scaled CTFT of $x(\bm{t})$ and the union of
sampled bands $\mathbb{W}$ is given by

$\mathbb{W}=\bm{T}_{s}\circ\mathbb{F}.$ (17)

We are interested in the dictionary of the signal $\bm{x}$, i.e., how many
tensors are enough to approximate $\bm{x}$. A natural approach is to examine
its covariance “matrix” and apply PCA. Yet, directly using the covariance
“matrix” brings inconvenience in both expressions and calculating. Below, we
construct an operator that has the same eigenvalues and eigen-tensors as the
covariance “matrix”.

To begin with, let
$\mathcal{B}_{\mathbb{W}}:\ell_{2}(\mathbb{Z}^{d})\rightarrow\ell_{2}(\mathbb{Z}^{d})$
denote the high-dimension multiband-limiting operator. We have

$\displaystyle\mathcal{B}_{\mathbb{W}}(y)[\bm{m}]$
$\displaystyle=\int_{\mathbb{W}}e^{j2\pi\left<\bm{f},\bm{m}\right>}\text{d}\bm{f}\star
y[\bm{m}]$ (18)
$\displaystyle=\sum_{\bm{n}=-\infty^{d}}^{\infty^{d}}\left(y[\bm{n}]\int_{\mathbb{W}}e^{j2\pi\left<\bm{f},(\bm{m-n})\right>}\text{d}\bm{f}\right).$

Further define the index-limiting operator
$\mathcal{I}_{\mathcal{N}}:\ell_{2}(\mathbb{Z}^{d})\rightarrow\mathbb{C}^{\times_{i=0}^{d-1}N_{i}}$
and its inverse operator $\mathcal{I}_{\mathcal{N}}^{*}$, where
$\mathcal{N}:=\\{0,1,\cdots,N_{0}-1\\}\times\\{0,1,\cdots,N_{1}-1\\}\times\cdots\times\\{0,1,\cdots,N_{d-1}-1\\}$

$\mathcal{I}_{\mathcal{N}}(y)[\bm{m}]=y[\bm{m}],\bm{m}\in\mathcal{N}$ (19)

$\mathcal{I}^{*}_{\mathcal{N}}(\bm{y})[\bm{m}]:=\begin{cases}&\bm{y}[\bm{m}],\bm{m}\in\mathcal{N}\\\
&0,\ \ \text{otherwise}.\end{cases}$ (20)

Combining these operators, we obtain the linear operator
$\mathcal{B}_{\bm{N},\mathbb{W}}$ which makes the signal $\bm{y}$ band-limited
and index-limited as

$\displaystyle\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y})[\bm{m}]$
$\displaystyle:=\mathcal{I}_{\bm{N}}(\mathcal{B}_{\mathbb{W}}(\mathcal{I}_{\bm{N}}^{*}(\bm{y})))[\bm{m}]$
(21)
$\displaystyle=\sum_{\bm{n}\in\mathcal{N}}\left(\bm{y}[\bm{n}]\int_{\mathbb{W}}e^{j2\pi\left<\bm{f},(\bm{m}-\bm{n})\right>\text{d}f}\right),\bm{m}\in\mathcal{N}.$

In multi-dimensional cases, for brevity, we use $\tilde{W}^{[j]}_{i}$ denote
the interval $[-W^{[j]}_{i}+f^{[j]}_{i},W^{[j]}_{i}+f^{[j]}_{i}]$, which
represent the range of the $i$-th narrow band in the $j$-th dimension. In 2-D
cases where $\bm{y}\in\mathbb{C}^{M\times N}$ is a matrix or 2-D tensor, one
can write $\mathcal{B}_{\bm{N},\mathbb{W}}$ as follows

$\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y}):=\sum_{i=0}^{J-1}\bm{B}_{M,\tilde{W}^{[0]}_{i}}\
\bm{y}\ \bm{B}^{T}_{N,\tilde{W}^{[1]}_{i}},$ (22)

or equivalently

$\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y}):=\text{ivec}_{\bm{y}}\left(\left(\sum_{i=0}^{J-1}\bm{B}_{N,\tilde{W}^{[1]}_{i}}\otimes\bm{B}_{M,\tilde{W}^{[0]}_{i}}\right)\text{vec}({\bm{y}})\right).$
(23)

Here, the function $\text{ivec}_{\bm{y}}(\cdot)$ rearranges a vector to a
tensor whose size is the same as $\bm{y}$. Then, in $d$-dimensional space, the
extended $\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y})$ can be defined as

$\displaystyle\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y})$
$\displaystyle:=\sum_{i=0}^{J-1}\text{ivec}_{\bm{y}}\left(\left(\bm{B}_{N_{d-1},\tilde{W}^{[d-1]}_{i}}\otimes\bm{B}_{N_{d-2},\tilde{W}^{[d-2]}_{i}}\right.\right.$
(24)
$\displaystyle\left.\left.\otimes\cdots\otimes\bm{B}_{N_{0},\tilde{W}^{[0]}_{i}}\right)\text{vec}({\bm{y}})\right).$

One can verify that
$\sum_{i=0}^{J-1}\bm{B}_{N_{d-1},\tilde{W}^{[d-1]}_{i}}\otimes\bm{B}_{N_{d-2},\tilde{W}^{[d-2]}_{i}}\otimes\cdots\otimes\bm{B}_{N_{0},\tilde{W}^{[0]}_{i}}$
is exactly the variance matrix of the original multi-dimensional signal after
sampling and vectorization. Therefore, the time- and band-limited operator
$\mathcal{B}_{\bm{N},\mathbb{W}}$ and the “variance matrix” share the same
eigenvalues and eigen-tensors. In 1-D cases, the operator
$\mathcal{B}_{\bm{N},\mathbb{W}}$ degrades to the matrix form
$\sum_{i=0}^{J-1}\bm{B}_{N,W_{i}}$, whose eigenvalues are discussed in Theorem
5.

One important difference between the 2-D case and the 1-D case lies in the
fact that the uni-bands of the 2-D case may have various shapes. In addition
to the cubic case, we consider the scenario that the uni-band is
parallelepipedic, which can be viewed as being obtained through a certain
affine transformation of a cube. Similarly, we can define the union of
disjoint parallelepipedic subbands
$\mathbb{W}^{\Diamond}=\bigcup_{i}\mathbb{W}^{\Diamond}_{i}$ and its time- and
band-limited operator $\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$ as (21).

$\displaystyle\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}(\bm{y})[\bm{m}]$
$\displaystyle:=\mathcal{I}_{\bm{N}}(\mathcal{B}_{\mathbb{W}}(\mathcal{I}_{\bm{N}}^{*}(\bm{y})))[\bm{m}]$
(25)
$\displaystyle=\sum_{\bm{n}\in\mathcal{N}}\left(\bm{y}[\bm{n}]\int_{\mathbb{W}^{\Diamond}}e^{j2\pi\left<\bm{f},(\bm{m}-\bm{n})\right>}\text{d}f\right),\bm{m}\in\mathcal{N}.$

When the original stochastic continuous signal is stationary and its power
spectrum is 1 on its supporting sets, the eigenvalues of
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$ are also the eigenvalues of its
“covariance matrix”. However, it cannot be unfolded to a Kronecker dot form,
because there exist cross-terms in this signal across different dimensions.

##  IV Main Result

Our main results are separated into three parts. Firstly, we prove that the
eigen-tensors of the time- and band-limited operator for the multi-dimensional
band-limited signals are formed by the outer products of DPSS bases, and its
eigenvalues have a clustering property in Section IV-A. Then, we consider the
multi-dimensional multiband signals and show the eigenvalues of its time- and
band-limited operator has a clustering property in Section IV-B. Thus, one can
form a low-dimensional dictionary with part of its eigen-tensors to
approximate the original signal. We show that the dictionary can be
approximated by the outer products of DPSS bases in Section IV-C, offering an
efficient way to construct a dictionary with low computational complexity. In
Section IV-D, we examine the case of parallelepipedic subbands and analyze the
distribution of eigenvalues. We mainly concern the 2-D cases, which can be
easily extended to higher dimensions.

###  IV-A Eigenvalues and Eigen-Tensors for Multi-dimensional Band-Limited
Signals with Cubic Subbands

Consider the base-band case that
$\mathcal{B}_{\bm{N},\bm{W}}(\bm{y})=\bm{B}_{M,W^{[0]}}\bm{y}\bm{B}^{T}_{N,W^{[1]}}$.
The following equation states the relationship between the eigenvalues and the
eigentensors of 2-D cases and those of 1-D cases.

$\displaystyle\bm{B}_{M,W^{[0]}}\bm{s}^{(l)}_{M,W^{[0]}}{\bm{s}^{(k)}_{N,W^{[1]}}}^{T}\bm{B}^{T}_{N,W^{[1]}}$
(26) $\displaystyle=$
$\displaystyle\bm{B}_{M,W^{[0]}}\bm{s}^{(l)}_{M,W^{[0]}}\left(\bm{B}_{N,W^{[1]}}\bm{s}^{(k)}_{N,W^{[0]}}\right)^{T}$
$\displaystyle=$
$\displaystyle\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}\bm{s}^{(l)}_{M,W^{[0]}}{\bm{s}^{(k)}_{N,W^{[1]}}}^{T}.$

In the above equation, $\lambda_{M,W^{[0]}}^{(l)}$ and
$\bm{s}^{(l)}_{M,W^{[0]}}$ ($\lambda_{N,W^{[1]}}^{(k)}$ and
$\bm{s}^{(k)}_{N,W^{[1]}}$) are the $l$-th ($k$-th) eigenvalue and the
corresponding eigentensor of the matrix $\bm{B}_{M,W^{[1]}}$
($\bm{B}_{N,W^{[1]}}$). The equation shows that the 2-D operator
$\mathcal{B}_{\bm{N},\bm{W}}$ has $MN$ eigentensors whose forms are
$\bm{S}_{\bm{N},\bm{W}}^{(p)}=\bm{s}^{(l)}_{M,W^{[0]}}{\bm{s}^{(k)}_{N,W^{[1]}}}^{T}$,
for some $l\in{0,1,\cdots,M-1}$ and $k\in{0,1,\cdots,N-1}$. The corresponding
eigenvalues
$\lambda_{\bm{N},\bm{W}}^{(p)}=\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}$.

The following theorem describes the clustering property of
$\lambda_{\bm{N},\bm{W}}^{p}$.

######  Theorem 3.

1\. Fixing $\epsilon\in(0,1)$, there exist constants
$\bar{C}_{1}(\bm{W},\epsilon)$, $\bar{C}_{2}(\bm{W},\epsilon)$, and integers
$\bar{M}_{1}(\bm{W},\epsilon)$, $\bar{N}_{1}(\bm{W},\epsilon)$ that

$\displaystyle 1-\lambda_{\bm{N},\bm{W}}^{(p)}$
$\displaystyle\leq\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W},\epsilon)\min{(M,N)}}$
(27) $\displaystyle\forall p\leq\lfloor 4MNW^{[0]}W^{[1]}(1-\epsilon)\rfloor$

for all $N\geq\bar{M}_{1}(\bm{W},\epsilon),M\geq\bar{N}_{1}(\bm{W},\epsilon)$.

2\. Fixing $\epsilon\in(0,\frac{1}{4W^{[0]}W^{[1]}}-1)$, there exist constants
$\bar{C}_{3}(\bm{W},\epsilon)$, $\bar{C}_{4}(\bm{W},\epsilon)$ and integers
$\bar{M}_{2}(\bm{W},\epsilon)$, $\bar{N}_{2}(\bm{W},\epsilon)$ that

$\displaystyle\lambda_{\bm{N},\bm{W}}^{(p)}$
$\displaystyle\leq\bar{C}_{3}(\bm{W},\epsilon)e^{-\bar{C}_{4}(\bm{W},\epsilon)\min{(M,N)}}$
(28) $\displaystyle\forall p\geq\lceil 4NMW^{[0]}W^{[1]}(1+\epsilon)\rceil$

for all $M\geq\bar{M}_{2}(\bm{W},\epsilon),N\geq\bar{N}_{2}(\bm{W},\epsilon)$.

###### Proof.

See Appendix A. ∎

The theorem indicates that about $4NMW^{[0]}W^{[1]}$ eigenvalues of
$\mathcal{B}_{\bm{N},\bm{W}}$ is close to 1, while the others are close to 0.

When $\bm{W}$ is not in the baseband but has a 2-D modulated frequency, we can
write $\mathcal{B}_{\bm{N},[-\bm{W}+\bm{f}_{c},\bm{W}+\bm{f}_{c}]}$ as

$\mathcal{B}_{\bm{N},[-\bm{W}+\bm{f}_{c},\bm{W}+\bm{f}_{c}]}\bm{y}=\bm{E}_{f_{c}^{[0]}}\bm{B}_{M,W^{[0]}}\bm{E}_{f_{c}^{[0]}}^{H}\bm{y}\bm{E}_{f_{c}^{[1]}}^{H}\bm{B}_{N,W^{[1]}}\bm{E}_{f_{c}^{[1]}}.$
(29)

The eigentensors of the operator can be written as

$\bm{\Lambda}_{\bm{N},[-\bm{W}+\bm{f}_{c},\bm{W}+\bm{f}_{c}]}^{(p)}=\bm{E}_{f_{c}^{[0]}}\bm{s}^{(l)}_{M,W^{[0]}}{\bm{E}_{f_{c}^{[1]}}\bm{s}^{(k)}_{N,W^{[1]}}}^{T},$
(30)

whose corresponding eigenvalues are the same as
$\lambda_{\bm{N},\bm{W}}^{(p)}$.

###  IV-B Eigenvalues for Multi-dimensional MultiBand Signals Cubic Subbands

In this section, we consider a multiband-limited case

$\mathbb{W}=[\bm{f}_{0}\pm\bm{W}_{0}]\cup[\bm{f}_{1}\pm\bm{W}_{1}]\cup\cdots\cup[\bm{f}_{J-1}\pm\bm{W}_{J-1}].$
(31)

We show that with such $\mathbb{W}$, the eigenvalues of the linear operator
$\mathcal{B}_{\bm{N},\mathbb{W}}$ also possess a clustering property.

Firstly, we bound the eigenvalues of $\mathcal{B}_{\bm{N},\mathbb{W}}$ roughly
with the following lemma.

######  Lemma 4.

Given any $\mathbb{W}$ and $\bm{N}$, the eigenvalues
$\lambda_{\bm{N},\mathbb{W}}^{(p)})$ of $\mathcal{B}_{\bm{N},\mathbb{W}}$
satisfy

$0<\lambda_{\bm{N},\mathbb{W}}^{(p)}<1,$ (32)

and

$\sum_{p=0}^{MN-1}\lambda_{\bm{N},\mathbb{W}}^{(p)}=\sum_{j}4NMW^{[0]}_{j}W^{[1]}_{j}=NM\|\mathbb{W}\|.$
(33)

###### Proof.

See Appendix B. ∎

The distribution of the eigenvalues shows a dramatic transition, as the
following theorem shows.

######  Theorem 5.

Given $\epsilon\in(0,\frac{1}{2})$, the number of the eigenvalues between
$\epsilon$ and $1-\epsilon$ is bounded by

$\\#\\{p:\epsilon\leq\lambda_{\bm{N},\mathbb{W}}^{(p)}\leq
1-\epsilon\\}=O(\frac{JM\log(N)+JN\log(M)}{\epsilon(1-\epsilon)}).$ (34)

###### Proof.

See Appendix C. ∎

This theorem along with Lemma 4 is almost sufficient to show that about
$NM\|\mathbb{W}\|$ eigenvalues are close to 1 while others are close to 0.
This indicates the effective dimensionality is about $NM\|\mathbb{W}\|$ for
multiband signal. Below, we give a more delicate analysis of the distribution
of the eigenvalues in 2-D cases.

######  Theorem 6.

Let $\mathbb{W}\subset[-\frac{1}{2},\frac{1}{2}]^{2}$ be a fixed union of $J$
disjoint intervals. Given an $\epsilon\in(0,\frac{1}{\|\mathbb{W}\|}-1)$,
there exist constants $\tilde{C}_{3}$ and $\tilde{C}_{4}$ satisfying

$\lambda^{(p)}_{\bm{N},\mathbb{W}}\leq\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min{(M,N)}},$
(35)

for all $p\geq\lceil MN\|\mathbb{W}\|(1+\epsilon)\rceil$,
$N\geq\tilde{N}_{2}(\mathbb{W},\epsilon)$ and
$M\geq\tilde{M}_{2}(\mathbb{W},\epsilon)$.

###### Proof.

See Appendix D. ∎

######  Theorem 7.

Let $\mathbb{W}\in[-\frac{1}{2},\frac{1}{2}]^{2}$ be a fixed union of $J$
disjoint intervals. Given a $\epsilon\in(0,1)$, there exist constants
$C_{5}(\mathbb{W},\epsilon)$

$\displaystyle\lambda^{(p)}_{\bm{N},\mathbb{W}}$ $\displaystyle\geq
1-6M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon),\min{M,N}},$
(36)

for all $p\leq J-1+\lfloor MN\|\mathbb{W}\|(1-\epsilon)\rfloor$.

###### Proof.

See Appendix E. ∎

The above 2 theorems show that only about $MN\|\mathbb{W}\|$ eigen-tensors are
effective in constructing the multi-dimensional multiband signals. Therefore,
one can use a low-dimensional dictionary formed by these eigen-tensors to
approximate the original signal with low MSE.

###  IV-C Approximation of Multiband Signal with Cubic Subbands

Up to now, we have shown that the eigenvalues of the operator
$\mathcal{B}_{\bm{N},\mathbb{W}}$ have a cluster property. Therefore, one can
use a dictionary with about $MN\|\mathbb{W}\|$ eigen-tensors of
$\mathcal{B}_{\bm{N},\mathbb{W}}$ to represent the original multi-dimensional
multiband signal. However, calculating the eigen-tensors of
$\mathcal{B}_{\bm{N},\mathbb{W}}$ is time consuming. Below, we show that the
dictionary can be approximated by a dictionary $\bm{\Psi}$ formed by modulated
DPSS.

Let $p\in{1,2,\dots,MN}$, $q_{i}\in{1,2,\dots,N}$ and $i\in{J}$. Define
3-dimensional tensors $\bm{\Phi}$ and $\bm{\Psi}$ as

$\displaystyle\bm{\Phi}$
$\displaystyle:=\left[[\bm{\Phi}^{(0)}],[\bm{\Phi}^{(1)}],\dots,[\bm{\Phi}^{(p-1)}]\right],$
(37) $\displaystyle\bm{\Psi}$
$\displaystyle:=\left[[\bm{\Psi}^{(0,0)}],[\bm{\Psi}^{(0,1)}],\dots,[\bm{\Psi}^{(0,q_{0})}],\dots[\bm{\Psi}^{(J-1,q_{J-1})}]\right].$
(38)

where $\bm{\Phi}^{(k)}$ is the $k$-th eigen-tensor of
$\mathcal{B}_{\bm{N},\mathbb{W}}$ and $\bm{\Psi}^{(i,j)}$ is the $j$-th eigen-
tensor of $\mathcal{B}_{\bm{N},\bm{W}_{i}}$.

Following [1], denoted by $\mathcal{S}_{\bm{\Phi}}$ and
$\mathcal{S}_{\bm{\Psi}}$ the subspace spanned by $\bm{\Phi}$ and $\bm{\Psi}$,
the similarity of the dictionaries can be measured by the angle between the
subspace as

$\cos(\Theta_{\mathcal{S}_{\bm{\Phi}}\mathcal{S}_{\bm{\Psi}}}):=\left\\{\begin{aligned}
&\inf_{\bm{\phi}\in\mathcal{S}_{\bm{\Phi}},\|\bm{\phi}\|_{F}=1}\|\mathcal{P}_{\bm{\Psi}}\bm{\phi}\|_{F},\
\ p\leq\sum_{i\in[J]}q_{i},\\\
&\inf_{\bm{\psi}\in\mathcal{S}_{\bm{\Psi}},\|\bm{\psi}\|_{F}=1}\|\mathcal{P}_{\bm{\Phi}}\bm{\psi}\|_{F},\
\ p\geq\sum_{i\in[J]}q_{i}.\end{aligned}\right.$ (39)

Here $\mathcal{P}$ denotes the orthogonal projection operator. The following
two theorems show that
$\cos(\Theta_{\mathcal{S}_{\bm{\Phi}}\mathcal{S}_{\bm{\Psi}}})$ approximates
to 1, and thus these two dictionaries are similar.

######  Theorem 8.

Fix $\epsilon\in(0,\min(1,\frac{1}{\|\mathbb{W}\|}-1))$. Let $p=\sum_{i}\lceil
MN\|\bm{W}_{i}\|(1+\epsilon)\rceil$ and $q_{i}\leq\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor$. The $p\times M\times N$ tensor
$\bm{\Phi}$ and the $(\sum_{i}q_{i})\times M\times N$ tensor $\bm{\Psi}$ are
defined as (37) and (38). Then for any matrix
$\bm{\Psi}^{(i,j)}\in{\bm{\Psi}}$,

$\displaystyle\|\bm{\Psi}^{(i,j)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|_{F}^{2}\leq
2\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min(M,N)}/$
(40)
$\displaystyle\left(1-\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min(M,N)}-\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min(M,N)}\right)^{2}$
$\displaystyle:=\chi_{1},$

and

$\displaystyle\cos(\Theta_{\mathcal{S}_{\bm{\Phi}}\mathcal{S}_{\bm{\Psi}}})\geq$
(41)
$\displaystyle\sqrt{1-MN\sqrt{\chi_{1}}-3MN\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)}e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min(M,N)/2}}/$
$\displaystyle\sqrt{1+3MN\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)}e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min(M,N)/2}}.$

###### Proof.

See Appendix F ∎

######  Theorem 9.

Fix $\epsilon\in(0,\min(1,\frac{1}{\|\mathbb{W}\|}-1))$. Let
$p=\sum_{i}\lfloor MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor$ and $q_{i}\geq\lceil
MN\|\bm{W}_{i}\|(1+\epsilon)\rceil$. The $p\times M\times N$ tensor
$\bm{\Phi}$ and the $(\sum_{i}q_{i})\times M\times N$ tensor $\bm{\Psi}$ are
defined as (37) and (38). Then for any matrix $\bm{\Phi}^{(i)}\in{\bm{\Phi}}$,

$\displaystyle\|\bm{\Phi}^{(i)}-\mathcal{P}_{\bm{\Psi}}\bm{\Phi}^{(i)}\|_{F}^{2}$
$\displaystyle\leq
12M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}$
(42) $\displaystyle\ \
+2MN\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min{(M,N)}}$
$\displaystyle:=\chi_{2},$

and

$\displaystyle\cos(\Theta_{\mathcal{S}_{\bm{\Phi}}\mathcal{S}_{\bm{\Psi}}})\geq\sqrt{1-MN\chi_{2}}$
(43)

###### Proof.

See Appendix G ∎

###  IV-D Eigenvalues of Multi-Dimensional Multiband Signal with
Parallelepipedic subbands

A parallelepipedic subband can be viewed as a cubic subband with affine
transformation. Just as the proof of Lemma 4, it is not difficult to see that
the eigenvalues of $\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$ are restricted
to [0,1]. However, the coupling relationships across dimensions posed
challenges for analysis, as its covariance does not lend itself to a Kronecker
product form, unlike that of a cubic subband. Therefore, it is rather
difficult to offer a strict analysis of the distribution of its eigenvalues as
Theorem 6 and Theorem 7. Instead, we show there is a sharp phase transition in
the distribution as Theorem 5.

######  Theorem 10.

Suppose
$\mathbb{W}^{\Diamond}\subset[-\frac{1}{2},\frac{1}{2}]\times[-\frac{1}{2},\frac{1}{2}]$
is a union of $J$ disjoint regions of parallelogram. For any
$\epsilon\in(0,\frac{1}{2})$, the number of the eigenvalues of
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$ between $\epsilon$ and
$1-\epsilon$ is bounded by

$\\#\\{p:\epsilon\leq\lambda_{\bm{N},\mathbb{W}^{\Diamond}}^{(p)}\leq
1-\epsilon\\}=O(\frac{JM\log(N)+JN\log(M)}{\epsilon(1-\epsilon)}).$ (44)

###### Proof.

See Appendix H ∎

This theorem shows that the number of eigenvalues that are not close to 1 or 0
is sufficiently small. In Appendix H, we also show that the sum of these
eigenvalues is $MN\|\mathbb{W}^{\Diamond}\|$. It is not difficult to see that
about $MN\|\mathbb{W}^{\Diamond}\|$ eigenvalues are greater than $1-\epsilon$.

##  V Conclusion

In this paper, we analyze the multi-dimensional multiband signal by
considering a time-frequency limiting operator. We prove that part of the
eigenvalues of the operator cluster to 1 while most of the others cluster to
0. This result indicates that there exists a low-dimensional representation of
the multi-dimensional multiband signal, which may contribute to the
reconstruction of such signal in certain cases.

##  Appendix A Proof of Theorem 3

This can be easily adopted by Lemma 1. For the first judgment, we define
$\epsilon^{\prime}=1-\sqrt{1-\epsilon}\in(0,1)$,
$\bar{N}_{1}(\bm{W},\epsilon)=N_{1}(W^{[1]},\epsilon^{\prime})$ and
$\bar{M}_{1}(\bm{W},\epsilon)=M_{1}(W^{[0]},\epsilon^{\prime})$. Using Lemma
1, we know that

$\displaystyle\lambda_{M,W^{[0]}}^{(l)}\geq
1-C_{1}(W^{[0]},\epsilon^{\prime})e^{-C_{2}(W^{[0]},\epsilon^{\prime})M},$
(45) $\displaystyle\lambda_{N,W^{[1]}}^{(k)}\geq
1-C_{1}(W^{[1]},\epsilon^{\prime})e^{-C_{2}(W^{[1]},\epsilon^{\prime})N},$
(46)

when $l\leq\lfloor 2MW^{[0]}(1-\epsilon^{\prime})\rfloor\text{ and
}k\leq\lfloor 2NW^{[1]}(1-\epsilon^{\prime})\rfloor$, for
$N\geq\bar{N}_{1}(\bm{W},\epsilon)$ and $M\geq\bar{M}_{1}(\bm{W},\epsilon)$
Multiplying the two inequalities, we obtain

$\displaystyle\ \lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}$ (47)
$\displaystyle\geq
1-\left(C_{1}(W^{[0]},\epsilon^{\prime})e^{-C_{2}(W^{[0]},\epsilon^{\prime})M}+C_{1}(W^{[1]},\epsilon^{\prime})e^{-C_{2}(W^{[1]},\epsilon^{\prime})N}\right)$
$\displaystyle\
+C_{1}(W^{[0]},\epsilon^{\prime})e^{-C_{2}(W^{[0]},\epsilon^{\prime})M}C_{1}(W^{[1]},\epsilon^{\prime})e^{-C_{2}(W^{[1]},\epsilon^{\prime})N}$
$\displaystyle\geq
1-\left(C_{1}(W^{[0]},\epsilon^{\prime})e^{-C_{2}(W^{[0]},\epsilon^{\prime})M}+C_{1}(W^{[1]},\epsilon^{\prime})e^{-C_{2}(W^{[1]},\epsilon^{\prime})N}\right).$

Denoted by
$\bar{C}_{1}(\bm{W},\epsilon)=2\max(C_{1}(W^{[0]},\epsilon^{\prime}),C_{1}(W^{[0]},\epsilon^{\prime}))$
and
$\bar{C}_{2}(\bm{W},\epsilon)=\min(C_{2}(W^{[0]},\epsilon^{\prime}),C_{2}(W^{[1]},\epsilon^{\prime}))$,
one have

$\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}\geq
1-\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W},\epsilon)\min(M,N)}.$
(48)

Since $\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}$ corresponds to a
unique $\lambda_{\bm{N},\bm{W}}^{(p)}$, we have compeled the proof for
judgement 1.

For the second judgment, define $\epsilon_{*}$ the positive root to the
equation

$\left[1+\left(\frac{1}{2W^{[0]}}-1\right)x\right]\left[1+\left(\frac{1}{2W^{[1]}}-1\right)x\right]=1+\epsilon.$
(49)

and

$\displaystyle\epsilon_{0}$ $\displaystyle=\epsilon_{*}(1/2W^{[0]}-1),$ (50)
$\displaystyle\epsilon_{1}$ $\displaystyle=\epsilon_{*}(1/2W^{[1]}-1).$ (51)

. One can verify that $\epsilon_{0}$ and $\epsilon_{1}$ are monotone
increasing with $\epsilon$. For
$\epsilon\in\left(0,\frac{1}{4W^{[0]}W^{[1]}}\right)$, $\epsilon_{0}$ and
$\epsilon_{1}$ are in the intervals $\left(0,\frac{1}{2W^{[0]}}\right)$ and
$\left(0,\frac{1}{2W^{[1]}}\right)$, repectively. Using Lemma 1, we have

$\displaystyle\lambda_{M,W^{[0]}}^{(l)}\leq
C_{3}(W^{[0]},\epsilon_{0})e^{-C_{4}(W^{[0]},\epsilon_{0})M},$ (52)
$\displaystyle\lambda_{N,W^{[1]}}^{(k)}\leq
C_{3}(W^{[1]},\epsilon_{0})e^{-C_{4}(W^{[1]},\epsilon_{0})N},$ (53)

when $l\geq\lceil 2MW^{[0]}(1+\epsilon_{0})\rceil\text{ and }k\geq\lceil
2NW^{[1]}(1+\epsilon_{1})\rceil$, for
$M\geq\bar{M}_{2}(\bm{W},\epsilon)=M_{2}(W^{[0]},\epsilon_{0})$ and
$N\geq\bar{N}_{2}(\bm{W},\epsilon)=N_{2}(W^{[1]},\epsilon_{1})$. Noting that
all the eigenvalues of $\bm{B}_{N,W}$ are less than 1, We obtain

$\displaystyle\
\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}\leq\min(\lambda_{M,W^{[0]}}^{(l)},\lambda_{N,W^{[1]}}^{(k)})\leq$
(54)
$\displaystyle\max\left(C_{3}(W^{[0]},\epsilon_{0})e^{-C_{4}(W^{[0]},\epsilon_{0})M},C_{3}(W^{[1]},\epsilon_{1})e^{-C_{4}(W^{[1]},\epsilon_{1})N}\right),$

for all $l\geq\lceil 2MW^{[0]}(1+\epsilon_{0})\rceil$ or $k\geq\lceil
2NW^{[1]}(1+\epsilon_{1})\rceil$.

Denoted by
$\bar{C}_{3}(\bm{W},\epsilon)=\max(C_{3}(W^{[0]},\epsilon_{0}),C_{3}(W^{[1]},\epsilon_{1}))$
and
$\bar{C}_{4}(\bm{W},\epsilon)=\min(C_{4}(W^{[0]},\epsilon_{0}),C_{4}(W^{[1]},\epsilon_{1}))$,
we have

$\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}\leq\bar{C}_{3}(\bm{W},\epsilon)e^{-\bar{C}_{4}(\bm{W},\epsilon)\min{(M,N)}}.$
(55)

Noting the facts that $\lambda_{M,W^{[0]}}^{(l)}\lambda_{N,W^{[1]}}^{(k)}$
corresponds to a unique $\lambda_{\bm{N},\bm{W}}^{(p)}$ and
$(1+\epsilon_{0})(1+\epsilon_{1})=1+\epsilon$, we have completed the proof of
judgement 2.

##  Appendix B Proof of Lemma 4

Given $\bm{Y}\in\mathbb{C}^{M\times N}$, then the eigenvalues of
$\mathcal{B}_{\bm{N},\mathbb{W}}$ satisfy

$\min_{\bm{Y}}\frac{\left<\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{Y}),\bm{Y}\right>}{\left<\bm{Y},\bm{Y}\right>}\leq\lambda_{\bm{N},\mathbb{W}}\leq\max_{\bm{Y}}\frac{\left<\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{Y}),\bm{Y}\right>}{\left<\bm{Y},\bm{Y}\right>}.$
(56)

Here, the inner product is defined as
$\left<\bm{A},\bm{B}\right>=trace(\bm{A}^{H}\bm{A})$. We have the following
equation

$\displaystyle\left<\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{Y}),\bm{Y}\right>=\sum_{\bm{m}=\bm{0}}^{\bm{N}}\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{Y}[\bm{m}])\bar{\bm{Y}}[\bm{m}]$
(57)
$\displaystyle=\sum_{\bm{m}=\bm{0}}^{\bm{N}}(\sum_{\bm{n}=\bm{0}}^{\bm{N}}\int_{\mathbb{W}}e^{j2\pi\left<\bm{f},(\bm{m}-\bm{n})\right>}\text{d}\bm{f}\
\bm{Y}[\bm{n}])\bar{\bm{Y}}[\bm{m}]$
$\displaystyle=\int_{\mathbb{W}}\left(\sum_{\bm{m}=\bm{0}}^{\bm{N}}e^{j2\pi\left<\bm{f},\bm{m})\right>}\bar{\bm{Y}}[\bm{m}]\right)\left(\sum_{\bm{n}=\bm{0}}^{\bm{N}}e^{-j2\pi\left<\bm{f},\bm{n})\right>}\bm{Y}[\bm{n}]\right)\text{d}\bm{f}$
$\displaystyle=\int_{\mathbb{W}}\|\mathcal{F}\bm{Y}\|^{2}\text{d}\bm{f}>0.$

Noting
$\int_{\mathbb{W}}\|\mathcal{F}\bm{Y}\|_{F}^{2}\text{d}\bm{f}\leq\int_{[-\frac{1}{2},\frac{1}{2}]\times[-\frac{1}{2},\frac{1}{2}]}\|\mathcal{F}\bm{Y}\|_{F}^{2}\text{d}\bm{f}\leq\|\bm{Y}\|_{F}^{2}$,
and the eigenvalues satisfy $0<\lambda_{\bm{N},\mathbb{W}}<1$. Further, we
bound the sum of $\lambda_{\bm{N},\mathbb{W}}$. We use the Kronecker product
form as (23) and obtain

$\displaystyle\sum_{p=0}^{MN-1}\lambda_{\bm{N},\mathbb{W}}^{(p)}$
$\displaystyle=\sum_{J}trace(\bm{B}_{N,W^{[1]}_{j}}\otimes\bm{B}_{M,W^{[0]}_{j}})$
(58) $\displaystyle=\sum_{j}4NMW^{[0]}_{j}W^{[1]}_{j}=NM\|\mathbb{W}\|.$

##  Appendix C Proof of Theorem 5

To begin with, we calculate the F norm of
$\bm{B}_{N,W^{[1]}}\otimes\bm{B}_{M,W^{[0]}}$ which is also the sum of square
of the eigenvalues of $\mathcal{B}_{\bm{N},\mathbb{W}}$

$\displaystyle\|\bm{B}_{N,W^{[1]}}\otimes\bm{B}_{M,W^{[0]}}\|_{F}^{2}=\|\bm{B}_{N,W^{[1]}}\|_{F}^{2}\|\bm{B}_{M,W^{[0]}}\|_{F}^{2}$
(59)
$\displaystyle\geq(2NW^{[1]}-\frac{2}{\pi^{2}}\frac{2N-1}{N-1}-\frac{2}{\pi^{2}}\log(N-1))$
$\displaystyle\quad\cdot(2MW^{[0]}-\frac{2}{\pi^{2}}\frac{2M-1}{M-1}-\frac{2}{\pi^{2}}\log(M-1))$

The above results yield

$\displaystyle\|\sum_{i=0}^{J-1}\bm{B}_{N,W_{i}^{[1]}}\otimes\bm{B}_{M,W_{i}^{[0]}}\|_{F}^{2}\geq\sum_{i=0}^{J-1}\|\bm{B}_{N,W_{i}^{[1]}}\otimes\bm{B}_{M,W_{i}^{[0]}}\|_{F}^{2}$
(60)
$\displaystyle\geq\sum_{i=0}^{J-1}(2NW_{i}^{[1]}-\frac{2}{\pi^{2}}\frac{2N-1}{N-1}-\frac{2}{\pi^{2}}\log(N-1))$
$\displaystyle\quad\quad\quad\cdot(2MW_{i}^{[0]}-\frac{2}{\pi^{2}}\frac{2M-1}{M-1}-\frac{2}{\pi^{2}}\log(M-1))$
$\displaystyle\geq MN\|\mathbb{W}\|-\frac{4MJ}{\pi^{2}}(3+\log(N))$
$\displaystyle\quad-\frac{4NJ}{\pi^{2}}(3+\log(M))$
$\displaystyle\quad+\frac{4J}{\pi^{4}}(3+\log(M))(3+\log(N))$

Recall the sum of $\lambda_{\bm{N},\mathbb{W}}^{(p)}$ (33), and we have the
following equation

$\displaystyle\sum_{p=0}^{MN-1}\lambda_{\bm{N},\mathbb{W}}^{(p)}(1-\lambda_{\bm{N},\mathbb{W}}^{(p)})$
(61)
$\displaystyle=trace(\bm{B}_{N,W^{[1]}}\otimes\bm{B}_{M,W^{[0]}})-\|\bm{B}_{N,W^{[1]}}\otimes\bm{B}_{M,W^{[0]}}\|_{F}^{2}$
$\displaystyle\leq\frac{4MJ}{\pi^{2}}(3+\log(N))+\frac{4NJ}{\pi^{2}}(3+\log(M))$

Take the number of $\lambda_{\bm{N},\mathbb{W}}$ as $\\#\\{medium\\}$, and we
can bound it as

$\displaystyle\sum_{p=0}^{MN-1}\lambda_{\bm{N},\mathbb{W}}^{(p)}(1-\lambda_{\bm{N},\mathbb{W}}^{(p)})\geq\sum_{\epsilon<\lambda_{\bm{N},\mathbb{W}}^{(p)}<1-\epsilon}\lambda_{\bm{N},\mathbb{W}}^{(p)}(1-\lambda_{\bm{N},\mathbb{W}}^{(p)})$
(62) $\displaystyle\geq\epsilon(1-\epsilon)\\#\\{medium\\}.$

Therefore, we have
$\\#\\{medium\\}=\frac{O(JM\log(N)+JN\log(M))}{\epsilon(1-\epsilon)}$.

##  Appendix D Proof of Theorem 6

From [25], we know that the following equation holds

$\lambda^{(p)}_{\bm{N},\mathbb{W}}\leq\sum_{i=0}^{J-1}\lambda_{\bm{N},\bm{W}_{i}}^{(l_{i})}.$
(63)

for $l_{i}\in[MN]$ and $p=\sum_{i=0}^{J-1}l_{i}$.

Using the clustering property of $\lambda_{\bm{N},\bm{W}_{i}}^{(l_{i})}$ (3),
we have

$\displaystyle\lambda_{\bm{N},\bm{W}_{i}}^{(l_{i})}$
$\displaystyle\leq\bar{C}_{3}(\bm{W}_{i},\epsilon)e^{-\bar{C}_{4}(\bm{W}_{i},\epsilon)\min(M,N)},$
(64) $\displaystyle\forall l_{i}\geq\lceil
4MNW_{i}^{[0]}W_{i}^{[1]}(1+\epsilon)\rceil,$

for all
$N\geq\tilde{N}_{2}(\mathbb{W},\epsilon)=\max_{i}\bar{N}_{2}(\bm{W}_{i},\epsilon)$
and
$M\geq\tilde{M}_{2}(\mathbb{W},\epsilon)=\max_{i}\bar{M}_{2}(\bm{W}_{i},\epsilon)$.
By selecting $l_{i}\geq\lceil MN\|\bm{W}_{i}\|(1+\epsilon)\rceil$, we have

$\displaystyle\ \lambda^{(p)}_{\bm{N},\mathbb{W}}$
$\displaystyle\leq\sum_{i=0}^{J-1}\bar{C}_{3}(\bm{W}_{i},\epsilon)e^{-\bar{C}_{4}(\bm{W}_{i},\epsilon)\min(M,N)}$
(65)
$\displaystyle\leq\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min{(M,N)}},$

for all $p\geq\lceil MN\|\mathbb{W}\|(1+\epsilon)\rceil$,
$N\geq\tilde{N}_{2}(\mathbb{W},\epsilon)$ and
$M\geq\tilde{M}_{2}(\mathbb{W},\epsilon)$, where
$\tilde{C}_{3}(\mathbb{W},\epsilon)=J\max_{i}\\{\bar{C}_{3}(\bm{W}_{i},\epsilon)\\}$
and
$\tilde{C}_{4}(\mathbb{W},\epsilon)=\min_{i}\\{\bar{C}_{4}(\bm{W}_{i},\epsilon)\\}$.

##  Appendix E Proof of Theorem 7

###  E-A $\epsilon$-pseudo eigenvalue

In this part, we show that
$\bm{E}_{f_{i}^{[0]}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}^{[1]}}$
is an $\epsilon-pseudo$ eigentensor of $\mathcal{B}_{\bm{N},\mathbb{W}}$, when
$[\bm{f}_{i}\pm\bm{W}_{i}]$ is one subband in $\mathbb{W}$.

For the operator $\mathcal{B}_{\bm{N},\mathbb{W}}$, we have

$\displaystyle\
\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})$
(66) $\displaystyle=e^{j2\pi
f_{i}m+g_{i}n}\lambda^{(l)}_{M,W_{i}^{[0]}}\lambda^{(k)}_{N,W_{i}^{[1]}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}+$
$\displaystyle\
\mathcal{B}_{\bm{N},\mathbb{W}/[\bm{f}_{i}\pm\bm{W}_{i}]}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}}).$

In the following, we bound the second term
$\bm{o}^{(p)}:=\mathcal{B}_{\bm{N},\mathbb{W}/[\bm{f}_{i}\pm\bm{W}_{i}]}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})$
as

$\displaystyle\
\|\bm{o}^{(p)}\|_{F}^{2}=\|\mathcal{B}_{\bm{N},\mathbb{W}/[\bm{f}_{i}\pm\bm{W}_{i}]}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})\|_{F}^{2}$
(67)
$\displaystyle\leq\|\mathcal{B}_{\mathbb{W}/[\bm{f}_{i}\pm\bm{W}_{i}]}\left(\mathcal{I}^{*}_{\bm{N}}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})\right)\|_{F}^{2}$
$\displaystyle=\|\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\|_{F}^{2}$
$\displaystyle\ \ \
-\|\mathcal{B}_{[\bm{f}_{i}\pm\bm{W}_{i}]}\left(\mathcal{I}^{*}_{\bm{N}}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})\right)\|_{F}^{2}$
$\displaystyle\leq\|\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\|_{F}^{2}$
$\displaystyle\ \ \
-\|\mathcal{B}_{\bm{N},[\bm{f}_{i}\pm\bm{W}_{i}]}(\bm{E}_{f_{i}}\bm{s}_{M,W_{i}^{[0]}}^{(l)}{\bm{s}_{N,W_{i}^{[1]}}^{(k)}}^{T}\bm{E}_{g_{i}})\|_{F}^{2}$
$\displaystyle\leq
1-(\lambda^{(l)}_{M,W_{i}^{[0]}}\lambda^{(k)}_{N,W_{i}^{[1]}})^{2}$
$\displaystyle\leq
1-\left(1-\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W},\epsilon)\min{(M,N)}}\right)^{2}$
$\displaystyle\leq
2\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W},\epsilon)\min{(M,N)}}$

###  E-B cluster near 1

In this part, we first introduce one matrix and one lemma that depicts the
correlations between different $\bm{s}_{N,W_{i}}$. Given $\epsilon\in(0,1)$
and $k_{i}=\lfloor 2NW_{i}(1-\epsilon)\rfloor,\ \forall i\in[J]$, the
dictionary matrix is defined as
$\bm{S}:=[\bm{S}_{0},\bm{S}_{1},\cdots,\bm{S}_{J-1}]$, where the columns in
$\bm{S}_{i}\in\mathbb{C}^{N\times k_{i}}$ is formed by the first $k_{i}$
eigenvectors of $\bm{B}_{N,W_{i}}$, $\bm{s}_{N,W_{i}}^{l_{i}},\
l_{i}\in[k_{i}]$.

######  Lemma 11.

[1] For any pair of distinct columns $\bm{s}_{N,W_{1}}^{l_{1}}$ and
$\bm{s}_{N,W_{2}}^{l_{2}}$ in $\bm{S}$ whose corresponding eigenvalues are
$\lambda_{1}$ and $\lambda_{2}$, the following inequalities hold

$|\left<\bm{s}_{N,W_{1}}^{l_{1}},\bm{s}_{N,W_{2}}^{l_{2}}\right>|\leq
3\sqrt{1-\min{(\lambda_{1},\lambda_{2})}},$ (68)

for $N\geq\tilde{N}_{1}(\bm{W},\epsilon)$.

Similarly, we can construct a matrix
$\bm{\Psi}:=[\bm{\Psi}_{0},\bm{\Psi}_{1},\cdots,\bm{\Psi}_{J-1}]$. Here, the
columns of $\bm{\Psi}_{i}\in\mathbb{C}^{MN\times k_{i}}$ is formed by the
first $k_{i}$ vectorized eigentensors of $\mathcal{B}_{\bm{N},\bm{W}_{i}}$,
$\text{vec}(\bm{s}_{\bm{N},\bm{W}_{i}}^{(p_{i})})$, for $p_{i}\in[k_{i}]$,
$k_{i}=\lfloor 4MNW_{i}^{[0]}W_{i}^{[1]}(1-\epsilon)\rfloor$ and
$\epsilon\in(0,1)$. Then, for any pair of distinct columns $\bm{\psi}_{1}$ and
$\bm{\psi}_{2}$, we have

$\displaystyle|\left<\bm{\psi}_{1},\bm{\psi}_{2}\right>|$
$\displaystyle=|trace(\bm{s}_{M,W^{[0]}}^{(l_{0})}{\bm{s}_{N,W^{[1]}}^{(k_{0})}}^{T}\bm{s}_{N,W^{[1]}}^{(k_{1})}{\bm{s}_{M,W^{[0]}}^{(l_{1})}}^{T})|$
(69)
$\displaystyle=|trace({\bm{s}_{M,W^{[0]}}^{(l_{1})}}^{T}\bm{s}_{M,W^{[0]}}^{(l_{0})}{\bm{s}_{N,W^{[1]}}^{(k_{0})}}^{T}\bm{s}_{N,W^{[1]}}^{(k_{1})})|$
$\displaystyle=|{\bm{s}_{M,W^{[0]}}^{(l_{1})}}^{T}\bm{s}_{M,W^{[0]}}^{(l_{0})}|\cdot|{\bm{s}_{N,W^{[1]}}^{(k_{0})}}^{T}\bm{s}_{N,W^{[1]}}^{(k_{1})}|$
$\displaystyle\leq
3\sqrt{1-\min{(\lambda_{M,W^{[0]}}^{(l_{1})}},\lambda_{M,W^{[0]}}^{(l_{0})},\lambda_{N,W^{[1]}}^{(k_{0})},\lambda_{N,W^{[1]}}^{(k_{1})})}$
$\displaystyle\leq
3\sqrt{1-\min{(\lambda_{\bm{N},\bm{W}}^{(p_{0})},\lambda_{\bm{N},\bm{W}}^{(p_{1})})}}$
$\displaystyle\leq
3\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}},$

where
$\tilde{C}_{1}(\mathbb{W},\epsilon)=\max_{i}{\bar{C}_{1}(\bm{W}_{i},\epsilon)}$
and
$\tilde{C}_{2}(\mathbb{W},\epsilon)=\min_{i}{\bar{C}_{2}(\bm{W}_{i},\epsilon)}$

Noting that the diagonal elements of the matrix $\bm{\Psi}^{H}\bm{\Psi}$ are
all 1 and the nondiagonal elements are bound by the above inequalities, we can
bound the spectral norm of $\bm{\Psi}^{H}\bm{\Psi}$ by Gerschgorin circle
theorem as

$\|\bm{\Psi}^{H}\bm{\Psi}\|_{2}\leq
1+3MN\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}}.$
(70)

Then we obtain

$\displaystyle\ \sum_{p=0}^{J-1+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\lambda_{\bm{N},\mathbb{W}}^{(p)}$ (71)
$\displaystyle\geq
trace\left(\bm{\Psi}^{H}\bm{B}_{\bm{N},\mathbb{W}}\bm{\Psi}\right)\bigg{/}\|\bm{\Psi}^{H}\bm{\Psi}\|_{2}$
$\displaystyle=\left(\sum_{i=0}^{J-1}\sum_{p_{i}=0}^{\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\left((\text{vec}(\bm{E}_{f_{i}}\bm{S}_{\bm{N},\bm{W}_{i}}^{(p_{i})}\bm{E}_{f_{i}}))^{H}\right)\right.$
$\displaystyle\left.\left(\lambda_{\bm{N},\bm{W}_{i}}^{(p_{i})}\text{vec}(\bm{E}_{f_{i}}\bm{S}_{\bm{N},\bm{W}_{i}}^{(p_{i})}\bm{E}_{f_{i}}))+\bm{o}_{i}^{(p_{i})}\right)\right)\bigg{/}\|\bm{\Psi}^{H}\bm{\Psi}\|_{2}$
$\displaystyle\geq\left(\sum_{i=0}^{J-1}\sum_{p_{i}=0}^{\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}(\lambda_{\bm{N},\bm{W}_{i}}^{(p_{i})}-\|\bm{o}_{i}^{p_{i}}\|_{2})\right)\bigg{/}\|\bm{\Psi}^{H}\bm{\Psi}\|_{2}$
$\displaystyle\geq\left(\sum_{i=0}^{J-1}\sum_{p_{i}=0}^{\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\left(1-\bar{C}_{1}(\bm{W}_{i},\epsilon)e^{-\bar{C}_{2}(\bm{W}_{i},\epsilon)\min{(M,N)}}\right.\right.$
$\displaystyle\left.\left.\ \
-\sqrt{2\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W},\epsilon)\min{((M,N))}}}\right)\right)\bigg{/}$
$\displaystyle\ \
\left(1+3MN\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)}e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{M,N}}\right)$
$\displaystyle\geq\left(J+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor\right.$ $\displaystyle\left.\ \
-3MNC_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}/2}\right)\bigg{/}$
$\displaystyle\ \
\left(1+3MNC_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}/2}\right)$
$\displaystyle\geq J+\sum_{i}\lfloor MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor$
$\displaystyle\ \ \
-6M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}/2}.$

Here,
$C_{5}(\mathbb{W},\epsilon)=\max{(\tilde{C}_{1}(\mathbb{W},\epsilon),\sqrt{\tilde{C}_{1}(\mathbb{W},\epsilon)})}$.
The numbers $M$ and $N$ should satisfy
$M\geq\tilde{M}_{1}(\mathbb{W},\epsilon)$,
$N\geq\tilde{M}_{1}(\mathbb{W},\epsilon)$ and
$3MNC_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}/2}<1$.

Therefore, we bound $\lambda_{\bm{N},\mathbb{W}}^{(p)}$ by

$\displaystyle\lambda_{\bm{N},\mathbb{W}}^{(p)}$
$\displaystyle=\left(\sum_{p^{\prime}=0}^{J-1+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\lambda_{\bm{N},\mathbb{W}}^{(p^{\prime})}\right)$
(72) $\displaystyle\ \ \ -\left(\sum_{p^{\prime}=0,p^{\prime}\neq
p}^{J-1+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\lambda_{\bm{N},\mathbb{W}}^{(p^{\prime})}\right)$
$\displaystyle\geq\left(\sum_{p^{\prime}=0}^{J-1+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor}\lambda_{\bm{N},\mathbb{W}}^{(p^{\prime})}\right)$
$\displaystyle\ \ \ -\left(J-1+\sum_{i}\lfloor
MN\|\bm{W}_{i}\|(1-\epsilon)\rfloor\right)$ $\displaystyle\geq
1-6M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}/2}.$

##  Appendix F Proof of Theorem 8

We first unfold the operator $\mathcal{B}_{\bm{N},\mathbb{W}}$ by
eigenfunction expansion as

$\mathcal{B}_{\bm{N},\mathbb{W}}(\cdot)=\sum_{k=0}^{NM-1}\lambda_{\bm{N},\mathbb{W}}^{(k)}\bm{\Phi}^{(k)}<\bm{\Phi}^{(k)},\cdot>.$
(73)

Fix $\epsilon$. Given $i\in[J]$ and $j\leq q_{i}$, the $j$-th eigen-tensor of
$\mathcal{B}_{\bm{N},\bm{W}_{i}}$, $\bm{\Psi}^{(i,j)}$ satisfies

$\displaystyle\lambda_{\bm{N},\mathbb{W}}^{(k)}<\bm{\Phi}^{(k)},\bm{\Psi}^{(i,j)}>$
$\displaystyle\overset{(a)}{=}<\bm{\Phi}^{(k)},\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{\Psi}^{(i,j)})>$
(74)
$\displaystyle\overset{(b)}{=}<\bm{\Phi}^{(k)},\lambda_{\bm{N},\bm{W}_{i}}^{(j)}\bm{\Psi}^{(i,j)}+\bm{o}^{(i,j)}>.$

The equation $(a)$ dues to eigenfunction expansion form. The equation $(b)$
owes to (66).

Then

$\displaystyle\|\bm{\Psi}^{(i,j)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|_{F}^{2}$
$\displaystyle=\sum_{k=NMW(1+\epsilon)}^{NM-1}<\bm{\Phi}^{(k)},\bm{\Psi}^{(i,j)}>^{2}$
(75)
$\displaystyle=\sum_{k=NMW(1+\epsilon)}^{NM-1}\frac{<\bm{\Phi}^{(k)},\bm{o}^{(i,j)}>^{2}}{|\lambda_{\bm{N},\bm{W}_{i}}^{(j)}-\lambda_{\bm{N},\mathbb{W}}^{(k)}|^{2}}.$

According to the bounds of $\lambda_{\bm{N},\bm{W}_{i}}^{(j)}$ in Theorem 3
and $\lambda_{\bm{N},\mathbb{W}}^{(k)}$ in Theorem 7, the denominator is
bounded as

$\displaystyle|\lambda_{\bm{N},\bm{W}_{i}}^{(j)}-\lambda_{\bm{N},\mathbb{W}}^{(k)}|^{2}\geq\left(1-\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min(M,N)}\right.$
(76) $\displaystyle\left.\
-\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min(M,N)}\right)^{2}:=\delta_{1}$

According to the bound of $\|\bm{o}^{i,j}\|_{F}$ in (67), we reach the final
bound as

$\displaystyle\|\bm{\Psi}^{(i,j)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|_{F}^{2}\leq\frac{\|\bm{o}^{i,j}\|_{F}^{2}}{\delta_{1}}$
(77)
$\displaystyle\leq\frac{2\bar{C}_{1}(\bm{W},\epsilon)e^{-\bar{C}_{2}(\bm{W}_{1},\epsilon)\min{(M,N)}}}{\delta_{1}}$
$\displaystyle\overset{(a)}{\leq}\frac{2\tilde{C}_{1}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}}{\delta_{1}}.$

The inequality $(a)$ is due to the definitions of $\tilde{C}_{1}$ and
$\tilde{C}_{2}$.

We use $\delta_{2}$ and $\delta_{3}$ to denote the upper bounds of
$\|\bm{\Psi}^{(i,j)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|^{2}_{F}$ in
(77) and $|<\|\bm{\Psi}^{(i,j)},\bm{\Psi}^{(u,v)}\|>|$ in (69) for
$(i,j)\neq(u,v)$. Then for any
$\bm{\psi}=\sum_{i\in[J]}\sum_{j<p_{i}}\alpha_{i,j}\bm{\Psi}^{(i,j)}\in\mathcal{S}_{\bm{\Psi}}$

$\displaystyle\|\bm{\psi}\|_{F}^{2}$
$\displaystyle=\left\|\sum_{i,j}\alpha_{i,j}\bm{\Psi}^{(i,j)}\right\|_{F}^{2}$
(78)
$\displaystyle\leq\sum_{i,j}\alpha_{i,j}^{2}\|\bm{\Psi}^{(i,j)}\|_{F}^{2}+\sum_{i.j}\sum_{u,v,(u,v)\neq(i.j)}|\alpha_{i,j}\alpha_{u,v}|\delta_{3}$
$\displaystyle\leq\sum_{i,j}\alpha_{i,j}^{2}+\sum_{i.j}\sum_{u,v,(u,v)\neq(i.j)}\frac{\alpha_{i,j}^{2}+\alpha_{u,v}^{2}}{2}\delta_{3}$
$\displaystyle\leq\left(\sum_{i,j}\alpha_{i,j}^{2}\right)(1+(MN-1)\delta_{3}).$

and

$\displaystyle\|\mathcal{P}_{\bm{\Phi}}\bm{\psi}\|_{F}^{2}=\left\|\sum_{i,j}\mathcal{P}_{\bm{\Phi}}(\alpha_{i,j}\bm{\Psi}^{(i,j)})\right\|_{F}^{2}$
(79)
$\displaystyle=\sum_{i,j}\alpha_{i,j}^{2}\|\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|_{F}^{2}+$
$\displaystyle\ \ \
\sum_{i,j}\sum_{u,v,(u,v)\neq(i,j)}<\alpha_{i,j}\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)},\alpha_{u,v}\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(u,v)}>$
$\displaystyle=\sum_{i,j}\alpha_{i,j}^{2}\|\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(i,j)}\|_{F}^{2}+\sum_{i,j}\sum_{u,v,(u,v)\neq(i,j)}$
$\displaystyle\ \ \
<\alpha_{i,j}\bm{\Psi}^{(i,j)},\alpha_{u,v}(\bm{\Psi}^{(u,v)}-(\bm{\Psi}^{(u,v)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(u,v)}))>$
$\displaystyle\overset{(a)}{\geq}\sum_{i,j}\alpha_{i,j}^{2}(1-\delta_{2})$
$\displaystyle\ \
-\sum_{i,j}\sum_{u,v,(u,v)\neq(i,j)}|\alpha_{i,j}\alpha_{u,v}|(\delta_{3}+\sqrt{\delta_{2}})$
$\displaystyle\overset{(b)}{\geq}(\sum_{i,j}\alpha_{i,j}^{2})(1-MN(\delta_{3}+\sqrt{\delta_{2}})).$

The inequality $(a)$ is due to
$<\bm{\Psi}^{(i,j)},\bm{\Psi}^{(u,v)}>\leq\delta_{3}$ and
$\|\bm{\Psi}^{(u,v)}-\mathcal{P}_{\bm{\Phi}}\bm{\Psi}^{(u,v)})\|\leq\sqrt{\delta_{2}}$.
The inequality $(b)$ follows the same procedures in (78).

Then one has

$\cos^{2}(\Theta_{\mathcal{S}_{\bm{\Phi}}\mathcal{S}_{\bm{\Psi}}})=\inf_{\bm{\psi}\in\mathcal{S}_{\bm{\Psi}}}\frac{\|\mathcal{P}_{\bm{\Phi}}\bm{\psi}\|_{F}^{2}}{\|\bm{\psi}\|_{F}^{2}}\geq\frac{1-MN(\delta_{3}+\sqrt{\delta_{2}})}{1+MN\delta_{3}}.$
(80)

The original theorem is proved by substituting corresponding $\delta_{2}$ and
$\delta_{3}$.

##  Appendix G Proof of Theorem 9

Define a new operator
$\bar{\mathcal{B}}(\cdot)=\sum_{i\in[J]}\sum_{j<q_{i}}\lambda^{(j)}_{\bm{N},\bm{W}_{i}}\bm{\Psi}^{(i,j)}<\bm{\Psi}^{(i,j)},\cdot>$.

Then, we have

$\displaystyle<\bm{y},\bar{\mathcal{B}}(\bm{y})>=\sum_{i\in[J]}\sum_{j<q_{i}}<\bm{y},\lambda^{(j)}_{\bm{N},\bm{W}_{i}}\bm{\Psi}^{(i,j)}<\bm{\Psi}^{(i,j)},\bm{y}>>$
(81)
$\displaystyle=\sum_{i\in[J]}\sum_{j<q_{i}}<\bm{y},\bm{\Psi}^{(i,j)}>\lambda^{(j)}_{\bm{N},\bm{W}_{i}}<\bm{\Psi}^{(i,j)},\bm{y}>$
$\displaystyle\leq\sum_{i\in[J]}\sum_{j<MN}\lambda^{(i)}_{\bm{N},\bm{W}}|<\bm{\Psi}^{(i,j)},\bm{y}>|^{2}$
$\displaystyle=<\bm{y}\mathcal{B}_{\bm{N},\mathbb{W}}(\bm{y})>$
$\displaystyle=\int_{\mathbb{W}}|\tilde{\bm{y}}(\bm{f})|^{2}\text{d}\bm{f},$

which yields $<\bm{y},\bar{\mathcal{B}}(\bm{y})>\leq\|\bm{y}\|_{F}^{2}$.
Therefore, the eigenvalues of $\bar{\mathcal{B}}(\cdot)$ are not greater than
1 and $\bar{\mathcal{B}}$ is semi-positive. We can perform eigendecomposition
on $\bar{\mathcal{B}}(\cdot)$ as
$\bar{\mathcal{B}}(\cdot)=\sum_{k}\lambda^{(k)}\bar{\bm{\Psi}}_{k}<\bar{\bm{\Psi}}_{k},\cdot>$.
The space spanned by $\bar{\bm{\Psi}}_{k}$ is the same as the space spanned by
$\bm{\Psi}^{(i,j)}$. We have

$\displaystyle\|\mathcal{P}_{\bm{\Psi}}\bm{y}\|_{F}^{2}$
$\displaystyle=\|\sum_{k}\bar{\bm{\Psi}}_{k}<\bar{\bm{\Psi}}_{k},\bm{y}>\|_{F}^{2}$
(82)
$\displaystyle\geq\|\sum_{k}\lambda^{(k)}\bar{\bm{\Psi}}_{k}<\bar{\bm{\Psi}}_{k},\bm{y}>\|_{F}^{2}$
$\displaystyle=\|\bar{\mathcal{B}}(\bm{y})\|_{F}^{2}.$

Consider back to the dictionary $\bm{\Phi}$, we obtain

$\displaystyle\|\mathcal{P}_{\bm{\Psi}}\bm{\Phi}^{(k)}\|_{F}\geq\|\bar{\mathcal{B}}(\bm{\Phi}^{(k)})\|_{F}$
(83)
$\displaystyle=\|{\mathcal{B}}_{\bm{N},\mathbb{W}}(\bm{\Phi}^{(k)})-\sum_{i\in[J]}\sum_{j=q_{i}}^{MN-1}\lambda^{(j)}_{\bm{N},\bm{W}_{i}}\bm{\Psi}^{(i,j)}<\bm{\Psi}^{(i,j)},\bm{\Phi}_{k}>\|_{F}$
$\displaystyle\geq\|{\mathcal{B}}_{\bm{N},\mathbb{W}}(\bm{\Phi}^{(k)})\|_{F}-\sum_{i\in[J]}\sum_{j=q_{i}}^{MN-1}\|\lambda^{(j)}_{\bm{N},\bm{W}_{i}}\bm{\Psi}^{(i,j)}<\bm{\Psi}^{(i,j)},\bm{\Phi}_{k}>\|_{F}$
$\displaystyle\geq\lambda^{(k)}_{\bm{N},\mathbb{W}}-\sum_{i\in[J]}\sum_{j=q_{i}}^{MN-1}\lambda^{(j)}_{\bm{N},\bm{W}_{i}}$
$\displaystyle\geq
1-6M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}$
$\displaystyle-
MN\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min{(M,N)}}.$

For the ease of representation, we denote $\delta_{4}$ as

$\displaystyle\delta_{4}$
$\displaystyle:=6M^{2}N^{2}C_{5}(\mathbb{W},\epsilon)e^{-\tilde{C}_{2}(\mathbb{W},\epsilon)\min{(M,N)}}$
(84) $\displaystyle\ \
+MN\tilde{C}_{3}(\mathbb{W},\epsilon)e^{-\tilde{C}_{4}(\mathbb{W},\epsilon)\min{(M,N)}}$
$\displaystyle\geq 1-\|\mathcal{P}_{\bm{\Psi}}\bm{\Phi}^{(k)}\|_{F}.$

Then one can bound the difference between $\bm{\Phi}^{(k)}$ and its projection
as

$\displaystyle\|\bm{\Phi}^{(k)}-\mathcal{P}_{\bm{\Psi}}\bm{\Phi}^{(k)}\|_{F}^{2}\overset{(a)}{=}\|\bm{\Phi}^{(k)}\|_{F}^{2}-\|\mathcal{P}_{\bm{\Psi}}\bm{\Phi}^{(k)}\|_{F}^{2}$
(85) $\displaystyle\leq 1-(1-\delta_{4})^{2}\leq 2\delta_{4}.$

The equality $(a)$ is due to the Pythagorean Theorem.

Then for any
$\bm{\phi}=\sum_{k}\alpha_{k}\bm{\Phi}^{(k)}\in\mathcal{S}_{\Phi}$, we follow
the same procedures in (78) and (79), to bound $\|\bm{\phi}\|_{F}^{2}$ and
$\mathcal{P}_{\bm{\Psi}}\bm{\phi}$. Noting that
$<\bm{\Phi}^{(k)},<\bm{\Phi}^{(l)}>=0$ for $k\neq l$, we have

$\|\bm{\phi}\|_{F}^{2}=(\sum_{k}\alpha_{k}^{2}),$ (86)

and

$\|\mathcal{P}_{\bm{\Psi}}\bm{\phi}\|_{F}^{2}\geq(\sum_{k}\alpha_{k}^{2})(1-MN\sqrt{2\delta_{4}}).$
(87)

Therefore, we complete the proof by

$\cos^{2}(\Theta_{\mathcal{S}_{\bm{\Psi}}\mathcal{S}_{\bm{\Phi}}})=\inf_{\bm{\phi}\in\mathcal{S}_{\bm{\Phi}}}\frac{\|\mathcal{P}_{\bm{\Psi}}\bm{\phi}\|_{F}^{2}}{\|\bm{\phi}\|_{F}^{2}}\geq
1-MN\sqrt{2\delta_{4}}.$ (88)

##  Appendix H Proof of Theorem 10

In this proof, we consider the trace and Frobenius norm of
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$. Like the proof of Theorem 5, we
bound the number of eigenvalues in $[\epsilon,1-\epsilon]$ by calculating
$\sum_{p}\lambda_{\bm{N},\mathbb{W}^{\Diamond}}^{(p)}(1-\lambda_{\bm{N},\mathbb{W}^{\Diamond}}^{(p)})$.
Firstly, we consider the $i$-th region $\mathbb{W}^{\Diamond}_{i}$. We assume
its center point is placed on the origin, as the location does not influence
the eigenvalues of $\mathbb{W}^{\Diamond}_{i}$. Given $ad-bc=V\neq 0$, the
$i$-th region on the frequency domain is

$\displaystyle\mathbb{W}^{\Diamond}_{i}=\left\\{(f,g):-W^{[0]}_{i}\leq
af+bg\leq W^{[0]}_{i},\right.$ (89) $\displaystyle\left.-W^{[1]}_{i}\leq
cf+dg\leq W^{[1]}_{i}.\right\\}$

The covariance of the samples at the “time” domain $[m,n]$ and $[p,q]$ is
given by

$\displaystyle\
B_{i}(m,n,p,q)=\int_{\mathbb{W}^{\Diamond}_{i}}exp(j2\pi(m-p)f+j2\pi(n-q)g)\text{d}f\text{d}g$
(90)
$\displaystyle=\frac{1}{|V|}\int_{-W^{[1]}_{i}}^{W^{[1]}_{i}}\int_{-W^{[0]}_{i}}^{W^{[0]}_{i}}exp(j2\pi(m-p)(d/Vu-b/Vv)$
$\displaystyle\ \ \ +j2\pi(n-q)(-c/Vu+a/Vv))\text{d}u\text{d}v$
$\displaystyle=\frac{1}{|V|}\int_{-W^{[1]}_{i}}^{W^{[1]}_{i}}\int_{-W^{[0]}_{i}}^{W^{[0]}_{i}}exp(j2\pi/V(md-
pd-nc+qc)u)$ $\displaystyle\ \ \ exp(j2\pi/V(-mb+pb+na-
qa)v)\text{d}u\text{d}v$
$\displaystyle=|V|\frac{\sin(2\pi/VW^{[0]}_{i}(-(n-q)c+(m-p)d))}{\pi(-(n-q)c+(m-p)d)}$
$\displaystyle\ \ \
\frac{\sin(2\pi/VW^{[1]}_{i}((n-q)a-(m-p)b))}{\pi((n-q)a-(m-p)b))}$

Then we can calculate the traces of
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}_{i}}$ and
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}$ respectively, as

$trace(\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}_{i}})=4MNW^{[0]}_{i}W^{[1]}_{i}/|V|=MN|\mathbb{W}^{\Diamond}_{i}|,$
(91)

and

$trace(\mathcal{B}_{\bm{N},\mathbb{W}}^{\Diamond})=\sum_{i}trace(\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}_{i}})=MN|\mathbb{W}^{\Diamond}|.$
(92)

Take $s=n-q$ and $t=m-p$. The square of the Frobenius norm of
$\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}_{i}}$ is calculated as

$\displaystyle F_{i}=$
$\displaystyle\sum_{n,q=0}^{N-1}\sum_{m,p=0}^{M-1}B(m,n,p,q)^{2}$ (93)
$\displaystyle=|V|^{2}\sum_{s=1-N}^{N-1}(N-|s|)\sum_{t=1-M}^{M-1}(M-|t|)$
$\displaystyle\ \
\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}.$

Below, we separate $F$ into two parts $F_{a}$ and $F_{b}$

$\displaystyle F_{a}=|V|^{2}MN\sum_{s=1-N}^{N-1}\sum_{t=1-M}^{M-1}$ (94)
$\displaystyle\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}.$

$\displaystyle F_{b}=$ (95)
$\displaystyle|V|^{2}\sum_{s=1-N}^{N-1}|s|\sum_{t=1-M}^{M-1}M\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}$
$\displaystyle+|V|^{2}\sum_{s=1-N}^{N-1}N\sum_{t=1-M}^{M-1}|t|\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}$ .

One can verify that $F_{i}\geq F_{a}-F_{b}$. We then bound
$F_{a}=MN|\mathbb{W}^{\Diamond}_{i}|-O(M+N)$ in Appendix H-A and
$F_{b}=O(M\log(N)+N\log(M))$ in Appendix H-B.

With these bounds, we finally show the following inequality

$\displaystyle\ \
\sum_{p}\lambda^{(p)}_{\bm{N},\mathbb{W}^{\Diamond}}(1-\lambda^{(p)}_{\bm{N},\mathbb{W}^{\Diamond}})$
(96)
$\displaystyle=trace(\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}})-\|\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}}\|_{F}^{2}$
$\displaystyle\leq
MN|\mathbb{W}^{\Diamond}|-\sum_{i=0}^{J-1}\|\mathcal{B}_{\bm{N},\mathbb{W}^{\Diamond}_{i}}\|_{F}^{2}$
$\displaystyle=O(JN\log(M)+JM\log(N)).$

The number of the eigenvalues lie in $[\epsilon,1-\epsilon]$ will be
$O(JN\log(M)+JM\log(N))/(\epsilon(1-\epsilon))$, which is small compared to
the total number $MN$.

###  H-A Bounding $F_{a}$

Note that $ad-bc\neq 0$. Therefore, $-sc+td$ and $sa-tb$ are both equal to 0
only when $s=t=0$.

$\displaystyle F_{a}$ (97)
$\displaystyle=|V|^{2}MN\sum_{s=1-N}^{N-1}\sum_{t=1-M}^{M-1}\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}$ $\displaystyle=4MNW_{i}^{[0]}W_{i}^{[1]}/|V|-$
$\displaystyle\sum_{\\{s,t:|s|\geq Nor|t|\geq
M\\}}\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}$ $\displaystyle\geq 4MNW_{i}^{[0]}W_{i}^{[1]}/|V|$
$\displaystyle-2MN|V|^{2}\underbrace{\sum_{\\{s,t:t\geq
M\\}}\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}}_{\alpha}$
$\displaystyle-2MN|V|^{2}\underbrace{\sum_{\\{s,t:s\geq
N\\}}\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}}_{\beta}$

Below, we bound $\alpha$. Denote $s_{1}=\lfloor\frac{td}{c}\rfloor$ and
$s_{2}=\lfloor\frac{tb}{a}\rfloor$. We assume $s_{2}-s_{1}>4$ without loss of
generality when $M$ is sufficiently large and $t\geq M$.

$\displaystyle\alpha$ $\displaystyle\leq\sum_{t\geq
M}\sum_{s=-\infty}^{s_{1}-2}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}$ (98) $\displaystyle+\sum_{t\geq
M}\sum_{s=s_{1}+2}^{s_{2}-2}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}$ $\displaystyle+\sum_{t\geq
M}\sum_{s=s_{2}+2}^{\infty}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}$ $\displaystyle+\sum_{t\geq
M}\sum_{s=s_{1}-1}^{s_{1}+1}\frac{4}{V^{2}}\frac{1}{\pi^{2}(as-bt)^{2}}$
$\displaystyle+\sum_{t\geq
M}\sum_{s=s_{2}-1}^{s_{2}+1}\frac{4}{V^{2}}\frac{1}{\pi^{2}(cs-dt)^{2}}$

In the above inequality, we separate the region
$\\{(s,t)\in\mathbb{Z}^{2}:t\geq M\\}$ into several disjoint parts. Then we
try to give the bounds of these summations with integrals over these
continuous regions. The first three parts are $\\{(s,t)\in\mathbb{Z}^{2}:t\geq
M,s\leq s_{1}-2\\}$, $\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s_{1}+2\leq s\leq
s_{2}-2\\}$ and $\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s\geq s_{2}+2\\}$. We take
$Z=\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s_{1}+2\leq s\leq s_{2}-2\\}$ for
example. For any $(s,t)\in Z$ and a large $M$, at least one region $C^{*}$
among $[s,s+1]\times[t,t+1]$, $[s-1,s]\times[t,t+1]$,$[s,s+1]\times[t-1,t]$
and $[s-1,s]\times[t-1,t]$ is a subset of $C=\\{(x,y)\in\mathbb{R}^{2}:y\geq
M-1,td/c+1\leq x\leq tb/a-1\\}$. We can bound
$\frac{1}{(-cs+dt)^{2}}\frac{1}{(as-bt)^{2}}$ with an integral on $C^{*}$ as

$\displaystyle\ \ \frac{1}{(-cs+dt)^{2}}\frac{1}{(as-bt)^{2}}$ (99)
$\displaystyle=\frac{1}{(-cs+dt)^{2}}\frac{1}{(as-
bt)^{2}}\frac{\int_{C^{*}}\frac{1}{(-cx+dy)^{2}}\frac{1}{(ax-
by)^{2}}dxdy}{\int_{C^{*}}\frac{1}{(-cx+dy)^{2}}\frac{1}{(ax-
by)^{2}}\text{d}x\text{d}y}$
$\displaystyle\leq\frac{(|-cs+dt|+|c|+|d|)^{2}}{(-cs+dt)^{2}}\frac{(|as-
bt|+|a|+|b|)^{2}}{(as-bt)^{2}}$ $\displaystyle\ \ \ \
\int_{C^{*}}\frac{1}{(-cx+dy)^{2}}\frac{1}{(ax-by)^{2}}\text{d}x\text{d}y$
$\displaystyle\leq\frac{(2|c|+|d|)^{2}(2|a|+|b|)^{2}}{a^{2}c^{2}}\int_{C^{*}}\frac{1}{(-cx+dy)^{2}}\frac{1}{(ax-
by)^{2}}\text{d}x\text{d}y.$

The first inequality is due to $\frac{1}{(-cx+dy)^{2}}\frac{1}{(ax-
by)^{2}}\leq\frac{1}{(|-cs+dt|+|c|+|d|)^{2}}\frac{1}{|as-bt|+|a|+|b|)^{2}}$
for any $(x,y)\in C^{*}$. The second inequality is due to $|-cs+dt|\geq c$ and
$|-as+bt|\geq a$ for any $(s,t)\in Z$. For the other two parts
$\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s\leq s_{1}-2\\}$ and
$\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s\geq s_{2}+2\\}$, the same bound holds.

The last two parts are $\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s_{1}-1\leq s\leq
s_{1}+1\\}$ and $\\{(s,t)\in\mathbb{Z}^{2}:t\geq M,s_{2}-1\leq s\leq
s_{2}+1\\}$. Similarly, we achieve the following two bounds for $(s,t)$ in
each part.

$\displaystyle\frac{1}{(as-bt)^{2}}$ $\displaystyle=\frac{1}{(as-
bt)^{2}}\frac{\int_{t}^{t+1}\frac{1}{(ax-
by)^{2}}\text{d}y}{\int_{t}^{t+1}\frac{1}{(ax-by)^{2}}\text{d}y}$ (100)
$\displaystyle\leq\frac{|as-bt|+|a|+|b|}{(as-
bt)^{2}}\int_{t}^{t+1}\frac{1}{(ax-by)^{2}}\text{d}y$
$\displaystyle\leq\frac{(2|a|+|b|)^{2}}{a^{2}}\int_{t}^{t+1}\frac{1}{(ax-
by)^{2}}\text{d}y$
$\frac{1}{(-cs+dt)^{2}}\leq\frac{(2|c|+|d|)^{2}}{c^{2}}\int_{t}^{t+1}\frac{1}{(-cx+dy)^{2}}\text{d}y$
(101)

Take the constant

$\displaystyle k$
$\displaystyle=4\max\left(\frac{(2|c|+|d|)^{2}(2|a|+|b|)^{2}}{a^{2}c^{2}},\right.$
(102)
$\displaystyle\left.\frac{(2|a|+|b|)^{2}}{a^{2}},\frac{(2|c|+|d|)^{2}}{c^{2}}\right),$

noting that the coefficient 4 is because the $1\times 1$ region may be used by
multiple (s,t) grids, and we can transfer the summation into integral form as

$\displaystyle\alpha$ $\displaystyle\leq
k\int_{t=M-1}^{\infty}\int_{s=-\infty}^{td/c-1}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}\text{d}s\text{d}t$ (103)
$\displaystyle+k\int_{t=M-1}^{\infty}\int_{s=td/c+1}^{tb/a-1}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}dsdt$
$\displaystyle+k\int_{t=M-1}^{\infty}\int_{s=tb/a-1}^{\infty}\frac{1}{\pi^{2}(-cs+dt)^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}\text{d}s\text{d}t$
$\displaystyle+k\int_{t=M-1}^{\infty}\sum_{s=s_{1}-1}^{s_{1}+1}\frac{4}{V^{2}}\frac{1}{\pi^{2}(as-
bt)^{2}}\text{d}t$
$\displaystyle+k\int_{t=M-1}^{\infty}\sum_{s=s_{2}-1}^{s_{2}+1}\frac{4}{V^{2}}\frac{1}{\pi^{2}(cs-
dt)^{2}}\text{d}t.$

Note that

$\displaystyle\ \ \int\frac{1}{(-cs+dt)^{2}}\frac{1}{(as-bt)^{2}}ds$ (104)
$\displaystyle=\frac{-2acs+adt+bct}{t^{2}V^{2}(as-bt)(cs-
dt)}+\frac{2ac}{t^{3}V^{3}}\log(\frac{|as-bt|}{|cs-dt|}).$

One can verify that all the items on the left of the second inequality are
$O(\frac{1}{M})$. Consequently, we have $\alpha=O(\frac{1}{M})$,
$\beta=O(\frac{1}{N})$ and $F_{a}=4MNW_{i}^{[0]}W_{i}^{[1]}/|V|-O(M+N)$.

###  H-B Bounding $F_{b}$

The process of bounding $F_{b}$ is much similar to that of $F_{a}$.

$\displaystyle F_{b}$
$\displaystyle=|V|^{2}\underbrace{\sum_{s=1-N}^{N-1}|s|\sum_{t=1-M}^{M-1}M\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}}_{\alpha}$ (105)
$\displaystyle+|V|^{2}\underbrace{\sum_{s=1-N}^{N-1}N\sum_{t=1-M}^{M-1}|t|\frac{\sin^{2}(2\pi/V(-sc+td))}{\pi^{2}(-sc+td)^{2}}\frac{\sin^{2}(2\pi/V(sa-
tb))}{\pi^{2}(sa-tb)^{2}}}_{\beta}$ .

Similarly, we can bound $\alpha$ with an integral on the region of interest
and additional values. By omitting the intermediate steps and abusing some
denotations, we obtain

$\displaystyle\alpha$ $\displaystyle\leq
V^{2}Nk\sum_{t=1-M}^{M-1}|t|\frac{-2acs+adt+bct}{t^{2}V^{2}(as-bt)(cs-dt)}$
(106) $\displaystyle\ \ +\frac{2ac}{t^{3}V^{3}}\log(\frac{|as-bt|}{|cs-
dt|})\Bigg{|}^{s=N}_{s=-N}$ $\displaystyle\ \
+V^{2}Nk\sum_{t=1-M}^{M-1}\frac{4}{V^{2}}\frac{1}{\pi^{2}(\frac{ad}{c}-b)^{2}|t|}.$

One can verify that $\alpha=O(N\log(M))$ and similarly $\beta=O(M\log(N))$.

## References

  * [1] Z. Zhu and M. B. Wakin, “Approximating sampled sinusoids and multiband signals using multiband modulated dpss dictionaries,” Journal of Fourier Analysis and Applications, vol. 23, no. 6, pp. 1263–1310, 2017.
  * [2] Y. C. Eldar and M. Mishali, “Robust recovery of signals from a structured union of subspaces,” IEEE Transactions on Information Theory, vol. 55, no. 11, pp. 5302–5316, 2009.
  * [3] D. L. Donoho, “De-noising by soft-thresholding,” IEEE transactions on information theory, vol. 41, no. 3, pp. 613–627, 1995.
  * [4] J. Wright, A. Y. Yang, A. Ganesh, S. S. Sastry, and Y. Ma, “Robust face recognition via sparse representation,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 31, no. 2, pp. 210–227, 2009.
  * [5] P. Indyk and M. Kapralov, “Sample-optimal fourier sampling in any constant dimension,” in 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 514–523, IEEE, 2014.
  * [6] M. Mishali and Y. C. Eldar, “From theory to practice: Sub-nyquist sampling of sparse wideband analog signals,” IEEE Journal of Selected Topics in Signal Processing, vol. 4, no. 2, pp. 375–391, 2010.
  * [7] M. Wakin, S. Becker, E. Nakamura, M. Grant, E. Sovero, D. Ching, J. Yoo, J. Romberg, A. Emami-Neyestanak, and E. Candes, “A nonuniform sampler for wideband spectrally-sparse environments,” IEEE Journal on Emerging and Selected Topics in Circuits and Systems, vol. 2, no. 3, pp. 516–529, 2012.
  * [8] D. Cohen, L. Pollak, and Y. C. Eldar, “Carrier frequency and bandwidth estimation of cyclostationary multiband signals,” in 2016 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 3716–3720, 2016.
  * [9] Z. Zhu and M. B. Wakin, “Wall clutter mitigation and target detection using discrete prolate spheroidal sequences,” in 2015 3rd International Workshop on Compressed Sensing Theory and its Applications to Radar, Sonar and Remote Sensing (CoSeRa), pp. 41–45, 2015.
  * [10] M. Mishali and Y. C. Eldar, “Blind multiband signal reconstruction: Compressed sensing for analog signals,” IEEE Transactions on Signal Processing, vol. 57, no. 3, pp. 993–1009, 2009.
  * [11] D. Slepian and H. O. Pollak, “Prolate spheroidal wave functions, fourier analysis and uncertainty — i,” Bell System Technical Journal, vol. 40, no. 1, pp. 43–63, 1961.
  * [12] H. J. Landau and H. O. Pollak, “Prolate spheroidal wave functions, fourier analysis and uncertainty — ii,” Bell System Technical Journal, vol. 40, no. 1, pp. 65–84, 1961.
  * [13] H. J. Landau and H. O. Pollak, “Prolate spheroidal wave functions, fourier analysis and uncertainty—iii: The dimension of the space of essentially time- and band-limited signals,” Bell System Technical Journal, vol. 41, no. 4, pp. 1295–1336, 1962.
  * [14] D. Slepian, “Prolate spheroidal wave functions, fourier analysis, and uncertainty—v: The discrete case,” Bell System Technical Journal, vol. 57, no. 5, pp. 1371–1430, 1978.
  * [15] T. Zemen and C. Mecklenbrauker, “Time-variant channel estimation using discrete prolate spheroidal sequences,” IEEE Transactions on Signal Processing, vol. 53, no. 9, pp. 3597–3607, 2005.
  * [16] M. A. Davenport and M. B. Wakin, “Compressive sensing of analog signals using discrete prolate spheroidal sequences,” Applied and Computational Harmonic Analysis, vol. 33, no. 3, pp. 438–472, 2012.
  * [17] Z. Zhu, S. Karnik, M. A. Davenport, J. Romberg, and M. B. Wakin, “The eigenvalue distribution of discrete periodic time-frequency limiting operators,” IEEE Signal Processing Letters, vol. 25, no. 1, pp. 95–99, 2018.
  * [18] A. Jain and S. Ranganath, “Extrapolation algorithms for discrete signals with application in spectral estimation,” IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 29, no. 4, pp. 830–845, 1981.
  * [19] X. Xu and Y. Gu, “Oblivious near-optimal sampling for multidimensional signals with fourier constraints,” in Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (F. Ruiz, J. Dy, and J.-W. van de Meent, eds.), vol. 206 of Proceedings of Machine Learning Research, pp. 4532–4555, PMLR, 25–27 Apr 2023.
  * [20] D. Slepian, “Prolate spheroidal wave functions, fourier analysis and uncertainty — iv: Extensions to many dimensions; generalized prolate spheroidal functions,” Bell System Technical Journal, vol. 43, no. 6, pp. 3009–3057, 1964.
  * [21] S. Ramani, D. Van De Ville, and M. Unser, “Non-ideal sampling and adapted reconstruction using the stochastic matern model,” in 2006 IEEE International Conference on Acoustics Speech and Signal Processing Proceedings, vol. 2, pp. II–II, IEEE, 2006.
  * [22] H. Avron, M. Kapralov, C. Musco, C. Musco, A. Velingker, and A. Zandieh, “A universal sampling method for reconstructing signals with simple fourier transforms,” in STOC 2019 - Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (M. Charikar and E. Cohen, eds.), Proceedings of the Annual ACM Symposium on Theory of Computing, pp. 1051–1063, Association for Computing Machinery, June 2019.
  * [23] J. Bosse and O. Rabaste, “Subspace rejection for matching pursuit in the presence of unresolved targets,” IEEE Transactions on Signal Processing, vol. 66, no. 8, pp. 1997–2010, 2018.
  * [24] Z. Li, H. Ye, Z. Liu, Z. Sun, H. An, J. Wu, and J. Yang, “Bistatic sar clutter-ridge matched stap method for nonstationary clutter suppression,” IEEE Transactions on Geoscience and Remote Sensing, vol. 60, pp. 1–14, 2022\.
  * [25] R. A. Horn and C. R. Johnson, Matrix analysis.  Cambridge university press, 2012.

  *[DPSSs]: discrete prolate spheroidal sequences
  *[2-D]: 2-dimensional
  *[PSWFs]: prolate spheroidal wave functions
  *[1-D]: 1-dimensional
  *[MSE]: mean squared error