| Sbornik: Mathematics |
|
|
|
|
|
Kolmogorov widths, Grassmann manifolds and unfoldings of time series V. M. Buchstaber Steklov Mathematical Institute of Russian Academy of Sciences, Moscow, Russia
Bibliographic databases:
    § 1. IntroductionThis paper is dedicated to the remarkable mathematician and wonderful person Vladimir Mikhailovich Tikhomirov. It is based on the slides of the author’s talk under the same title at the conference “Mekhmat-24: Actual Problems of Mathematics and Mechanics”, in December 2-4, 2024, at the section dedicated to the 90th birthday of V. M. Tikhomirov. The concept of $n$-width was introduced by Kolmogorov in 1936; see [14], paper no. 28. One of the most famous smooth manifolds in algebraic topology is the Grassmann manifold $G(N,n)$ of all $n$-dimensional subspaces $L\subset\mathbb{R}^N$; see, for example, [23]. Our paper is devoted to the theory and applications of multidimensional unfoldings of time series; see [8] and [9]. We discuss results based on methods of applied statistical data analysis, the theory of shift operators and functional equations. Algorithms for solving extremal problems on Grassmann manifolds are presented; see [6], [7] and [1]. The key objective of this paper is to expose the connection between the theory of widths and the theory of unfoldings of time series in problems of function approximation, recovery of a function from a series of its values at a discrete set of points, and bounds for parameters of families of functions. The difference between the formulations of problems in these theories is that, instead of a set of points, piecewise linear curves (graphs) with nodes at these points are considered. This paper is related to Kolmogorov’s works “On the best approximation of functions of a given function class” (1936) and “Curves in Hilbert space invariant with respect to a one-parameter group of motions” (1940); see [14], paper nos. 28 and 42. The concept of the $n$-width $D_n(F)$ of a class of functions $F$ with respect to the $n$-dimensional subspaces of the space of approximating functions was introduced by Kolmogorov in 1936; see [14], paper no 28. In this way the decreasing sequence $\{D_n(F),\, n=1,2,\dots\}$ of nonnegative numbers was assigned to the class $F$, and the following problem was stated:
