# Curse of dimensionality for time series?

I am a bit boggled when trying to conciliate econometric and machine learning view for time series.

Let's assume that each of the $N$ (stochastic) time series have $T$ synchronous i.i.d. observations, but can be correlated between themselves. That is an input matrix $X \in \mathbf{R}^{N \times T}$.

According to the "curse of dimensionality" well-known in machine learning, using an Euclidean distance between these series will find that they are more and more equidistant as $T \rightarrow +\infty$; cf. section "Distance functions" from the Wikipedia article:

For any fixed $N$, it turns out that the minimum and the maximum distance between a random reference point $Q$ and a list of $N$ random data points $P_1,...,P_N$ become indiscernible compared to the minimum distance: $$\lim_{T \to \infty} \mathbf{E}\left(\frac{\mathrm{dist}_{\max} (T) - \mathrm{dist}_{\min} > (T)}{\mathrm{dist}_{\min} (T)}\right) \to 0.$$ This is often cited as distance functions losing their usefulness (for the nearest-neighbor criterion in feature-comparison algorithms, for example) in high dimensions.

My problem:

Many papers in machine learning consider a time series as a point in $\mathbf{R}^T$, and then claim that as $T$ is growing it is much more involved for doing nearest-neighbor search or performing clustering on the $N$ time series, which (to me) seems contradictory with the econometric view where for a fixed number of time series $N$, more observations (bigger $T$), the better. It is particularly true for estimate of correlation between these time series for example. Correlations $\rho_{ij}$ which can be then cast as a distance (and is actually often used in econophysics, e.g. $\rho_{ij} \mapsto \sqrt{2(1-\rho_{ij}}$) between these time series.

It becomes all the more puzzling for me when considering the following situation:

Let $X$ and $Y$ be two of these $N$ time series. Let's assume that they are normally distributed: $X \sim \mathcal{N}(\mu_X,\sigma_X^2)$, $Y \sim \mathcal{N}(\mu_Y,\sigma_Y^2)$ with a correlation $\rho(X,Y)$ between them. Then, we can compute an Euclidean distance between them: $$\mathbf{E}[(X-Y)^2] = (\mu_X - \mu_Y)^2 + (\sigma_X - \sigma_Y)^2 + 2\sigma_X \sigma_Y (1 - \rho(X,Y)).$$ Let's specify the variables/time series a bit more to make the problem more obvious: $\mu_X = \mu_Y$ and $\sigma_X = \sigma_Y = 1$. We then get: $$\mathbf{E}[(X-Y)^2] = 2(1 - \rho(X,Y)).$$

The Euclidean distance is a function of the correlation which is estimated more and more precisely as $T \rightarrow +\infty$. If the time series have a distinct correlation, then it will become more and more easy to separate them with growing $T$ unlike what is claimed by the curse of dimensionality / machine learning view.

Does someone have an idea how to conciliate in this case these two views?

• This seems to apply not only to time series, but also to cross sections, making it a very general problem. – Richard Hardy Mar 20 '17 at 9:39
• In your example with X and Y, are these random variables T x 1 vectors? If thats the case, when you right (...)^2 do you mean the norm in R^T? – Igor Mar 20 '17 at 19:39