IdentificationofWirelessSystems TesidiLaurea CorsodiLaureainIngegneriadelleTelecomunicazioni UniversitàdegliStudidiPadova

Dipartimento di Ingegneria dell'Informazione, Padova. Department of Information Technology and Electrical

Engineering, ETH Zürich.

Corso di Laurea in Ingegneria delle Telecomunicazioni

Tesi di Laurea

Identification of Wireless Systems

Laureando

Irene Pappalardo

Relatore

Prof. Michele Zorzi

Correlatori

Prof. Helmut Bölcskei, Ing. Reinhard Heckel

1. Introduction 1

2. Identication of Wideband Time-Varying Systems 7

2.1. Mellin Transform and its Sampling Theorem . . . 7

2.2. Input-Output Relation of a Wideband Time-Varying System . . . 11

2.3. Discrete Time-Scale Characterization . . . 12

2.4. Finite Approximation . . . 18

2.5. Uncertainty Principle for Frequency and Scale Operators . . . 20

3. Identication of Narrowband Time-Varying Sparse Systems 29 3.1. Discrete Time-Frequency Characterization . . . 29

3.2. Matrix Representations . . . 32

3.3. Recovery Algorithms . . . 37

3.4. Simulation Results . . . 39

4. Identication of Parametric Underspread Linear Systems 43 4.1. System Characterization . . . 43

4.2. Assumptions for Identication . . . 44

4.3. Recovery Procedure: The Sampling Stage . . . 47

4.4. Matrix Formulation . . . 48

4.5. Recovery Procedure: The Recovery Stage . . . 51

4.5.1. First step: recovery of the measurement vectors. . . 51

4.5.2. Second step: ESPRIT algorithm and recovery of the delays . . 52

4.5.3. Third step: recovery of the Doppler-shifts and attenuation factors . . . 56

4.6. Implementation of the Recovery Stage . . . 57

4.7. Sucient Conditions for Identiability . . . 59

4.8. Identication for Multiple Inputs . . . 62

A. Proof of Theorem 5 67

1

Introduction

System identication is an important problem in engineering and it has many practical applications. These include channel identication in wireless communica-tion or underwater communicacommunica-tion, control engineering and radar imaging. In this thesis we consider the identication of wireless systems.

A wireless channel is usually modeled as a linear time-varying system [1]. The simplied characterization of a wireless channel is given by the multipath approxima-tion: the electromagnetic eld from the transmitter to the receiver is described by individual waves that travel along specic propagation paths and undergo dierent eects, like diraction, reection and absorption. At every point in space and time, the individual waves interfere with each other and form the overall electromagnetic eld. Furthermore, since the terminals of a wireless system are often mobile and the objects in the environment move as well, the resulting electromagnetic eld is also time-varying [2], i.e., the received signal consists of the superposition of time- and frequency- shifted versions of the transmitted signal, weighted by a spreading func-tion sH that characterizes the environment in which the communication takes place.

Under the approximation of innite multipath components, the received signal can be represented as [3] y(t) = Z τ Z ν sH(τ, ν)x(t − τ )ej2πνt dνdτ. (1.1)

This characterization implicitly assumes that signals involved are narrowband. That is, during the transmission of the signals, the motions in the system are slow com-pared to the signal propagation speed and the objects in the environment do not change position relative to the positional resolution of the signal (slowly uctuating objects) [4]. Suppose the transmitted signal has duration T and that the object velocity is v, then the narrowband condition on the signal bandwidth B is given by

2v

c 

1

T B (1.2)

precise and a wideband model is needed to account for the eects caused by high speed motion [6]. In the wideband signal model, the received signal is given by a superposition of the time shifted and time scaled versions of the input signal, weighted by a wideband spreading function χH. Letting a the scale parameter, the

input-output relation of a wideband system can be modeled as [6] y(t) = Z a Z τ χH(a, τ ) √ a x(a(t − τ )) dτ da. (1.3)

The identication problem, which is depicted in Fig. 1.1, can be stated as de-termining the parameters of the operator H, which models the channel/system, by input-output operations on the system response y(t) to a known probing signal x(t). The crucial point is to select a suitable probing signal and make appropriate compu-tations on the output in order to recover the parameters that completely characterize the system H. In particular, in order to recover an operator of the form (1.1), we need to recover sH; and to recover an operator of the form (1.3), we need to recover

χH. x(t) (known) H y(t) (measured)

Figure 1.1.: Identication problem.

If we consider the particular case of a linear time-invariant system, we have sH(τ, ν) = h(τ )δ(ν) for narrowband systems and χH(a, τ ) = g(τ )δ(a) for wideband

systems, where h(t) and g(t) are the impulse responses of the respective systems. Since the output of the system to the input probing signal x(t) = δ(t) is exactly its impulse response, which fully characterizes H, linear time-invariant systems are always identiable. The situation is fundamentally dierent for linear time-variant systems, where the response to the input x(t) = δ(t) is not equal to the impulse response and does not allow a complete characterization of the system. We require then to investigate on some conditions of the operator H, for which identication is possible. These requirements are often expressed in terms of the spreading functions support, which in both narrowband and wideband representations is supposed to be nite according to some physical limitations. In fact, due to physical restrictions on the system, time delays, Doppler shifts and scale shifts cannot take any real value but they are bounded within some ranges. For narrowband systems (1.1) Kailath [7] found that linear time-varying systems with spreading function sH compactly

sup-ported on a rectangle are identiable if and only if the spreading function's support area is not larger than 1. This result is generalized by allowing any shape of the support region, provided that the total area is not larger than 1 [8].

with the scale parameter.

Diculties arose because to apply a similar argument as Kailath did, we would need a result that species the approximate number of degrees of freedom of a scale and band limited signal, paralleling the 2WT theorem [9]. Therefore, the problem remains open.

In the second part of this thesis, we analyze the identication of sparse systems. Sparsity is an important property which has wide applications in many communi-cation channels. Practical examples are given by underwater environment, radar imaging and mobile communication. We consider a discretized version of (1.1) and assume the spreading function is sparse in a sense made precisely later. As for the case of wideband systems, some constraints on the input and output signals are needed in order to use the sampling theorem to derive a discrete representation of the system. In particular, we consider band limited input signals and assume the output is observed for a nite time duration. We focus on the possible procedures for recovery the samples of the spreading function, starting from the discrete repre-sentation of (1.1) developed in [15]. This allows to state the identication problem as solving a linear system of equations, i.e.,

Y = XS (1.4)

where X is the matrix of the known input samples, while Y and S contain, re-spectively, the samples of the output, measured from the system response, and the samples of the spreading function to be recovered.

The necessary conditions for identiability are connected with the notion of com-pressive sensing. The central idea is to identify the system, i.e., reconstruct the spreading function samples in S, assuming S has only a few nonzero entries. In this case the spreading function is referred to sparse and, as long as the system of equations (1.4) is underdetermined, it can admit a unique solution.

We analyze and compare two approaches that dier in the choices of the input signal and the algorithms used for recovery. The rst approach allows to formu-late the problem as a multiple measured vector (MMV) problem [16] where both Y and S in (1.4) are matrices whose columns constitute single measurements. The main property of the model is that the collection of sparse vectors share a common sparse support set, i.e., the positions of the nonzero samples in the columns of S are unchanged. The second approach is to formulate the recovery as a block-sparse prob-lem. In this case, the sparse vector of the spreading function has nonzero samples occurring in clusters, i.e., blocks. The algorithms we use for recovery are adap-tions of the orthogonal matching pursuit (OMP) algorithm which is the canonical greedy algorithm for sparse approximation [18]. The simultaneous OMP (S-OMP) algorithm [19] is used for the rst approach, while the block-sparse OMP (B-OMP) algorithm [20] is used for the second approach.

case. The main result is that the rst approach is superior to the second one, especially when the number of the samples of the discrete spreading function is large, i.e., the approximation of the continuous spreading function to be recovered is more precise.

As the third part of this thesis, we study the identication of a particular multiple input narrowband system, supposing always the communication channel is sparse. An interesting question on system identication is whether the spreading function can be identied when dealing with multiple input multiple output (MIMO) systems. In this situation, each output can be represented as a superposition of the responses of dierent subsystems applied to each input. Given that the spreading functions of the subchannels are independent, to characterize the identiability of MIMO systems we can without loss of generality consider multiple input single output (MISO) systems. We consider the extension to multiple inputs of a particular narrowband system, called parametric underspread linear system (ULS) [23], whose spreading function is described by a nite set of delays and Doppler-shifts, as expressed in the following. The input-output relation is given by

y(t) = Z τ Z ν X i ˜ sHi(τ, ν)xi(t − τ )e j2πνt_{dνdτ (1.5)}

where the spreading function ˜sHi of the i-th subchannel is given by

˜

sHi(τ, ν) =

Ki

X

k=1

αi,kδ(τ − τi,k)δ(ν − νi,k). (1.6)

In (1.6) the parameters αi,k, τi,k and νi,k represent the attenuation factor, the time

delay and the Doppler-shift,respectively, associated with the i-th subchannel, while Ki is the number of delay-Doppler pairs involved in ˜sHi. The crucial dierence to

the model considered in the second part of this thesis is that, in order to identify the system, we need to specify all the parameters above, for every subsystem ˜sHi. The

