Spectra of spatial and temporal covariance matrices

Question

Suppose $(x_i(t))$ is a $n$-dimensional time-series, where $t$ is an integer between $1$ and $T$ (time is discrete) and $i$ an integer between $1$ and $n$, and I assume $n<T$. From this time-series, one can construct two interesting covariance matrices:

The spatial covariance matrix : $A_{ij} = \sum_{t} x_i(t)x_j(t)$

The temporal covariance matrix : $B_{st} = \sum_{i} x_i(s)x_i(t)$

If one puts $x_i(t)$ in matrix form $X$, with $X_{it}=x_i(t)$, then $A=X.X'$ and $B=X'.X$.

So from the singular value decomposition of $X$ we know that $A$ and $B$ share exactly the same eigenvalues (the only difference is that, in addition, $B$ has $T-n$ zero eigenvalues).

Therefore, my question is : what does it MEAN ? Is there an explanation of this fact somewhere ? Do you have some physical interpretation ?

Answer 1

For a meaningful answer to your question about "physical interpretation", I need to work with empirical covariance matrices, so averaged over many trials. (You consider a single trial in your question, but that somehow obscures the interpretation.) My conclusion is:

If you find that the empirical spatial and temporal covariance matrices share the same positive eigenvalues, then you know that your data is self-averaging in both space and time.

Consider a data set $x_{ij}^{(k)}$ of measured values at position $i$, time sample $j$ in the $k$-th trial. The empirical spatio-temporal covariance matrix is defined by

$$C_{ii',jj'}=\frac{1}{N_{\rm trials}}\sum_{k=1}^{N_{\rm trials}}x_{ij}^{(k)}x_{i'j'}^{(k)}.$$

Empirical spatial and temporal covariance matrices are constructed as partial traces,

$$S_{ii'}=\sum_{j}C_{ii',jj},\qquad T_{jj'}=\sum_{i}C_{ii,jj'}.$$

In general, these two matrices $S$ and $T$ will have different sets of positive eigenvalues.

However, if the data is self-averaging in time, then the empirical spatial covariance matrix is $\bar{S}_{ii'}=\sum_{j}x_{ij}^{(k)}x_{i'j}^{(k)}$ independent of the sample index $k$; if moreover the data is self-averaging in space, then the empirical temporal covariance matrix is $\bar{T}_{jj'}=\sum_{i}x_{ij}^{(k)}x_{ij'}^{(k)}$ independent of $k$. These two matrices $\bar{S}$ and $\bar{T}$ (corresponding to your $A$ and $B$) have the same set of positive eigenvalues.

Answer 2

The singular value decomposition of $X$ yields two matrices $U_{i\alpha}$ and $V_{t\alpha}$, and a diagonal matrix of singular values $\Sigma_{\alpha\alpha}=\sigma_\alpha$. The decomposition satisfies $X=U\Sigma V^T$. The number of singular values $r$ is determined by the rank of $X$. The shape of $U$ is $n\times r$, and the shape of $V$ is $T\times r$, in other words, $U$ has $r$ rows of length $n$, and $V$ has $r$ rows of length $T$. The shapes of $U$ and $V$ suggest that the rows of $U$ have spatial character and the rows of $V$ have temporal character. In essence, we can interpret the SVD as follows:

• The rows of $U$ describe spatial modes of variation of $X$.
• The rows of $V$ describe temporal modes of variation of $X$.
• The singular values describe the magnitude of those variations.

An alternative interpretation of the SVD is

$$x_i(t)=\sum_\alpha\sigma_\alpha y^\alpha_i(t)$$

where each $y^\alpha$ is a normal mode given by the tensor product of a spatial vector and a temporal vector

$$y^\alpha_i(t)=u^\alpha_i\otimes v^\alpha(t).$$

A matrix that is the tensor product of vectors is called a simple tensor, or tensor of rank one. Using tensor notation allows us to extend the SVD to higher dimensions (see tensor rank decomposition). As a concrete example of thinking of these as normal modes, consider solutions to the wave equation. A possible solution set is $u^\alpha_i=\sin(k_\alpha i)$ and $v^\alpha(t)=\sin(\omega_\alpha t)$ with the constraint $k_\alpha\omega_\alpha=c$ with wave speed $c$. The normal modes are just $y^\alpha_i(t)=u^\alpha_i v^\alpha(t)$.