The theory and applications of $n$-widths have been at the centre of Tikhomirov’s scientific work. His results in this direction (see [25]–[30], [19] and [31]) have received international recognition. On the web-portal Math-Net.Ru the list of his main publications begins with the paper [25] of 1960. Let some function space $\mathfrak{F}$ be chosen and a distance $\rho$ be fixed in it. Let a family (class) $F \subset \mathfrak{F}$ and a linear space of approximating functions $\Phi \subset \mathfrak{F}$ be given. Consider the problem of the approximation of a function $f\in F$ by linear forms of the type where $\varphi_1, \dots, \varphi_n$ is a fixed set of functions from $\Phi$. Let $L_\varphi$ be the $n$-dimensional subspace of $\Phi$ spanned by $(\varphi_1, \dots, \varphi_n)$. Let $E_n(f,L_\varphi)$ denote the distance $\rho$ from $f$ to $L_\varphi$ and by $D_n(F,L_\varphi)$ the least upper bound of the quantities $E_n(f,L_\varphi)$, where ${f\in F}$.Kolmogorov called the deviation of the set $F$ from $\Phi$, in the sense of the greatest lower bound $D_n(F,\Phi)$ of the quantities $D_n(F,L_\varphi)$, where $L_\varphi$ ranges over all $n$-dimensional subspaces of $\Phi$, the $n$-width of the set $F \subset \mathfrak{F}$ with respect to the space $\Phi$. As noted in Tikhomirov’s survey [25], the deviations of the set of periodic functions $F$ from the spaces $\Phi$ of trigonometric and ordinary polynomials were calculated by Favard [11], Akhiezer and Krein [4], Akhiezer [3], Krein [15], Nagy [22] and Babenko [5]. Among the papers on Kolmogorov widths published after 1960, we note [12], [13] and [16]–[19]. The following definition was given in Tikhomirov’s survey [31] of 2022. Definition 1. Let $(\mathcal{X},\|\cdot\|_\mathcal{X})$ be a normed space and l $C$ be a family (class) of elements of $\mathcal{X}$. The set of affine subspaces (translations of linear subspaces) $L_n$ of dimension $n$ is denoted by $\operatorname{Lin}(\mathcal{X})$. Then the quantity is called the Kolmogorov $n$-width of $C$. A presentation and an analysis of the results obtained in the theory of $n$-widths and in its applications up to 2022 can also be found in [31]. The precise value of the width of a set of $N$ orthonormal vectors in Euclidean space is known (see, for example, [31]). Among recent works on this topic, we note Malykhin’s paper [20], in which the widths of systems of $N$ functions in $L_p$-spaces were studied. It turns out that the widths of finite systems of vectors are related directly to important concepts in discrete mathematics, such as the approximate rank and rigidity of matrices; see also [13]. When $\mathcal{X}=\mathbb{R}^N$ is $N$-dimensional Euclidean space, the set $\operatorname{Lin}(\mathcal{X})$ is the tangent manifold $TG(N,n)$ of the Grassmann manifold $G(N,n)$. In this case the concept of $n$-width is related to a number of areas in theoretical and applied mathematics in which extremal problems on Grassmann manifolds $G(N,n)$ are solved. In this paper we use a construction that relates results in the theory of unfoldings of time series to $n$-widths. To describe this construction, we have to use the term ‘$q$-width’ in place of ‘$n$-width’. Let some set $F$ of continuous functions on the closed interval $[0,1]$ be fixed in the Kolmogorov problem. We choose a discretization step $\Delta$ and associate with a function $f \in F$ the time series
$$
\begin{equation*}
S_f=(f_1,\dots,f_N),\quad \text{where } f_s=f(t_1+(s-1)\Delta), \quad s=1,\dots,N.
\end{equation*}
\notag
$$
Given $n$, consider the piecewise linear curve $X_f\subset\mathbb{R}^n$ with the nodes
$$
\begin{equation*}
X_1,\dots,X_P, \quad\text{where } X_k=(f_k,\dots,f_{k+n-1})\in \mathbb{R}^n, \quad P=N-n+1.
\end{equation*}
\notag
$$
By the $q$-width of the time series $S_f$ we mean the $q$-width of the set $X_f\subset\mathbb{R}^n$. By the $q$-width of the set of time series $\{S_f,\ f\in F\}$ we mean the $q$-width of the set $X_F=\bigcup_{f\in F} X_f$. The time series analysis based on component analysis (the ‘Caterpillar’ method; see [10]) coincides with the corresponding part of the theory of unfoldings of time series; see [8] and [9]. In this paper we present an algorithm for calculating the $q$-widths of time series by means of component analysis. Important algorithms of the theory of time series and topological data analysis can be written in terms of the theory of unfoldings of multidimensional time series. We show this in §6 using the example of the discrete Fourier transform, one of the most famous linear methods of time series analysis. Also note the section “Multivariate unfolding in nonlinear time series analysis” of [9], which discusses the connection of multivariate unfolding with some statements of problems and results in nonlinear analysis, including the well-known Takens theorem; see [24]. In the final section of this paper, § 7, we discuss the solution to the problem of the statistical analysis of the time series of monitoring data on atmospheric CO$_2$; see [2]. § 2. Extremal problems on Grassmann manifoldsWe present the requisite facts about Grassmann manifolds; for details, see [21] and [23]. Definition 2. The Grassmann manifold $G_{\mathbb{R}^n}(n,q)$ (in what follows, $G(n,q)$) is the manifold of all $q$-dimensional linear subspaces of $\mathbb{R}^n$. Every $q$-dimensional linear subspace $L$ in $\mathbb{R}^n$ is spanned by $q$ orthonormal $n$-dimensional vectors, which are defined up to an orthogonal transformation of $L$. Thus, a point in $G(n,q)$ is given by an $n\times q$ matrix $\Pi=(\ell_{i,j}\colon 1\leqslant i\leqslant n,\, 1\leqslant j\leqslant q)$ up to a right action $\Pi B$ by orthogonal matrices $B\in O(q)$. The manifold $G(n,q)$ is homogeneous with respect to the left action $A\Pi$ by orthogonal matrices $A\in O(n)$, that is, for any $x,y\in G(n,q)$ there exists a matrix $A\in O(n)$ such that $Ax=y$. Let $\operatorname{Sym}(n,n)$ be the linear space of all symmetric $n \times n$ matrices $M$. The orthogonal group $O(n)$ acts on $\operatorname{Sym}(n,n)$ by conjugation, in accordance with the formula $AMA^\top$, where $A\in O(n)$ and $A^\top$ is the transposed matrix. We define an $O(n)$-equivariant embedding (that is, $\varphi(Ax)=A\varphi(x)$) associating with a subspace $L$ of $\mathbb{R}^n$ the matrix $\Pi\Pi^\top$, where $\Pi$ is an $ n\times q $ matrix formed by $q$ orthonormal $n$-dimensional vectors. The embedding $\varphi$ realizes $G(n,q)$ as a smooth algebraic subvariety of dimension $q(n-q)$ of a linear space of dimension $(n+1)n/2$.For example, the $n$-dimensional projective space is realized as an algebraic subvariety of $\mathbb{R}^N=\operatorname{Sym}(n+1,n+1)$, $N=(n+2)(n+1)/2$, equivariantly with respect to the action of $O(n+1)$.Each $q$-dimensional linear subspace $L\subset \mathbb{R}^n$ defines an orthogonal projection $\mathbb{R}^n\to\mathbb{R}^n$ with image $L$. We denote this projection by the same symbol $L$. The manifold is realized as the manifold of all orthogonal projections $L \colon \mathbb{R}^n\to \mathbb{R}^n$ of rank $q$, that is, such that $\dim\operatorname{Im} L=q$.Corresponding to an orthogonal projection $L$ is the linear $q(n-q)$-dimensional space of projections $\mathbb{R}^n\to \mathbb{R}^n$ with image $L\subset \mathbb{R}^n$. The manifold of affine subspaces of $\mathbb{R}^n$ is realized as the tangent manifold $TG(n,q)$ of $G(n,q)$. The manifold $TG(n,q)$ is realized as the manifold of all affine projections ${\mathbb{R}^n\mkern-1mu\!\to\! \mathbb{R}^n}$ of rank $q$. Topological data analysis on $G(n,q)$ (for details, see [1])In this subsection, by subspaces $L$ we mean affine subspaces of $\mathbb{R}^n$. Let $P$ points $X=\{X_1,\dots,X_P\}$ be fixed in $\mathbb{R}^n$. In statistical data analysis a point $X_k=(x_{k1},\dots, x_{kn})$ describes the $k$th object determined by $n$ parameters. Problem 1 (dimensionality reduction). Find a $q$-dimensional subspace $L$ of $\mathbb{R}^n$, $q < n$, such that the orthogonal projection of $X$ onto $L$ loses the minimum of information about the structure of $X$. The set $X \subset \mathbb{R}^n$ defines a set $Y=\{Y_1$, …, $Y_n\}\subset \mathbb{R}^P$, where $Y_m=(Y_{m1}$, …, $Y_{mP})$ and $Y_{mk}=X_{km}$. Problem 2 (clustering). Find a $q$-dimensional subspace $L$ of $\mathbb{R}^P$, $q \ll P$, such that the orthogonal projection of the set $Y$ onto $L$ loses the minimum of information about the structure of $Y$. Let $P$ points $X'$ and $Q$ points $X''$ be fixed. We introduce the array of vectors
$$
\begin{equation*}
Z=\{Z_{ij},\, i \in [1, P],\, j \in [1, Q]\},\quad\text{where } Z_{ij}=X'_i - X''_j.
\end{equation*}
\notag
$$
Problem 3. Find a $q$-dimensional subspace of $L$, $q\ll n$, such that the projection of the array $Z$ onto $L$ takes no vector $Z_{ij}$ to zero. If such a subspace $L$ is found, then the sets $X'$ and $X''$ are said to be representative with respect to the decision rule specified by the subspace $L$. Unfolding a time seriesWe regard the time series $f=(f_1,\dots,f_N)$ under consideration as a sequence of values of some function $f(t)$: Definition 3. The piecewise linear curve $X_f$ in $\mathbb{R}^n$ obtained by connecting successively the vectors $X_1,\dots,X_P$, $P=N-n+1$, where $X_q=(f_q,\dots,f_{q+n-1})$, is called the $n$-dimensional unfolding $X_f=X_f(N;n)$ of the time series $f=(f_1,\dots,f_N)$. The vectors $X_1,\dots,X_P$, $P=N-n+1$, are called the nodes of the curve $X_f$. The method of unfolding on $G(n,q)$Below we consider orthogonal projections of $\mathbb{R}^n$ onto $q$-dimensional subspaces $L$. Let $X_f \subset \mathbb{R}^n$ be the unfolding of the time series $f$. Problem 4. Find a subspace $L \subset \mathbb{R}^n$ such that the projection of the curve $X_f$ onto $L$ is the most expressive one. Problem 5. Find subspaces $L_1,L_2 \subset \mathbb{R}^n$ such that the projections onto these subspaces of the curve $X_f$ show different expressive properties of $X_f$. The space of unfoldings of time seriesThe space $M(n,P)$ of all piecewise linear curves with $P$ nodes in $\mathbb{R}^n$ is identified with $\mathbb{R}^{nP}$. The set $T^N$ of all time series $(f_1, \dots , f_N)$ of length $N$ is identified with $\mathbb{R}^N$. Let $T_u^N \subset M(n,P)$ denote the subspace of unfoldings of time series of length $N$, $\operatorname{dim}T_u^N=N$. We will define the orthogonal projection $\Pi \colon M(n,P)\to T_u^N$; see Definition 17 below. Recovering a series from projections of its unfoldingConsider the unfolding $X_f\subset\mathbb{R}^n$ of a time series $f$ with $N$ samples, fix a subspace $L\subset\mathbb{R}^n$, and let $\pi_L(X_f)$ denote the projection of the curve $X_f$ onto $L$. Problem 6. Find the projection $\Pi(\pi_L(X_f))$ of the curve $\pi_L(X_f)\in M(n,p)$ onto the linear space $T_u^N$. Definition 4. By the $\pi_L(X_f)$-approximation of a time series $f$ we mean the time series $\Pi(\pi_L(X_f))$. Problem 7. Find a subspace $L$ such that the $\pi_L(X_f)$-approximation of a time series $f$ is the best one in the uniform or statistical sense. Problems 1–7 use the concepts of ‘most expressive projection’, ‘minimum information loss’, ‘most representative projection’ and ‘best approximation of a time series’. All these concepts are formalized in terms of criteria. These criteria define functions on $G(n,q)$, and solutions to Problems 1–7 are reduced to algorithms for finding extreme values of these functions. Functions on $G(n,q)$Let $X=(x_1,\dots, x_n)\in \mathbb{R}^n$, $\overline{X}=\frac{1}{n} (x_1+\dots+x_n)$ and $\widetilde{X}=X-\overline{X}$. We consider the functions
$$
\begin{equation*}
F_X(L)=\|L(X)\|^2\quad\text{and} \quad F_{\widetilde{X}}(L)=\| L(\widetilde{X}) \|^2,
\end{equation*}
\notag
$$
where $L\in G(n,q)$ is the point corresponding to the orthogonal projection $L$: ${\mathbb{R}^n\to \mathbb{R}^n}$, and $\|Y\|$ is the norm of the vector $Y \in \mathbb{R}^n$. Let $F=\{F_1(L),\dots,F_m(L)\}$ be a set of functions on $G(n,q)$. The functions
$$
\begin{equation*}
\sum_{k=1}^{m}\alpha_k F_k(L)\quad\text{and} \quad \min \{ F_k(L),\, k=1,\dots, m\}
\end{equation*}
\notag
$$
are used in applications. Algorithms for solving extremal problems on $G(n,q)$ use the differential geometry of this manifold. Gradient optimization on $G(n,q)$Let $1 \leqslant k \leqslant q$, $q+1 \leqslant l \leqslant n$ and $1 \leqslant i$, $j \leqslant n$. Consider the following set of $q(n-q)$ orthogonal $n\times n$ matrices $A(t;k,l)= (a_{i,j}(t;k,l))$ with matrix elements
$$
\begin{equation*}
\begin{aligned} \, &a_{i,i}(t;k,l) =1 \quad\text{if } i\neq k \text{ or } i\neq l; \\ &a_{k,k}(t;k,l) =a_{l,l}(t;k,l)=\cos t \quad\text{and}\quad a_{k,l}(t;k,l)=-a_{l,k}(t;k,l)=\sin t \quad\text{if } l\neq k; \\ &a_{i,j}(t;k,l) =0 \quad\text{otherwise}. \end{aligned}
\end{equation*}
\notag
$$
For every function $\varPhi$ on the manifold $G(n,q)$ and every point $L\in G(n,q)$ we obtain the set of $q(n-q)$ functions $F_L(t;k,l)=\varPhi(A(t;k,l) L)$, $0 \leqslant t \leqslant 2\pi$, and $F_L(0;k,l)= \varPhi(L)$. Theorem 1. For the gradient optimization of an arbitrary smooth function $\varPhi (L)$ on $G(n,q)$ it is necessary and sufficient to have the set of functions $F_L(t; k,l)$. The proof follows from the fact that the trajectories $(A(t;k,l) L)$ for $0\leqslant t< 2\pi$ define the coordinate axes in a neighbourhood of each point $L\in G(n,q)$ represented by the space $L\subset \mathbb{R}^n$. Schubert symbolConsider a sequence of subspaces $\mathbb{R}\subset\mathbb{R}^2\subset\dots\subset\mathbb{R}^n$ in $\mathbb{R}^n$, where $\mathbb{R}^k$ is the subspace with the standard basis
$$
\begin{equation*}
e_1=(1,0,\dots,0), \quad \dots, \quad e_k=(0,0,\dots,1,0,\dots,0).
\end{equation*}
\notag
$$
For every $q$-dimensional linear subspace $L$ in $\mathbb{R}^n$ the following sequence of numbers is defined:
$$
\begin{equation*}
0 \leqslant \operatorname{dim}(L \cap \mathbb{R}) \leqslant \operatorname{dim}(L \cap \mathbb{R}^2) \leqslant \dots \leqslant \operatorname{dim}(L \cap \mathbb{R}^n)=q.
\end{equation*}
\notag
$$
Definition 5. The Schubert symbol of a $q$-dimensional subspace $L \subset \mathbb{R}^n$ is the sequence of integers $1 \leqslant \sigma_1 < \sigma_2 < \dots < \sigma_q \leqslant n$, where Example 2. Every one-dimensional subspace $L\subset\mathbb{R}^n$ has a Schubert symbol $\sigma_1(L)$, $1\leqslant\sigma_1(L)\leqslant n$. Moreover, $\sigma_1(L)=k$ if and only if $L$ is spanned by a vector $\sum_{i=1}^{k}c_ie_i$, where $c_k\neq 0$. A CW-decomposition of the manifold $G(n, q)$ (for details, see [21])The Schubert symbol defines the function For any point $L\in G(n,q)$ the preimage of the value $\sigma (L)$ is a cell, and the set of all these cells defines a CW-decomposition of the manifold $G(n,q)$. The dimension of the cell corresponding to $\sigma(L)=(\sigma_1, \dots, \sigma_q)$ is $(\sigma_1 -1)+\dots +(\sigma_q - q)$. The Schubert basisIt is easy to prove that a $q$-dimensional subspace $L \subset \mathbb{R}^n$ has a Schubert symbol $1 \leqslant \sigma_1 < \sigma_2 < \dots < \sigma_q \leqslant n$ if and only if it has an orthogonal basis $\Omega_1, \dots, \Omega_q$ that is uniquely determined by the following conditions: $\Omega_k \in \mathbb{R}^{\sigma_k}$, and for each $k=1,\dots,q$ the $\sigma_k$th coordinate of the vector $\Omega_k$ is equal to $-1$. Definition 6. The Schubert basis of a subspace $L \subset \mathbb{R}^n$ is the orthogonal basis $\Omega_1, \dots, \Omega_q$ in $L$ corresponding to the Schubert symbol of this space. The principal component method (for details, see [1] and [32])Let $X=\{X_1,\dots, X_P\}$, where $X_k \in \mathbb{R}^n$, and let $\overline{X}=\frac{1}{P} (X_1+\dots+ X_P)$ and $\widetilde{X}_k=X_k - \overline{X}$. Definition 7. The scattering matrix $W=(w_{ij})$ of a set of vectors $X$ is the Gram matrix of the family $\widetilde{X}=\{\widetilde{X}_k\}$, where $w_{ij}=\langle\widetilde{X}_i, \widetilde{X}_j\rangle$ is the standard scalar product. The matrix $W$ is symmetric and nonnegative definite. Let $\lambda_1 \geqslant \lambda_2 \geqslant \dots \geqslant \lambda_n \geqslant 0 $ be the set of eigenvalues of $W$ and $v_1,\dots, v_n$ be the orthonormal set of eigenvectors of this matrix, where the eigenvector $v_k$ corresponding to $\lambda_k$ is called the $k$th principal component of $X$. The vectors $v_k$ are solutions of extremal problems on $G(n,q)$Let $X=\{X_1,\dots, X_P\}$, $X_k \in \mathbb{R}^n$. Consider the function
$$
\begin{equation*}
\varPhi_X(L)=\| L(\widetilde{X}_1)\|^2+\dots+\| L(\widetilde{X}_P)\|^2
\end{equation*}
\notag
$$
on $ G(n, q)$. The value $\varPhi_X(L)$ is equal to the statistical spread of the vectors $L(\widetilde{X}_1),\dots,L(\widetilde{X}_P)$ in $ L$; cf. [1]. Theorem 2. Let $L_{*} \in G(n, q)$ correspond to the subspace $L_{*}$ of $\mathbb{R}^n$ spanned by the first $q$ principal components $v_1,\dots,v_q$. Then The proof uses an explicit description of the gradient of $\varPhi_X(L)$ on the Grassmann manifold; see [7], or [1], Ch. 20. § 3. $q$-widths of time seriesDefinition 8. A piecewise linear curve $K \in M(n, P)$ has rank $r$ if it lies in an $r$-dimensional affine subspace $L$ of $\mathbb R^n$. Definition 9. We say that a piecewise linear curve $K \in M(n,P)$ with nodes $\{X_1,\dots,X_P\}$ belongs to the $\varepsilon$-neighbourhood of the $r$-dimensional affine subspace of $L\subset \mathbb{R}^n$ if $\sum^P_{i=1} \| L - X_i\|^2 < \varepsilon$, where $\| L-X_i\|$ is the distance of the vector $X_i$ to the subspace $L$. Definition 10. A piecewise linear curve $K \in M(n,P)$ has $\varepsilon$-rank $r$ if it lies in the $\varepsilon$-neighbourhood of the $r$-dimensional affine subspace $L\subset \mathbb{R}^n$. Let $X=\{X_1,\dots,X_P\}$ be the set of nodes of $K \in M(n,P)$. Definition 11. The scattering matrix of the curve $K\in M(n,P)$ is the scattering matrix $W_K$ of the set $X$. Thus, the eigenvalues and eigenvectors of any piecewise linear curve $K\in M(n,P)$ are well defined. Definition 12. The scattering matrix of the unfolding $X_f$ of a series $f$ is called the scattering matrix of this series. According to the theory of principal components (see [1]), the following assertion holds. Lemma 1. The rank of a curve $K \in M(n,P)$ does not exceed $r$ if and only if $\lambda_i=0$ for all $i > r$, where $\lambda_1 \geqslant \lambda_2 \geqslant \dots \geqslant\lambda_n \geqslant 0 $ are the eigenvalues of the matrix $W_K$. In addition, the $\varepsilon$-rank of a curve $X_f$ does not exceed $r$ if and only if A curve $K \,{\in}\, M(n,P)$ has rank $r$ if and only if $K\,{=}\,\overline{X}+V(r)(V(r)^\top K)$, where $V(r)$ is the $ r\times n $ matrix whose columns $v_1, \dots, v_r$ are eigenvectors of the scattering matrix of $K$. Corollary 1. Let $f$ be a time series of rank $r$, and let $\lambda_1 \geqslant \lambda_2 \geqslant \dots \geqslant\lambda_n \geqslant 0 $ be the eigenvalues of the scattering matrix of the set of nodes $X_1,\dots,X_P$ of the unfolding $X_f$. Then the $q$-width of the time series $f$ is equal to $\sum_{i=q+1}^{r}\lambda_i$. An analysis of the geometry of the unfolding $X_f$ enables us to obtain some information about the properties of the time series. The rank of the unfolding gives an estimate for the number and nature of the components of the time series. An important task in time series analysis is the following approximation problem: constructing a continuous function that models a given time series. For an application of the $q$-widths of time series to this problem, see § 4 below. Definition 14. The rank of a continuous function $f(t)$ does not exceed $r$ if for all $t_1$, $\Delta t$, $n$, $N$, $n < N$, the rank of the unfolding $X_f$ of the corresponding time series $f$ does not exceed $r$. Regression by the method of multivariate unfoldingConsider a time series $f$ whose rank does not exceed $r\leqslant n-1$. Then there exists an $r$-dimensional plane $L$ such that the curve $X_f$ lies in $L$. Any vector $X \in L$ can uniquely be represented in the form $X=\widetilde{X}+\xi$, where $\widetilde{X}$ is the image of the orthogonal projection of this vector onto the $r$-dimensional subspace $\widetilde{L}$ parallel to $L$ and passing through the origin, and $\xi$ is a vector orthogonal to $L$. Let $\widetilde{L}^{\perp}$ be the $(n-r)$-dimensional subspace of $\mathbb{R}^n$ orthogonal to $\widetilde{L}$. We assign to the space $\widetilde{L}^{\perp}$ its Schubert symbol $\sigma_1 < \sigma_2< \dots < \sigma_{n-r}$ and the corresponding Schubert basis $\Omega_1,\dots,\Omega_{n-r}$. As noted above, for the vector $\Omega_k=(\omega_{k,1}, \dots, \omega_{k,\sigma_{k-1}}, -1, 0, \dots, 0)$ of this basis we have
$$
\begin{equation}
\langle X_q, \Omega_k\rangle=\sum_{j=1}^{\sigma_{k-1}} \omega_{k,j}f_{q+j-1} -f_{q+\sigma_{k-1}}+\omega_{k,0}=0,
\end{equation}
\tag{5}
$$
where $\omega_{k,0}=-\langle\xi, \Omega_k\rangle$. We write $q+\sigma_{k-1}=m$, $q+j-1=m-s$ and obtain
$$
\begin{equation}
f_m=\sum_{s=1}^{\sigma_{k-1}}\omega_{k,\sigma_{k-s}}f_{m-s}+\omega_{k,0},
\end{equation}
\tag{6}
$$
where $m=\sigma_k,\dots, p_k$, $k=1,\dots,n-r$, and $p_k=N-n+\sigma_k$. Thus, if the rank of the time series $f=(f_1,\dots,f_N)$ does not exceed $r\leqslant n-1$, then there exist constants $c_0, c_1, \dots, c_k$, $k\leqslant r$, such that
$$
\begin{equation}
f_m=\sum^k_{s=1}c_{k-s+1}f_{m-s}+c_0, \qquad m=k+1,\dots,P.
\end{equation}
\tag{7}
$$
Corollary 2. Formula (7) allows one to calculate the values of the $\widetilde{f}_m$ for $m=P+1,\dots,N$ while preserving the rank. In general, the numbers $\widetilde f_m$ do not necessarily coincide with the corresponding components $f_m$ of the series $f$. Example 3. Consider the series $f=(0, 1, 2, 3, 4, 2)$, where $N=6$. Its 3-dimensional unfolding has four nodes: $X_1=(0,1,2)$, $X_2=(1,2,3)$, $X_3=(2,3,4)$ and $X_4=(3,4,2)$. We obtain $\xi=\frac{1}{4}(6, 10, 11)$, and $\widetilde{X}_1=\frac{1}{4}(-6, -6, -3)$, $\widetilde{X}_2=\frac{1}{4}(-2, -2, 1)$, $\widetilde{X}_3=\frac{1}{4}(2, 2, 5)$ and $\widetilde{X}_4=\frac{1}{4}(6, 6, 3)$. Consequently, the rank of the series $f$ is $2$. The orthogonal complement to the two-dimensional carrier of the unfolding $X_f$ has Schubert symbol $\sigma_1= 2$ and the Schubert vector $\Omega_1=(1,-1,0)$. Using formula (7) we obtain $f_m=f_{m-1}+1$ for $m=2, 3, 4, 5$, but $f_6 \neq \widetilde{f_6}=f_5+1$. Thus, according to (7), this series cannot be extended preserving rank $2$. In time series analysis, we say in this case that a disorder occurs in the time series $f$. Definition 15. A time series $\widetilde{f}=(\widetilde{f}_m)$ of length $\widetilde{N} > N$ is called an extension of the time series $f=(f_m)$ of length $N$ if $\widetilde{f}_m=f_m$ for all $m \leqslant N$. Theorem 3. Let $1\leqslant r\leqslant n-1$ and $N_1 > N$. A series $f=(f_1, \dots, f_N)$ of rank $r$ admits an extension $\widetilde{f}=(f_1, \dots, f_N, \widetilde{f}_{N+1}, \dots, \widetilde{f}_{N_1})$ with rank preservation if and only if there exist numbers $c_0, c_1, \dots, c_k$, $k\leqslant r$, such that For the proof, see [8]. § 4. Finite rank functionsConsider the class of continuous functions $f(t)$ satisfying functional equations of the form for some continuous functions $\varphi_s(t)$ and $\psi_s(t)$, $s=1,\dots,r$.For fixed $t_1,n,N$ and $\Delta$ we set $Y_s=(Y_{s,1},\dots,Y_{s,n})\in \mathbb{R}^{n}$, where $Y_{s,k}=\varphi_s(t_1+(k-1)\Delta)$. Then $X_f=(X_1, \dots, X_P)$, where $X_q=(X_{q,1},\dots,X_{q,n})\in \mathbb{R}^{n}$ and $X_{q,k}=f(t_1+(q+k-2)\Delta)=\sum_{s=1}^{r}\psi_s((q-1)\Delta)Y_{s,k}$, that is,
$$
\begin{equation*}
X_q=\sum_{s=1}^{r}\psi_s((q-1)\Delta)Y_s, \qquad q=1,\dots,P.
\end{equation*}
\notag
$$
Therefore, the unfolding $X_f$ lies in the $r$-dimensional space spanned by the vectors $Y_s$. Thus, we have shown that any continuous function satisfying the functional equation (9) has a rank not exceeding $r$. Some examples of functions of rank $r$:
Lemma 2. Let $f(t)$ be a function with $r$ derivatives satisfying the functional equation (9) in which the functions $\psi_s(\tau)$, $s=1,\dots,r$, are $r$ times differentiable at $\tau=0$. Then $f(t)$ is a solution of an ordinary differential equation with constant coefficients. Proof. Differentiating equation (9) $r$ times with respect to $\tau$, for $\tau=0$ we obtain a system of $r+1$ linear equations with constant coefficients. This completes the proof of the lemma. According to the theory of ordinary differential equations, the general solution $f(t)$ of equation (10) has the form
$$
\begin{equation}
f(t)=\sum a_{k}(t)e^{\lambda_{k}t} \sin(\omega_{k}t+\varphi_{k}),
\end{equation}
\tag{11}
$$
that is, this solution is a function of finite rank; see the above examples. The problem of the approximation of a time series by functions of the form (11) is classical. It arises naturally in modern theoretical and applied research. Algorithms for its solution are complicated and produce unstable results unless some a priori information about the series is used. Simpler algorithms of the theory of multidimensional unfoldings enable us to calculate the widths of the series under consideration and thereby obtain some information about the class of functions of the form (11) which can be sufficient for a stable result. § 5. $L$-approximation of time seriesConsider the space $M(n,P) \approx \mathbb{R}^{nP}$ of all piecewise linear curves with $P$ nodes in $\mathbb{R}^{n}$. We introduce the distance
$$
\begin{equation}
\| Y_1 - Y_2\|^2=\frac{1}{P} \sum_{i=1}^{P} \| X_{1i} - X_{2i}\|^2
\end{equation}
\tag{12}
$$
in $M(n,P)$, where $Y_1$ and $Y_2$ are curves in $M(n,P)$, $Y_k=(X_{k1}, \dots, X_{kn})$, $k=1, 2$, and $\| \cdot \|$ denotes the Euclidean norm. Let $M^r(n,P)$ be the set of piecewise linear curves of rank at most $r$ in $M(n,P)$, and consider the projection Definition 16. A curve $Y_{*}(r) \mkern-1mu\!\in\! M^r(n,P)$ is the projection of a curve $Y \mkern-1mu\!\in\! M(n,P)$ if Definition 17. A time series $\widehat f=(\widehat f_1, \dots, \widehat f_N)$ is called the orthogonal projection of a curve $Y \in M^r(n,P)$ onto the space of time series $T^N$ if where $X_{\widehat f}$ and $X_f$ are the unfoldings of the time series $\widehat f$ and $f$, respectively. Theorem 4. Given a curve $Y \in M(n,P)$, its projection $\widehat f(Y)$ onto the space $T^N$ of time series has the form $\widehat f(Y)=(\widehat f_1, \dots, \widehat f_N)$, where Formulae (14) and (15) immediately imply the formula
$$
\begin{equation*}
\| Y - X_{f}\|^2=\| X_{\widehat f(Y)} - X_f\|^2+\| Y - X_{\widehat f(Y)}\|^2,
\end{equation*}
\notag
$$
from which we obtain the proof of Theorem 4. Let a series $f=(f_1,\dots,f_N)\in \mathbb{R}^{n}$ and some $q$-dimensional subspace $L\subset\mathbb{R}^{n}$ be fixed. Let $X_f(L)$ denote the projection of the unfolding $X_f$ onto $L$. We set $r_f(L)=f-\widehat f(L)\in \mathbb{R}^{n}$. We fix a number $q<n$ and some norm $\| \cdot \|_*$ in $\mathbb{R}^{n}$. § 6. Discrete Fourier transform and time series unfoldingThe aim of the discrete Fourier transform is to expand the series under consideration with respect to the Fourier basis; see, for example, [32]. We present a result relating the discrete Fourier transform to multidimensional unfoldings. Consider the function $f(t)=\sin\omega t$ and the time series $f=(f_1,\dots,f_N)$, where $f_q=\sin (q-1)\omega$, $q=1,\dots,N$. Fixing $n\ll N$ we obtain the unfolding
$$
\begin{equation*}
X_f=(X_1,\dots,X_P),\quad \text{where } X_k= (f_k,\dots,f_{k+n-1}),\quad k=1,\dots,P=N-n+1.
\end{equation*}
\notag
$$
We introduce the $n$-dimensional vectors and Using the formula ${\sin\omega(t+\tau) =\cos\omega t \sin\omega\tau+\sin\omega t \cos\omega\tau}$ we obtain
$$
\begin{equation*}
X_k=\cos(k-1)\omega V_1+\sin(k-1)\omega V_2, \qquad k=1,\dots,P.
\end{equation*}
\notag
$$
Therefore, the rank of the unfolding $X_f$ is $2$ for $\omega\neq 0$, and this unfolding lies in the linear subspace $L_f \in G(n,2)$ with basis $V_1$, $V_2$. Moreover:
In Figures 1 and 2, for the unfolding $X_f$ of the discretization series of the function $f$ we show the projections of $X_f \subset \mathbb{R}^{16}$ onto the two-dimensional planes $L_{i,j}\subset \mathbb{R}^{16}$ spanned by the $i$th ($y$-axis) and $j$th ($x$-axis) principal components of the series $f$ under consideration. The period $T$ of the function $f$, the number of samples $n$ in the viewing window, the discretization step $ \Delta t$, the reference point $t_1$ and the total number of samples $N$ are indicated. Figure 3 contains the following fragments:
The contents of the fragments and all captions in Figure 4 differ from the ones in Figure 3 only by the value $D = 0.05$ of the variance. § 7. Statistical analysis of the monitoring data for atmospheric $\operatorname{CO}_2$The algorithms of the method of unfoldings of time series have found applications to problems in applied statistics (see [1]) in various areas of research. In [2] results obtained in the problem of anthropogenic influence on the climate and estimates of the contribution of the Earth’s vegetation to the formation of atmospheric $\operatorname{CO}_2$ series were described. Figures 5 and 6 present the results of an analysis of the many-year series of atmospheric $\operatorname{CO}_2$ concentrations according to the Barrow Arctic Research Center/Environmental Observatory. In [2] the results of an analysis of the data from other stations of the international network monitoring atmospheric $\operatorname{CO}_2$ were presented. Figure 5 shows the results of an analysis of the time series
$$
\begin{equation*}
f=(f_1,\dots,f_N) \text{ with } n=12,\quad\text{where } f_q= f(t_0+(q-1)\Delta t),
\end{equation*}
\notag
$$
over the interval from 1971 to 1988 with a step of 1 month, that is, $t_0=1971$, $\Delta t= \frac{1}{12}$ and $N=205$. The behaviour of the trend of cycles with periods of one year and six months is described. Figure 5 contains the following fragments:
We denote by $L_{[k]}(f)\subset\mathbb{R}^{n}$ the subspace with a basis formed by the first $k$ principal components of the unfolding of the series $f\in\mathbb{R}^{N}$. As shown in § 5, the $L_{[k]}$-approximation $\widehat f(L_{[k]})$ of $f$ and the series of remainders are well defined.For the series of $\operatorname{CO}_2$ concentrations under discussion, Figure 6 presents the graphs of the series $\widehat f(L_{[k]})$ and $r_f(L_{[k]})$, where: (a) $k=1$; (b) $k=3$; (c) $k=5$. AcknowledgementsThe author expresses his gratitude to G. G. Magaril-Il’yaev for useful discussions of the results in this paper and to Yu. V. Malykhin for some important information concerning recent results in the theory of widths.
Citation in format AMSBIB
\Bibitem{Buc25} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Contact us: |
Terms of Use
|
Registration to the website |
Logotypes |
|