Thao Tran

Thi Phuong

Saeed Ahlame Douzal

Varasteh Yazdi

Paul Honeine

Patrick Gallinari

Kernel methods are known to be e↵ective to analyse complex objects by implicitly embedding them into some feature space. To interpret and analyse the obtained results, it is often required to restore in the input space the results obtained in the feature space, by using pre-image estimation methods. This work proposes a new closed-form pre-image estimation method for time series kernel analytics that consists of two steps. In the first step, a time warp function, driven by distance constraints in the feature space, is defined to embed time series in a metric space where analytics can be performed conveniently. In the second step, the time series pre-image estimation is cast as learning a linear (or a nonlinear) transformation that ensures a local isometry between the time series embedding space and the feature space. The proposed method is compared to the state of the art through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation learning. The extensive experiments conducted on 33 publicly-available datasets show the benefits of the pre-image estimation for time series kernel analytics.

Introduction

Kernel methods [START_REF] Scholkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF] are well known to be e↵ective in dealing with nonlinear machine learning problems in general, and are often required for machine learning tasks on complex data as sequences, time series or graphs. The main idea behind kernel machines is to map the data from the input space to a higher dimension feature space (i.e., kernel space) via a nonlinear map, where the mapped data can be then analysed by linear models. While the mapping from input space to the feature space is of primary importance in kernel methods, the reverse mapping of the obtained results from the feature space back to the input space (called the pre-image problem) is also very useful. Estimating pre-images is important in several contexts for interpretation and analysis purposes. From the beginning, it has been often considered to estimate denoised and compressed results of a kernel Principal Component Analysis (PCA). Other tasks are of great interest, since the pre-image estimation allows, for instance, to obtain the reverse mapping of the centroids of a kernel clustering, and of the atoms as well as of the sparse representations in kernel dictionary learning.

In view of the importance of the pre-image estimation issue and of its benefits in machine learning, several major propositions have been developed. First, in Mika et al. [START_REF] Schölkopf | Kernel pca pattern reconstruction via approximate pre-images[END_REF], the problem is formalised as a nonlinear optimisation problem and, for the particular case of the Gaussian kernel, a fixed-point iterative solution to estimate the reverse mapping is proposed. To avoid numerical instabilities of the latter approach, in Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], the relationship between the distances in feature and input spaces is established for standard kernels, and then used to approximate pre-images by multidimensional scaling. In Bakir et al. [START_REF] Bakır | Learning to find pre-images[END_REF], the pre-image estimation problem is cast as a regression problem between the input and the mapped data, the learned regression model is then used to predict pre-images. Honeine and Richard proposed in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] an approach where the main idea is to estimate, from the mapped data, a coordinate system that ensures an isometry with the input space; this approach has the advantage to provide a closed-form solution, to be independent of the kernel nature and to involve only linear algebra. More recently, task-specific estimation has been studied, such as the resolution of the pre-image problem for nonnegative matrix factorisation in [START_REF] Zhu | Bi-objective nonnegative matrix factorization: Linear versus kernel-based models[END_REF].

All the proposed methods for pre-image estimation are either based on optimisation schema, such as gradient descent or fixed-point iterative solution, or based on ideas borrowed from dimensionality reduction methods. In particular, these methods were developed for Euclidean input spaces, as derivations are straightforward owing to linear algebra (see [START_REF] Honeine | Preimage problem in kernel-based machine learning[END_REF] for a survey on the resolution of the pre-image problems in machine learning). A major challenge arises when dealing with non-Euclidean input spaces, that describe complex data as sequences, time series, manifolds or graphs. Some recent works address that pre-image problem on that challenging data. For instance, in Cloninger et al. [START_REF] Cloninger | The pre-image problem for laplacian eigenmaps utilizing l 1 regularization with applications to data fusion[END_REF] the pre-image problem is addressed for Laplacian Eigenmaps under L 1 regularisation and in Bianchi et al. [START_REF] Bianchi | Learning representations for multivariate time series with missing data using temporal kernelized autoencoders[END_REF] an encoder-decoder is used to learn a latent representation driven by the kernel similarities, where the pre-image estimation is explicitly given by the decoder side.

For temporal data, while kernel machinery has been increasingly investigated with success for time series analytics [START_REF] Do | Multi-modal and multi-scale temporal metric learning for a robust time series nearest neighbors classification[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF][START_REF] Yazdi | Time warp invariant dictionary learning for time series clustering: application to music data stream analysis[END_REF][START_REF] Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF][START_REF] Wu | Random warping series: A random features method for time-series embedding[END_REF][START_REF] Paparrizos | Grail: e cient time-series representation learning[END_REF], the pre-image problem for temporal data remains in its infancy. In addition, time series data, that involve varying delays and/or di↵erent lengths, are naturally lying in a non-Euclidean input space, making the above existing pre-image approaches for static data inapplicable. This work aims to fill this gap, by proposing a preimage estimation approach for time series kernel analytics, that consists of two steps. In the first step, a time warp function, driven by distance constraints in the feature space, is defined to embed time series in a metric space where analytics can be performed conveniently. In the second step, the time series pre-image estimation is cast as learning a linear or a nonlinear transformation that ensures a local isometry between the time series embedding space and the feature space. The relevance of the proposed method is studied through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising under kernel PCA, and 3) time series representation learning and dictionary learning under kernel k-SVD. The benefits of time series that may include varying delays and be of the di↵erent lengths.

The main contributions of this paper are:

1. We propose a time warp function, driven by distance constraints in the feature space, that embeds time series into an Euclidean space 2. We cast the time series pre-image estimation approach as learning a linear or nonlinear transformations in the feature space 3. We propose a closed-form solution for pre-image estimation by preserving a local isometry between the temporal embedded space and the feature space 4. We conduct wide experiments to compare the proposed approach to the major alternative pre-image estimation methods under three crucial tasks:

1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation and dictionary learning.

The reminder of the paper is organised as follows. Section 2 gives a brief introduction to kernel PCA and kernel k-SVD and Section 3 presents the major pre-image estimation methods. In Section 4, we formalise the pre-image estimation problem for time series and develop the proposed solution as well as the corresponding algorithm. We detail the experiments conducted and discuss the obtained results in Section 5.

Kernel PCA and kernel k-SVD

Kernel methods [START_REF] Scholkopf | Learning with kernels: support vector machines, regularization, optimization, and beyond[END_REF] rely on embedding samples x i 2 R d with (x i ) into a feature space H, a Hilbert space of arbitrary large and possibly infinite dimension. The map function needs not to be explicitly defined, since computations conducted in H can be carried out by a kernel function that measures the inner product in that space, namely (x i ,

x i 0 ) = h (x i ), (x i 0 )i for all x i , x i 0 . Given a set of input samples {x i } N i=1 , x i 2 R d , let K be the Gram matrix related to the kernel, namely K ii 0 = (x i , x i 0 ). Let X = [x 1 , ..., x N ] 2 R d⇥N be the description of N input samples x i 2 R d
and, with some abuse of notation, let (X) be the matrix of entries (x 1 ), ..., (x N ).

