{'fraction_non_alphanumeric': 0.05070282211777956, 'fraction_numerical': 0.011479066946784779, 'mean_word_length': 3.9160988074957412, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 19, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Sampling of stochastic operators

We develop sampling methodology aimed at determining stochastic operators that satisfy a support size restriction on the autocorrelation of the operators stochastic spreading function. The data that we use to reconstruct the operator (or, in some cases only the autocorrelation of the spreading function) is based on the response of the unknown operator to a known, deterministic test signal.


INTRODUCTION
In wireless and wired communication, in radar detection, and in signal processing it is usually assumed that a signal is passed through a filter, whose parameters have to be determined from the output. Commonly, such systems are modeled with a time-variant linear operator acting on a space of signals. For narrow-band signals, we can model the effects of Doppler shifts and multi-path propagation as the sum of "few" time-frequency shifts that are applied to the sent signal. In general, the channel consists of a continuum of time-frequency scatterers: the channel is formally represented by an operator with a superposition integral (1) (Hf )(x) = η(t, ν) M ν T t f (x) dt dν, where T t is a time-shift by t, that is, T t f (x) = f (x − t), t ∈ R, M ν is a frequency shift or modulation given by M ν f (x) = e 2πiνx f (x), ν ∈ R. We define the Fourier transform of a function f (x) to be It follows that M ν f (ξ) = f (ξ − ν) = T ν f (ξ). The function η(t, ν) is called the (Doppler-delay) spreading function of H.
To identify the operator means to determine the spreading function η of H from the response Hf (x) of the operator to a given sounding signal f (x). The not necessarily rectangular support of the spreading function is known as the occupancy pattern, and its area as spread of the operator H. The fundamental restriction for the spread to be less than one has been shown to be necessary and sufficient for the identifiability of channels [12,4,24,29]. This extends results on classes of underspread operators that are defined as those with rectangular occupancy pattern of area less than one.
This extension of the class of underspread channels to operators with spread less than one is particularly of interest in the field of sonar communication [14] and in the multiple input-single output channel settings. Acoustic channels possess larger spreads than radar and wireless channels. This is due to the speed of sound being magnitudes lower than that of electromagnetic waves, resulting in time delays up to several seconds and Doppler spreads in the tens of Hertz for highfrequency channels [2]. Another type of channels with large values for the area of the occupancy pattern are multiple input -single output (MIMO) channels; they combine several deterministic spreading functions into one channel, thus covering a larger region of the time-frequency plane [26].
In recent work, the identifiability results [12,4,16,29] have been recast within the framework of operator sampling [28,24]. For example, in [28], concrete reconstruction formulas for deterministic operators are established, that satisfy the spread constraints mentioned above, and which resemble the Whittaker-Shannon interpolation formula In this paper, we develop operator sampling in the stochastic setting and give analogous reconstruction formulas.
Taking into account the random nature of real-world communication environments, we model such channels with stochastic time-variant operators [10,12,3,4]. In this setting, the spreading function η(t, ν) of the operator H in (1) is a random process † indexed by (t, ν) that is to be recovered from the output process Hf (x) indexed by x. For the purposes of this paper, it would be enough to think of η(t, ν; ω) as a (t, ν)-indexed family of random variables on a common probability space Ω , or as a random process with instances from L 2 (R 2 ).
In the sibling paper [25] we develop and use the theory of stochastic modulation spaces to rigorously define and prove identification results for operators with spreading functions belonging to a class of generalized random processes -including delta functions and white noise. The norm inequalities that are proven there are essential to justify use of delta trains as sounding signals. However, in this paper, we are going to ignore these subtleties and treat distributions on par with Lebesgue integrable functions, for ease of exposition only. The fine points of the underlying mathematical analysis will be mentioned in a few side remarks.
1.1. Operator sampling theory in the historical perspective. The progress of operator identification theory largely follows the evolution of the related theory of function sampling. The two major directions of generalization are the introduction of stochasticity (stationary and non-stationary) and the removal of the requirement that the "bandlimitation" is rectangular. For convenience, we summarize this development in Table 1.
For example, based on the classical Shannon-Nyquist sampling theorem, a corresponding result for bandlimited stationary stochastic processes was proven in great † Here, and in remainder of the paper, random functions and operators are denoted by boldface characters, x is a complex conjugate of x, x * conjugate transpose. E stands for expectation, and µ for both 2D area and 4D volume.  [20]. We cite it here in the form given in a classic book by Papoulis.
Theorem 1. [23, p. 378] If a stationary process x(t) is bandlimited, that is, if its power spectral density S(ξ) = F τ →ξ E{x(t)x(t + τ )} is integrable and supp S(ξ) ⊂ [−Ω/2, Ω/2], then we can recover x(t) in the mean-square sense from the samples taken at rate Ω = T −1 . In fact, The requirements of stationarity and the bandlimitation of the spectrum to the symmetric interval were later relaxed by Kluvánek and Lloyd. In his 1963 groundbreaking paper [12], Kailath realized that for a deterministic time-variant channel to be identifiable, it is necessary and sufficient that the product ΩT of the maximum time delay T and maximum Doppler spread Ω is not greater than one. Since, channels were called underspread whenever ΩT < 1, and overspread if ΩT > 1 [37]. The insight of Kailath has been generalized and formalized by Kozek and Pfander. Following in Kailath footsteps, the seminal paper of Bello lays the groundwork for channel sampling and characterization tools and vocabulary. In the sequel [4] Bello further argues that it is not the product ΩT that matters for identification of a deterministic time-variant channel, but rather the spread, or the area of what he calls an occupancy pattern, that is, the not necessarily rectangular support of the spreading function supp η. In particular, Bello's assertion has been put into a rigorous mathematical framework and was proven using novel tools from Gabor analysis by Pfander and Walnut. Also, the ideas developed in [3] were used to estimate the capacity of the channels with non-rectangular spread [7].
A brief comment of Kailath [12] suggests sufficiency of ΩT ≤ 1 for the identification of stationary stochastic channels as well as deterministic, and Bello treats this question as a side matter, more interested in developing the estimator for η(t, ν) when the output has been contaminated by additive noise.
As with the development of function sampling, a simpler stationary model for operator identification has seen most research. The channel has the property of widesense stationarity with uncorrelated scattering (WSSUS), that is, the autocorrelation function of η(t, ν) has the form In other words, taps at different delays are uncorrelated and stationary. The function C η (t, ν) is known as the scattering function of H. It completely characterizes the second-order statistics of η and represents the power spectral density of the transfer function of the channel. This means that the scattering function represents the expected behavior of the operator. Two common types of methods to identify the scattering function are deconvolution and direct measurement methods [1,9,21,13]. In [32] we apply the methodology developed here and in [25] to study WSSUS channels in depth. Theorem 16 below guarantees identifiability of a WSSUS channel whenever its scattering function is merely compactly supported.
In this paper, we address a more general problem of stochastic spreading function reconstruction and stochastic operator sampling and identification for not necessarily WSSUS channels.
1.2. Overview of the paper. Deterministic identification results in [16,29] allow for the recovery of the deterministic spreading function whenever its support has area less than one. We discuss this in detail in Section 2.1. It is easy to see that in the case of a stochastic spreading function, such deterministic reconstruction formulas are still applicable to each random variate, allowing for the recovery of an instance spreading function η(t, ν; ω) from the response H(ω)f (x), where ω is an element of the sample space Ω . However, on its own, each instance will provide little information about the average behavior of the operator H. Secondly, it is possible that the 4-dimensional volume of the support of the 4D autocorrelation function R η (t, ν; t , ν ) is less than one, while some instances η(t, ν; ω) have 2D area greater than one.
The contributions of this paper follow. In Section 2.3 we consider the case when the 4-dimensional autocorrelation function R η (t, ν; t , ν ) of the operators' spreading function is supported on a 4D region U = supp R η (t, ν; t , ν ) that can be expressed as a tensor product of some 2D region S with itself. In this scenario, we prove that it is possible -and give an explicit reconstruction formula (10) -to recover the stochastic spreading function of the channel in the mean-square sense from the response Hf of a channel to a periodic weighted delta train, provided that the set S occupies a region of area less than one. This case will include the special case deterministic operators as their autocorrelation functions satisfy R η (t, ν; t , ν ) = η(t, ν) η(t , ν ).
In Section 2.4 the case of an arbitrary support region U = supp R η (t, ν; t , ν ) is considered. With some abuse of nomenclature, we will also say that we can (stochastically) identify a stochastic operator if we can recover the 4-dimensional autocorrelation function R η (t, ν; t , ν ) (and not the stochastic spreading function, as in the previous case) from the autocorrelation function of the response Hf of the channel to a periodically weighted delta train (and not the stochastic response itself). In Theorem 12 we prove that in this sense we can identify the operator H provided that the support pattern of the autocorrelation function is permissible.
Analogous to the deterministic criterion µ(S) < 1, the requirement µ(U ) < 1 is also necessary for stochastic identifiability of a stochastic operator, as we show in an sibling paper [25]. In this paper, we demonstrate patterns that correspond to regions of 4D volume less than one but are nonetheless unidentifiable by our methods.
Permissibility of a pattern is a geometric property linking the operator sampling theory to finite Gabor frame theory. After giving preliminary remarks on Gabor frames in finite dimensions in Section 1.3 below, in Section 3 we show that the support patterns of the the autocorrelation functions of the operators are in one-to-one correspondence with the column subsets of special Gabor frames. We provide a (partial) classification of the autocorrelation patterns and analyze several phenomena that emerge for Gabor frames of higher dimension Section 3.1 and Section 3.2.
1.3. Finite-dimensional Gabor frames. A deterministic operator is a particular case of the stochastic operator with a degenerate probability distribution, so the results for stochastic operator identification must necessarily be compatible with the deterministic ones. In the theory of deterministic operator identification, the existing operator identification proofs pivot on the so-called Haar property of Gabor frames. A finite-dimensional Gabor frame in C L is defined as , where the finite-dimensional translation operators T k and modulation operators M n operating on a vector c ∈ C L are given by A frame has the Haar property whenever its elements are in general linear position, that is, any subset of L elements is linearly independent. A finite-dimensional Gabor frame G generated by window c as defined in (2), has the Haar property for almost every choice of window c, given that the ambient dimension L is prime [18]. Application of our methods to the stochastic case spawns a more peculiar Gabor frame on Z L × Z L , the properties of which differ in the key respect of linear independence of its subsets. In particular, such a frame has small subsets that are linearly dependent for any choice of window c, even when the parameter L is prime.

Deterministic operators.
Equivalently to (1), any operator H acting on onevariable signals can be represented with its symbols, and its Kohn-Nirenberg symbol σ(x, ξ) = F t→ξ h(x, t), then All these symbols of H can be transformed into each other using partial Fourier transforms and area-preserving shears, such as I 2 f (x, t) = f (x + t, x) [11]. In particular, the spreading function and the Kohn-Nirenberg symbol are related through where the symplectic Fourier transform is given by In the following, it will sometimes be advantageous to present the results with h, κ, or σ instead of η and we will not hesitate to do so. However, we formulate our results primarily with η due to its particularly simple relationship to the short-time Fourier transform. On the Schwartz dual space S of tempered distributions, we define the short-time Fourier transform to be for any ϕ in the Schwartz space S. Then for all f, ϕ ∈ S we have the useful equality The inner product ·, · is taken to be conjugate linear in the second variable.
We will say that H belongs to an operator Paley-Wiener space if the support of the spreading function η(t, ν) = F s σ(x, ξ) is contained in a compact subset of the time-frequency plane, Colloquially, we refer to H as "bandlimited" to S.
The connection of the operator sampling theory to the more established function sampling is best observed on the following theorem for Hilbert-Schmidt operators with the spreading function supported on a rectangle in the time-frequency plane. An operator H : L 2 (R n ) → L 2 (R n ) is Hilbert-Schmidt (H ∈ HS(R n )) whenever its spreading function η(t, ν) ∈ L 2 (R 2n ).
and H can be reconstructed by with convergence in L 2 (R 2 ). Here and in the following, we denote δ a (t) = δ(t − a).
Note that if H is a multiplication operator with a bandlimited multiplier, Theorem 2 reduces to the classic Shannon sampling theorem.
Remark. In order to accommodate delta functions and other generalized functions as identifiers we require that η(t, ν) is a mapping from the dual M ∞ (R 2 ) of the Feichtinger algebra M 1 (R 2 ) into the Hilbert space of zero-mean random variables RV(Ω ). Here, the modulation space M 1 (R n ) is defined via the finiteness of the norm is its continuous dual [11].
Functional analytic arguments of [16,30,24,25] show that whenever η(t, ν) is compactly supported (which is a physically reasonable assumption taken here) it is possible to extend the domain of H from L 2 to the whole of M ∞ and further to the Wiener amalgam space W (FL ∞ (R 2d ), 1 ). Therefore, η(t, ν) is well-defined as a linear functional on the corresponding predual space W (FL 1 (R 2d ), ∞ ) that includes certain tempered distributions, in particular, weighted delta trains x c = k∈Z c k δ kT as input for H.
Below, Theorem 5 gives a deep generalization of Theorem 2. It provides guarantees for recovery of those operators whose spreading function is supported on a set of arbitrary shape -not just a rectangle -as long as the area of the support is less than one. Additionally, it shows that it is possible to replace sin x/x with smooth functions with better decay through the use of partitions of unity generated by continuous functions. For a, ε > 0 we say r(t) generates an (a, ε)-partition of unity {r(t + ak)} k∈Z whenever

Lemma 4. For any compact set
Proof. This is a standard result from a theory of Jordan domains. A proof can be found in [8]. Any compact set with Jordan content less than one can be covered with L rectangles of cumulative area L · 1 L = 1, and it is easy to see that we do not lose generality requiring a, b to be small enough to satisfy a < 1/T, b < 1/Ω and L prime.
, Λ)-rectified as in Definition 3 (with ΩT not necessarily smaller than 1). Then there a vector c ∈ C L , and the test signal with convergence in L 2 (R 2 ). Here, the coefficients a j,k are uniquely determined by the choice of {c n }, and r(t), ϕ(t) are any functions such that r(t − ak) and ϕ(γ − bn) are (a, ε)-(respectively, (b, ε)-) partitions of unity in time (respectively, frequency) domains, with ε > 0 dependent on S.
Since we can always rectify a compact S with measure µ(S) < 1, Theorem 5 holds for a wider class of regions, namely, of all regions S whose so-called Jordan outer content is less than one [29].

