Estimation of signal parameters via rotational invariance techniques

At instance $t$

, the $M$

(complex-valued) output signals (measurements) $y\_m[t]$, $m\; =\; 1,\; \backslash ldots,\; M$

, of the system are related to the $K$

(complex-valued) input signals $x\_k[t]$

, $k\; =\; 1,\; \backslash ldots,\; K$

, as$$y\_m[t]\; =\; \backslash sum\_\{k=1\}^K\; a\_\{m,k\}\; x\_k[t]\; +\; n\_m[t],$$where $n\_m[t]$

denotes the noise added by the system. The one-dimensional form of ESPRIT can be applied if the weights have the form $a\_\{m,k\}\; =\; e^\{-j(m-1)\backslash omega\_k\}$

, whose phases are integer multiples of some radial frequency $\backslash omega\_k$

. This frequency only depends on the index of the system's input, i.e. $k$

. The goal of ESPRIT is to estimate $\backslash omega\_k$

's, given the outputs $y\_m[t]$

and the number of input signals, $K$

. Since the radial frequencies are the actual objectives, $a\_\{m,k\}$

is denoted as $a\_m(\backslash omega\_k)$

.

Collating the weights $a\_m(\backslash omega\_k)$

as $\backslash mathbf\; a(\backslash omega\_k)\; =\; [\backslash ,1\; \backslash ,\backslash \; e^\{-j\backslash omega\_k\}\; \backslash ,\backslash \; e^\{-j2\backslash omega\_k\}\; \backslash ,\backslash \; ...\; \backslash ,\backslash \; e^\{-j(M-1)\backslash omega\_k\}\backslash ,]^\backslash top$ and the $M$

output signals at instance $t$

as $\backslash mathbf\; y[t]\; =\; [\backslash ,y\_1[t]\backslash ,\backslash \; y\_2[t]\; \backslash ,\backslash \; ...\; \backslash ,\backslash \; y\_M[t]\backslash ,]^\backslash top$, $$\backslash mathbf\; y[t]\; =\; \backslash sum\_\{k=1\}^K\; \backslash mathbf\; a(\backslash omega\_k)\; x\_k[t]\; +\; \backslash mathbf\{n\}[t],$$where $\backslash mathbf\; n[t]\; =\; [\backslash ,n\_1[t]\backslash ,\backslash \; n\_2[t]\; \backslash ,\backslash \; ...\; \backslash ,\backslash \; n\_M[t]\backslash ,]^\backslash top$. Further, when the weight vectors $\backslash mathbf\; a(\backslash omega\_1),\; \backslash \; \backslash mathbf\; a(\backslash omega\_2),\backslash \; ...,\; \backslash \; \backslash mathbf\; a(\backslash omega\_K)$

are put into a Vandermonde matrix $\backslash mathbf\; A\; =\; [\backslash ,\backslash mathbf\; a(\backslash omega\_1)\; \backslash ,\backslash \; \backslash mathbf\; a(\backslash omega\_2)\; \backslash ,\backslash \; ...\; \backslash ,\backslash \; \backslash mathbf\; a(\backslash omega\_K)\backslash ,]$, and the $K$ inputs at instance $t$

into a vector $\backslash mathbf\; x[t]\; =\; [\backslash ,x\_1[t]\; \backslash ,\backslash \; ...\; \backslash ,\backslash \; x\_K[t]\backslash ,]^\backslash top$, we can write$$\backslash mathbf\; y[t]\; =\; \backslash mathbf\; A\backslash ,\; \backslash mathbf\; x[t]+\backslash mathbf\; n[t].$$With several measurements at instances $t\; =\; 1,\; 2,\; \backslash dots,\; T$

and the notations $\backslash mathbf\{Y\}\; =\; [\backslash ,\backslash mathbf\{y\}[1]\; \backslash ,\backslash \; \backslash mathbf\{y\}[2]\; \backslash ,\backslash \; \backslash dots\; \backslash ,\backslash \; \backslash mathbf\{y\}[\; T\; ]\backslash ,]$, $\backslash mathbf\{X\}\; =\; [\backslash ,\backslash mathbf\{x\}[1]\; \backslash ,\backslash \; \backslash mathbf\{x\}[2]\; \backslash ,\backslash \; \backslash dots\; \backslash ,\backslash \; \backslash mathbf\{x\}[\; T\; ]\backslash ,]$ and $\backslash mathbf\{N\}\; =\; [\backslash ,\; \backslash mathbf\{n\}[1]\; \backslash ,\backslash \; \backslash mathbf\{n\}[2]\; \backslash ,\backslash \; \backslash dots\; \backslash ,\backslash \; \backslash mathbf\{n\}[\; T\; ]\backslash ,]$, the model equation becomes$$\backslash mathbf\{Y\}\; =\; \backslash mathbf\{A\}\; \backslash mathbf\{X\}\; +\; \backslash mathbf\{N\}.$$