condition for identiability of a MIMO channel is provided in [21], given that the supports of the subsystems are known and in [15] given the support is unknown. The spreading functions ˜sHi in (1.6) are identiable if and only if the sum of the areas

of the support regions of ˜sHi is not larger than 1. We generalize the results of [22]

and [23] for SISO systems to MISO systems. In particular, with some adjustments we adopt the multiple inputs problem to a single input problem, applying then the same recovery procedure.

continuous channel. In Chapter 2 we study the identication of sparse systems and compare empirically the performances of two dierent recovery approaches. In Chapter 3 we extend the identication of the parametric underspread linear sys-tem to a multiple input single output syssys-tem and derive sucient conditions for identication.

Notations.

Lowercase boldface letters stand for column vectors and uppercase letters designate matrices. For the matrix A we write its transpose, complex conjugate, Hermitian (complex conjugate of the transpose) and Penrose pseudo-inverse by AT_{, A}∗_{, A}H

and A†_{, respectively. The entry in the kth row and lth column of A is denoted by}

[A]k,l. For the vector a, the kth element is written [a]k and its Euclidean norm is

denoted by kak2. Finally, for two functions x(t) and y(t) dened for t ∈ R, we write

2

Identication of Wideband Time-Varying

Systems

In the rst part of this chapter (Section 2.1) we introduce the Mellin transform, which will be useful to obtain a discrete characterization of wideband time-varying systems. The Mellin transform can be seen as an equivalent representation of the signal in the scale domain as well as the Fourier transform provides the spectral representation in the frequency domain. We also discuss a sampling theorem which enables the exact reconstruction of a scale limited signal from its samples in the time domain.

In the second part of the chapter (Sections 2.2 - 2.4) we derive the discrete char-acterization of a wideband channel, using the sampling theorems both in frequency and scale domains.

We conclude the chapter (Section 2.5) making some remarks about the scale op-erator and deriving the uncertainty principle for frequency and scale domains.

2.1. Mellin Transform and its Sampling Theorem

All the material in this section can be found in [12].

The Mellin transform Mf(β)of a function f(t), whose support in time domain is

(0, +∞), is dened [12] as Mf(β) = Z +∞ 0 1 √ tf (t)e +j2πβ ln t_{dt (2.1)}

If f(t) is dened also on (−∞, 0), the positive and negative parts have to be treated separately.

The inverse Mellin transform is dened as f (t) = Z +∞ −∞ 1 √ tMf(β)e −j2πβ ln t dβ (2.2)

1. Scale invariance. Indicating with Mf(β) the Mellin transform of f(t), then

the Mellin transform of f0(t) =

√

c0f (c0t) is given by

Mf0(β) = e

−j2πβ ln c0_M

f(β) (2.3)

Proof. Applying the denition in (2.1) on f0(t),

Mf0(β) = Z +∞ 0 1 √ t √ c0f (c0t)e+j2πβ ln tdt  u = c0t ⇒ dt = du c0  = Z +∞ 0 c0 √ uf (u)e +j2πβ ln u c0du c0 = e−j2πβ ln c0 Z +∞ 0 1 √ uf (u)e +j2πβ ln u_du = e−j2πβ ln c0_M f(β)

Note that Mf(β) and Mf0(β)have same supports.

2. Multiplicative convolution. Indicating with Mf1(β) and Mf2(β) the Mellin

transforms of f1(t) and f2(t) respectively, then the Mellin transform of the

multiplicative convolution of f1(t) and f2(t), given by

f1~ f2(t) = Z +∞ 0 f1(tt0)f2∗(t 0 )dt0 (2.4) is simply Mf1(β)M ∗ f2(β).

Proof. Applying the denition in (2.1) on f(t) = f1~ f2(t),

Mf(β) = Z +∞ 0 1 √ t Z +∞ 0 f1(tt0)f2∗(t 0 )dt0e+j2πβ ln tdt  u = tt0 ⇒ dt = du t0  = Z +∞ 0 Z +∞ 0 r t0 uf1(u)f ∗ 2(t 0 )e+j2πβ lnt0udt0du t0 = Z +∞ 0 1 √ uf1(u)e +j2πβ ln u_du Z +∞ 0 1 √ t0f ∗ 2(t 0 )e−j2πβ ln t0dt0 = Mf1(β)M ∗ f2(β)

In the same way as the Fourier transformation is used to reconstruct a band limited function from its uniformly spaced samples, the Mellin transform can be used to recover a scale limited function from its samples, exponentially spaced in the time domain. A function f(t) is said to be scale limited to scale β0 if the support

of its Mellin transform Mf(β) is [−β0, β0]. The scale support width is indicated

with B, B = 2β0.

Theorem 1. Sampling Theorem. A function f(t) ∈ L2_{(R), scale limited to}

β0, can be exactly reconstructed from its samples in time domain if the samples

are exponentially spaced along the time axis, i.e. from {f(τn_)}+∞

n=−∞, where τ =

e1/B _{and B = 2β} 0.

Proof. Consider a signal f(t), whose Mellin transform Mf(β) is scale limited to β0,

and indicate with B = 2β0 the scale support width of Mf(β). Due to the Fourier

series representation, for β ∈ [−β0, β0] Mf(β) can be expressed as

Mf(β) = +∞ X m=−∞ amej2π m Bβ (2.5)

where am are the coecients of the series expansion

am = 1 B Z β0 −β0 Mf(β)e−j2π m Bβdβ , m ∈ Z (2.6)

Indicating with τ = e1/B _{= e}1/(2β0), the coecients a

m in (2.6) are given by am = ln τ Z β0 −β0 Mf(β)e−j2πβm ln τdβ = ln τ Z β0 −β0 Mf(β)e−j2πβ ln τ m dβ , m ∈ Z (2.7)

The function f(t) can be expressed as the inverse Mellin transform of Mf(β)and,

using that f(t) is scale limited, (2.2) becomes f (t) = Z β0 −β0 1 √ tMf(β)e −j2πβ ln t_{dβ (2.8)} For t = τm_{, (2.8) becomes} f (τm) = Z β0 −β0 1 √ τmMf(β)e −j2πβ ln τm dβ (2.9)

Comparing (2.7) and (2.9), the relation between the coecients am and the function

f (t)is

am = ln τ

√

τm_{f (τ}m_{), m ∈ Z (2.10)}

represen-tation in (2.5) with m B = ln τ m _yields f (t) = Z β0 −β0 1 √ tMf(β)e −j2πβ ln t dβ = Z β0 −β0 1 √ t +∞ X m=−∞ amej2πβ ln τ m e−j2πβ ln tdβ = √1 t +∞ X m=−∞ am Z β0 −β0 e−j2πβ ln (τ−mt)dβ = √1 t +∞ X m=−∞ am 1 j2π ln (τ−m_t) h ej2πβ0ln (τ−mt)_{− e}−j2πβ0ln (τ−mt)i = √1 t +∞ X m=−∞ am sin[π(2β0) ln(τ−mt)] π ln(τ−m_t) = √1 t +∞ X m=−∞ am sin[πB ln(τ−mt)] π ln(τ−m_t)

Finally, substituting am from (2.10),