In the following, we describe two well-known kernel methods, kernel PCA and kernel k-SVD, as nonlinear extensions of the well-known PCA and k-SVD.

While both methods estimate a linear combination for optimal reconstruction of the input samples, the former forces the orthogonality of the atoms that leads to an orthonormal basis, and the latter forces the sparsity while relaxing the orthogonality condition.

Kernel PCA

Kernel PCA extends standard PCA to find principal components that are nonlinearly related to the input variables. For that, the principal components are rather determined in the feature space. For the sake of clarity, we assume for now that we are dealing with centred mapped data, namely

P N i=1 (x i ) = 0.
The covariance matrix in the feature space takes then the form

C = 1 N N X i=1 (x i ) (x i ) T . (1)
Similarly to standard PCA, the objective comes to find the pairs of eigenvalue j 0 and corresponding eigenvector u j 2 H \ 0 that satisfy

j u j = Cu j , (2)
namely for each (x i )

j hu j , (x i )i = hCu j , (x i )i. (3)
As each eigenvector u j lies in the span of (x 1 ), ..., (x N ), there exist coecients ↵ ij , ..., ↵ Nj such that

u j = N X i=1 ↵ ij (x i ). (4)
From Eq. (3) and Eq. ( 4), and by simple developments, the problem in Eq. ( 2)

remains to find the solution of the eigendecomposition problem:

j ↵ j = 1 N K↵ j . (5)
Let 1 ... p be the p highest non-zero eigenvalues of 1 N K and ↵ 1 , ..., ↵ p their corresponding eigenvectors. The principal components in the feature space are then given by computing the projections P j ( (x)) of the sample x onto the eigenvector u j = (X) ↵ j :

P j ( (x)) = hu j , (x)i = N X i=1 ↵ ij h (x i ), (x)i = k x ↵ j (6)
with

k x = [(x 1 , x), ..., (x N , x)]
. By denoting ↵ = [↵ 1 , ..., ↵ p ], the description P ( (x)) of (x) into the subspace of the p first principal components is then

P ( (x)) = (k x ↵) T (7)
Two considerations should be taken. First, the eigenvector expansion coecients ↵ j should be normalised by requiring j h↵ j , ↵ j i = 1. Secondly, as (x i ) are assumed centred, both the Gram matrix K in Eq. ( 5) and k x used in Eq. ( 6) and Eq. ( 7) need to be substituted with their centred counterparts, namely

e K ij = (K 1 N K K1 N + 1 N K1 N ) ij (8) e k x = ⇣ k x 1 N 1 T N K ⌘ (I N 1 N ) (9)
with (1 N ) ij = 1/N for all i, j, I N the identity matrix and 1 N 2 R N the unit vector.

Kernel k-SVD

Sparse coding and dictionary learning become popular methods for a variety of tasks as feature extraction, reconstruction, denoising, compressed sensing and classification [START_REF] Jenatton | Proximal methods for sparse hierarchical dictionary learning[END_REF][START_REF] Balasubramanian | Smooth sparse coding via marginal regression for learning sparse representations[END_REF][START_REF] Bengio | Group sparse coding[END_REF]. k-SVD [START_REF] Aharon | K-svd: An algorithm for designing overcomplete dictionaries for sparse representation[END_REF] is among the most-known and tractable dictionary learning approach to learn a dictionary and to sparse represent the input samples as a linear combination of the dictionary atoms. When dealing with complex data, kernel k-SVD may be required to learn, in the feature space, the dictionary and the sparse representations of the mapped samples as a nonlinear combination of the dictionary atoms [START_REF] Van Nguyen | Kernel dictionary learning[END_REF]. Let us introduce a brief description of kernel k-SVD.

Let D = [d 1 , ..., d L ] 2 R d⇥L be the dictionary composed of L atoms d j 2 R d .
The embedded dictionary (D) = (X)B is defined as a linear representation of (X), since the atoms lie in the subspace spanned by the (X). The kernel dictionary learning problem takes the form min

B,A k (X) (X)B Ak 2 F (10) s.t. ka i k 0  ⌧ 8i = 1, ..., N, (11)
where k.k F is the Frobenius norm 1 , the matrix

B = [ 1 , ..., L ] 2 R N ⇥L
gives the representation of the embedded atoms into the base (X) and A = [a 1 , ..., a N ] 2 R L⇥N gives the sparse representations of (X), with the sparsity level ⌧ imposed by the above constraint.

The kernel k-SVD algorithm iteratively cycles between two stages. In the first stage, the dictionary is assumed fixed with B known and a kernel orthogonal matching pursuit (OMP) technique [START_REF] Pati | Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition[END_REF] is deployed to estimate A. As in standard OMP, given a sample x, we select the first atom that best reconstructs (x); namely we select the j-th atom that maximises

k x a T x B T K j . (12)
The sparse codes are then updated by the projections onto the subspace of the yet selected atoms

a x = B T ⌦ KB ⌦ 1 (k x B ⌦ ) T , (13)
where B T ⌦ is the submatrix of B limited to the yet selected atoms. The procedure is reiterate until the selection of ⌧ atoms.

Once the sparse codes A of the N samples estimated, the second stage of the kernel k-SVD is performed to update both B and A. For that, the reconstruction

1 kM k F = q P p i=1 P q j=1 (m ij ) 2 is the Frobenius norm of the matrix M 2 R p⇥q of general term m ij error is defined as min B,A k (X) (X) L X j=1 j a j. k 2 F , (14)
with a j. 2 R N referencing the j-th row of A, namely min

B,A k (X)E k (X) k a k. k 2 F , (15)
with E k = I N P j6 =k j a j. the error of reconstruction matrix when removing the k-th atom. An eigendecomposition is then performed to get

(E R k ) T K(E R k ) = V ⌃V T , (16)
where E R k is the error of reconstruction restricted to the samples that have involved the k-th atom. The sparse codes k and a R k. are updated by using the

first eigenvector v 1 with a R k. = 1 v T 1 and k = 1 1 E R k v 1 . (17)

Related works on pre-image estimation

From the representer theorem [START_REF] Schlegel | When is there a representer theorem[END_REF] any result ' 2 H obtained by some kernel method may be expressed in the form ' = P N i=1 i (x i ); that is as a linear combination of the mapped training samples { (x i )} N i=1 . In general, finding the exact pre-image x such that (x) = ' is an ill-posed problem, that is often addressed by providing an approximate solution, namely by estimating x ⇤ such that (x ⇤ ) ⇡ '. In the following, we describe three major methods to estimate the pre-image x ⇤ of a given ' 2 H.