Stochastic operator Paley-Wiener spaces. Let H be a stochastic operator with integral representation
and stochastic spreading function η(t, ν) a zero-mean random process such that η(t, ν; ω) ∈ L 2 (R 2 ) for all ω ∈ Ω . We denote the space of all such stochastic processes by StL 2 (R 2 ). The autocorrelation of the spreading function is given by

Definition 6.
We say that H is a stochastic Paley-Wiener operator bandlimited to U , whenever the support of R η (t, ν; t , ν ) is contained within a closed set U ⊆ R 4 , that is, In this section, we always assume U already rectified, as done in the deterministic case.
The symmetries of the autocorrelation function require a symmetric rectification, defined below. However, it will not cause any confusion that whenever we speak of a rectified 4D region, we always mean a symmetrically rectified one.

Definition 7.
The set U is (a, b, Λ)-symmetrically rectified if it can be covered by the translations Λ = λ j = (k j , n j , k j , n j ) such that the 4D volume of 2 is small: ab = 1 L , L is prime, and the right-hand side is a symmetric set.
It is easy to see that the above requirements imply that the volume of U satisfies µ(U ) ≤ 1, and conversely, it can be shown with little work that any symmetric compact set with Jordan content less than one can be rectified with a sufficiently large L [8]. This restriction on the area is crucial for operator identification. Before giving results for general operators whose autocorrelation functions are supported on arbitrary sets U ⊂ R 4 , we look at the sets of a special kind, where U = S × S. A general case will be considered in Section 2.4 below.
2.3. Sampling of stochastic operators supported on S × S. Under the special circumstance that U can be represented as a product S × S of some set S in R 2 , or rather, if we assume U to be (a, b, Λ)-symmetrically rectified, Λ = Γ × Γ for some Γ ⊂ Z × Z such that |Γ| = L, the operator (via its spreading function) can be reconstructed directly from the output of the weighted delta train input with an explicit formula similar to the one presented by Pfander and Walnut [31].
We define the non-normalized Zak transform Z : We say that a series of random processes n∈Z x n (t) converges to x(t) in meansquare sense where the translations χ (t + ak, ν + bn) generate an (a, b, ε)-partition of unity in the time-frequency domain.
This means that it is always possible to find c such that any two operators from StOPW(S × S) can be distinguished from their response to the pilot signal Proof. Let a, b > 0, L -prime with ab = 1 L be fixed numbers to be chosen later. This choice will depend on the support of η(t, ν). Let c ∈ C L ; indices of c should always be understood modulo L.
with all the equalities holding ω-surely, and the last equality being true for arbitrary p ∈ Z. Applying Zak transform to both sides, we get For all t, ν ∈ and all ω ∈ Ω we then have a mixing matrix equation is a vector-valued function on (t, ν) ∈ . By Lemma 4, the set S can be (a, b, Γ)-rectified, that is, there exists a collection of indices Γ = {(k j , n j )} L−1 j=0 such that η k,n (t, ν) ≡ 0 on (t, ν) ∈ for any (k, n) ∈ Γ. Therefore, by Lemma 9 below, the infinite sums in (5) can be trimmed to finite sums to obtain where G is the L × L 2 Gabor matrix of all time-frequency shifts of c ∈ C L given by (2), G Γ is the submatrix of G corresponding to columns indexed by Γ mod L, and is a column vector of nonzero patches of η(t, ν) defined by (4).
Without loss of generality, no two indices in Γ correspond to the same column of G, that is, (k, n) = (k , n ) mod L ∈ Γ for all (k, n) = (k , n ) ∈ Γ. Such collisions can always be avoided by choosing a different rectification (a , b , Γ ) such that the entire support set S is within [0, a L ) × [0, b L ), which can always be achieved using the inverse of G Γ . The solution to (6) can now be found, giving We can now combine the patches η k,n (t, ν) into the whole spreading function η(t, ν).
Proof. Denote Q = Z/LZ × LZ × Z the set of all indices on the left hand side. Consider The rectification of R η guarantees that Remark. Since the autocorrelation functions of WSSUS operators have the special form R η (t, ν; t , ν ) = δ(t − t ) δ(ν − ν ) C η (t, ν), Theorem 8 is applicable to WSSUS operators whenever the area of the support of the scattering function (also known as the spread of the operator) satisfies † In fact, for prime L the set of c ∈ C L such that every L × L submatrix of G is invertible is a dense open subset of C L [18]. Furthermore, all entries of c can be additionally chosen to have absolute value one.
µ(supp C η (t, ν)) < 1. However, it is intuitively clear that it is excessive to cover a 4D diagonal (a set of measure zero in R 4 ) with a single 4D parallelepiped of volume one. Indeed, covering it with a string of small parallelepipeds (as in Figure 2) is enough for identification and allows recovery of C η for supp C η bounded, of arbitrary size. This comes as a corollary from Theorem 13 and Theorem 16.
2.4. Stochastic operators with non-tensored support. In this section we proceed to the most general case of stochastic operators. Consider an operator H with a spreading function η(t, ν) such that the autocorrelation function R η (t, ν; t , ν ) is supported on some arbitrary bounded set U in R 4 . We will see that in general it is no longer possible to reconstruct η(t, ν) itself. For instance, this happens because with nonzero probability some instances η(t, ν; ω) may have spread larger than one, violating the necessary condition of the deterministic Theorem 5. Nevertheless, one may hope to recover R η (t, ν; t , ν ) from the autocorrelation of the received information R f (t, t ).
To prove Theorem 12 below, we will need to solve equations of the form Y = GXG * with both X, Y positive semi-definite. † To this end, we need a standard technique from linear algebra. Let vectorization vec : C n×n → C n 2 be the linear isomorphism between the space of matrices C n×n and the space of column vectors C n 2 given by stacking of the columns (vec A) i = A i mod n, i /n , i = 0, . . . , n 2 − 1. The following identity relating vectorization and the Kronecker product of matrices is well known [36,34]: (7) vec(AXB t ) = (A ⊗ B) vec X. For an arbitrary matrix A, the set Λ A = {(λ, λ ) : A λ,λ = 0} is called the support set of A. From the properties of positive semi-definite matrices it is easy to see that (8) (λ, λ ) ∈ Λ implies {(λ , λ), (λ, λ), (λ , λ )} ⊆ Λ. With some abuse of terminology, we call sets that may appear as support sets of positive semi-definite matrices, and hence satisfy (8), positive semi-definite patterns or, for short, spd patterns. Proof. (i) ⇒ (ii) By contraposition, let there be 0 = N ∈ C n×n such that GN G * = 0; let E be the diagonal matrix whose λth diagonal entry is one if (λ, λ) ∈ Λ and zero else. Then there exists a positive real number C (for example, Gershgorin circle theorem guarantees C = N 1 = sup 1≤i≤m m j=1 |N ij | < ∞ will be enough) such that both CE + N and CE are positive semi-definite, and G(CE + N )G * = G(CE)G * + GN G * = G(CE)G * , thus violating the uniqueness of X in (i), as both supp(CE + N ) and supp N ⊆ Λ. † An hermitian matrix X ∈ C n×n is positive semi-definite if for any a ∈ C n , a * Xa ≥ 0.
(iii) ⇒ (ii) Let an Hermitian matrix N be supported on Λ and be a solution to 0 = GN G * . Applying vectorization to both sides of 0 = GN G * , we get by (7) (9) vec 0 = (G ⊗ G) vec N, Let A ∈ C m×m be an arbitrary square matrix supported on Λ such that G ⊗ G Λ vec A = 0, that is, GAG * = 0. The Cartesian decomposition of A is given by A = H 1 + iH 2 with both H 1 , H 2 Hermitian, defined by It is easy to see that both supp H 1 , supp H 2 ⊆ Λ, and GH 1 G * = GH 2 G * = 0, since GA * G * = (GAG * ) * = 0. Therefore, by (ii), H 1 = H 2 = 0 , and A = 0. It follows that vec A = 0. Since vec A is arbitrary, it follows that the columns of G ⊗ G Λ are linearly independent, that is, G ⊗ G Λ is left invertible.
Definition 11. We would say that a spd support set Λ is a permissible pattern if some c ∈ C L generates a Gabor frame G = [M n T k c] L−1 k,n=0 such that the equivalent conditions of Lemma 10 are satisfied. If an spd pattern is not permissible, it will be called defective.
This designation reflects the emergence of these patterns as those which permit the sampling of operators with delta trains.
Proof. Again, as in the deterministic case, we start with the support already rectified in the sense of Definition 7. We proceed in the same manner as in the direct product case until the mixing formula (5), which guarantees that for p = 0, . . . , L − 1 for all (t, ν) within the base rectangle = [0, a) × [0, b) Taking autocorrelation on both sides, we get for all p, p = 0, . . . , L − 1, and (t, ν), (t , ν ) ∈ , Let supp R η (t, ν; t , ν ) be covered by L 2 4-dimensional parallelepipeds indexed by Λ = {(k, n, k , n )}, that is, Without loss of generality, all (k, n) and (k , n ) are distinct modulo L. † For brevity, let T j be the translation Let us denote Y p,p = E Z p Z * p and X k,n,k ,n = E η k,n η * k ,n , where * stands for conjugate transpose. As covariance matrices of zero-mean random vectors, both X k,n,k ,n and Y p,p are positive semi-definite, and conversely, every positive semi-definite matrix is a covariance matrix for some random vector [23]. With this notation, we write for each (t, ν), (t , ν ) ∈ a deterministic matrix equation where G = [M n T k c] is a Gabor matrix as in (2).
To have a a unique positive semi-definite solution X of the underdetermined system of equations (11) with an arbitrary positive semi-definite Y , by Lemma 10 it is necessary and sufficient that G ⊗ G Λ is left invertible. Let A denote its left inverse, The autocorrelation of the channel spreading function can be recovered from X by observing (starting with the definition (4) of η k,n ), where we construct Y from the autocorrelation of the received signal f (t) = Hx c (t) via Translating and simplifying, we get Upon substitution of the above back into (12), we get the desired reconstruction formula (10). This completes the proof of Theorem 12.
If the support of R η can be factored into a tensor square of some set of area less than one on the time-frequency plane, then Theorem 12 guarantees reconstruction of R η from the autocorrelation R f of the received measurement Hx c , which is a weaker result than Theorem 8. To wit, assume that R η is supported on a product set S × S such that S × S is (a, b, Λ)-rectified, and that the area of S is less than one. It follows that Λ itself can be represented as a direct product of some index set, say, Λ = Γ × Γ such that S is (a, b, Γ)-rectified. For some vector c the submatrix of its time-frequency shifts G Γ is left invertible [29,18]. Then (G ⊗ G)| Λ = G Γ ⊗ G Γ is also left invertible, and R η (t, ν; t , ν ) can be recovered from R f (t, t ).
The strength of Theorem 12 is that it allows to exploit information about more complicated dependencies between scatterers manifested in the geometry of the support of the autocorrelation function R η (t, ν; t , ν ).   For example, consider the important case of the WSSUS operators, already mentioned in the Lemma 2.3 after Theorem 8. Let H big be some WSSUS operator whose scattering function C η (t, ν) is supported on a 2D rectangle S big = [0, 1)×[0, L). This rectangle S big of area greater than one can always be rectified with a collection Λ big of L 2 translations of a box [0, 1) × [0, 1 L ). From the WSSUS assumption we know that R η (t, ν; t , ν ) = 0 whenever (t, ν) and (t , ν ) are in different boxes, therefore, the 4D set supp R η (t, ν; t , ν ) is (1, 1 L , Λ big )-rectifiable, as shown in Figure 2b. It follows that in the sense of Theorem 12, H big is identifiable whenever the diagonal set Λ big is a permissible pattern. Since, according to Theorem 16, this is always the case with any such diagonal set, we obtain the following corollary of Theorem 12. depending only on c such that we can reconstruct the scattering function C(t, ν) of H from the autocorrelation of its response to an L-periodic c-weighted delta train x c = k∈Z c k mod L δ ak using (13).
Proof. For an arbitrary ε, it is always possible to find a, b > 0, 1 ab > µ(S) + ε such that the support of the scattering function S is covered by N translations of the rectangle [0, a) × [0, b) (as usual, indexed by Λ), such that µ(S) ≤ N ab ≤ µ(S) + ε. Without loss of generality, all (k, n) ∈ Λ are distinct modulo L = 1 ab . We cover the 4D diagonal of the set S × S with N 4D parallelepipeds of volume 1/(ab) 2 , so the total volume of the cover is N L 2 ≤ 1. By Theorem 12, there exists c ∈ C L such that we can reconstruct the autocorrelation of the spreading function from the response f = Hx c using a version of (10) that takes advantage of the stationarity of H and periodicity of x c :