File:Max overlapping subarrays.png

The weight vector $\backslash mathbf\; a(\backslash omega\_k)$

has the property that adjacent entries are related.$$[\backslash mathbf\{a\}(\backslash omega\_k)]\_\{m+1\}\; =\; e^\{-j\backslash omega\_k\}\; [\backslash mathbf\{a\}(\backslash omega\_k)]\_\{m\}$$

For the whole vector $\backslash mathbf\; a(\backslash omega\_k)$

, the equation introduces two selection matrices $\backslash mathbf\{J\}\_1$

and $\backslash mathbf\{J\}\_2$

: $\backslash mathbf\; J\_1\; =\; [\backslash mathbf\; I\_\{M-1\}\; \backslash quad\; \backslash mathbf\; 0]$ and $\backslash mathbf\; J\_2\; =\; [\backslash mathbf\; 0\; \backslash quad\; \backslash mathbf\; I\_\{M-1\}]$. Here, $\backslash mathbf\; I\_\{M-1\}$ is an identity matrix of size $(M-1)$ and $\backslash mathbf\; 0$ is a vector of zeros.

The vector $\backslash mathbf\; J\_1\; \backslash mathbf\; a(\backslash omega\_k)$

$[\backslash mathbf\; J\_2\; \backslash mathbf\; a(\backslash omega\_k)]$

contains all elements of $\backslash mathbf\; a(\backslash omega\_k)$

except the last [first] one. Thus, $\backslash mathbf\; J\_2\; \backslash mathbf\; a(\backslash omega\_k)\; =\; e^\{-j\backslash omega\_k\}\; \backslash mathbf\; J\_1\; \backslash mathbf\; a(\backslash omega\_k)$ and$$\backslash mathbf\; J\_2\; \backslash mathbf\; A\; =\; \backslash mathbf\; J\_1\; \backslash mathbf\; A\; \backslash mathbf\; H$$

,\quad\text{where}\quad

{\mathbf {H}} := \begin{bmatrix} e^{-j\omega_1} & \\ & e^{-j\omega_2} \\ & & \ddots \\ & & & e^{-j\omega_K} \end{bmatrix}

.The above relation is the first major observation required for ESPRIT. The second major observation concerns the signal subspace that can be computed from the output signals.

The singular value decomposition (SVD) of $\backslash mathbf\; Y$

is given as$$\backslash mathbf\{Y\}\; =\; \backslash mathbf\; U\; \backslash mathbf\; \backslash Sigma\; \backslash mathbf\; V^\backslash dagger$$where $\backslash mathbf\; U\; \backslash in\backslash mathbb\; C^\{M\backslash times\; M\}$

and $\backslash mathbf\; V\; \backslash in\; \backslash mathbb\; C^\{T\backslash times\; T\}$

are unitary matrices and $\backslash mathbf\; \backslash Sigma$

is a diagonal matrix of size $M\; \backslash times\; T$, that holds the singular values from the largest (top left) in descending order. The operator $\backslash dagger$

denotes the complex-conjugate transpose (Hermitian transpose).

Let us assume that $T\; \backslash geq\; M$. Notice that we have $K$ input signals. If there was no noise, there would only be $K$ non-zero singular values. We assume that the $K$ largest singular values stem from these input signals and other singular values are presumed to stem from noise. The matrices in the SVD of $\backslash mathbf\; Y$ can be partitioned into submatrices, where some submatrices correspond to the signal subspace and some correspond to the noise subspace.$$\backslash begin\{aligned\}$$

\mathbf{U} =

\begin{bmatrix}

\mathbf{U}_\mathrm{S} &

\mathbf{U}_\mathrm{N}

\end{bmatrix},

& &

\mathbf{\Sigma} =

\begin{bmatrix}

\mathbf{\Sigma}_\mathrm{S} & \mathbf{0} & \mathbf{0} \\

\mathbf{0} & \mathbf{\Sigma}_\mathrm{N} & \mathbf{0}

\end{bmatrix},

& &

\mathbf{V} =

\begin{bmatrix}

\mathbf{V}_\mathrm{S} &

\mathbf{V}_\mathrm{N} &

\mathbf{V}_\mathrm{0}

\end{bmatrix}