Pre-image estimation under distance constraints

The main idea proposed in Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] is to use the distances between ' and (x i ) and their relation to the distances between the pre-image x ⇤ and x i . The main steps of the proposed approach are:

1. Let e d 2 (', (x i )) = h', 'i 2h', (x i )i+h (x i ), (x i )i be the square dis-
tance between ' and any (x i ). In practice, only neighbouring elements are considered. Let ( ẋ1 ), ... ( ẋn ) denote the n-th closest elements to '.

2. For an isotropic kernel2 , the relation

d 2 (x i , x j ) = g( e d 2 ( (x i ), (x j )
)) between the distances in the input and the feature spaces can be established.

3.

A solution is then deployed to determine the pre-image x ⇤ such that

[d 2 (x ⇤ , ẋ1 ), . . . , d 2 (x ⇤ , ẋn )] = ⇥ g( e d 2 (', ( ẋ1 ))), ..., g( e d 2 (', ( ẋn ))) ⇤ . (18)
For that, an SVD is deployed on the centred version of the submatrix

X n = [ ẋ1 , ..., ẋn ], namely X n (I n 1 n ) = U ⇤V T , (19)
where U = [u 1 , . . . , u q ] is the d ⇥ q matrix of the left-singular vectors.

Let Z = [z 1 , . . . , z n ] = ⇤V T be the q ⇥ n matrix giving the projections of ẋi on the u j 's orthonormal vectors. The pre-image estimation x ⇤ is then obtained as:

x ⇤ = U z ⇤ + 1 n X n 1 n , (20)
where z ⇤ , the projection of x ⇤ on the [u 1 , ..., u q ] coordinate system, is

z ⇤ = 1 2 (Z Z T ) 1 Z (d 2 d 2 0 ), (21)
with

d 2 0 = [kz 1 k 2 , ..., kz n k 2 ] T , d 2 = [d 2 1 , . . . , d 2 n ] T and d 2 i = g( e d 2 (', ( ẋi ))).

Pre-image estimation by isometry preserving

To learn the pre-image x ⇤ of a given ' = P N i=1 i (x i ), the proposed approach in [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] proceeds in two steps. First, a coordinate system, spanned by the feature vectors { (x i )} N i=1 is learned to ensure an isometry with the input space; subsequently, the coordinate system is used to estimate the pre-image x ⇤ of '. These two main steps are summarised in the followings:

1. Let = { 1 , ..., p } (p  N ) be a coordinate system in the feature space, with k = (X)↵ k . The projection of (X) onto the coordinate system is P ( (X)) = (KA) T , where A = [↵ 1 , ..., ↵ p ]. To estimate the coordinate system that is isometric with the input space, the following optimisation problem is solved arg min

A kX T X KAA T Kk 2 F + kKAk 2 F , (22)
where the second term controls through the regularisation parameter the smoothness of the solution. The solution of this problem satisfies

AA T = K 1 (X T X K 1 )K 1 .
2. Based on this result, the pre-image estimation x ⇤ takes the form

x ⇤ = arg min x kX T x (X T X K 1 ) k 2 F ( 23
)
with = ( 1 , ..., N ) T . This problem defines a standard overdetermined equation system (N d) that can be resolved as a least-square minimisation problem (i.e., any technique such as the pseudo-inverse or the eigendecomposition). The pre-image estimation is then:

x ⇤ = (XX T ) 1 X(X T X K 1 ) . (24)

Pre-image estimation by kernel regression

In Bakir et al. [START_REF] Bakır | Learning to find pre-images[END_REF], the pre-image estimation consists in learning a kernel regression function that maps all the (x i ) in the feature space H (related to the kernel ) to x i in the input space R d . For that, first a kernel PCA is deployed to embed (X) into the subspace spanned by the eigenvectors u 1 , ..., u p defined in ( 4), with u j = (X)↵ j . Then, a kernel regression is learned from the set of the projections onto the kernel PCA subspace and X as arg min

B kX B b Kk 2 F + kBk 2 F , (25)
where B 2 R d⇥N is the regression coe cient matrix and b K is the Gram matrix

with entries b K ij = b (P ( (x i )), P ( (x j ))
). The solution to the problem ( 25) is then

B = X b K( b K 2 + I N ) 1 (26)
For a given result ' = (X) 2 H, its pre-image x ⇤ is then estimated as:

x ⇤ = B b k T P (') , (27) with b
k P (') = [b (P ('), P ( (x 1 ))), ..., b (P ('), P ( (x N )))], (28)
where b (P ('), P ( (

x i ))) = b (↵ T K , ↵ T k T xi ) and ↵ = [↵ 1 , ..., ↵ p ].

Overview

To sum up, the three major methods presented above define three di↵erent approaches for pre-image estimation problem. First of all, all the methods involve only linear algebra and propose solutions that don't su↵er from numerical instabilities. In Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF], the solution is mainly requiring the definition of a relation between the distances into the input and the kernel feature spaces.

That requirement limite the Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] approach to linear or isotropic kernels. Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] alleviate that point by proposing a closed-form solution that is applicable to any type of kernels. Furthermore, while in Honeine et al. [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] the pre-image estimation is obtained by learning a linear transformation into the feature space that preserves the isometry between the input and the feature space, in Bakir et al. [START_REF] Bakır | Learning to find pre-images[END_REF], the pre-image estimation is obtained by using a non linear kernel regression that predicts the input samples from their images into the feature space. Finally, while both [START_REF] Honeine | A closed-form solution for the pre-image problem in kernel-based machines[END_REF] and [START_REF] Bakır | Learning to find pre-images[END_REF] proposals involve the whole training samples for pre-image estimation, Kwok et al. [START_REF] Kwok | The pre-image problem in kernel methods[END_REF] uses only the samples on the neighborhood of ', which o↵ers a significant speed-up; highly valuable in the case of large scale data.

Proposed pre-image estimation for time series kernel analytics

Let {x i } N i=1 be a set of N time series, where each x i 2 R d⇥ti is a multivariate time series of length t i that may involve varying delays. Let (x i ) be the -mapping of the time series x i into the Hilbert space H related to a temporal kernel  that involves dynamic time alignments such as dtak [START_REF] Shimodaira | Dynamic time-alignment kernel in support vector machine[END_REF],

kdtw [START_REF] Bahlmann | Online handwriting recognition with support vector machines-a kernel approach[END_REF] and kga [START_REF] Cuturi | A kernel for time series based on global alignments[END_REF]. Let K be a the corresponding Gram matrix, with

entries K ii 0 = (x i , x i 0 ). Given ' = P N i=1 i (x i ) a result generated in H,
the objective is to estimate the time series x ⇤ 2 R d⇥t ⇤ that is the pre-image of '. This problem is particularly challenging since, under varying delays, the time series are not longer lying in a metric space, which makes inapplicable the related work on pre-image estimation.

We tackle this problem in two parts. In the first part, we formalise the pre-image estimation problem as the estimation of a linear transformation in the feature space, that ensures an isometry between the input and the feature spaces. Moreover, this result is extended to the estimation of a nonlinear transformation in the feature space, shown powerful on challenging data in Section 5. Subsequently, we propose a local time-warp mapping function to embed time series into a vector space where the pre-image estimation can be estimated conveniently.

Learning linear and nonlinear transformations for pre-image estimation

Let X = [x 1 , ..., x N ] 2 R t⇥N be a matrix giving the description of N univariate3 time series x i that we assume first lying in the metric space R t ; Section 4.2 addresses the general case of time series that are lying into nonEuclidean space.

The proposed pre-image method relies on learning a linear transformation R in the feature space that ensures an isometry between X and (X). We first describe the method as a linear transformation, and then extend it to nonlinear transformations.

Linear transformation

The main idea to solve the pre-image problem is the isometry preserving, in the same spirit as the method described in Section 3.2. For this purpose, we formalise the pre-image problem as the estimation of the square matrix R that establishes an isometry between X and (X), by solving the optimisation problem

R ⇤ = arg min R kX T X (X) T R (X)k 2 F . (29)
By using a kernel PCA where a relevant subspace is considered, an explicit description P ( (X)) 2 R p⇥N of (X) is given and Eq. ( 29) can thus be rewritten as:

R ⇤ = arg min R kX T X P ( (X)) T R P ( (X))k 2 F . (30)
As P ( (X)) P ( (X)) T is invertible, a closed-form solution is given by:

R ⇤ = P ( (X))P ( (X)) T 1 P ( (X))X T XP ( (X)) T P ( (X))P ( (X)) T 1 . (31)
The estimation of the time series x ⇤ , as the pre-image of ' = (X) , is then given by:

x ⇤ = (XX T ) 1 X P ( (X)) T R ⇤ P (') = (XX T ) 1 X P ( (X)) T R ⇤ ↵ T K , (32)
with P (') = ↵ T K and ↵ defined in Eq. ( 7).

One can easily include some regularisation terms in the optimisation problems ( 29) and ( 30), which can be easily propagated to the pre-image expression.

For example, in the case of non-invertible XX T , a regularisation term is introduced in Eq. ( 32) as:

x ⇤ = (XX T + I t ) 1 X P ( (X)) T R ⇤ ↵ T K , (33)
for some positive regularisation parameter .

Nonlinear transformation

In The pre-image estimation problem can be then defined as learning a nonlinear transformation that defines an isometry between X and b ( (X)) as:

R ⇤ = arg min R kX T X b ( (X)) T R b ( (X))k 2 F . (34)
Similarly, a closed-form solution for R ⇤ can be obtained as:

R ⇤ = (P ( b ( (X))) P ( b ( (X))) T ) 1 P ( b ( (X))) (35) X T XP ( b ( (X))) T (P ( b ( (X)))P ( b ( (X))) T ) 1 ,
and

P ( b ( (X))) = b ↵ T b K. ( 36
)
To estimate b K, an indirect manner is to use a kernel PCA, with b ( (x i ), (x j )) ⇡ b (P ( (x i )), P ( (x j ))). A simpler way is possible when dealing with kernels that are radial basis functions. For example, for the well-known Gaussian ker-

nel b , b K is estimated directly from K as: b ( (x i ), (x j )) = exp k (x i ) (x j ) k 2 2 2 ! = exp ✓ h (x i ), (x i )i 2h (x i ), (x j )i + h (x j ), (x j )i 2 2 ◆ = exp ✓ (x i , x i ) 2(x i , x j ) + (x j , x j ) 2 2 ◆ ( 37
)
The estimation of the pre-image of ' = P N i=1 i (x i ) is then given by the time series x ⇤ :

x ⇤ = (XX T ) 1 X P ( b ( (X))) T R ⇤ P ( b (')), (38)
with

P ( b (')) = ( b k ' b ↵) T , where b k ' is the vector whose i-th entry is b (', (x i )) = exp T K 2 T k T xi + K ii 2 2 ! . (39)
The above proposed formulations and results for pre-image estimation (Section 4.1) present some similarities and di↵erences with the method proposed in [START_REF] Honeine | Preimage problem in kernel-based machine learning[END_REF] and presented in Section 3.2. First of all, both approaches propose formulations and solutions that only require linear algebra and are independent of the type of kernel. To establish the isometry, in [START_REF] Honeine | Preimage problem in kernel-based machine learning[END_REF] a linear transformation restricted to the form R = (X)AA T (X) T is estimated, whereas in our proposal the estimated R may be linear Eq. [START_REF] Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF] or non linear Eq.( 34) and is importantly unconstrained, namely of general form which enlarges its potential to deal with complex structures. Finally, while in [START_REF] Honeine | Preimage problem in kernel-based machine learning[END_REF] the solution Eq.( 24) involves the kernel information through the regularisation term, which may be canceled for lower values of , in the proposed solutions Eq.(33) and Eq.(38) the kernel information is entirely considered regardless of the regularisation specifications.

Learning a metric space embedding for time series pre-image estimation

In Section 4.1, time series are assumed of the same length and lying in a metric space. However, in general X = {x i } N i=1 is instead composed of time series

x i of di↵erent lengths t i that are located in a non-metric space, rendering the previous results as well as the pre-image estimation related works not applicable.

To address the pre-image estimation for such challenging time series, we define an embedding function that allows to represent the time series in a metric space, where the previous linear and nonlinear transformations method for preimage estimation can be performed conveniently.

For this purpose, first we define N ' in H and N 1 ' as the set of the n-closest neighbours of ' and its pre-image, given as:

N' = n (xi) h (xi), 'i = N X j=1 j (xi, xj) is among the n highest values o , (40)
N 1 ' = xi (xi) 2 N' (41)
Let (xr) be the representative of N' with xr 2 R t ⇤ defined as:

(xr) = arg max

(x i )2N' X (x j )2N' (xi, xj). ( 42
)
To resorb the arising delays, a temporal alignment between each x i and x r is then performed by dynamic programming. An alignment ⇡ of length |⇡| = m between x i and x r is defined as the set of m increasing couples

⇡ = ((⇡1(1), ⇡2(1)), (⇡1(2), ⇡2(2)), ..., (⇡1(m), ⇡2(m))),
where the applications ⇡ 1 and ⇡ 2 defined from {1, ..., m} to {1, ..., t i } and {1, ..., t ⇤ } respectively obey to the following boundary and monotonicity conditions:

1 = ⇡1(1)  ⇡1(2)  ...  ⇡1(m) = ti 1 = ⇡2(1)  ⇡2(2)  ...  ⇡2(m) = t ⇤
and 8 l 2 {1, ..., m}, ⇡1(l + 1)  ⇡1(l) + 1 and ⇡2(l + 1)  ⇡2(l) + 1, (⇡1(l + 1)

⇡1(l)) + (⇡2(l + 1) ⇡2(l)) 1.
Intuitively, an alignment ⇡ between x i and x r describes a way to associate each element of x i to one or more elements of x r and vice-versa. Such an alignment can be conveniently represented by a path in the t i ⇥ t ⇤ grid, as shown in Figure 1 (left), where the above monotonicity conditions ensure that the path is neither going back nor jumping. The optimal alignment ⇡ ⇤ between

x i and x r is then obtained as:

⇡ ⇤ = arg min ⇡=(⇡ 1 ,⇡ 2 ) kx ⇡ 1 i x ⇡ 2 r k 2 (43)
where x ⇡1 i = (x i ⇡1(1) , ..., x i ⇡1(m) ) and x ⇡2 r = (x r ⇡2(1) , ..., x r ⇡2(m) ) are x i and

x r aligned through ⇡.

We define f r , the temporal embedding function, to embed time series x i 2 R d⇥ti into a new temporal metric space as:

f r : X ! e X ⇢ e I = R d⇥t ⇤ x i ! f r (x i ) = x i W ir N ir ( 44
)
where W ir 2 {0, 1} ti⇥t ⇤ is the binary matrix related to the optimal temporal alignment between x i and x r , as shown in Figure 1 (right). The matrix

x "# W "% = ⎝ ⎜ ⎛ 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1⎠ ⎟ ⎞

x "/

x "0

x %# x %/ 1 2 1 3 x "4

x "5

x %4 x %5 x %0 x %6 Figure 1: In the left, the temporal alignment between x i (t i = 5) and xr (t ⇤ = 6), the optimal alignment ⇡ ⇤ is indicated in green. In the right, the adjacency binary matrix related to the optimal temporal alignment.

N ir = diag(W T ir 1 ti ) 1 is the weight diagonal matrix of order t ⇤ , of general term 1 |Nt| , that gives the weight of the element t of x r , where |N t | is the number of time stamps of x i aligned to t. In particular, note that x r remains unchanged by f r , as

W rr = N rr = diag([1, 1, . . . , 1]).
The set of embedded time series e X = {f r (x 1 ), ..., f r (x N )} is for now lying in a metric space e I, where the delays are resorbed w.r.t. the representative time series x r . The pre-image solution provided in the method described in Section 4.1 can be developed to establish a linear or nonlinear transformations to preserve an isometry between e X and (X). The algorithm for the proposed solution TsPrima is summarised in Algorithm 1.

Algorithm 1 TsPrima: Pre-image estimation for time series 1: Input:

{x i } N i=1 with x i 2 R d⇥ti ,  (a temporal kernel), b  (a Gaussian kernel), 2:
(with ' = P N i=1 i (x i )), n (the neighbourhood size) 3: Output: x ⇤ the pre-image estimation of ' 4:

5: Define N ' , N 1 ' and x r using respectively (40), ( 41) and (42)

6: Embed N 1
' into a temporal metric space by using Eq. ( 44), set e

N 1 ' = f r (N 1 ' ) 7: Set X = e N 1
' and (X) = N ' 8: Learn a linear (resp. nonlinear) transformation R by using Eq. (31) (resp.

Eq. ( 35)) 9: Estimate the pre-image x ⇤ based on a linear (resp. nonlinear) transformation using Eq. (33) (resp. Eq. (38))

Experiments

In this section, we evaluate the e ciency of the proposed pre-image estimation method under three major time series analysis tasks: the order set out in [START_REF] Chen | The ucr time series classification archive URL[END_REF]. The 25 obtained datasets are composed of univariate time series and half of the datasets include significant delays. We consider a dataset as including significant delays if the di↵erence between the 1-NN Euclidean distance error and the 1-NN Dynamic time warping [START_REF] Sakoe | Dynamic programming algorithm optimization for spoken word recognition[END_REF] error is greater than 5%. The 5 next datasets include univariate and multivariate time series covering local and noisy salient events as described in [START_REF] Yazdi | Time warp invariant ksvd: Sparse coding and dictionary learning for time series under time warp[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF][START_REF] Frambourg | Learning multiple temporal matching for time series classification[END_REF] and the three last datasets are related to handwritten digits and characters, they are described as multivariate time series of variable lengths [START_REF] Chen | 6dmg: A new 6d motion gesture database[END_REF]. In the following, we detail the evaluation process of the pre-image estimation methods then give and discuss the obtained results.

Time series averaging

Estimating the centroid of a set of time series is a major topic for many time series analytics as summarisation, prototype extraction or clustering. Time series averaging has been an active area in the last decade, where the propositions mainly focus on tackling the tricky problem of multiple temporal alignments [START_REF] Frambourg | Learning multiple temporal matching for time series classification[END_REF][START_REF] Soheily-Khah | Progressive and iterative approaches for time series averaging[END_REF][START_REF] Soheily-Khah | Generalized k-means-based clustering for temporal data under weighted and kernel time warp[END_REF]. A suitable way to circumvent the problem of multiple temporal alignments is to use a temporal kernel method to evaluate the time series centroid in the feature space. The pre-image of the centroid is then estimated to obtain the time series averaging in the input space.

In that context, let {x i } N i=1 and { (x i )} N i=1 be, respectively, a set of time series and their mapped images into the Hilbert space H related to the temporal kernel dtak [START_REF] Shimodaira | Dynamic time-alignment kernel in support vector machine[END_REF]. Let ' = 1 N P N i=1 (x i ) be the centroid of the mapped time series in the feature space and x ⇤ its pre-image in the input space. The quality of the obtained centroids is given by the within-class similarity P i dtak(x ⇤ , x i ); the higher the within-class similarity, the better is the estimated centroid.

To evaluate the e ciency of each pre-image estimation method, the time series centroid is estimated for each class of the studied datasets and the induced

Time series reconstruction and denoising

The reconstruction and denoising tasks represent a standard application context for pre-image estimation. For the time series reconstruction task, a kernel 3 2 1

1.5 TsPrima PCA is performed on the training set, the reconstruction of a given test sample

x is then defined as the pre-image x ⇤ of its kernel PCA projection P ( (x)).

The latter takes the form ' = (X) , with defined as:

= (I N 1 N ) ↵ ↵ T e k T x + 1 N 1 N (45)
The quality of the reconstruction is then measured as the similarity dtak(x ⇤ , x)

between each test sample x and its reconstruction x ⇤ ; the higher the criterion, the better is the reconstruction. Table 3 gives the average quality of reconstruction obtained for each dataset and each method. Figure 4 gives the critical di↵erence diagram related to the Nemenyi test for the average ranking comparison of the studied methods. Figure 5 shows the reconstructions obtained for some challenging time series of digits, lower and upper datasets.

For the time series denoising task, first a kernel PCA is performed on the training set, then a (0, 2 ) Gaussian noise is added to the test samples x to generate noisy samples x with di↵erent variances 2 . The denoised sample is obtained as the pre-image x ⇤ of its kernel PCA projection P ( (x)), with defined as in Eq. (45). Similarly, the quality of the denoising is measured as the similarity dtak(x ⇤ , x) between x ⇤ and the initial x. Table 4 gives, for di↵erent values of 2 , the average quality of the denoising for some datasets. Figure 6 illustrates the denoising results for some challenging times series of the noisy spiral2 data and of the class "M" of upper dataset. For time series representation learning, the kernel k-SVD (⌧ = 5) is used to learn, for each class of the considered datasets, the dictionary (X)B and the sparse representations A = [a 1 , ..., a N ] of its membership time series, as defined in Section 2.2. The pre-images D ⇤ and X ⇤ of the dictionary (X)B and of the sparse codes A are then obtained by considering = B and = BA, respectively. The quality of the learned sparse representations is then measured as the similarity dtak(x i , x ⇤ i ) between each time series x i and the pre-image

x ⇤ i of the sparse representation (X)B a i . Table 5 gives the average quality of the learned representations for each dataset and each pre-image estimation method. Figure 7 gives the critical di↵erence diagram related to the Nemenyi test for the average ranking comparison of the studied methods. Figure 8 shows the learned representations for some time series of digits, lower and upper datasets and Figure 9 illustrates, for a challenging sample of the class "k" of lower dataset, the learned representations as well as the top 3 atoms involved in its reconstruction. the defined temporal embedding function f r (Section 4.2) and 2) the proposed transformation R to preserve an isometry between the time series embedding space and the feature space (Section 4.1). In this last part, the aim is to evaluate the e ciency of the proposed transformation R, regardless of the e↵ect of f r .

For that, TsPrima is compared to the alternative methods Honeine, Kwok and Bakir once all the time series embedded into the same metric space; namely, all the pre-image estimation methods are performed between the time series embedding space and the feature space. Similar experiments are performed on the 33 public datasets (Table 1), the results obtained for the three tasks are summarised into Table 6 and the related Nemenyi tests are given in Figure 10.

Overall analysis

The experiments conducted in Sections 5.1 to 5.3 show that the proposed method TsPrima leads on almost all the datasets and through the three studied tasks to the best results. On the other hand, the performances obtained by the alternative methods seem slightly equivalent and lower than those obtained by TsPrima.

In particular, for time series averaging task, we can see in Table 2 For time series reconstruction, Table 3 shows that TsPrima leads to the highest reconstruction accuracies through almost all the datasets, followed by Honeine, Bakir and Kwok methods. Figure 4 indicates that there is no significant di↵erence between the performances of the three state of the art methods (connected by a solid bold line). These results are assessed in Figure 5 that shows, for some input time series, the quality of the reconstructions obtained by TsPrima and the state of the art methods.

For the time series denoising task, we observe from Table 4 and for all the methods that the quality of the denoising decreases when the intensity of noise increases. This result is illustrated in Figure 6, that shows the denoising results of the time series "M" of upper dataset and of the highly noisy time series of spiral2 dataset. In particular, note that that Kwok and TsPrima methods lead to the best results on spiral2 data and seem less sensitive to noise than Honeine and Bakir methods.

Lastly, for time series representation learning task, Table 5 indicates that each studied method leads to the best sparse representations for at least some We can see that while the first atom learned by TsPrima is nearly su cient to sparse represent the "k" input sample, the state of the art methods need obviously more that one atom to sparse represent the input sample. Finally, the analysis of Figure 7 indicates that Honeine method performs equivalently than Kwok and Bakir, whereas the Kwok performances are significantly better that those of Bakir method.

Further comparisons (Table 6) are conducted in Section 5.4 to evaluate the e ciency of TsPrima related to the learned transformation R, regardless of the temporal embedding f r . For averaging task, TsPrima, Honeine and Bakir lead equivalently to the best performances, followed by Kwok method (Figure 10 (a)). From these results we can conjecture that, linear transformations seem su cient to achieve good pre-image estimations for averaging task on these datasets, as both linear and non linear approaches (TsPrima, Honeine, Bakir) perform equivalently. Furthermore, while Honeine and Bakir involve the whole datasets for the centroid pre-image estimations, Kwok uses a subset of samples into the neighbourhood of ', which may explain the slightly lower performances of Kwok method. Note that, although TsPrima involves, similarly to Kwok method, fewer samples into the neighbourhood of ', it succeeds to reach the best performances thanks to the e ciency of the learned transformation R. Finally, as all the studied methods propose closed-form solutions, they lead to comparable complexities. However, for large data, TsPrima and Kwok methods are expected to perform faster as requiring fewer samples on the neighborhood of ' than Honeine and Bakir that involve the whole samples for pre-image estimation. Note that the complexity of the proposed solutions is mainly related to the matrix inversion operator. In Kwok method, the inversion of ZZ T required in Eq. ( 21), with Z of dimension (q ⇥ n) and n is the neighbourhood size, induces a complexity of O(q 2 n) + O(q 3 ); as q is in general small and fixed beforehand, the overall complexity is about O(n). For Honeine method, Eq. For the time series embedding part, the complexity is mainly related to the time warping function which is of order O(d 2 n). As d is in general higher that the neighbourhood size n, the overall complexity for TSPrima is about O(d 3 ).

To sum up, as the neighbourhood size n << N and d << N (for not extra large time series), the complexity induced by both Kwok and TSPrima remains lower that the one of Honeine and Bakir. Note that, the Honeine method can be developed to consider only the neighbourhoods instead of all samples.

Conclusion

This work proposes TsPrima, a new closed-form pre-image estimation method for time series analytics under kernel machinery. The method consists of two stages. In the first step, we define a time warp embedding function, driven by distance constraints in the feature space, that allows to embed the time series in a metric space. In the second step, the time series pre-image estimation is cast as learning a linear (or a nonlinear) transformation to ensure a local isometry between the time series embedding space and the feature space. Extensive experiments show the e ciency and the benefits of TsPrima through three major tasks that require pre-image estimation: 1) time series averaging, 2) time series reconstruction and denoising and 3) time series representation and dictionary learning. Future work will focus on using pre-image estimation methods to enhance the interpretability and the computation of deep learning tasks for time series, sequence and graph analytics.

  the following, we propose to extend the above result to learn nonlinear transformations for pre-image estimation. Let b  be a kernel defined on the feature space H, and b the corresponding embedding function that maps any element of H into the Hilbert space defined by b . With some abuse of notation, we denote b ( (X)) the matrix of all mapped elements b ( (x i )), for i = 1, ..., N. Let b K be the Gram matrix of general term b ( (x i ), (x j )).

416 test [ 12 ]

 12 is performed to compare the significance of the obtained results, with 417 the related critical di↵erence diagram given in Figure2. The estimated time 418 series centroids for some challenging classes are shown in Figure3, where we 419 retain particularly spiral1 and the handwritten digits and characters datasets 420 (digits, lower and upper) as they are more intuitive to visually evaluate the quality of the estimated time series centroids.

Figure 3 :

 3 Figure 3: Time series centroids for some challenging classes of digits, lower, upper and spiral1 datasets

Figure 4 :Figure 5 :

 45 Figure 4: Nemenyi test: comparison of pre-image methods under kernel PCA reconstruction

Figure 7 :

 7 Figure 7: Nemenyi test: comparison of pre-image methods under kernel k-SVD representation learning

Figure 8 :Figure 9 :

 89 Figure 8: The learned time series representations under kernel k-SVD of some samples of digits, lower, upper datasets

Figure 10 :

 10 Figure 10: Nemenyi Tests.

  that the centroids estimated by TsPrima lead to the highest within-class similarity on almost all the datasets; namely, each centroid obtained by TsPrima is in general the closest to the set of time series it represents. The analysis of the critical di↵erence diagram given in Figure2indicates that the next best results are obtained respectively by Bakir, Honeine and Kwok methods. In addition, as the state of the art methods are connected by a solid bold line, their performances remain equivalent. From Figure3, we can see that while all the methods succeed to restitute the centroids of some input classes (shown on the left column) as the class "6" of digits and "S" of upper dataset, only TsPrima succeeds to estimate the centroids of the most challenging classes, as the "k" class of lower dataset and spiral1.

datatsets and that

  TsPrima performs better on almost all the datasets. Figure 8 shows the goodness of the sparse representations obtained. While all the methods succeed to sparse represent some input time series, the time series of "k" and "B" classes appear challenging for Honeine and Bakir methods. In Figure 9, we get a look on the quality of the learned atoms, that are involved into the reconstruction of the input samples. The first row gives for some input sample "k" (on the left), the sparse representations learned by each method. The three next rows, provide the three first atoms involved into the reconstructions.

For the remaining tasks

  reconstruction, denoising and representation learning, TsPrima achieves the highest performances, followed by far by Honeine, Kwok and Bakir (Figure 10 (b), (c) and (d)), which assesses the crucial contribution of the learned transformations R of TsPrima. Lastly, of particular note is that Honeine and Bakir that involve the whole training samples induce much computations, specifically for the time series embedding process, than Kwok and TsPrima that require fewer samples into the neighbourhood of '.

( 24 )

 24 requires two inversions of XX T and K, which induces, respectively, a complexity of O(d 2 N ) + O(d 3 ) and O(N 3 ), that leads to an overall complexity of O(N 3 ). For Bakir method, Eq. (26), requires the inversion of the Gram matrix, which leads to a complexity of O(N 3 ). For TsPrima, Eq. (32) involves the inversion of XX T , with X is of dimension (d ⇥ n), d is the time series length and n is the neighbourhood size. The induced complexity is of O(d 2 n) + O(d 3 ).

Table 1 :

 1 Data Description

	Dataset	Nb. Classes	Train	Test	Time series	Univariate
			size	size	length
	CC GunPoint CBF OSULeaf SwedishLeaf Trace FaceFour Lighting2 Lighting7 ECG200 Adiac FISH Beef Co↵ee OliveOil DiatomSizeR ECG5Days FacesUCR ItalyPowerD MedicalImages MoteStrain SonyAIBOII SonyAIBO Symbols TwoLeadECG	6 2 3 6 15 4 4 2 7 2 37 7 5 2 4 4 2 14 2 10 2 2 2 6 2	300 50 30 200 500 100 24 60 70 100 390 175 30 28 30 16 23 200 67 381 20 27 20 25 23	300 150 900 242 625 100 88 61 73 100 391 175 30 28 30 306 861 2050 1029 760 1252 953 601 995 1139	60 150 128 427 128 275 350 637 319 96 176 463 470 286 570 345 136 131 24 99 84 65 70 398 82	X X X X X X X X X X X X X X X X X X X X X X X X X
	spiral1	1	50	50	101	7
	spiral2	1	50	50	300	7
	PowerCons BME UMD	2 3 3	73 30 36	292 150 144	144 128 150	X X X
	digits	10	100	100	29⇠218	7
	lower	26	130	260	27⇠163	7
	upper	26	130	260	27⇠412	7
	within-class similarity is evaluated. The average within-class similarity is then

414

reported in Table

2

for each dataset and each pre-image estimation method; the 415 best values are indicated in bold (t-test at 5% risk). In addition, a Nemenyi

Table 2 :

 2 Average within-class similarity of the estimated time series centroids

	DataSet	TsPrima Honeine Kwok Bakir
	CC	0.744	0.709	0.721 0.709
	GunPoint	0.902	0.910 0.882 0.886
	CBF	0.798	0.737	0.755 0.737
	OSULeaf	0.985	0.987 0.986 0.987
	SwedishLeaf	0.910	0.920 0.920 0.920
	Trace	0.998	0.992	0.991 0.992
	FaceFour	0.981	0.980 0.981 0.98
	Lighting2	0.918	0.876	0.859 0.875
	Lighting7	0.964	0.930	0.930 0.931
	ECG200	0.593	0.565	0.567 0.566
	Adiac	0.997	0.997 0.996 0.997
	FISH	0.996	0.995	0.994 0.995
	Beef	0.900	0.892	0.898 0.890
	Co↵ee	0.998	0.998 0.998 0.998
	OliveOil	0.999	0.999 0.998 0.999
	DiatomSizeR	0.997	0.997 0.997 0.997
	ECG5Days	0.777	0.746	0.417 0.746
	FacesUCR	0.721	0.699	0.648 0.700
	ItalyPowerD	0.610	0.552	0.420 0.542
	MedicalImages 0.671	0.644	0.637 0.646
	MoteStrain	0.776	0.777 0.701 0.777
	SonyAIBOII	0.749	0.740	0.716 0.740
	SonyAIBO	0.960	0.962 0.955 0.962
	Symbols	0.959	0.949	0.904 0.951
	TwoLeadECG	0.980	0.977	0.911 0.977
	spiral1	0.831	0.823	0.799 0.824
	spiral2	0.947	0.940	0.934 0.940
	PowerCons	0.458	0.328	0.436 0.330
	BME	0.701	0.572	0.638 0.555
	UMD	0.800	0.765	0.724 0.755
	digits	0.746	0.575	0.657 0.581
	lower	0.713	0.544	0.645 0.545
	upper	0.764	0.572	0.570 0.573
	Nb. Best	28	9	4	8
	Avg. Rank	1.5	2.68	3.24	2.58

Table 3 :

 3 Quality of the time series reconstruction under kernel PCA

	DataSet	TsPrima Honeine Kwok Bakir
	CC	0.798	0.747	0.758 0.747
	GunPoint	0.994	0.996	0.992 0.990
	CBF	0.916	0.854	0.896 0.875
	OSULeaf	0.997	0.998	0.995 0.998
	SwedishLeaf	0.798	0.701	0.690 0.650
	Trace	0.689	0.519	0.597 0.519
	FaceFour	0.981	0.951	0.967 0.964
	Lighting2	0.993	0.967	0.984 0.975
	Lighting7	0.954	0.920	0.938 0.922
	ECG200	0.965	0.979	0.959 0.962
	Adiac	0.194	0.127	0.139 0.125
	FISH	0.779	0.580	0.586 0.579
	Beef	0.528	0.703	0.643 0.704
	Co↵ee	0.584	0.595	0.570 0.559
	OliveOil	0.150	0.125	0.141 0.121
	DiatomSizeR	0.330	0.174	0.186 0.173
	ECG5Days	0.996	0.996	0.995 0.995
	FacesUCR	0.939	0.825	0.878 0.847
	ItalyPowerD	0.831	0.892	0.023 0.851
	MedicalImages	0.946	0.906	0.935 0.928
	MoteStrain	0.971	0.987	0.970 0.979
	SonyAIBOII	0.978	0.989	0.969 0.985
	SonyAIBO	0.939	0.98	0.924 0.967
	Symbols	0.885	0.822	0.724 0.761
	TwoLeadECG	0.825	0.630	0.444 0.669
	spiral1	0.961	0.939	0.933 0.911
	spiral2	0.966	0.939	0.946 0.940
	PowerCons	0.971	0.966	0.955 0.977
	BME	0.896	0.800	0.858 0.666
	UMD	0.885	0.855	0.904 0.797
	digits	0.840	0.721	0.798 0.726
	lower	0.787	0.696	0.747 0.685
	upper	0.856	0.678	0.787 0.687
	Nb. Best	22	9	1	3
	Avg. Rank	1.56	2.67	2.71	3.06

Table 4 :

 4 Quality of the denoising for several noise levels

	DataSet	2	TsPrima	Honeine	Kwok	Bakir
	digits	0.01	0.832	0.669	0.782	0.666
		0.05	0.808	0.619	0.742	0.627
		0.1	0.791	0.605	0.723	0.612
		0.15	0.783	0.598	0.719	0.606
	lower	0.01	0.766	0.651	0.721	0.637
		0.05	0.746	0.614	0.689	0.606
		0.1	0.736	0.601	0.675	0.596
		0.15	0.729	0.594	0.670	0.591
	upper	0.01	0.837	0.627	0.765	0.638
		0.05	0.806	0.579	0.712	0.600
		0.1	0.789	0.561	0.688	0.590
		0.15	0.782	0.554	0.679	0.586
	Nb. Best		12	0	0	0
	Avg. Rank		1.00	3.58	2.00	3.42

Table 5 :

 5 Quality of the time series representation learning under Kernel k-SVD

	DataSet	TsPrima Honeine Kwok Bakir
	CC	0.788	0.730	0.751 0.732
	GunPoint	0.993	0.994	0.992 0.985
	CBF	0.917	0.862	0.900 0.872
	OSULeaf	0.996	0.996	0.995 0.996
	SwedishLeaf	0.789	0.659	0.691 0.623
	Trace	0.687	0.514	0.602 0.514
	FaceFour	0.971	0.940	0.959 0.947
	Lighting2	0.991	0.961	0.982 0.968
	Lighting7	0.961	0.934	0.947 0.934
	ECG200	0.953	0.957	0.950 0.941
	Adiac	0.184	0.122	0.131 0.117
	FISH	0.757	0.553	0.579 0.560
	Beef	0.411	0.555	0.605 0.621
	Co↵ee	0.596	0.607	0.586 0.560
	OliveOil	0.145	0.133	0.152 0.120
	DiatomSizeR	0.287	0.177	0.198 0.178
	ECG5Days	0.996	0.996	0.995 0.994
	FacesUCR	0.917	0.834	0.878 0.842
	ItalyPowerD	0.800	0.781	0.034 0.728
	MedicalImages	0.937	0.860	0.930 0.878
	MoteStrain	0.969	0.970	0.971 0.970
	SonyAIBOII	0.974	0.975	0.973 0.975
	SonyAIBO	0.932	0.938	0.930 0.936
	Symbols	0.811	0.785	0.794 0.755
	TwoLeadECG	0.810	0.617	0.411 0.629
	spiral1	0.944	0.913	0.920 0.914
	spiral2	0.964	0.936	0.949 0.937
	PowerCons	0.968	0.946	0.957 0.951
	BME	0.872	0.734	0.843 0.622
	UMD	0.888	0.842	0.905 0.788
	digits	0.822	0.699	0.793 0.706
	lower	0.773	0.678	0.738 0.671
	upper	0.840	0.664	0.797 0.675
	Nb. Best	24	7	3	3
	Avg. Rank	1.5	3.02	2.33	3.15

Table 6 :

 6 Further comparisons for pre-image estimation

					TsPrima Honeine Kwok Bakir
	Averaging			Nb. Best	19	20	4	19
				Avg. Rank	2.23	2.21	3.35	2.21
	Reconstruction Nb. Best	24	10	0	1
	(kernel PCA)		Avg. Rank	1.56	2.35	3.05	3.05
	Denoising			Nb. Best	12	0	0	0
	(kernel PCA)		Avg. Rank	1.50	3.25	2.62	3.12
	Rep. Learning Nb. Best	25	8	1	2
	(kernel kSVD) Avg. Rank	1.44	2.67	2.58	3.32
	CD
	4	3	2	1
				2.2121 Honeine

an isotropic kernel is a function of the form k(x, y) = f (kx yk) that depends only on the norm of the lag vector between two samples.

For multivariate time series, simply define X 2 R d t⇥N .

Acknowledgment

This work is supported by the French National Research Agency through the projects locust (ANR-15-CE23-0027-02) and APi (ANR-18-CE23-0014).