PERMISSIBLE PATTERNS
The preceding discussion shows that it is ultimately important to study which spd patterns Λ are permissible, that is, for which sets Λ there exists c ∈ C L such that G ⊗ G Λ is full rank. Consider the spreading function η(t, ν) of H given by Due to the specifics of the underlying time-frequency analysis, it will be convenient to index the matrices with the finite index set J given by We call the autocorrelation pattern of η the indicator matrix ACP ∈ {0, 1} J ×J where λ = (k, n), λ = (k , n ), λ, λ ∈ J . Clearly, ACP must be symmetric, moreover, just as in (8), and conversely, for any matrix A ∈ C J ×J that satisfies (15), there exists an operator with the spreading function η A (t, ν; t , ν ) whose autocorrelation pattern is A. We visualize autocorrelation patterns with diagrams such as Figure 3, where shaded boxes correspond to nonzero correlation between patches.
Lemma 10 indicates that the problem at hand is linked to the Haar property of Gabor systems. We explore this connection in more detail in Section 3.3. The Haar property of a finite-dimensional Gabor frame reads that any L columns of a generic Gabor matrix G are in general linear position. By the result from [18], this holds for almost every G with L prime. Therefore, any deterministic spreading function supported on L boxes of area 1/L on a time-frequency plane can be identified. In other words, any set Γ ⊂ J such that |Γ| = L indexes a subset of columns of G that is linearly independent for almost every seed vector c. This contrasts with the stochastic setting, where we will see that there exist plenty of spd patterns that correspond to submatrices of G ⊗ G which are rank-deficient for every choice of c.
Generally, G ⊗ G can be viewed as a Gabor system on the non-cyclic group (k, n), (k , n ) ∈ J , π(k, n, k , n ) = M n T k c ⊗ M n T k c}.
The Haar property of G ⊗ G would require all subsets of G ⊗ G of order L 2 to be linearly independent, which is not the case for any prime number L ≥ 2. However, the positive-definiteness of the autocorrelation function demands the autocorrelation pattern to satisfy property (15). This precludes certain subsets of G ⊗ G from being tested for linear dependence. Below we show that this restriction implies that for L = 2 every spd pattern is permissible; not so for L ≥ 3. Figures 3 and 4 we show all possible spd patterns for L = 2.