\end{aligned},where $\backslash mathbf\{U\}\_\backslash mathrm\{S\}\; \backslash in\; \backslash mathbb\{C\}^\{M\; \backslash times\; K\}$

and $\backslash mathbf\{V\}\_\backslash mathrm\{S\}\; \backslash in\; \backslash mathbb\{C\}^\{N\; \backslash times\; K\}$

contain the first $K$ columns of $\backslash mathbf\; U$

and $\backslash mathbf\; V$

, respectively and $\backslash mathbf\{\backslash Sigma\}\_\backslash mathrm\{S\}\; \backslash in\; \backslash mathbb\{C\}^\{K\; \backslash times\; K\}$

is a diagonal matrix comprising the $K$ largest singular values.

Thus, The SVD can be written as$$\backslash mathbf\{Y\}\; =\; \backslash mathbf\; U\_\backslash mathrm\{S\}\; \backslash mathbf\; \backslash Sigma\_\backslash mathrm\{S\}\; \backslash mathbf\; V\_\backslash mathrm\{S\}^\backslash dagger$$

+ \mathbf U_\mathrm{N} \mathbf \Sigma_\mathrm{N} \mathbf V_\mathrm{N}^\dagger

,where $\backslash mathbf\{U\}\_\backslash mathrm\{S\}$

, ⁣$\backslash mathbf\{V\}\_\backslash mathrm\{S\}$

, and $\backslash mathbf\{\backslash Sigma\}\_\backslash mathrm\{S\}$

represent the contribution of the input signal $x\_k[t]$

to $\backslash mathbf\; Y$

. We term $\backslash mathbf\{U\}\_\backslash mathrm\{S\}$

the signal subspace. In contrast, $\backslash mathbf\{U\}\_\backslash mathrm\{N\}$

, $\backslash mathbf\{V\}\_\backslash mathrm\{\; N\; \}$

, and $\backslash mathbf\{\backslash Sigma\}\_\backslash mathrm\{N\}$

represent the contribution of noise $n\_m[\; t\; ]$

to $\backslash mathbf\; Y$

.

Hence, from the system model, we can write $\backslash mathbf\{A\}\; \backslash mathbf\{X\}\; =$

\mathbf U_\mathrm{S} \mathbf \Sigma_\mathrm{S} \mathbf V_\mathrm{S}^\dagger

and $\backslash mathbf\{N\}\; =$

\mathbf U_\mathrm{N} \mathbf\Sigma_\mathrm{N} \mathbf V_\mathrm{N}^\dagger

. Also, from the former, we can write$$\backslash mathbf\; U\_\backslash mathrm\{S\}$$

= \mathbf{A} \mathbf{F},

where $\{\backslash mathbf\; F\; \}\; =\; \backslash mathbf\{X\}\; \backslash mathbf\; V\_\backslash mathrm\{S\}\; \backslash mathbf\; \backslash Sigma\_\backslash mathrm\{S\}^\{-1\}$

. In the sequel, it is only important that there exists such an invertible matrix $\backslash mathbf\; F$

and its actual content will not be important.

Note: The signal subspace can also be extracted from the spectral decomposition of the auto-correlation matrix of the measurements, which is estimated as$$\backslash mathbf\{R\}\_\backslash mathrm\{YY\}$$

=

\frac{1}{T}

\sum_{t=1}^T \mathbf{y}[t] \mathbf{y}[t] ^\dagger

=\frac{1}{T}

\mathbf{Y} \mathbf{Y}^\dagger

=

\frac{1}{T}

\mathbf U

{\mathbf \Sigma \mathbf \Sigma^\dagger}

\mathbf U^\dagger

=

\frac{1}{T}

\mathbf U_\mathrm{S} \mathbf \Sigma_\mathrm{S}^2 \mathbf U_\mathrm{S}^\dagger

+

\frac{1}{T}

\mathbf U_\mathrm{N} \mathbf \Sigma_\mathrm{N}^2 \mathbf U_\mathrm{N}^\dagger.

We have established two expressions so far: $\backslash mathbf\; J\_2\; \backslash mathbf\; A\; =\; \backslash mathbf\; J\_1\; \backslash mathbf\; A\; \backslash mathbf\; H$

and $\backslash mathbf\; U\_\backslash mathrm\{S\}\; =\; \backslash mathbf\{A\}\; \backslash mathbf\{F\}$

. Now, $$\backslash begin\{aligned\}$$

\mathbf J_2 \mathbf A

= \mathbf J_1 \mathbf A \mathbf H

\implies