f (t) = √1 t +∞ X m=−∞ ln τ√τm_{f (τ}m₎sin[πB ln(τ −m_t)] π ln(τ−m_t) (2.11) = ln τ +∞ X m=−∞ f (τm)sin[πB ln(τ −m_t)] π√τ−m_{t ln(τ}−m_t) (2.12) = ln τ +∞ X m=−∞ f (τm)γ(τ−mt) (2.13)

where the function γ(t) is dened as γ(t) = sin[πB ln t]

π√t ln t = B √

t sinc(B ln t) (2.14)

with the sinc function dened as

sinc t = sin(πt) πt

For the sake of completeness, note that the Mellin transform of γ(t) is exactly the rectangular function with support [−β0, β0], similarly to the Fourier case. Applying

Mγ(β) = Z +∞ 0 1 √ tγ(t)e +j2πβ ln t_dt = Z +∞ 0 B t sinc(B ln t)e +j2πβ ln t dt (u = ln t ⇒ dt = tdu) = Z +∞ −∞ B sinc(Bu)e+j2πβudu = F−1[B sinc(Bu)] = rect β B  = = rect  β 2β0  = 1 if |β| ≤ β0 0 elsewhere (2.15)

where F−1 _{denotes the inverse Fourier transform and the rect function is dened as}

rect t = 1 if |t| ≤

1 2

0 elsewhere

2.2. Input-Output Relation of a Wideband

Time-Varying System

In a wideband time-varying system, the received signal y(t) is composed of a superposition of dierent versions of the transmitted signal x(t), time shifted and Doppler scaled ([5] and [6]), whose input-output relation is given by

y(t) = Z +∞ 0 Z +∞ −∞ χ(τ, a)√ax(a(t − τ ))dτ da. (2.16) The propagation delay τ is due to dierent scattering multipath lengths from transmitter to receiver and the time scale parameter a is due to relative motion of transmitter, scatters and receiver (Doppler eect). The scale parameter a can correspond either to a time expansion, if 0 < a < 1, or to a time compression, if a > 1, depending on whether the scatter is moving away from the receiver or is approaching it. The wideband spreading function χ(τ, a) represents the strength of the scatterers.

Due to physical limitations of the system, the support of the spreading function is assumed to be nite. χ(τ, a) can be considered eectively nonzero only for (τ, a) ∈ [0, Td] × [Al, Au], where Td is the multipath delay spread and As = Au − Al is the

2.3. Discrete Time-Scale Characterization

We follow the analysis presented in [10], to express (2.16) according to a corre-sponding discrete representation. The assumptions for the discrete time-scale model are presented here.

1. The Fourier transform X(f) of the transmitted signal x(t) has bounded sup-port within f ∈ [−W/2, W/2].

2. The Mellin transform Mx(β)of x(t) is band limited within β ∈ [−β0/2, β0/2].

These conditions could violate the uncertainty principle, particularly if the product of the scale support width and the bandwidth is small (see Section 2.5, Theorem 3). The analysis of the time-scale model is related only to the classes of input and output signals, for which the uncertainty principle is (approximately) valid.

Due to the assumptions above, it is reasonable to use the sampling theorems in the Fourier and in the Mellin domain (see Section 2.1), and consider the spreading function χ(τ, a), sampled both in time delay τ and in Doppler scale a.

Starting from the input-output relation (2.16) and using assumptions 1 and 2 above, a discrete time-scale characterization is derived as follows.

Function θ(τ, t) is dened as

θ(τ, t)= χM ∗(τ, t)√t. (2.18)

Indicating with Mθ(τ, β) the Mellin transform of θ(τ, t) with respect to t, M∗θ(τ, β)

is given by M∗_θ(τ, β) = Z +∞ 0 1 √ tθ ∗ (τ, t)e−j2πβ ln tdt = Z +∞ 0 1 √ tχ(τ, t) √ te−j2πβ ln tdt = Z +∞ 0 χ(τ, t)e−j2πβ ln tdt. (2.19) Using the denition (2.18), χ(τ, t) = θ∗_{(τ, t)/}√_{t. Substituting this expression into}

Now, applying the inverse Mellin transform (2.2) on function (x ~ θ(τ, ·))(t − τ) and using the multiplicative convolution property, the input-output relation (2.20) becomes y(t) = Z +∞ −∞ Z +∞ −∞ 1 √ t − τMx(β)M ∗ θ(τ, β)e −j2πβ ln (t−τ )_{dβdτ . (2.21)}

Assuming that the support of the Mellin transform of x(t) is bounded to [−β0/2, β0/2],

Mx(β) can be replaced with Mx(β)Pβ0(β), where

Pβ0(β) = rect  β β0  = 1 if |β| ≤ β0 2 0 elsewhere (2.22)

After this replacement, Mf(τ, β) = M∗θ(τ, β)Pβ0(β)is a scale limited Mellin

trans-form within [−β0/2, β0/2]. Its inverse Mellin transform f(τ, a) is, by denition (2.2),

f (τ, a) = Z +∞ −∞ 1 √ aM ∗ θ(τ, β)Pβ0(β)e −j2πβ ln a dβ (2.23)

and, according to the sampling theorem in scale domain (section 2.1, theorem 1), can be exactly reconstructed from its exponentially spaced samples, {f(τ, em/B_)}+∞

m=−∞,

with B = β0. Substituting the denitions (2.19) and (2.22) into (2.23) yields

f (τ, a) = Z β0₂ −β0₂ 1 √ a Z +∞ 0 χ(τ, t)e−j2πβ ln tdt e−j2πβ ln adβ = Z +∞ 0 1 √ aχ(τ, t) Z β0₂ −β0₂ e−j2πβ ln(ta)dβdt = Z +∞ 0 1 √ aχ(τ, t)β0sinc(β0ln(ta))dt. (2.24) From (2.24), the exponentially spaced samples of f(τ, a), with a = em/β0, m ∈ Z,

are given by f (τ, em/β0_{) =} Z +∞ 0 1 √ em/β0 χ(τ, t)β0sinc β0ln tem/β0

dt = Z +∞ 0 1 √ em/β0 χ(τ, t)β0sinc (m + β0ln t)dt , m ∈ Z. (2.25)

According to the nal result (2.12) of the sampling theorem in scale domain and using the samples in (2.25), function f(τ, a) in (2.24) can be expressed as

Finally, using the denition of the Mellin transform (2.1) on f(τ, a) in (2.26), with respect to a, Mf(τ, β) = M∗θ(τ, β)Pβ0(β)becomes M∗_θ(τ, β)Pβ0(β) = Z +∞ 0 1 √ af (τ, a)e j2πβ ln a_da = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc(m + β0ln t)dt × Z +∞ 0 1 aβ0sinc β0ln(ae −m/β0)
ej2πβ ln a_da. (2.27)

Using the denition (2.14) of γ(t) (with B = β0 in this case) on the last integral in

(2.27), M∗_θ(τ, β)Pβ0(β) = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc(m + β0ln t)dt × Z +∞ 0 1 √ a √ e−m/β0√ β0 ae−m/β0 sinc β0ln(ae−m/β0)
ej2πβ ln ada = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc(m + β0ln t)dt × Z +∞ 0 1 √ a √ e−m/β0γ(ae−m/β0₎  ej2πβ ln ada. (2.28)

Using the expression of the Mellin transform Mγ(β)in (2.15) and the scale invariance

property (2.3) on the last integral in (2.28), M∗_θ(τ, β)Pβ0(β) = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc(m + β0ln t)dt e−j2πβ ln e −m/β0 rect β β0  = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc(m + β0ln t)dt ej2πmβ/β0rect  β β0   1 β0 = ln a0  = +∞ X m=−∞ Z +∞ 0 χ(τ, t) sinc  m + ln t ln a0  dt ej2πmβ ln a0_rect β β0  . (2.29) From (2.29), with a sign change of variable m, the nal expression of M∗

Substituting (2.30) into (2.21), the input-output relation becomes y(t) = +∞ X m=−∞ Z +∞ −∞ Z +∞ 0 Z +∞ −∞ χ(τ, a) sinc  m − ln a ln a0  ×√ 1 t − τMx(β)e −j2πβ ln (am 0 (t−τ ))_dβdadτ = +∞ X m=−∞ Z +∞ −∞ Z +∞ 0 χ(τ, a) sinc  m − ln a ln a0  ×pam 0 Z +∞ −∞ 1 pam 0 (t − τ ) Mx(β)e−j2πβ ln (a m 0(t−τ ))dβdadτ.

Applying the inverse Mellin transform (2.2) in the last integral, y(t) = +∞ X m=−∞ Z +∞ −∞ Z +∞ 0 χ(τ, a) sinc  m − ln a ln a0  pam 0 x(a m 0 (t − τ ))dadτ = +∞ X m=−∞ Z +∞ −∞ Z +∞ 0 χ(τ, a) sinc ln a m 0 − ln a ln a0  da a m 2 0 x(a m 0 (t − τ ))dτ = +∞ X m=−∞ Z +∞ −∞ ˜ χ(τ, am₀ )a m 2 0 x(a m 0 (t − τ ))dτ (2.31)

where function ˜χ(τ, a) is a scale-smoothed version of the spreading function χ(τ, a) ˜ χ(τ, a) = Z +∞ 0 χ(τ, a0) sinc ln a − ln a 0 ln a0  da0. (2.32)

The nal discrete time-scale model results from (2.31), using a similar procedure as before but based on the Fourier transform, which is detailed as follows.

The integral in (2.31) is the convolution of the functions ˜χ(τ, am

0 )and a

m 2

0 x(am0 τ ).

Applying the denition of the inverse Fourier transform and using the convolution property of the Fourier transform, the input-output relation in (2.31) becomes

y(t) = +∞ X m=−∞  ˜ χ(τ, ·) ∗ a m 2 0 x(a m 0 τ )  (t) = +∞ X m=−∞ Z +∞ −∞ ˜ U (f, am₀ )a− m 2 0 X(a −m 0 f )e j2πf t_{df (2.33)}

where ˜U (f, a) is the Fourier transform of ˜χ(τ, a), with respect to τ, and X(f) is the Fourier transform of x(τ). Note that a−m

2

0 X(a −m

0 f ) is the Fourier transform of

a

m 2

0 x(am0 τ ).

Assuming that the support of the Fourier transform X(f) is band limited to [−W/2, W/2], then the Fourier transform a−

m 2

0 X(a −m

[−am

0 W/2, am0 W/2]and can be replaced with a −m₂ 0 X(a −m 0 f )Pam 0 W(f ), where Pam 0 W(f ) = rect  f am 0 W  = 1 if |f| ≤ am 0W 2 0 elsewhere (2.34)

After this replacement, G(f, am

0 ) = ˜U (f, a)Pam

0W(f ) is a band limited Fourier

transform. Its inverse Fourier transform is g(t, am₀ ) = Z +∞ −∞ ˜ U (f, a)Pam 0W(f )e j2πf t_{df (2.35)}

and, according to the sampling theorem in Fourier domain, can be exactly recon-structed from its uniformly spaced samples, {g(n/(am

0 W ), am0 )}+∞n=−∞. Substituting

the denitions of ˜U (f, a) and Pam

0 W(f ) into (2.35) yields g(t, am₀ ) = Z am₀ W₂ −am 0 W 2 Z +∞ −∞ ˜ χ(τ0, am₀ )e−j2πτ0fdτ0ej2πf tdf = Z +∞ −∞ ˜ χ(τ0, am₀ ) Z am₀ W₂ −am 0 W 2 e−j2π(τ0−t)fdf dτ0 = Z +∞ −∞ ˜ χ(τ0, am₀ )am₀ W sinc(am₀ W (τ0 − t))dτ0. (2.36)

From (2.36), the uniformly spaced samples of g(t, am

0 )are given by g  n am 0 W , am₀  = Z +∞ −∞ ˜ χ(τ0, am₀ )am₀ W sinc  am₀ W  τ0− n am 0 W  dτ0 = Z +∞ −∞ ˜ χ(τ0, am₀ )am₀ W sinc(n − am₀ W τ0)dτ0 , n ∈ Z. (2.37)

According to the sampling theorem in Fourier domain, function g(t, am

Finally, applying the Fourier transform in (2.38), with respect to t, G(f, am 0 ) = ˜ U (f, a)Pam 0W(f ) becomes ˜ U (f, a)Pam 0 W(f ) = Z +∞ −∞ g(t, am₀ )e−j2πf tdt = +∞ X n=−∞ Z +∞ −∞ ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0 × Z +∞ −∞ am₀ W sinc  am₀ W  t − n am 0 W  e−j2πf tdt = +∞ X n=−∞ Z +∞ −∞ ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0 × e−j2π nf am 0W rect  f am 0 W  . (2.39)

Substituting (2.39) into (2.33), the input-output relation becomes y(t) = +∞ X m=−∞ +∞ X n=−∞ Z +∞ −∞ Z +∞ −∞ ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0 × e−j2π nf am₀ W_a− m 2 0 X(a −m 0 f )e j2πf t_df = +∞ X m=−∞ +∞ X n=−∞ Z +∞ −∞ ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0 × Z +∞ −∞ a− m 2 0 X(a −m 0 f )e j2πf  t−_amn 0 W  df = +∞ X m=−∞ +∞ X n=−∞ Z +∞ −∞ ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0a m 2 0 x  am₀ t − n W 

Theorem 2. In a wideband time-varying system, if the transmitted signal x(t) is band limited and scale limited, i.e. its Fourier transform X(f) ≡ 0 if f /∈ [−W/2, W/2] and its Mellin transform Mx(β) ≡ 0 if β /∈ [−β0/2, β0/2], the

received signal y(t) is decomposed into discrete time shifts and Doppler scalings on the input signal x(t), weighted by a smoothed and sampled version of the wideband spreading function.

y(t) = +∞ X m=−∞ +∞ X n=−∞ ˆ χ  n am 0 W , am₀  a m 2 0 x  am₀ t − n W  (2.42) where ˆ χ(τ, am₀ ) = Z +∞ 0 Z +∞ −∞ χ(τ0, a0) sinc ln a − ln a 0 ln a0  sinc(am₀ W (τ − τ0))dτ0da0 (2.43) The relation (2.43) is obtained combining (2.32) and (2.41).

2.4. Finite Approximation

Both summations in (2.42) involve innitely many terms. However, due to the physical system restrictions described in section 2.2, the support of spreading func-tion χ(τ, a) is bounded in both time and scale domains, as expressed in (2.17). Specically, if χ(τ, a) is nonzero only when Al ≤ a ≤ Au, than ˜χ(τ, am0 ) dened in

(2.32) can be expressed as ˜ χ(τ, am₀ ) = Z Au Al χ(τ, a0) sinc ln a m 0 − ln a0 ln a0  da0 (γ = ln a0 ⇒ da0 = eγdγ) = Z ln Au ln Al χ(τ, eγ) sinc ln a m 0 − γ ln a0  eγdγ = Z ln Au ln Al χ(τ, eγ) sinc  m − γ ln a0  eγdγ. (2.44) Considering the approximation that the sinc function in (2.44) is nonzero only in the mainlobe, values of m corresponding to nonzero coecients of ˜χ(τ, am

0 ) are −1 ≤ m − γ ln a0 ≤ 1 γ ln a0 − 1 ≤ m ≤ γ ln a0 + 1 (2.45)

or, since m assumes only integer values,  ln Al ln a0  ≤ m ≤ ln Au ln a0  (2.46) Similarly, if χ(τ, a) is nonzero only when 0 ≤ τ ≤ Td, than ˆχ(n/(am0 W ), am0 ) dened

in (2.41) can be expressed as ˆ χ  n am 0 W , am₀  = Z Td 0 ˜ χ(τ0, am₀ ) sinc(n − am₀ W τ0)dτ0. (2.47) Applying in (2.47) the sinc approximation as before, values of n corresponding to nonzero coecients of ˆχ(n/(am

0 W ), am0 ) are −1 ≤ n − am₀ W τ0 ≤ 1 am₀ W τ0− 1 ≤ n ≤ am 0 W τ 0 + 1 (2.48)

From the integral in (2.47), substituting maximum and minimum values of τ0 _in

(2.48), it results that

−1 ≤ n ≤ am₀ W Td+ 1

or, approximately,

0 ≤ n ≤ dam₀ W Tde (2.49)

Combining the approximations (2.46) and (2.49) due to the limited system sup-port, the input-output relation in (2.16) admits the following nite-dimensional rep-resentation y(t) ≈ M1 X m=M0 N (m) X n=0 χn,mxn,m(t) (2.50) where M0 = bln Al/ ln a0c, M1 = dln Au/ ln a0e, N(m) = dam0 W Tde, χn,m = ˆχ  n am 0 W , am₀  (2.51) and xn,m(t), a time shifted and scaled version of x(t),

xn,m(t) = a m 2 0 x  am₀ t − n W  . (2.52)

The number of nonzero coecients in (2.50) are given by

or, without considering the ceil function in the right hand side of (2.53), M ≈ (M1− M0+ 1) + M1 X m=M0 am₀ W Td = (M1− M0+ 1) + W Td M1 X m=M0 am₀ = (M1− M0+ 1) + W Td aM1+1 0 − a M0 0 a0− 1 (2.54)

From (2.54), approximating M0 = ln Al/ ln a0 and M1 = ln Au/ ln a0

M ≈  ln Au ln a0 − ln Al ln a0 + 1  + W Td a ln Au ln a0+1 0 − a ln Al ln a0 0 a0− 1

(change of base formula) = ln

Au Al ln a0 + 1 ! + W Td a0Au− Al a0− 1 = ln Au Al ln a0 + 1 ! + W TdAl a0A_Au l − 1 a0− 1 (2.55)

2.5. Uncertainty Principle for Frequency and Scale

Operators

In this section we express the constraints intrinsically related to a signal with bounded Fourier and Mellin transforms, since our discrete model in section 2.3 is based on these assumptions. At rst we state the uncertainty principle for two arbitrary operators, as given in [11] and [14], and then derive the results for frequency and scale operators.

Some important notions are provided as a preliminary to the uncertainty principle. For a physical quantity a, there is always an operator A associated to. For two physical quantities a and b, with operators A and B, the operator AB means to operate rst with B and then with A.

The commutator of two operators A and B is an operator dened as

[A, B] =M AB − BA. (2.56)

If [A, B] = 0 or, equivalently, if AB = BA, the two operators commute. The anticommutator is dened as

[A, B]+ M

=AB + BA. (2.57)

Given a signal f(a) with unitary energy, i.e. R |f(a)|2_{da = 1, the average or mean}

of a is

hai = Z

a|f (a)|2da. (2.58)

In the above denition, function |f(a)|2 _{can be considered as the density function}

of a. The variance σ2

a of a is dened as the average of (a − hai)2

σ2_a = Z (a − hai)2|f (a)|2_da = Z a2|f (a)|2_{da +} Z hai2_{|f (a)|}2_{da − 2} Z ahai|f (a)|2da = ha2i + hai2_{− 2hai}2 = ha2i − hai2_{. (2.59)}

The standard deviation σa is dened as the square root of the variance.

Suppose to represent signal f(a) in a dierent domain, through an unitary trans-formation that associates to f(a) a new signal s(t). Then, the operator A is associ-ated to the variable a if the following relation is satised

hAi=M Z

s∗(t)As(t)dt = hai. (2.60)

Depending on the signal s(t) and on the domain where it is dened, the same operator A can be expressed in dierent forms, as it will be claried later for time and frequency operators.

The operator A associated to a is used in (2.60) to express the mean hai in (2.58), but it can also be used to express the variance σ2

a in (2.59) as the average of (A − hAi)2, according to σ_a2 = Z s∗(t)(A − hAi)2s(t)dt = Z s∗(t)A2s(t)dt + Z s∗(t)hAi2s(t)dt − 2 Z s∗(t)AhAis(t)dt = hA2i + hAi2_{− 2hAi}2 = hA2i − hAi2_{. (2.61)}

Given two operators A and B, associated to the variables a and b respectively, then the covariance Covab between a and b is dened as

Covab =

1

2hAB + BAi − hAihBi

= 1

2h[A, B]+i − hAihBi. (2.62)

An operator A is Hermitian if for any pair of functions f(t) and g(t) Z

f∗(t)Ag(t)dt = Z

g(t){Af(t)}∗dt. (2.63)

1. The mean hAi is real, as

hAi = Z

s∗(t)As(t)dt (Hermitian def. (2.63)) = Z s(t){As(t)}∗dt

= Z

s∗(t)As(t)dt ∗

= hAi∗ (2.64)

2. The operator A − hAi is also Hermitian, as Z

f∗(t)(A − hAi)g(t)dt = Z

[f∗(t)Ag(t) − f∗(t)hAig(t)] dt ((2.64) and Hermitian def. (2.63)) =

Z [g(t){Af(t)}∗− f∗(t)hAi∗g(t)] dt = Z [g(t){Af(t)}∗− g(t){hAif(t)}∗] dt = Z g(t){(A − hAi)f(t)}∗dt (2.65)

3. The mean of the operator A2 _is

hA2_{i =} Z s∗(t)A2s(t)dt = Z |As(t)|2_{dt (2.66)} hA2_{i =} Z s∗(t)A(As(t))dt (Hermitian def. (2.63) on s(t) and As(t)) =

Z As(t){As(t)}∗ dt = Z |As(t)|2dt

The adjoint A† _{of an operator A is another operator for which the following}

equality holds Z f∗(t)Ag(t)dt = Z g(t){A†f (t)}∗dt. (2.67) If A†

= A, then condition (2.67) becomes the denition of a Hermitian operator, and A is called self adjoint operator. The adjoint of a product of operators is given by

(AB)†=B†A†. (2.68)

In fact, operators A + A† _{and (A − A}†_{)/j are Hermitian whether A is Hermitian or}

not.

The anticommutator of two Hermitian operators A and B is also Hermitian, as [A, B]†₊ = (AB + BA)† = (AB)†+ (BA)† (property (2.68)) = B†A†+A†B† (A† =A and B†=B) = BA + AB = [A, B]+ (2.70) Having [A, B]†

+ = [A, B]+, the anticommutator is Hermitian. The product of two

Hermitian operators AB is not necessarily Hermitian. However, using the decom-position (2.69), the operator AB can be also expressed as

AB = 1 2(AB + (AB) † ) + 1 2(AB − (AB) † ) (property (2.68)) = 1 2(AB + B †_A† ) + 1 2(AB − B †_A† ) (A† =A and B†=B) = 1 2(AB + BA) + 1 2(AB − BA) (def. (2.56) and (2.57)) = 1 2[A, B]++ j 2[A, B]/j (2.71)

Theorem 3. Uncertainty Principle. For any two quantities a and b repre-sented by the respective Hermitian operators A and B, which do not commute, the uncertainty principle is

σaσb ≥

1

2|h[A, B]i| (2.72)

where σa and σb are the standard deviations of a and b, respectively, and h[A, B]i

is the mean of the commutator of A and B.

Proof. Dene operators A0 = A − hAi and B0 = B − hBi. From property (2.65),

they are Hermitian and their mean is zero. The commutator of A0 and B0 is equal

to that of A and B, as

[A0,B0] = A0B0−B0A0

= (A − hAi)(B − hBi) − (B − hBi)(A − hAi)

= AB − BA = [A, B]. (2.73)

The anticommutator of A0 and B0 is

[A0,B0]+ = A0B0+B0A0

= (A − hAi)(B − hBi) + (B − hBi)(A − hAi) = AB + BA − 2hBiA − 2hAiB + 2hAihBi

Taking the expectation of both sides of (2.74) and using the denition (2.62) yields h[A0,B0]+i = 2  1 2h[A, B]+i − hAihBi  = 2 Covab. (2.75)

Using the denition of variance in (2.61), σ_a2σ_b2 = Z s∗(t)(A − hAi)2s(t)dt × Z s∗(t)(B − hBi)2s(t)dt (def. of A0 and B0) = Z s∗(t)A2₀s(t)dt × Z s∗(t)B2₀s(t)dt (property (2.66)) = Z |A0s(t)|2dt × Z |B0s(t)|2dt (Schwarz inequality) ≥     Z {A0s(t)}∗{B0s(t)}dt     2 (Hermitian def. (2.63) on B0) =     Z s∗(t)A0B0s(t)dt     2 (def. (2.60)) = |hA0B0i| 2 . (2.76)

Expressing the product A0B0 as in (2.71)

A0B0 =

1

2[A0,B0]++ j

2[A0,B0]/j (2.77)

and taking the expectation of both sides of (2.77) yields hA0B0i = 1 2h[A0,B0]+i + j 2h[A0,B0]/ji (prop. (2.75)) = Covab+ j 2h[A0,B0]/ji. (2.78) Note that Covab and 1₂h[A0,B0]/ji are the real and imaginary parts of hA0B0i.

Substituting (2.78) into (2.76) yields σ_a2σ2_b ≥     Covab+ j 2h[A0,B0]/ji     2 = Cov2_ab+1 4|h[A0,B0]i| 2 (prop. (2.73)) = Cov2_ab+1 4|h[A, B]i| 2 . (2.79) Equation (2.79) is equivalent to σaσb ≥ 1 2 q 4 Cov2_ab+ |h[A, B]i|2.

which is a more general result of the uncertainty principle. Since Cov2

ab is non

The uncertainty principle holds in particular for frequency and scale operators. Before applying the theorem in this particular case, the time T, frequency F and scale C operators are here dened.

Assume that s(t) is an arbitrary function dened in time domain and S(f) is its Fourier transform. According to denition (2.58), the mean time hti is

hti = Z

t|s(t)|2dt = Z

s∗(t)ts(t)dt. (2.80)

Comparing (2.80) with (2.60), the time operator T, expressed in time domain, is simply

T = t. (2.81)

Starting from (2.80) and expressing s∗_{(t) as inverse Fourier transform yields}

hti = Z Z S∗(f )e−j2πf tdf ts(t)dt = Z S∗(f ) Z ts(t)e−j2πf tdtdf (derivative property) = Z S∗(f ) 1 −j2π dS(f ) df df = Z S∗(f ) j 2π d dfS(f )df (2.82) = Z S∗(f )TS(f)df. (2.83)

Comparing (2.82) and (2.83) with (2.60), the time operator T in frequency domain, is given by

T = j 2π

d

df. (2.84)

In the same way, the frequency operator F in frequency domain is

F = f (2.85)

as, according to the frequency mean hfi in Fourier domain hf i =

Z

f |S(f )|2df = Z

S∗(f )f S(f )df . (2.86) Starting from (2.86) and expressing S∗_{(t) as Fourier transform yields}

From (2.87) and (2.88), the frequency operator F in time domain is F = 1 j2π d dt = − j 2π d dt. (2.89)

Summarizing, the time T and frequency F operators in both time and frequency domains are T = t ; F = − j 2π d dt (time domain) (2.90) T = j 2π d df ; F = f (frequency domain) (2.91)

Note that the time and frequency operators are Hermitian. To prove this, consider frequency operator in time domain F = 1

j2π d

dt and substitute it into (2.63). For any

two functions f(t) and g(t), with nite energy, left hand side of (2.63) becomes Z f∗(t)Fg(t)dt = Z f∗(t) 1 j2π d dtg(t)dt (integration by parts) = 1 j2πf ∗ (t)g(t)     −∞ +∞ − 1 j2π Z g(t)d dtf ∗ (t)dt (nite energy assumption) =

Z g(t)  1 j2π d dtf (t) ∗ dt = Z g(t) (Ff(t))∗dt (2.92)

which is the condition (2.63) for operator F. An equal proof can be done for time operator T in frequency domain.

The scale operator C is dened as C M

= 1

2[T, F]+= 1

2(TF + FT) (2.93)

and its representations in both time and frequency domains are C = 1 4πj  t d dt + d dtt  (time domain) (2.94) C = j 4π  f d df + d dff  (frequency domain) (2.95)

The operator C is also Hermitian because the anticommutator of two Hermitian operators is Hermitian (property (2.70)).

The uncertainty principle can be applied for frequency and scale operators, as they do not commute. In fact, the commutator of F and C is given by

[F, C] = FC − CF = 1

2(FTF + FFT − TFF − FTF) = 1

To evaluate [F, C], the operator in the right hand side of (2.96) is applied on an arbitrary function s(t), using the denitions of T and F in time domain (2.90).

[F, C]s(t) = 1 2(FFT − TFF)s(t) = 1 2  − j 2π d dt  − j 2π d dt(s(t)t)  − t  − j 2π d dt  − j 2π ds(t) dt  = 1 2 "  − j 2π 2 d dt  tds(t) dt + s(t)  − t  − j 2π 2 d2_s(t) dt2 # = 1 2  − j 2π 2 td 2_s(t) dt2 + ds(t) dt + ds(t) dt − t d2_s(t) dt2  =  − j 2π 2 ds(t) dt = − j 2πFs(t) (2.97)

Substituting the operator [F, C] = −j

2πF into (2.72), the uncertainty principle for

frequency and scale operators is σfσc≥

1

2|h[F, C]i| = 1

4π|hFi|. (2.98)

Condition (2.98) implies some restrictions on the signals involved in the discrete time-scale model of sections 2.3 and 2.4. In particular, for an input signal x(t), with given variances σ2

f and σ 2

c, in frequency and scale domains respectively, the mean

3

Identication of Narrowband

Time-Varying Sparse Systems

In this chapter we study and compare two approaches for the identication of a sparse narrowband time-varying system.

In Section 3.1 we derive a discrete characterization of the system and describe the corresponding model for the discrete spreading function to be identied.

In Section 3.2 we formulate the recovery according to two dierent approaches, reducing the identication problem both to a MMV problem and to a block-sparse problem, providing also the matrix representation in both cases.

The algorithms used for recovery are described in detail in Section 3.3, while in Section 3.4 we provide numerical results to compare the performances of the two approaches.

In the following, we refer to the two approaches simply as approach 1 and approach 2, respectively.

3.1. Discrete Time-Frequency Characterization

The output y(t) of a narrowband time-varying system can be represented as a weighted superposition of time-frequency shifted versions of the input signal x(t)

y(t) = Z τ Z ν sH(τ, ν)x(t − τ )ej2πνtdνdτ (3.1)

where sH(τ, ν) is the spreading function of the operator H, which describes the

system. Indicating with Tτ and Mν the time- and frequency-shift operators on the

signal x(t), (Tτx)(t) M = x(t − τ ) (3.2) (Mνx)(t) M = ej2πνtx(t) (3.3)

the operator H is the continuous weighted superposition of time-frequency shift operators, i.e., the input-output relation can be expressed as

Due to physical limitations of the system (see e.g. [17]), the support of the spread-ing function is assumed to be nite, i.e., sH(τ, ν) ≡ 0for (τ, ν) /∈ [0, τmax) × [0, νmax).

In order to study the discrete characterization of (3.4), we base on the model pre-sented in [15], where the region [0, τmax) × [0, νmax) is divided in rectangular cells,

that are either active, if sH is nonzero on these cells, or null. More precisely, suppose

to choose L ∈ R and T ∈ R such that the area [0, τmax) × [0, νmax)of the (τ, ν)-plane

can be divided in L2 _{rectangular cells of the same area 1/L, partitioning the τ-axis}

in L parts of length T and the ν-axis in L parts of length 1/(T L), as shown in Fig. 3.1. Consequently, τmax = T L , νmax = 1 T (3.5) and τmaxνmax= L. (3.6)

Then the arbitrary, possibly fragmented, support of the spreading function of op-erator H, indicated as MΓ, can be expressed as the union of a particular subset of

these cells MΓ M = [ (k,m)∈Γ  U +kT, m T L  (3.7) where U M

= [0, T ) × [0, 1/(T L)) is the fundamental cell in the (τ, ν)-plane and, con-sequently, U + (kT, m/(T L) is the cell with the below-left corner at (kT, m/(T L)). Γ species the active cells that identify the support of the spreading function,

Γ ⊆ Σ= {(0, 0), (0, 1), . . . , (L − 1, L − 1)}M (3.8) and |Γ| is the number of active cells.

Starting from the continuous input-output relation (3.1), a discrete characteriza-tion of the system can be derived, using the following assumpcharacteriza-tions.

1. The probing signal x(t) is bandlimited to [−B, B].

2. The signal y(t) is observed for the nite time interval [−V, V ]. The truncated version of the system response y(t) on [−V, V ] is indicated as y(t).

We report here the basic steps in [15] in order to have an intuition of the discrete model we use in the following analysis, and refer to [15] for more details.

We dene sH(τ, ν) as the eective spreading function of the system, obtained

from sH(τ, ν)after considering the assumptions 1 and 2 above. It can be shown that

sH(τ, ν) is a smoothed version of sH(τ, ν), both in time and frequency domain and

is given as

sH(τ, ν) = 4BV sH(τ, ν) ∗ sinc(2Bτ ) ∗ sinc(2V ν). (3.9)

From (3.9), sH(τ, ν) is not supported on [0, τmax) × [0, νmax) but, considering the

approximation that the sinc functions are nonzero only in their mainlobes, most of the volume of sH(τ, ν)is supported on [−1/(2B), τmax+ 1/(2B)) × [−1/(2V ), νmax+

τ ν T 1 T L T L 1 T Lcells L cells U

Figure 3.1.: Model for the support of the spreading function.

bandlimited within [−B, B + νmax], hence it can be sampled at rate fs= 2B + νmax,

yielding the discrete output y[n]. We dene then function sH[m, l] as a sampled

version of sH(τ, ν), given by sH[m, l] M = sH  m fs , l 2V  e−jπl. (3.10)

Relation (3.10) suggests the model for the support of the discrete spreading func-tion of the system, where the (τ, ν)-plane is discretized both in τ-direcfunc-tion, with resolution of 1/fs, and in ν-direction, with resolution 1/(2V ), i.e., the spreading

function is uniformly sampled in the (τ, ν)-plane.

Finally, the integer parameters E and D are set such that τmax = EL fs , νmax = DL 2V . (3.11)

According to denition (3.11), E and D are the number of samples taken on an active cell of sH(τ, ν) in τ and ν direction, respectively, as indicated in Fig. 3.2.

The continuous input-output relation in (3.1) is then equivalent to the following discrete characterization of the system

y[n] = X m∈Z X l∈Z sH[m, l]x[n − m]ej2π ln DEL , n = 0, . . . , DEL − 1 (3.12)

where the discrete signal x[n] is a sampled version of x(t).

From the approximation sH(τ, ν) ≡ 0 for (τ, ν) /∈ [−1/(2B), τmax + 1/(2B)) ×

[−1/(2V ), νmax + 1/(2V )) and from the denitions of τmax and νmax in (3.11), the

τ ν Ek fs E(k+1) fs Dm 2V D(m+1) 2V E samples D samples

Figure 3.2.: Model for the support of the discrete spreading function.

{0, 1, . . . , DL − 1} and, consequently, the two summations in (3.12) involve only nitely many terms.

y[n] = EL−1 X m=0 DL−1 X l=0 sH[m, l]x[n − m]ej2π ln DEL , n = 0, . . . , DEL − 1. (3.13)

Furthermore, if most of the volume of sH(τ, ν) is approximately supported on MΓ,

given in (3.7), then the samples of the spreading function in (3.13) satisfy sH[m, l] ≡ 0 for  m fs , l 2V  / ∈ MΓ. (3.14)

3.2. Matrix Representations

In the following we compare two approaches to identify a system with input-output relation (3.13). The approach 1 allows to formulate the problem as a multiple measured vectors (MMV) problem, in which equation (3.13) admits the following matrix representation

Z = AcS. (3.15)

The matrices Z ∈ CL×DE_{, A}

c ∈ CL×L

2

and S ∈ CL2_×DE

depend on y[n], x[n] and sH[m, l], respectively. In particular, Z contains the discrete Zak transform of

y[n], Ac translates in time and frequency the input samples x[n] and each row of

S contains the samples sH[m, l] inside each active cell. The precise denitions are

Z Ac S = L DE L2 L2 DE |Γ|active cells

Figure 3.3.: Model for the MMV problem.

problem involves a particular probing signal x[m], given as a train of Dirac impulses x[m] = c−k if m = Ek

0 otherwise (3.16)

with the additional property that

ck = ck+L. (3.17)

The coecients ck, k = 0, . . . , L − 1 are independent and uniformly at random,

chosen on the complex unit disc.

The approach 2 leads to a matrix representation as a Block-Sparsity model, given by

y = Xs. (3.18)

The vectors y ∈ CDEL×1 _{and s ∈ C}DEL2_×1

contain samples of the output y[n] and of the spreading function sH[m, l], respectively, while matrix X ∈ CDEL×DEL

2

depends on the probing signal x[m], which is a sequence of independent symbols with distribution CN (0, 1). A graphical representation of (3.18) is presented in Fig. 3.4.

The two models are detailed below. 1. MMV model.

To derive the matrix representation (3.15) from the discrete input-output re-lation (3.13), we calculate rst the discrete Zak transform of y[n], dened as ZEL,D y [n, r] M = 1 D D−1 X q=0 y[n + ELq]e−j2πqrD , n = 0, . . . , EL − 1 , r = 0, . . . , D − 1. (3.19) Substituting n in (3.19) with n = n0 _{+ Ep, where n}0 _{= 0, . . . , E − 1 and}

Z_yEL,D[n0+ Ep, r] = 1 D D−1 X q=0 y[n0+ Ep + ELq]e−j2πqrD (from (3.13)) = 1 D D−1 X q=0 EL−1 X m=0 DL−1 X l=0 sH[m, l]x[n0+ Ep + ELq − m] × ej2πl(n0+Ep+ELq)DEL e−j2π qr D (m = m0+ Ek) = 1 D D−1 X q=0 E−1 X m0₌₀ L−1 X k=0 DL−1 X l=0 sH[m0+ Ek, l]

× x[n0_{− m}0_{+ E(p + Lq − k)]e}j2πl(n0+Ep+ELq)_{DEL e}−j2πqr_D

From the denition (3.16) of the probing signal and using (3.17) x[n0− m0+ E(p + Lq − k)] = ck−p if m

0 _{= n}0

0 if m0 6= n0 (3.20)

Substituting (3.20) into the equation above yields ZEL,D y [n 0 + Ep, r] = 1 D D−1 X q=0 L−1 X k=0 DL−1 X l=0 ck−psH[n0+ Ek, l]ej2π l(n0+Ep+ELq) DEL e−j2π qr D (l = l0+ Dh) = 1 D D−1 X q=0 L−1 X k=0 D−1 X l0₌₀ L−1 X h=0 ck−psH[n0+ Ek, l0+ Dh] × ej2π(l0+Dh)(n0+Ep+ELq)_{DEL e}−j2πqr D = 1 D D−1 X q=0 L−1 X k=0 D−1 X l0₌₀ L−1 X h=0 ck−psH[n0+ Ek, l0+ Dh] × ej2π(l0+Dh)(n0+Ep)_{DEL e}j2πql0_De−j2πqr_D = 1 D D−1 X q=0 L−1 X k=0 D−1 X l0₌₀ L−1 X h=0 ck−psH[n0+ Ek, l0+ Dh] × ej2π(l0+Dh)(n0+Ep)DEL ej2π q(l0−r) D = L−1 X k=0 L−1 X h=0 ck−psH[n0+ Ek, r + Dh]ej2π (r+Dh)(n0+Ep) DEL (3.21)

where the last equality is due to the DFT. Dene zp[n, r]as

zp[n, r] M = Z_yEL,D[n + Ep, r] = L−1 X k=0 L−1 X h=0 ck−psH[n + Ek, r + Dh]ej2π (r+Dh)(n+Ep) DEL (3.22) where n = 0, . . . , E − 1, r = 0, . . . , D − 1 and p = 0, . . . , L − 1.

The p-th entry of the (n, r)th column z[n, r] of Z in (3.15) is dened as [z[n, r]]p

M

= zp[n, r]e−j2π

rp

Parameters n and r identify the columns of Z, which are ordered as follows (n, r) ∈ {(0, 0), (0, 1), . . . , (E − 1, D − 1)}. (3.24) The column of matrix S in (3.15), identied by parameters n and r as in (3.24), is dened as s[n, r]= [sM 0,0[n, r], s0,1[n, r], . . . , sL−1,L−1[n, r]]T (3.25) where sk,m[n, r] M = sH[n + Ek, r + Dm]ej2π n(r+Dm) DEL , k, m = 0, . . . , L − 1. (3.26)

From denition (3.26), each row of S contains all the samples of sH[m, l]inside

the same active cell (see Fig. 3.2), with the exception of a phase shift. As we assume that there are only |Γ| active cells, then S has |Γ| nonzero rows. Finally, matrix Ac in (3.15) is given by

Ac= [AM c,0|Ac,1| . . . |Ac,L−1] (3.27)

with the square L × L submatrices dened as

Ac,k = CM c,kFH (3.28) where Cc,k M = diag{ck, ck−1, . . . , ck−(L−1)} and [F]p,m M = e−j2πpmL , with p, m = 0, . . . , L − 1.

With the denitions above, (3.15) describes exactly the discrete input-output relation (3.13). Denote the matrix obtained from S by selecting only the rows corresponding to the active cells of sH[m, l]with SΓ and let AΓ be the matrix

containing the columns of Ac corresponding to the same cells. Then (3.15) is

equivalent to

Z = AΓSΓ. (3.29)

2. Block-Sparsity model.

The matrix representation of this problem follows directly from the input-output relation (3.13). With a change of variables m = m0_{+Ekand l = l}0_+Dr,

(3.13) becomes y[n] = E−1 X m=0 L−1 X k=0 D−1 X l=0 L−1 X r=0 sH[m + Ek, l + Dr]x[n − (m + Ek)]ej2π (l+Dr)n DEL , n = 0, . . . , DEL − 1. (3.30) The column vector y in (3.18) contains the DEL samples of the output y[n], n = 0, . . . , DEL − 1. Dene the column vector s in (3.18) as

y _X s = DEL DEL2 DE DE DEL2 sk,r_H |Γ| active cells ˜ Xk,r

Figure 3.4.: Model for the B-sparsity problem. where each subvector sk,r

H ∈ CDE×1, k, r = 0, . . . , L−1, contains all the samples

of the spreading function sH[m, l]on the same cell of Fig. 3.2,

sk,r_H = [sM k,r_H (0, 0), sk,r_H (0, 1), . . . , sk,r_H (E − 1, D − 1)]T (3.32) with sk,r

H (m, l) M

= sH[m + Ek, l + Dr]. Assuming that the number of active cells

is |Γ|, only |Γ| blocks are nonzero, so that s is block-sparse. Finally, matrix X is given by

X = [ ˜X0,0| ˜X0,1| . . . | ˜XL−1,L−1] (3.33) where the submatrices ˜Xk,r _{∈ C}DEL×DE_{, k, r = 0, . . . , L − 1, are dened as}

˜

Xk,r M= [˜xk,r(0, 0)|˜xk,r(0, 1)| . . . |˜xk,r(E − 1, D − 1)] (3.34) with the n-th entry of vector ˜xk,r_{(m, l) ∈ C}DEL×1 _{, m = 0, . . . , E − 1, l =}

0, . . . , D − 1 given by [˜xk,r(m, l)]n

M

= x[n − (m + Ek)]ej2π(l+Dr)nDEL , n = 0, . . . , DEL − 1. (3.35)

Denote the vector obtained from s by selecting only the blocks corresponding to the active cells of sH[m, l] by sΓ and let XΓ be the matrix containing the

columns of X corresponding to those cells. Then (3.18) is equivalent to

3.3. Recovery Algorithms

The goal of the two algorithms described in this section is to recover both the support Γ and the samples sH[m, l] of the spreading function in (3.13), given the

input signal x[n] in both cases. The algorithms are adaptions of the orthogonal matching pursuit (OMP) algorithm [18]. Before starting the detailed description of the two algorithms, some practical observations are presented. It can be shown that the identication of a system of the form (3.13) fails if the value of sparsity satises |Γ| ≥ L, since in this case there are more unknowns than knowns. The simulations performed in section 3.4 are applied under the necessary condition |Γ| ≤ L. The recovery depends on Acand X. In particular, the more the samples of the spreading

function are well approximated by the same set of elements in Ac and X, the more

successful the recovery is. In the case of high recovery probability, matrices Ac and

X are well-conditioned.

1. Simultaneous Orthogonal Matching Pursuit (S-OMP).

Recovery of S from Z obtained as Z = AcS, when we assume that the columns

of S share the same sparsity pattern, is a MMV problem. The S-OMP algo-rithm is one approach to solve it, i.e., to reconstruct S from Z, obtained as Z = AcS. The S-OMP algorithm deals with the approximation of several

signals at once (column vectors s[n, r] of matrix S) using dierent linear com-binations of the same elementary signals (columns of matrix Ac) [19].

Algorithm 1. S-OMP Input:

ˆ Matrix Z of the observed samples. ˆ Matrix Ac (dictionary).

ˆ Value of sparsity |Γ| of matrix S (number of nonzero rows of S). Output:

ˆ Matrix S of the samples of the spreading function. Procedure:

a) Initialize the residual matrix R0 = Z and the index set Λ0 = ∅. The

iteration counter is t = 1.

b) Find an index λt that solves the optimization problem

λt = arg max i=1,...,L2 RH_t−1(Acei) 2 (3.37)

where ei is the i-th canonical basis column vector in CL

2

and, conse-quently, Acei is the i-th column of Ac.

d) Determine matrix ˜A , selecting from Ac the columns with indexes in

Λt.

e) Calculate the new approximation of S and the new residual matrix ˜

St = A˜†Z (3.38)

Rt = Z − ˜St (3.39)

f) Increment t. If t = |Γ|, stop; otherwise return to step (b).

g) Set SΓ = ˜S|Γ|. Matrix S is obtained from SΓ adding zero rows,

corre-sponding to indexes in {1, . . . , L2_{}not included in Λ} |Γ|.

Since the matrix S has a sparsity of |Γ|, the algorithm is performed for |Γ| times, so that AΓ in (3.29) contains the |Γ| columns of Ac that best

approxi-mate the spreading function.

Step (b) is referred to as the greedy selection of the algorithm. Maximizing the `2-norm in (3.37) means nding the element of the dictionary that can

contribute a lot of energy to every column of the matrix S. 2. Block-sparse Orthogonal Matching Pursuit (B-OMP).

Because of the structure of vector s in (3.18), where nonzero entries appear in blocks, one approach for identication of the B-sparsity model is the B-OMP algorithm [20]. Since a MMV model is a special case of a block-sparse model, S-OMP algorithm is equivalent to B-OMP algorithm if MMV is formulated as a block-sparse model. That makes the two approaches comparable.

Algorithm 2. B-OMP Input:

ˆ Vector y of the observed samples. ˆ Matrix X (dictionary).

ˆ Value of sparsity |Γ| of vector s (number of nonzero blocks of s). Output:

ˆ Vector s of the samples of the spreading function. Procedure:

a) Initialize the residual vector r0 = y and the block index set E0 = ∅.

The iteration counter is t = 1.

b) Find an index λt that solves the optimization problem

where ˜X[i] ∈ CDEL×DE is the i-th block of X. ˜X[i] = ˜Xk,r in (3.33) for some proper values of k and r.

c) Set Et= Et−1∪ λt.

d) Determine matrix ˜X , selecting from X the blocks with indexes in Et.

e) Calculate the new approximation of s and the new residual vector ˜

st = X˜†y (3.41)

rt = y − ˜st (3.42)

f) Increment t. If t = |Γ|, stop; otherwise return to step (b).

g) Set sΓ= ˜s|Γ|. Vector s is obtained from sΓ adding zero blocks,

corre-sponding to indexes in {1, . . . , L2_{} not included in E} |Γ|.

3.4. Simulation Results

The two approaches presented above are compared in the noiseless and noisy cases. 1. Noiseless case. The identication of the spreading function from the observed samples is performed without introducing noise. The two models are com-pared in terms of recovery probability. Recovery is regarded as successful if the relative error between the recovered spreading function ˆsH and the original

one sH is less than a xed tolerance, admitted because of limited precision in

the simulations, i.e.,

ksH − ˆsHk2

kˆsHk2

≤ 10−5 (3.43)

The recovery probability is the average of the successful recoveries upon 1000 trials.

2. Noisy case. In this case the observed samples are corrupted by complex addi-tive white Gaussian noise, with a SNR of 20 dB. The two models are compared in terms of the root mean square error, sqrt-MSE, of the recovered spreading function ˆsH. The average of the relative error dened in (3.43) is evaluated

upon 1000 trials.

Some parameters are set before the simulation is performed:

- Parameter L is xed and set to L = 19 and, consequently, the number of cells on the (τ, ν)-plane is L2 _{= 361.}

- The cardinality |Γ| of the support set of the spreading function is varied from 1 to 19.

- For each pair (DE,|Γ|), 1000 trials are performed to obtain the recovery prob-ability and the root MSE.

Spreading functions are generated by choosing uniformly at random a support set Γ with cardinality |Γ|, which corresponds to an area of ∆ = |Γ|/L in the continuous setting. Samples sH[m, l]are then chosen independently with distribution CN (0, 1).

In Fig. 3.5 and 3.6 we report the results, for the noiseless and the noisy case, respectively.

From Fig. 3.5, it can be seen that the approach 2 performs signicantly better than the approach 1, especially for large values of DE. The choice of taking iid symbols as the probing signal for the approach 2 guarantees that submatrices of X in (3.18) are much more well-conditioned than submatrices of Ac in (3.15). For

DE = 1 the approaches perform almost equal.

0

5

10

15

20

0

0.2

0.4

0.6

0.8

1

|Γ|

reco

very

probabilit

y

DE = 1

DE = 7

DE = 13

DE = 19

(a) MMV model, S-OMP

0

5

10

15

20

0

0.2

0.4

0.6

0.8

1

|Γ|

reco

very

probabilit

y

DE = 1

DE = 7

DE = 13

DE = 19

(b) B-sparsity model, B-OMP

0

5

10

15

20

0

0.2

0.4

0.6

0.8

1

|Γ|

sqrt-MSE

DE = 1

DE = 7

DE = 13

DE = 19

(a) MMV model, S-OMP

0

5

10

15

20

0

0.2

0.4

0.6

0.8

1

|Γ|

sqrt-MSE

DE = 1

DE = 7

DE = 13

DE = 19

(b) B-sparsity model, B-OMP

4

Identication of Parametric Underspread

Linear Systems

In this chapter we study the identication of a particular class of narrowband systems, called parametric underspread linear systems. The identication conditions seen for a narrowband system in general hold also in this case. We extend the analysis presented for a single input system to a multiple input system, using some ideas as in [23].

In Section 4.1 we provide the characterization of a parametric ULS. In Section 4.2 we formalize the problem of identication and give the system assumptions.

A matrix formulation of the problem is given in Section 4.4. In Sections 4.3 and 4.5 we propose a recovery procedure of the parameters that describe the system, while in section 4.6 we discuss on the implementation of the recovery procedure.

In Section 4.7 we specify the sucient conditions on the input signal needed to guarantee the unique identication using the proposed procedure.

Finally, in Section 4.8 we extend the results [23] found previously for the system identication with a single input, to multiple inputs.

4.1. System Characterization

The general input-output relation of a linear time-varying system, as seen in chapter 3, is given by y(t) = Z τ Z ν sH(τ, ν)x(t − τ )ej2πνtdνdτ (4.1)

where the received signal y(t) consists of the continuous superposition of time- and frequency-shifted versions of the transmitted signal x(t), weighted according to the spreading function sH(τ, ν).

We consider systems with spreading function characterized by a nite set of delays τk and Doppler-shifts νk (Fig. 4.1), i.e.,

sH(τ, ν) = K

X

k=1

τ ν τmax νmax (τ1, ν1) (τk, νk) (τK, νK)

Figure 4.1.: Spreading function of a parametric ULS.

where parameters αk ∈ C are the attenuation factors associated with the

delay-Doppler pairs (τk, νk) and the delays τk are assumed to be distinct. Relation (4.1)

can be expressed, using (4.2), as y(t) =

K

X

k=1

αkx(t − τk)ej2πνkt. (4.3)

Systems described by (4.3) are referred to as parametric underspread linear systems in [23]. The term underspread is referred to as systems, whose spreading function is supported within a region in the delay-Doppler plane of area smaller than 1. Such systems are identiable as noticed in Kailath's work [7].

The identication of (4.3) involves nding a probing signal x(t) that guarantees the system parameters to be recovered from the observed signal y(t). The parameters that completely characterize the system are the triplets (τk, νk, αk), for k = 1, . . . , K.

In the following, we give conditions on the probing signal that ensure the identica-tion of (4.3) and derive a recovery procedure that estimates the parameters above.

4.2. Assumptions for Identication

The rst assumption, already mentioned above, is that the delays of the spreading function are distinct. This could seem a restrictive property but it is largely veried in practical situations.

t g(t)

0 T

Figure 4.2.: Example of the prototype pulse g(t).

t x(t) 0 x0g(t) T x1g(t − T ) 2T x2g(t − 2T ) 3T (N − 1)T N T

Figure 4.3.: Example of the probing signal x(t).

ˆ g(t) is a prototype pulse, supported on [0, T ] and with unit energy, R |g(t)|2_{dt = 1}

(an example is depicted in Fig. 4.2); ˆ {xn∈ C} is an N-length probing sequence.

An example of the probing signal x(t) is shown in Fig. 4.3. The temporal support of x(t), indicated as T , is dened as T = NT , while its two-sided bandwidth, indicated as W, is the same as that of g(t).

Since for an arbitrary pulse g(t) the bandwidth and the temporal support are related to each other as W ∝ 1/T , the parameter N is proportional to the time-bandwidth product of x(t),

N = T

T ∝ T W (4.5)

which is according to the 2W T -Theorem [9] the number of temporal degrees of freedom available for estimating the system.

The following assumptions are made in order to have some restrictions on the support of the spreading function sH(τ, ν).

A) The support of the spreading function sH(τ, ν)in (4.2) lies within a rectangular

region of the delay-Doppler plane, i.e., (τk, νk) ∈ [0, τmax] × [0, νmax], for k =

1, . . . , K. The parameters τmax and νmax are referred to as delay spread and

B) The delay spread is strictly smaller than the temporal support of g(t), or τmax < T.

C) The Doppler spread is much smaller than the bandwidth of g(t), νmax  W.

Noting that W ∝ 1/T , this assumption is equivalent to νmaxT  1.

The main result for the identication of a ULS with a single input is summarized in the following theorem.

Theorem 4. Identication of Parametric Underspread Linear Systems. Suppose that a parametric ULS is completely described by K triplets (τk, νk, αk),

where delays τk are distinct. Then the system can be identied as long as it

satises assumptions A), B), C), the probing sequence {xn} is nonzero for all

n = 0, . . . , N − 1 and the time-bandwidth product of the known input signal x(t) satises the condition

T W ≥ 4K (4.6)

The probing signal that guarantees identication is not arbitrary but needs to be of the form of (4.4), as it will be clear in the following.

Before describing the recovery procedure in detail, a proper expression for the response signal y(t) is derived. According to the probing signal in (4.4), the input-output relation in (4.3) can be expressed as

y(t) = K X k=1 N −1 X n=0 αkxnej2πνktg(t − τk− nT ) (4.7) ≈ K X k=1 N −1 X n=0 αkxnej2πνknTg(t − τk− nT ) (4.8) = K X k=1 N −1 X n=0 ak[n]g(t − τk− nT ) (4.9)

where the sequences ak[n], k = 1, . . . , K in (4.9) are dened as

ak[n] = αkxnej2πνknT , n = 0, . . . , N − 1 (4.10)

The approximation in (4.8) follows from the assumptions B) and C), which is seen as follows. Since g(t) is compactly supported on [0, T ], then g(t − τk− nT ) = 0 for

t /∈ [nT + τk, (n + 1)T + τk]. First of all, due to the assumption B), τk < T ∀k and

g(t−τk−nT ) = 0for t /∈ [nT, (n+2)T ]. Therefore, for each value of k and n in (4.7),

ej2πνkt_{g(t − τ}

k− nT ) = ej2πνk[(n+1)T +˜t]g(t − τk− nT ), where ˜t ∈ [−T, T ]. Secondly,

due to the assumption C), νkT  1 ∀k and then ej2πνkT ≈ 1 and ej2πνk ˜

t _{≈ 1. As}

a consequence, the largest error committed by approximating ej2πνknT ≈ ej2πνkt in