Case L = 2. On
In addition, the last pattern on Figure 4b, corresponds to a linear dependent set of elements of G ⊗ G. However, due to lack of symmetry, such a set cannot appear as a support set for the autocorrelation of the spreading function of the stochastic operator. We mention it here to highlight the connection of the stochastic operator identification theory with the analysis of Gabor frames on general abelian groups, for this example, Z 2 × Z 2 . Further properties of such frames, including this pattern, can be found in [17,27].    Interestingly, the only admissible patterns on L = 2 belong to one of the two types, shown on Figure 3 and Figure 4a. The first type contains sets that can be represented as rank-1 products † of sets of order L in J , that is, there exists a set Γ or order |Γ| = L such that Λ = Γ × Γ. Such product patterns inherit the linear independence properties of their factors, since the Haar property of G guarantees (16) rank The second type, all boxes on the diagonal, of maximal possible tensor rank, is also a permissible pattern for L = 2, as we observe the determinant of the matrix or almost all choices of the generating atom c = [c 0 c 1 ] t . This concludes the analysis of the L = 2 case with a happy ending: Let a function R η (t, ν; t , ν ) be supported on a set of measure less than or equal to one covered with 4 boxes 2 + (k j a, n j b, k j a, n j b) for some {(k j , n j , k j , n j ) ∈ J × J } 3 j=0 , and such that ab = 1 /2 and all (k, n), (k , n ) distinct modulo 2. Let η(t, ν) be some function with R η (t, ν; t , ν ) as its autocorrelation function, and H a stochastic channel with η its spreading function. Then we can recover R η (t, ν; t , ν ) from the response of H to the sounding signal Here, 1 corresponds to the diagonal case, plus there are 9 7 choices of 7 boxes on the diagonal, any two of which can be correlated corresponding to the 7 2 factor, etc. ‡ The problem of classifying all possible arrangements of boxes becomes intractable very quickly with L. In Section 3.3, we show that whenever some Λ is a permissible pattern for almost all c, there is a related (via the permutations of the Gabor elements) family of Λ σ that will be permissible patterns for almost all c. Such observations simplify the classification problem, although they do not suffice to give a complete classification.
Secondly, alas, unlike L = 2, some spd patterns correspond to rank-deficient subsets of G ⊗ G. That is, there are sets that satisfy (8) but are not permissible, for example, see Figure 5. It turns out that there are structural reasons for patterns on Figure 6 and Figure 5 to be permissible (respectively, defective).
With little effort it can be seen that patterns with tensor rank 2 (as on Figure 5) can never be permissible, owing solely to the properties of the tensor product † We say that an element b ∈ S ⊗ S has tensor rank k if k is the smallest number with the property that there exist a 1 , a 2 , . . . , a k , b 1 , b 2 , . . . , b k ∈ S such that Λ = a 1 ⊗ b 1 + · · · + a k ⊗ b k . ‡ The case of even number of boxes on the diagonal is always counted within the larger odd case; by symmetry considerations, every correlation between boxes adds two boxes on the field). space and not to the specifics of the underlying Gabor structure. In fact, for any L, permissible patterns cannot contain two complete large sets of pairwise tensor products. (Here, such two sets are {η 00 , η 01 } and {η 02 , η 10 }, and in this context, large means that # {η 00 , η 01 } + # {η 02 , η 10 } = 2 + 2 > 3.) Proposition 15. Let G ∈ C n×m be an arbitrary matrix, and G 1 , G 2 its submatrices comprising columns of G indexed, respectively, by Γ 1 and Γ 2 such that Γ 1 ∩ Γ 2 = ∅.
Both are Hermitian, and This means that we have found a Hermitian matrix supported on Λ such that GN G * = 0 and, hence, G ⊗ G Λ is linearly dependent. It follows that Λ is not a permissible pattern.
On the other hand, the patterns with maximal tensor rank (that is, diagonal patterns) will always be permissible. This corresponds to the important case of WSSUS operators. We give here an elementary proof for finite dimensions. (See also [5,Theorem 3.1] for a discussion of this in the realm of Hilbert-Schmidt operators in infinite dimensions.) Theorem 16. Denote π(k, n) = M n T k . Let G = {π(k, n)c} L−1 k,n=0 be a Gabor frame generated by c. Then for almost all c ∈ C L , the set G ⊗ G diag of all tensor products of each Gabor element with itself is linearly independent, that is, for almost all c ∈ C L the diagonal set is a permissible pattern.
Proof. It is a straightforward observation that the linear independence of the set G ⊗ G diag ∈ C J ×J is equivalent to the linear independence of the family of the corresponding finite-dimensional Hilbert-Schmidt operators P k,n : C L → C L given by P k,n x = x, π(k, n)c π(k, n)c. Clearly, P k,n = (M n T k )P 0,0 (M n T k ) * . From the spreading function representation of H : it is easy to see with the help of the commutation relation T k M n = e −2πikn M n T k that for any H we have Here and in what follows, the summation is over Z L and all the indices of vectors c, x ∈ C L are taken modulo L. We compute which proves that η 0,0 [p, q] = 1 L V c c[p, q]. We claim that for almost every c ∈ C L , V c c has full support. For a fixed pair p, q ∈ Z L × Z L , the set of solutions Z p,q = {c ∈ C L : V c c [p, q] = 0} is a manifold of zero measure in C L . Hence, V c c has full support almost everywhere, namely whenever c ∈ C L \ p,q Z p,q . The proof is complete by observing that whenever η 0,0 has full support, the family {M (k,n) η 0,0 } (k,n)∈Z L ×Z L is linearly independent in    Another source of deficiency that begins to appear only with L ≥ 4 is illustrated on Figure 7. Proposition 17. Let the height (or, equivalently, the width) of the pattern Λ exceed L, or, formally, for some λ 0 ∈ Λ, #{λ : (λ 0 , λ ) ∈ Λ} > L.
Then Λ is not the permissible pattern. The matrix G ⊗ G Λ is singular for all c ∈ C L .
Proof. Let Γ = {λ : (λ 0 , λ ) ∈ Λ}. Then |Γ| > L, therefore, the set G Γ is linear dependent. Hence, we can find a nontrivial vector a ∈ ker G Γ . We now have That is, we have found a nontrivial linear combination i∈Γ a i g i = 0, and i∈Γ a i g i ⊗ g 1 = i∈Γ a i (g i ⊗ g 1 ) = 0.
The theorem immediately follows from Lemma 10 by observing that whenever there exists a non-trivial A supported on Λ, not skew-Hermitian and such that GA = 0, (here, A = a 0 ), then a non-trivial Hermitian matrix A + A * satisfies G(A + A * )G * = 0.
The existence of defective spd sets shows that one must be careful when trying to reconstruct the autocorrelation of the spreading function by sampling an operator with the delta train. Luckily, the task of weeding out defective patterns is uncoupled from the sampling procedure. All defective patterns Λ bad can be discovered numerically and inexpensively by testing a Gabor matrix generated by a random vector c. It is easy to see that the rank deficiency of G ⊗ G Λ will (with probability one) indicate whether Λ is good or bad.
Remark. Theorem 12 gives a procedure to recover E η η from the autocorrelation E f f of the response f = Hx c of H to an L-periodic c-weighted delta train x c = k∈Z c k mod L δ ak . The result is based on finding a permissible rectification of the set U . If some rectification satisfies the symmetry conditions for autocorrelations, but is not permissible, one can seek alternative (possibly finer) rectifications with the hope that one of them is permissible. However, Propositions 15 and 17 indicate that for some sets U there are no permissible rectifications, hence, Theorem 12 does not apply to StOPW(U ).
This observation does not imply that there exist symmetric U with 4D volume less than one and the property that no test signal g allows to recover E η η from the autocorrelation E Hg Hg . In fact, recovery may be possible using a different type of a pilot signal, for example, a non-periodic delta train.
3.3. Equivalence classes of permissible patterns. Let S J be the symmetry group of all permutations on the group J of order L 2 defined in (14). Definition 18. We call two spd patterns Λ and Λ σ on the grid J × J homologous whenever there exists a permutation σ ∈ S J such that Two homologous patterns Λ and Λ σ are equivalent if for almost all choices of the window c ∈ C L generating G, For example, the patterns on Figure 8 are all homologous, with the first two provably equivalent, according to Proposition 19 below.
Numerical evidence shows that linear independence of the subsets of the tensored Gabor frame G ⊗ G is invariant under homology in the sense of Definition 18, for example, all the patterns on Figure 8 are permissible, as tested on a large number of randomly chosen c. Also, for L = 3, 5, and 7, entire orbits of patterns {Λ σ } σ∈S J are permissible. Additional indirect support to the hypothesis that any two patterns that are homologous with respect to the permutation of the Gabor atoms have the same linear independence status for almost all c comes from the equivalence of all patterns for the case L = 2 (see Figure 3) and the universality of Theorems 15, 16 and 17 with respect to the permutations of the Gabor atoms.
We will describe the permutations σ ∈ S J such that Λ and Λ σ are provably equivalent for any Λ for almost all c ∈ C L . Clearly, all such permutations form a subgroup of S J . It remains an open question whether this subgroup is the whole group S J .
For sake of notational simplicity, let us identify the atoms of a Gabor frame G generated by a window c ∈ C L with the elements of the torus Z L × Z L . The (k, n)th atom g = M n T k c = π(k, n) c would correspond to (k, n) ∈ Z L × Z L , where finite-dimensional operators M and T are defined in (3), and π(k, n) = M n T k .

Proposition 19. Let
A denote the group of permutations σ ∈ S J such that Λ and Λ σ are equivalent for all spd patterns Λ ⊆ J for all c ∈ C L , except maybe for a set of measure zero. a) translations of the torus σ a (k, n) = (k +q, n+p) mod L belong to A for all p, q ∈ Z. b) reflection of the torus σ b (k, n) = (−n, k) mod L belongs to A. c) rotation of the torus σ c (k, n) = (k, −n) mod L belongs to A. Proof. Note that the linear independence of the subset G Λ of elements of G is invariant under scaling the atoms by scalars p λ , complex conjugation, and any invertible linear transformation T . Let G = [M n T k c] L−1 k,n=0 . First, we construct several Gabor frames closely related to G. a) It is easy to see that the Gabor frame G a constructed from the atom c a = ϕ a (c) = M p T q c is a column permutation of G up to constant multiples of columns by C = e 2πipk . Indeed, π(k, n) c a = M n T k (M p T q c) = M n e 2πipk M p T k T q c = e 2πipk M n+p T k+q c = C a π(k + q, n + p)c. The Fourier transform is a unitary operation which acts on the Gabor matrix from the left, hence it does not change the linear independence of the columns, scaling of columns by the constant C b notwithstanding. In other words, G b is a frame that is unitarily equivalent to a particular permutation of G, namely, it corresponds to rotating the torus, see Figure 10 [6,35]. Curiously, the vertical flip operation Ic j = c −j also creates an equivalent pattern. This can be understood by observing I = F 2 . This corresponds to the reflection of both rows and columns of the torus Z L × Z L . c) Another operation that preserves linear independence is conjugation. Let the Gabor frame G c be generated by the window c c = ϕ c (c) = c. Then G c contains all the atoms of G in the order that corresponds to the horizontal reflection of the torus group on itself. Note that taking conjugation does not destroy the linear independence of the vectors. Now let Λ be any spd pattern. From the above constructions of the Gabor frames G α , α = a, b, c, it is evident that for all generating atoms c α = ϕ α (c) ∈ C L , rank G α ⊗ G α Λ σα = rank G ⊗ G Λ . For any α = a, b, c the transformation ϕ α : c → c α is a bijective mapping C L → C L , therefore, if Λ is permissible for some c, then Λ σ is also permissible (for some other c), and moreover, if Λ is permissible for all c ∈ C L except a zero set Z, then Λ σ is also permissible for all c ∈ C L except a possibly different zero set Z σ . And conversely, if Λ is defective, then Λ σ is also defective. Since there are finitely many permutations σ, the union of all bad sets σ∈S J Z σ has measure zero, and it follows that Λ and Λ σ are equivalent.

CONCLUSION
We show that a large class of stochastic operators can be reconstructed from the stochastic process resulting from the application of the operator to an appropriately designed deterministic test signal. Our results are based on combining recently developed sampling results for deterministic band limited operators [16,29,24] and the sampling theory of stochastic processes [19,23]. The classes of stochastic operators considered here are characterized by support constraints on the autocorrelation of the stochastic spreading function of the operator. Our results do not necessitate the frequently used WSSUS condition, nor the so-called underspread condition on operators. Moreover, we show that in some cases when the operator cannot be fully determined from its action on a test signal, still, the second order statistics of the spreading function, that is, its autocorrelation can be determined from the operator output. While in the deterministic case the possibility of operator reconstruction only depends on the support size of the spreading function, we show that in the stochastic case geometric considerations play a fundamental role for reconstruction.