As an application of this mode based intuition consider $X$ as a random sample. In this setting small singular values could be suggestive of noise, something we might want to remove, while larger singular values correspond to actual modes of the system. Thinking in that way, the SVD can be used for compression. We can compress the data by storing only the largest singular values and corresponding columns of $U$ and $V$. The number of singular values and vectors that we keep determines the compression rate. In cases where $X$ is not full rank, i.e., $r<n$ and $r<T$, then we can achieve lossless compression with the SVD since the full $\Sigma$, $U$, and $V$ matrices take up less space than the original $X$. Note that none of this interpretation relies on the fact that $t$ is temporal and $i$ is spatial. For image compression the data is an array of pixels $x_{ij}$. Also I should clarify that typical image compression methods rely on FFT rather than SVD, but even FFT methods can be interpreted as SVD with Fourier modes presupposed.

Now let's return to the $A$ and $B$ covariance matrices. Using the SVD we have $A=U\Sigma V^T V\Sigma U^T$ which is just $U\Sigma^2 U^T$; so, the spatial covariance matrix only knows about the spatial modes of $X$. And similarly the temporal covariance matrix only knows about the temporal modes $B=V\Sigma^2 V^T$. The common singular values are a consequence of the fact that the spatial and temporal modes are locked together in a tensor product in the tensor rank decomposition of $X$. In the wave equation example, it was the wave equation itself that determined the interdependency between spatial and temporal variations. In a more general setting, it is quite surprising that the temporal and spatial fluctuations can be related, but that is just the magic of the tensor rank decomposition.

Answer 3

@Carlo's answer is very insightful from a physics perspective, thanks a lot for the teaching and learning here. My answer is from a more ML and statistic perspective as @Ed Smith asked.

But in the OP, I think the formulation is not accurate, your spatial and temporal covariance matrices do not have to share the same set of singular values, noticing that the $B_{st} = \sum_{i} x_i(s)x_i(t)$ involves also spatial indices $s$ while $A_{ij}$ depends only on temporal indices $t$.

Shared eigenvalues and shared eigenvectors/eigenspaces are not the same, the latter is a much stronger feature in general.

(1) Shared eigenvalues As pointed out by @Carlo, "when the empirical spatial and temporal covariance matrices share the same positive eigenvalues, then you know that your data is self-averaging in both space and time." In addition, if shared singular values are detected, the joint inference of spatial temporal series might be possible (known as "Spatial-Temporal Spectrum Sensing" [Do et.al.], where a Fourier basis is used). Another important pattern is that, since your eigenvalues are the same, so would the ordering of eigenvalues. This additional factor may be useful in detecting change-point via SVD when evolutionary dynamics exists [Townsend&Gong]. However, due to numerical issues for large matrices or outliers in observations, sometimes positive eigenvalues (since we are concerning covariance matrices) may be very close to zero; then shared eigenvalues to correct numerical or detect outliers.

(2) Shared eigenspaces A more important feature may be the eigenspaces spatial and temporal covariance spans, since the eigenvectors represent the spatial and the temporal modes [Greenewald&Hero], shared eigenspaces may allow borrowing information from spatial data to estimate temporal parameters and vice versa. Besides, we may find a good basis spanned by eigenvectors (or chosen spectrum basis) that approximates both spatial and temporal dependence well. This is consistent with Carlo's answer above.

If there are shared eigenvectors for both matrices, another natural thought would be to construct effective approximations when the model is fitted to large datasets like spatial datasets [Genton]. Effective approximations of certain models like Gaussian processes and Gaussian random fields are of central important in machine learning and spatial statistics [Bauer et.al.], especially for the scenarios that require efficient fits to large datasets. When you use approximation techniques for SVD in large spatial-temporal matrices, shared spatial-temporal spectra may allow a better approximation [Bogaardt et.al.]. It also allows fine filtering in image processing (other than signal processing).

Reference (by date, not necessarily past 7 years.)

[Genton] Separable approximations of space-time covariance matrices, 2007.

[Do et.al.] Joint Spatial-Temporal Spectrum Sensing for Cognitive Radio Networks, 2010.

[Greenewald&Hero]Robust Kronecker Product PCA for Spatio-Temporal Covariance Estimation, 2015.

[Bauer et.al.]Understanding Probabilistic Sparse Gaussian Process Approximations, 2016.

[Baranger et.al.] Adaptive Spatiotemporal SVD Clutter Filtering for Ultrafast Doppler Imaging Using Similarity of Spatial Singular Vectors, 2018.

[Townsend&Gong] Detection and analysis of spatiotemporal patterns in brain activity, 2018.

[Bogaardt et.al.] Dataset Reduction Techniques to Speed Up SVD Analyses on Big Geo-Datasets, 2019.