\mathbf J_2 (\mathbf U_\mathrm{S} \mathbf{F}^{-1})

= \mathbf J_1 (\mathbf U_\mathrm{S} \mathbf{F}^{-1}) \mathbf H

\implies

\mathbf S_2 = \mathbf S_1 \mathbf{P},

\end{aligned}where $\backslash mathbf\{S\}\_1\; =\; \backslash mathbf\; J\_1\; \backslash mathbf\; U\_\backslash mathrm\{S\}$ and $\backslash mathbf\{S\}\_2\; =\; \backslash mathbf\; J\_2\; \backslash mathbf\; U\_\backslash mathrm\{S\}$ denote the truncated signal sub spaces, and $$\backslash mathbf\{P\}\; =\; \backslash mathbf\{F\}^\{-1\}\; \backslash mathbf\; H\; \backslash mathbf\{F\}.$$The above equation has the form of an eigenvalue decomposition, and the phases of the eigenvalues in the diagonal matrix $\backslash mathbf\; H$ are used to estimate the radial frequencies.

Thus, after solving for $\backslash mathbf\; P$ in the relation $\backslash mathbf\; S\_2\; =\; \backslash mathbf\; S\_1\; \backslash mathbf\{P\}$, we would find the eigenvalues $\backslash lambda\_1,\backslash \; \backslash lambda\_2,\backslash \; \backslash ldots,\backslash \; \backslash lambda\_K$

of $\backslash mathbf\; P$, where $\backslash lambda\_k\; =\; \backslash alpha\_k\; \backslash mathrm\{e\}^\{j\; \backslash omega\_k\}$, and the radial frequencies $\backslash omega\_1,\backslash \; \backslash omega\_2,\backslash \; \backslash ldots,\backslash \; \backslash omega\_K$

are estimated as the phases (argument) of the eigenvalues.

Remark: In general, $\backslash mathbf\; S\_1$ is not invertible. One can use the least squares estimate $\{\backslash mathbf\; P\}\; =\; (\backslash mathbf\; S\_1^\backslash dagger\; \{\backslash mathbf\; S\_1\})^\{-1\}\; \backslash mathbf\; S\_1^\backslash dagger\; \{\backslash mathbf\; S\_2\}$. An alternative would be the total least squares estimate.

Input: Measurements $\backslash mathbf\{Y\}\; :=\; [\backslash ,\backslash mathbf\{y\}[1]\; \backslash ,\backslash \; \backslash mathbf\{y\}[2]\; \backslash ,\backslash \; \backslash dots\; \backslash ,\backslash \; \backslash mathbf\{y\}[\; T\; ]\backslash ,]$

, the number of input signals $K$

(estimate if not already known).

1. Compute the singular value decomposition (SVD) of $\backslash mathbf\{Y\}\; =\; \backslash mathbf\; U\; \backslash mathbf\; \backslash Sigma\; \backslash mathbf\; V^\backslash dagger$ and extract the signal subspace $\backslash mathbf\{U\}\_\backslash mathrm\{S\}\; \backslash in\; \backslash mathbb\{C\}^\{M\; \backslash times\; K\}$

as the first $K$ columns of $\backslash mathbf\; U$.

1. Compute $\backslash mathbf\{S\}\_1\; =\; \backslash mathbf\; J\_1\; \backslash mathbf\; U\_\backslash mathrm\{S\}$ and $\backslash mathbf\{S\}\_2\; =\; \backslash mathbf\; J\_2\; \backslash mathbf\; U\_\backslash mathrm\{S\}$

, where $\backslash mathbf\; J\_1\; =\; [\backslash mathbf\; I\_\{M-1\}\; \backslash quad\; \backslash mathbf\; 0]$ and $\backslash mathbf\; J\_2\; =\; [\backslash mathbf\; 0\; \backslash quad\; \backslash mathbf\; I\_\{M-1\}]$.

1. Solve for $\backslash mathbf\{P\}$

in $\backslash mathbf\; S\_2\; =\; \backslash mathbf\; S\_1\; \backslash mathbf\{P\}$

(see the remark above).

1. Compute the eigenvalues $\backslash lambda\_1,\; \backslash lambda\_2,\; \backslash ldots,\; \backslash lambda\_K$

of $\backslash mathbf\{P\}$

.

1. The phases of the eigenvalues $\backslash lambda\_k\; =\; \backslash alpha\_k\; \backslash mathrm\{e\}^\{j\; \backslash omega\_k\}$

provide the radial frequencies $\backslash omega\_k$

, i.e., $\backslash omega\_k\; =\; \backslash arg\; \backslash lambda\_k$

.

In the derivation above, the selection matrices $\backslash mathbf\; J\_1\; =\; [\backslash mathbf\; I\_\{M-1\}\; \backslash quad\; \backslash mathbf\; 0]$ and $\backslash mathbf\; J\_2\; =\; [\backslash mathbf\; 0\; \backslash quad\; \backslash mathbf\; I\_\{M-1\}]$ were used. However, any appropriate matrices $\backslash mathbf\; J\_1$ and $\backslash mathbf\{J\}\_2$ may be used as long as the rotational invariance $($i.e., $\backslash mathbf\; J\_2\; \backslash mathbf\; a(\backslash omega\_k)\; =\; e^\{-j\backslash omega\_k\}\; \backslash mathbf\; J\_1\; \backslash mathbf\; a(\backslash omega\_k)$$)$, or some generalization of it (see below) holds; accordingly, the matrices $\backslash mathbf\; J\_1\; \backslash mathbf\; A$ and $\backslash mathbf\; J\_2\; \backslash mathbf\; A$ may contain any rows of $\backslash mathbf\; A$.

The rotational invariance used in the derivation may be generalized. So far, the matrix $\backslash mathbf\; H$ has been defined to be a diagonal matrix that stores the sought-after complex exponentials on its main diagonal. However, $\backslash mathbf\; H$ may also exhibit some other structure.{{Cite journal |last1=Hu |first1=Anzhong |last2=Lv |first2=Tiejun |last3=Gao |first3=Hui |last4=Zhang |first4=Zhang |last5=Yang |first5=Shaoshi |date=2014 |title=An ESPRIT-Based Approach for 2-D Localization of Incoherently Distributed Sources in Massive MIMO Systems |url=https://ieeexplore.ieee.org/document/6777542 |journal=IEEE Journal of Selected Topics in Signal Processing |volume=8 |issue=5 |pages=996–1011 |doi=10.1109/JSTSP.2014.2313409 |arxiv=1403.5352 |bibcode=2014ISTSP...8..996H |s2cid=11664051 |issn=1932-4553}} For instance, it may be an upper triangular matrix. In this case, $\backslash mathbf\{P\}\; =\; \backslash mathbf\{F\}^\{-1\}\; \backslash mathbf\; H\; \backslash mathbf\{F\}$constitutes a triangularization of $\backslash mathbf\; P$.

• Multiple signal classification
• Generalized pencil-of-function method
• Independent component analysis

{{reflist}}

• {{Citation | last1=Paulraj | first1=A. | last2=Roy | first2=R. | last3=Kailath | first3=T. | title=Nineteenth Asilomar Conference on Circuits, Systems and Computers | isbn=978-0-8186-0729-5 | year=1985 | chapter=Estimation Of Signal Parameters Via Rotational Invariance Techniques - Esprit | doi=10.1109/ACSSC.1985.671426 | pages=83–89| s2cid=2293566 }}.
• {{Cite journal | last1=Roy | first1=R. | last2=Kailath | first2=T. | title=Esprit - Estimation Of Signal Parameters Via Rotational Invariance Techniques | year=1989 | journal=IEEE Transactions on Acoustics, Speech, and Signal Processing | url=http://www.vtvt.ece.vt.edu/research/references/uwb/ranging_mobile_location/esprit.pdf | volume=37 | issue=7 | pages=984–995 | doi=10.1109/29.32276 | s2cid=14254482 | access-date=2011-07-25 | archive-date=2020-09-26 | archive-url=https://web.archive.org/web/20200926212409/https://www.vtvt.ece.vt.edu/research/references/uwb/ranging_mobile_location/esprit.pdf | url-status=dead }}.
• {{cite journal|first1=A. M.|last1= Ibrahim|first2= M. I.|last2= Marei|first3= S. F.|last3= Mekhamer|first4= M. M.|last4= Mansour | journal=Electric Power Components and Systems

|volume= 39| issue= 1|year= 2011

|title=An Artificial Neural Network Based Protection Approach Using Total Least Square Estimation of Signal Parameters via the Rotational Invariance Technique for Flexible AC Transmission System Compensated Transmission Lines|doi= 10.1080/15325008.2010.513363 |pages= 64–79|s2cid= 109581436}}

• Haardt, M., Zoltowski, M. D., Mathews, C. P., & Nossek, J. (1995, May). 2D unitary ESPRIT for efficient 2D parameter estimation. In icassp (pp. 2096-2099). IEEE.

Category:Signal estimation

Category:Trigonometry

Category:Wave mechanics