betaFeedback

WorksComputer Science

M-Tensor Formalism: A Non-iterative High Dimensional Least Squares Regression for Nonlinear Models with Scarce Data

Abstract

We present a multilinear regression framework based on tensor algebra tailored to high-dimensional contexts where data is scarce. We exploit algebraic properties of a partial tensor product, namely the m-tensor product, to leverage structured equations with separated variables. The proposed method combines kernel properties along with tensor algebra to prevent explicit construction of the exponentially large feature space and tackle approximations up to hundreds of parameters while avoiding the fixed-point strategy. This is achieved by only ever employing the regression operator in a factorized form. We present this formalism along with different regularization techniques suited for low amount of data with a high number of parameters while preserving well-known matrix-based properties. We demonstrate complexity scaling on a general benchmark to show robustness for engineering problems and ease of implementation.

Introduction

Engineering problems are often made dependent on parameters. In certain cases, the number of those parameters might be reduced by identifying fewer latent variables as is done by model order reduction techniques. In certain scenarios the dependence has to be explicit. In that case even for problems with low latent dimensionality, making explicit use of those parameters becomes intractable. This issue is often found in design optimization problems for instance. Manipulating a large number of parameters often becomes numerically intractable because of a wall of complexity coined curse of dimensionality [4]. This curse translates the exponential growth of models (i.e. the number of coefficients) and that of the required amount of data with respect to the number of parameters. In contexts where data is scarce and costly, that curse makes models simply inaccessible.

Solutions proposed to circumvent this curse can rely on a modification of the grid required by the model, e.g. with a sparse grid [16], or with an adaptive selection of the pertinent points of that grid to retain [6]. A reduction of complexity can also be found by leveraging the structure of the equations. A common approach is to formulate the problem with separated variables. A prime example of this approach can be found in the works of Beylkin and Mohlenkamp [5]. The separated variables representation inherently relies on a tensorial factorization of the operators, often based on the use of Kronecker product-based linear systems [1, 19]. This reliance on tensor representation can explain the recent development of plenty of methods based on tensor network formalisms, more specifically the Tensor-Train (TT-) format [22] and the overall gain of interest toward tensor methods [18, 9, 13].

A popular variable separation technique stemming from computational mechanics is the Proper Generalized Decomposition (PGD) [2] and its sparse data-based version, the s-PGD [15]. Those approaches rely on a Canonical Polyadic Decomposition (CPD) of the field that is learnt from one-dimensional modes, i.e. a rank-1 tensor is added at each loop on all axes. It resembles the CP-ALS method [18] and solves for each mode employing a fixed-point strategy. This fixed-point approach implies a sequential construction and may append modes late in the algorithm that serve only as correctives for early ones that were not optimal.

Many recent approaches are based on the TT-format and its good scaling with high-dimensional problems. A framework that inspired this paper is that of MANDy [11]. In this work, Gelß et al. adapt the popular SINDy framework [7] to high-dimensional dynamical system identification, which remains a limitation for SINDy. To achieve good scaling, the authors built sparse TT cores from a choice of one-dimensional basis functions. The same authors later expanded the same methodology to image classification [17] where they started mixing their tensorial framework with kernel interpretations to tackle efficiently higher dimensional problems without relying on the TT-SVD sequential algorithm which they demonstrated became a computational bottleneck. At the same time as Baddoo et al. with their fully kernel-based approach to dynamic model learning [3], Gelß et al. published the kernel Feature Space Approximation (kFSA) method that once again mixes TT-formulated feature maps to kernel methods to provide a high-dimensional regularization (and model reduction) technique. We further investigated the work of Engel et al. in signal processing [8] that develop a kernel recursive least squares algorithm for online learning of signals. In their work, they provide several useful results, noticeably on the limitation of the number of retained signals (finite dictionary) and a bound with respect to ℓ2\ell_2 optimality provided by the kernel Principal Component Analysis (kPCA). The evaluation of distance in the feature space that defines their Almost Linearly Dependent (ALD) criterion is the same later used by Gelß and Baddoo in their respective works. We use the same approach in our framework.

In this work, we keep the philosophy of structuring the equations that build the regression operator from a separated variables perspective. Considering the lack of data as a structural constraint, we isolate it in the structure of the proposed operator and define a partial tensor product. We consider it an algebraically minimalistic approach to generalize matrix-based regression. It allows us to preserve properties of usual matrix-based linear systems while avoiding storage of- and computations with the exponentially large operator. By circumventing the fixed point strategy usually encountered in high dimensional contexts, we can produce the minimum-norm least squares solution from available data at a very low cost. We present the approach as algebraically minimalistic for its conceptual simplicity compared to tensor networks or abstract kernel feature spaces for instance. Working with tensor algebra and then identifying the kernel from the dot products also allows us to avoid the usual limitation of kernel methods to a few well-known kernels while leveraging their properties. For instance we are able to use the properties of kPCA. Furthermore, the sought minimalism allows us to avoid the necessity for sparse operators in practice for computational efficiency in the case of TT-formulation. The presented regularizations allow to mitigate kernel ill-conditioning and prove more efficient in high-dimensional contexts (more than 100 parameters) than TT-based techniques.

The proposed approach is structured around a tensor formalism from which we derive nice algebraic properties and computational tricks. We call it the m-tensor format as it is directly relates to the unmanageable matrix that would be built naively to solve the problem. This is how we retain many of the desirable properties of the matrix-based approach in a fully (tensor-)factorized manner. By preserving a structure of higher order, we enjoy the great efficiency of tensor-based approaches. Those properties would otherwise be lost by the matrix-based structure. As it is tailored for regression operators, this formalism is not investigated as a potential data structure for high order problems. The tools used in this paper are available on GitHub1 along with numerical examples.

The paper is organized as follows. In section 2, we set the problem of the least squares approximation of a scalar function in a general form. Section 3 builds the link between separable variables and tensor structure, this leads us to present the tensor operations we will use within our framework. The m-tensor format is presented in the case of least squares regression in section 4. We provide a general numerical analysis of the method in subsection 4.3. Section 5 provides different regularization techniques for m-tensor regression. We apply our method to demonstrate scalability and robustness in section 6 on a polynomial benchmark with growing dimension, comparing with existing approaches. Section 7 draws conclusions and presents perspectives for future works.

Notations. We present the notations adopted in the remainder of the paper. Operation symbols are given with their definition. Working with high dimensional objects relies on burdensome notations in order to disambiguate definitions, therefore we try to strictly stick to conventions given here. Uppercase bold symbols (e.g. T\mathbf{T}) are used for tensors. Uppercase symbols (e.g. MM) are used for matrices. Lowercase bold symbols (e.g. v\mathbf{v}) are used for vectors. The notation [⋅]ijk…[\cdot]_{ijk\ldots} denotes the ijk…ijk\ldots-th element of the tensor in brackets, each index evolving along an axis of the tensor. Due to the high order nature of the object of the paper, indices are more frequently subscripted with axis number, i.e. elements of a tensor T\mathbf{T} of order nn will be denoted as [T]i1i2…in[\mathbf{T}]_{i_1i_2\ldots i_n}. We denote the identity of size mm as Idm\mathrm{Id}_m and the vector of ones of size mm as 1m\mathbf{1}_m.

Least squares approximation of a scalar function

In order to provide a general approach, let D⊂Rd\mathcal{D} \subset\mathbb{R}^{d} denote a dd-dimensional domain, defined as the cartesian product of one-dimensional intervals in R\mathbb{R}, i.e. D=∏i=1d[ai,bi]\mathcal{D} = \prod_{i=1}^{d}[a_i,b_i], [ai,bi]⊂R[a_i,b_i] \subset\mathbb{R}. The aim is to approximate a scalar function ff defined over that domain. Let φ1≤i≤N\varphi_{1\leq i\leq\mathcal{N}} denote basis functions to be chosen, we give an approximation of ff with the form

f^(x)=∑i=1Nciφi(x)=φT(x)c,(1)\widehat{f}(\mathbf{x}) = \sum_{i=1}^{\mathcal{N}} c_i\varphi_i(\mathbf{x}) = \boldsymbol{\varphi}^{\mathsf{T}}(\mathbf{x})\mathbf{c}, \tag*{(1)}

where coefficients c\mathbf{c} are the best fit (in the least squares sense) for the chosen basis functions. The number of terms N\mathcal{N} depends on the choice of bases as well. Let P\mathcal{P} denote a set of mm distinct samples in D\mathcal{D} such that

P={xk∈D, ∀k, 1≤k≤m}.\mathcal{P} = \{\mathbf{x}_k \in\mathcal{D},\ \forall k,\ 1 \leq k \leq m\}.

Consider we are given the evaluation of ff at each sample of P\mathcal{P}. We denote y∈Rm\mathbf{y} \in\mathbb{R}^{m} the vector defined as

[y]k=f(xk)∀k, 1≤k≤m, xk∈P.[\mathbf{y}]_k = f(\mathbf{x}_k)\quad\forall k,\ 1 \leq k \leq m,\ \mathbf{x}_k \in\mathcal{P}.

Let Φ∈Rm×N\Phi\in\mathbb{R}^{m \times\mathcal{N}} denote the evaluation of bases φ\varphi used in (2.1) over the set P\mathcal{P}. With [Φ]k[\Phi]_k denoting the kk-th row of Φ\Phi, we have

[Φ]k=φT(xk)∀ k, 1≤k≤m, xk∈P.[\Phi]_k = \varphi^{\mathsf{T}}(\mathbf{x}_k) \quad\forall\ k,\ 1 \le k \le m,\ \mathbf{x}_k \in\mathcal{P}.

Then, the least squares solution c^\hat{\mathbf{c}} is the one that, for any given bases φ\varphi, minimizes the squared ℓ2\ell_2 error with respect to y\mathbf{y}:

c^=argmin⁡c∥∑k=1mφT(xk)c−[y]k∥22(2)\hat{\mathbf{c}} = \underset{\mathbf{c}}{\operatorname{argmin}}\left\lVert\sum_{k=1}^{m}\varphi^{\mathsf{T}}(\mathbf{x}_k)\mathbf{c} - [\mathbf{y}]_k \right\rVert_2^2 \tag*{(2)}

This minimization problem admits an explicit solution based on whether Φ\Phi has linearly independent columns (2.3) or rows (2.4) that we build using the Moore-Penrose inverse formulation [23]:

c^=(ΦTΦ)−1ΦTy,(3)\hat{\mathbf{c}} = (\Phi^{\mathsf{T}}\Phi)^{-1}\Phi^{\mathsf{T}}\mathbf{y}, \tag*{(3)}
c^=ΦT(ΦΦT)−1y.(4)\hat{\mathbf{c}} = \Phi^{\mathsf{T}}(\Phi\Phi^{\mathsf{T}})^{-1}\mathbf{y}. \tag*{(4)}

We use this widely used explicit formulation of least squares solution to determine the coefficients c\mathbf{c} of the approximation. Without any prior knowledge of ff, the aim is then to define basis functions φ\varphi such that ff is well approximated. To that end, one can choose to tailor the functions in order to minimize N\mathcal{N} or provide a rich enough set of bases so that all features of ff can be captured. In what follows we choose the latter and show how our tensorial framework alleviates the curse of dimensionality within the regression approach.

Separable variables and tensor structure

A popular approach in high dimension is the separation of variables. In this setting, the basis functions φ\varphi are sought as products of one-dimensional functions. We denote those one-dimensional functions ψ\psi and define multidimensional bases φ\varphi as

∀ i, 1≤i≤N,φi(x)=∏j=1dψij([x]j).\forall\ i,\ 1 \le i \le\mathcal{N},\quad\varphi_i(\mathbf{x}) = \prod_{j=1}^{d}\psi_{ij}([\mathbf{x}]_j).

Like all combinatorial problems, no standard approach would scale well in order to compute all combinations of one-dimensional basis functions. Therefore we demonstrate the use of a convenient tensor framework. Let ψ∈Rp\boldsymbol{\psi} \in\mathbb{R}^{p} denote the vector of pp one-dimensional basis functions deemed rich enough to represent the problem in one dimension given as

ψ(x)=[ψ1(x)ψ2(x)⋯ψp(x)].\boldsymbol{\psi}(\mathbf{x}) = [\psi_1(\mathbf{x})\quad\psi_2(\mathbf{x})\quad\cdots\quad\psi_p(\mathbf{x})].

All combinations of one-dimensional bases would be found without redundancy in the elements of the tensor φ\boldsymbol{\varphi} defined as

φ(x)=⨂j=1dψ([x]j).\boldsymbol{\varphi}(\mathbf{x}) = \bigotimes_{j=1}^{d}\boldsymbol{\psi}([\mathbf{x}]_j).

We note that φ∈Rp×p×⋯×p\boldsymbol{\varphi} \in\mathbb{R}^{p \times p \times\cdots\times p} is a rank-1 tensor of order dd. Having the same set of basis functions along each axis is an arbitrary choice made to alleviate notations.

Based on this representation, the formulation of the approximation of ff in (1) can be written as the inner product

f^(x)=⟨φ(x),C⟩.(5)\hat{f}(\mathbf{x}) = \langle\varphi(\mathbf{x}), \mathbf{C}\rangle. \tag*{(5)}

Here C∈Rp×p×⋯×p\mathbf{C} \in\mathbb{R}^{p \times p \times\cdots\times p} is an order dd tensor of coefficients. The least squares coefficient tensor C^\hat{\mathbf{C}} is the one minimizing the ℓ2\ell_2 error with respect to y\mathbf{y}:

C^=argmin⁡C∥∑k=1m⟨φ(xk),C⟩−[y]k∥22.(6)\hat{\mathbf{C}} = \underset{\mathbf{C}}{\operatorname{argmin}}\left\| \sum_{k=1}^{m} \langle\varphi(\mathbf{x}_k), \mathbf{C}\rangle- [\mathbf{y}]_k \right\|_2^2. \tag*{(6)}

If we were to vectorize this tensor formulation, we would find the expression given for (1) with N=pdN = p^d. The most important aspect is therefore the ability to only use factorized formulations for problems that would otherwise be inaccessible memory- and computationally-wise. The unmanageable nature of the least squares solution C^\hat{\mathbf{C}} has motivated research on various tensor formats [9, 13, 18]. The general strategy being to truncate the rank of the solution either in the canonical sense of tensor rank, or in the multilinear one. The former view of rank is the one used in PGD or CP-ALS while the latter is the one found in tensor trains or Tucker representation. In what follows, our aim is to retain the full least squares approximation in an efficient manner, hence our optimality claim.

M-Tensor least squares regression

In this section, we define elementary operations to be used in what we refer to as the m-tensor formalism to efficiently compute a multidimensional least squares regression. The aim is to make the tensor least squares (6) manageable in arbitrarily high dimensions in the scarce data context, i.e. underdetermined problem.

Definitions

We first define a row-wise tensor product. Further in this paper we refer to it as the m-tensor product. It generalizes the face-splitting product [26] (transposed Khatri-Rao) the same way the tensor product generalizes the matrix Kronecker product. Our approach uses a similar structure as the face-splitting product but preserves its multidimensionality, therefore avoiding the index mapping burden.

Definition 4.1. (Row-wise tensor product). For a given set of matrices {Ψi∈Rm×pi}i=1d\{\Psi_i \in\mathbb{R}^{m \times p_i}\}_{i=1}^{d}, we define their row-wise tensor product, building an order d+1d+1 tensor Φ∈Rm×p1×p2×⋯×pd\mathbf{\Phi} \in\mathbb{R}^{m \times p_1 \times p_2 \times\cdots\times p_d} as

[Φ]ki1i2…id=[⨂j=1dΨj]ki1i2…id=∏j=1d[Ψj]kij.[\mathbf{\Phi}]_{k i_1 i_2 \ldots i_d} = \left[\bigotimes_{j=1}^{d} \Psi_j\right]_{k i_1 i_2 \ldots i_d} = \prod_{j=1}^{d} [\Psi_j]_{k i_j}.

We show in this paper how well-suited tensors built that way are for multilinear regression. We refer to the matrices {Ψj}j=1d\{\Psi_j\}_{j=1}^{d} as cores of the m-tensor Φ\mathbf{\Phi}. We call rows the rank-1 tensors resulting from the row-wise tensor product and columns the mode-1 fibers of the tensor.

Proposition 4.2. The mode-1 unfolding of this tensor, denoted Φ(1)\mathbf{\Phi}_{(1)}, results in a dense matrix in Rm×p1p2…pd\mathbb{R}^{m \times p_1p_2\ldots p_d}. That unfolding is exactly equal to the face-splitting product of its cores defined using notations introduced by Slyusar [26] as

Φ(1)=Ψ1□Ψ2□…□Ψd.\mathbf{\Phi}_{(1)} = \Psi_1 \square\Psi_2 \square\ldots\square\Psi_d.

:::`

This can easily be demonstrated element-wise from both definitions. We introduce the transposition definition that will later allow us to copy matrix operations formalism with tensors.

Definition 4.3. (Transposition). Let Φ∈Rm×p1×p2×⋯×pd\Phi\in\mathbb{R}^{m\times p_1\times p_2\times\cdots\times p_d} built as the mm-tensor product of cores {Ψj}j=1d\{\Psi_j\}_{j=1}^{d}, its transpose is given as

ΦT∈Rpd×pd−1×⋯×p1×m, with [ΦT]idid−1⋯i1k=∏j=1d[Ψj]kjij.\Phi^{\mathsf{T}} \in\mathbb{R}^{p_d\times p_{d-1}\times\cdots\times p_1\times m}, \text{ with } [\Phi^{\mathsf{T}}]_{i_d i_{d-1}\cdots i_1 k}=\prod_{j=1}^{d}[\Psi_j]_{k_j i_j}.

A key element of our framework is to be able to efficiently act on a massive amount of combinations of basis functions seamlessly. To do so we seek to obtain operations equivalent to the matrix ones. We first settle elements towards a m-tensor equivalent to matrix multiplication by adapting the general definition of tensor inner product to our case, i.e. by leveraging the efficiency of rank-1 tensor operations.

Definition 4.4. (Inner product). Let φ1,φ2∈Rp1×p2×⋯×pd\varphi_1,\varphi_2 \in\mathbb{R}^{p_1\times p_2\times\cdots\times p_d} be two arbitrary tensors. Their inner product is defined as

⟨φ1,φ2⟩=∑i1=1p1∑i2=1p2⋯∑id=1pd[φ1]i1i2⋯id[φ2]i1i2⋯id.\langle\varphi_1,\varphi_2\rangle=\sum_{i_1=1}^{p_1}\sum_{i_2=1}^{p_2}\cdots\sum_{i_d=1}^{p_d}[\varphi_1]_{i_1i_2\cdots i_d}[\varphi_2]_{i_1i_2\cdots i_d}.

That computation scales as O(pd)O(p^d) considering ∀i\forall i, pi=pp_i=p. This definition naturally leads to the norm ∥φ∥=⟨φ,φ⟩\|\varphi\|=\sqrt{\langle\varphi,\varphi\rangle}. We identify the specific case of the inner product of rank-1 tensors that we further leverage in the case of m-tensors.

Proposition 4.5. Let φ1,φ2∈Rp1×p2×⋯×pd\varphi_1,\varphi_2 \in\mathbb{R}^{p_1\times p_2\times\cdots\times p_d} defined as rank-1 tensors, respectively

φ1=⨂i=1dui1,andφ2=⨂i=1dui2,\varphi_1=\bigotimes_{i=1}^{d}\mathbf{u}_i^1,\qquad\text{and}\qquad\varphi_2=\bigotimes_{i=1}^{d}\mathbf{u}_i^2,

where ∀i\forall i, 1≤i≤d1\le i\le d, ui1,2∈Rpi\mathbf{u}_i^{1,2}\in\mathbb{R}^{p_i}. Then the complexity of their inner product falls to O(dp)O(dp) considering ∀i\forall i, pi=pp_i=p for ease of notation.

Proof. From the rank-1 structure of φ1\varphi_1 and φ2\varphi_2 and Definition 4.4, we have

⟨φ1,φ2⟩=∏i=1d(ui1)Tui2.\langle\varphi_1,\varphi_2\rangle=\prod_{i=1}^{d}(\mathbf{u}_i^1)^{\mathsf{T}}\mathbf{u}_i^2.

This simplifies the dd-dimensional problem and allows to separately evaluate dd vector inner products, hence the O(dp)O(dp) complexity scaling. □

From that property, we can demonstrate the efficiency of m-tensor operations required for our regression framework. We then develop the generalization of matrix product for tensors through the dd-way contracted product.

Definition 4.6. (D-way contracted product). Let Φ1∈Rm1×p1×p2×⋯×pd\Phi_1\in\mathbb{R}^{m_1\times p_1\times p_2\times\cdots\times p_d} and Φ2∈Rm2×p1×p2×⋯×pd\Phi_2\in\mathbb{R}^{m_2\times p_1\times p_2\times\cdots\times p_d}, their dd-way contracted product, denoted ⋉\ltimes, is given as

Φ1⋉Φ2T=(Φ1)(1)(Φ2)(1)T\Phi_1\ltimes\Phi_2^{\mathsf{T}}=(\Phi_1)_{(1)}(\Phi_2)_{(1)}^{\mathsf{T}}

In a general setting, that product is computed with complexity O(m2pd)O(m^2p^d), by considering for ease of notation that m1=m2=mm_1=m_2=m and ∀i\forall i, pi=pp_i=p. We can however give a special case when considering m-tensors.

Proposition 4.7. Let Φ1∈Rm1×p1×p2×⋯×pd\Phi_1 \in\mathbb{R}^{m_1 \times p_1 \times p_2 \times\cdots\times p_d} and Φ2∈Rm2×p1×p2×⋯×pd\Phi_2 \in\mathbb{R}^{m_2 \times p_1 \times p_2 \times\cdots\times p_d} be mm-tensors respectively based on cores {Ψi1}1≤i≤d\{\Psi_i^1\}_{1 \le i \le d} and {Ψi2}1≤i≤d\{\Psi_i^2\}_{1 \le i \le d}. Their dd-way contracted product is computed as

Φ1⋉Φ2T=⨀i=1dΨi1(Ψi2)T.\Phi_1 \ltimes\Phi_2^{\mathsf{T}} = \bigodot_{i=1}^{d} \Psi_i^1\left(\Psi_i^2\right)^{\mathsf{T}}.

Considering, for ease of notation that m1=m2=mm_1=m_2=m and ∀i\forall i, pi=pp_i=p, the complexity of this product is O(m2dp)O(m^2dp).

Proof. Starting from the general case of dd-way contracted product given in Definition 4.6 and proceeding element-wise, we identify inner products of rank-1 tensors, whose complexity scales as O(dp)O(dp) as proven for Proposition 4.5. Considering m1=m2=mm_1=m_2=m we have m2m^2 of those products to compute. This amounts to computing the Hadamard product of Gram matrices as given in the proposition, hence the complexity O(m2dp)O(m^2dp) considering m1=m2=mm_1=m_2=m and ∀i\forall i, 1≤i≤d1 \le i \le d, pi=pp_i=p.

Least squares approximation

From those definitions we can build our framework. Provided the set of sampled parameters P={xk}k=1m\mathcal{P}=\{\mathbf{x}_k\}_{k=1}^{m} and corresponding evaluations of ff in a vector y\mathbf{y}, we define the basis functions tensor as

φ(x)=⨂i=1dψ([x]i),with ψ:x↦[ψ1(x)  ψ2(x)  ⋯  ψp(x)].\varphi(\mathbf{x}) = \bigotimes_{i=1}^{d}\psi([\mathbf{x}]_i), \qquad\text{with } \psi:x\mapsto[\psi_1(x)\ \ \psi_2(x)\ \ \cdots\ \ \psi_p(x)].

This structure amounts to combining one-dimensional bases ψ1≤i≤p\psi_{1\le i\le p} for all input parameters. This gives us a large approximation capability, unreachable with a matrix-based regression. We define the cores

∀i, 1≤i≤d,Ψi=[ψ1([x1]i)ψ2([x1]i)⋯ψp([x1]i)ψ1([x2]i)ψ2([x2]i)⋯ψp([x2]i)⋮⋮⋱⋮ψ1([xm]i)ψ2([xm]i)⋯ψp([xm]i)].\forall i,\ 1 \le i \le d,\qquad \Psi_i = \begin{bmatrix} \psi_1([\mathbf{x}_1]_i) & \psi_2([\mathbf{x}_1]_i) & \cdots& \psi_p([\mathbf{x}_1]_i) \\ \psi_1([\mathbf{x}_2]_i) & \psi_2([\mathbf{x}_2]_i) & \cdots& \psi_p([\mathbf{x}_2]_i) \\ \vdots& \vdots& \ddots& \vdots\\ \psi_1([\mathbf{x}_m]_i) & \psi_2([\mathbf{x}_m]_i) & \cdots& \psi_p([\mathbf{x}_m]_i) \end{bmatrix}.

Mappings can be defined differently for each variable. Note that by providing nonlinear mappings, the (multi-)linear system we build is able to approximate nonlinear models in a non-iterative manner. That definition of the cores allows us to define the mm-tensor regression operator Φ\Phi as

Φ=⨂i=1dΨi.(7)\Phi= \bigotimes_{i=1}^{d}\Psi_i. \tag*{(7)}

We can now reformulate the regression problem in mm-tensorial setting. We seek the regression coefficients C∈Rp×p×⋯×p\mathbf{C} \in\mathbb{R}^{p \times p \times\cdots\times p} such that

Φ⋉C=y.(8)\Phi\ltimes\mathbf{C} = \mathbf{y}. \tag*{(8)}

A least squares solution C^\widehat{\mathbf{C}} to this problem can be built explicitly based on the general pseudoinverse formulation (2.4). Provided that Φ\Phi has linearly independent rows, we have the solution

C^=ΦT(Φ⋉ΦT)−1y.(9)\widehat{\mathbf{C}} = \Phi^{\mathsf{T}}\left(\Phi\ltimes\Phi^{\mathsf{T}}\right)^{-1}\mathbf{y}. \tag*{(9)}

We made our approach fully equivalent to the matrix framework while taking advantage of the tensor factorization, therefore that definition holds in any dimension. We consider the linearly independent rows case because, in general, the exponential growth of the system with dd will prevent it to have linearly independent columns as it would require mm to grow exponentially with dd. This makes our approach well defined in the under-determined case.

We generally cannot use coefficients formulated as (4.3). For that reason, we readily build the approximation of ff as

f^(x)=φ(x)⋉ΦT(Φ⋉ΦT)−1y.(10)\hat{f}(\mathbf{x})=\varphi(\mathbf{x})\ltimes\Phi^{\mathsf{T}}\left(\Phi\ltimes\Phi^{\mathsf{T}}\right)^{-1}\mathbf{y}. \tag*{(10)}

This expression shows explicitly how it results only in efficient operations. In fact, by computing

z=(Φ⋉ΦT)−1y∈Rm,(11)\mathbf{z}=\left(\Phi\ltimes\Phi^{\mathsf{T}}\right)^{-1}\mathbf{y}\in\mathbb{R}^{m}, \tag*{(11)}

we evaluate f^\hat{f} only by computing φ(x)⋉ΦT∈Rm\varphi(\mathbf{x})\ltimes\Phi^{\mathsf{T}}\in\mathbb{R}^{m} and its inner product with z\mathbf{z}:

f^(x)=⟨φ(x)⋉ΦT,z⟩.(12)\hat{f}(\mathbf{x})=\left\langle\varphi(\mathbf{x})\ltimes\Phi^{\mathsf{T}},\mathbf{z}\right\rangle. \tag*{(12)}

This evaluation’s complexity scales as O(mdp)O(mdp). The result provided is optimal in the least squares sense for the selected mappings and given sampled points.

Numerical analysis

In this section we analyze the influence of the structure we propose on roundoff error, noise sensitivity and conditioning. For the setting, we consider that our regression operator Φ\Phi is built upon a sample P\mathcal{P} of mm elements and a tensorized mapping φ=⨂i=1dψi\varphi=\bigotimes_{i=1}^{d}\psi_i. We assume the mappings {ψi∈Rp}i=1d\{\psi_i\in\mathbb{R}^{p}\}_{i=1}^{d} to be able to capture ff, i.e.

∃ C∈Rp×p×⋯×p, ∀ x∈Rd,f(x)=φ(x)C.\exists\,\mathbf{C}\in\mathbb{R}^{p\times p\times\cdots\times p},\ \forall\,\mathbf{x}\in\mathbb{R}^{d},\quad f(\mathbf{x})=\varphi(\mathbf{x})\mathbf{C}.

In that section we drop the ⋉\ltimes for ease of reading. All proofs are developed in section A. We assume the function ff, evaluated over P\mathcal{P} in the vector y\mathbf{y} and denote the approximation we build f~(x)=φ(x)(C+δC)\widetilde{f}(\mathbf{x})=\varphi(\mathbf{x})(\mathbf{C}+\delta\mathbf{C}). We will consider input perturbation [δx]1≤i≤d=O(ϵmachine)[\delta\mathbf{x}]_{1\leq i\leq d}=O(\epsilon_{\mathrm{machine}}) to evaluate its effect of the stability of our approach. In what follows, we consider approximations by neglecting at least doubly infinitesimal quantities, i.e. we consider first order approximations.

Theorem 4.8. (Bound on φ(x+δx)\varphi(\mathbf{x}+\delta\mathbf{x})). Let {ξi}i=1d:Rd×Rd→Rp\{\xi_i\}_{i=1}^{d}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{p} denote a 1D mapping error due to input perturbation such that the separated variables representation yields

φ(x+δx)=⨂i=1dψi([x]i+[δx]i)=⨂i=1dψi([x]i)+ξi([x]i,[δx]i).\varphi(\mathbf{x}+\delta\mathbf{x})=\bigotimes_{i=1}^{d}\psi_i([\mathbf{x}]_i+[\delta\mathbf{x}]_i)=\bigotimes_{i=1}^{d}\psi_i([\mathbf{x}]_i)+\xi_i([\mathbf{x}]_i,[\delta\mathbf{x}]_i).

Let the 1D mappings {ψi}i=1d\{\psi_i\}_{i=1}^{d} be normalized element-wise, then the evaluation error of φ\varphi is bounded as

∥φ(x+δx)−φ(x)∥F≲pd−1∑i=1d∥ξi([x]i,[δx]i)∥F.\left\|\varphi(\mathbf{x}+\delta\mathbf{x})-\varphi(\mathbf{x})\right\|_{F}\lesssim\sqrt{p^{d-1}}\sum_{i=1}^{d}\left\|\xi_i([\mathbf{x}]_i,[\delta\mathbf{x}]_i)\right\|_{F}.

Theorem 4.8 demonstrates the necessity to analyze the behaviour of the terms ξ\xi when choosing a mapping so as to minimize input perturbation error. The specific case of input roundoff error gives Lemma 4.9.

Lemma 4.9. (Input roundoff error). Let each input xx of φ\varphi be perturbed with [δx]1≤i≤d=O(εmachine)[\delta x]_{1\le i\le d} = O(\varepsilon_{\mathrm{machine}}), then there exists a mapping-dependent constant cc such that

∥φ(x+δx)−φ(x)∥F≤dcεmachinepd.\lVert\varphi(\mathbf{x}+\delta\mathbf{x})-\varphi(\mathbf{x})\rVert_F \le dc\varepsilon_{\mathrm{machine}}\sqrt{p^d}.

We draw conclusions on the backward stability of the approach under those assumptions and derive strategies to guarantee stability.

Theorem 4.10. (Backward stability). Let ψi\psi_i, i=1,…,di=1,\ldots,d, denote normalized 1D mappings with separable perturbation-induced errors of the shape ψi(x+δx)=ψi(x)+ξi(x,δx)\psi_i(x+\delta x)=\psi_i(x)+\xi_i(x,\delta x). Let cc denote a constant such that over its domain of definition

∥ξi(x,δx)∥F≤cp.\lVert\xi_i(x,\delta x)\rVert_F\le c\sqrt{p}.

Then if dc≪1dc\ll1, the backward error tends to

∥f~(x)−f(x+δx)∥∥f(x+δx)∥≲∥δC∥∥C∥.\frac{\lVert\widetilde{f}(x)-f(x+\delta x)\rVert}{\lVert f(x+\delta x)\rVert}\lesssim\frac{\lVert\delta C\rVert}{\lVert C\rVert}.

Theorem 4.10 tells us that controlling the bounding constant cc, which is directly derived from the choice of 1D mapping, we can guarantee that the backward error tends purely to the approximation error of the model δC\delta C. The advantage is that a uniform scaling of the bases suffices to lower that constant without impacting the conditioning (for which we design specific regularization strategies in section 5).

The aim of our method is to piggy-back on the matrix properties of its mode-1 unfolding Φ(1)∈Rm×pd\boldsymbol{\Phi}_{(1)}\in\mathbb{R}^{m\times p^d}. Thus we may consider the SVD of that unfolding

Φ(1)=UΣVT.(13)\boldsymbol{\Phi}_{(1)}=U\Sigma V^{\mathsf{T}}. \tag*{(13)}

We can access UU and Σ\Sigma through the eigendecomposition of

P=ΦΦT=Φ(1)Φ(1)T=UΣ2UT.(14)P=\boldsymbol{\Phi}\boldsymbol{\Phi}^{\mathsf{T}}=\boldsymbol{\Phi}_{(1)}\boldsymbol{\Phi}_{(1)}^{\mathsf{T}}=U\Sigma^2U^{\mathsf{T}}. \tag*{(14)}

This gives us an easy read on the effective condition number of Φ(1)\boldsymbol{\Phi}_{(1)} given by

κ(Φ)=σ1σr,(15)\kappa(\boldsymbol{\Phi})=\frac{\sigma_1}{\sigma_r}, \tag*{(15)}

where σ1\sigma_1 denotes the largest singular value in Σ\Sigma and σr\sigma_r its lowest nonzero singular value. Then we can assess noise sensitivity by assuming the perturbations [δy]k=1m[\delta y]_ {k=1}^{m}.

Theorem 4.11. (Noise sensitivity). Assuming the sampled points P\mathcal{P} are sufficient and that the basis φ\varphi is well suited to approximate ff, then the error stemming from data noise δy\delta y is bounded as

∥δC∥≤∥δy∥σr.\lVert\delta C\rVert\le\frac{\lVert\delta y\rVert}{\sigma_r}.

This bound demonstrates the crucial necessity to regularize the regression.

Regularization of m-tensor regression

In this section we adapt regularization techniques for m-tensor regression. In under-determined regression with mm samples, the rank is at most mm and the condition number is an indicator on row correlation. In the case of m-tensor regression, this means measuring how close to linearly dependent the mappings {φ(xk)}k=1m\{\varphi(x_k)\}_{k=1}^{m} are. In this section, we denote P=ΦΦTP=\boldsymbol{\Phi}\boldsymbol{\Phi}^{\mathsf{T}}.

Tikhonov regularization

Analogously to the matrix case, Tikhonov regularization for mm-tensors is given as

C^2=ΦT(P+λ2I)−1y.\widehat{\mathbf{C}}_2 = \mathbf{\Phi}^{\mathsf{T}}\left(P+\lambda^2\mathbb{I}\right)^{-1}y.

This results in a uniform lifting of the eigenvalues of PP, hence the conditioning improvement. The approximation of ff with Tikhonov regularization is then given by evaluating the inner product

f^2(x)=⟨φ(x)ΦT,z2⟩ with z2=(P+λ2I)−1y.(16)\widehat{f}_2(x)=\langle\varphi(x)\mathbf{\Phi}^{\mathsf{T}},z_2\rangle\text{ with }z_2=\left(P+\lambda^2\mathbb{I}\right)^{-1}y. \tag*{(16)}

This approaches’ complexity is dominated by the inversion scaling as O(m3)O(m^3) and the construction of PP itself, scaling as O(m2pd)O(m^2pd). Inference, given in (16), has a complexity O(mpd)O(mpd).

Spectral truncation

We manage to always take advantage of the high efficiency of the inner product of rank-1 tensors. In the under-determined case, we make P=ΦΦTP=\mathbf{\Phi}\mathbf{\Phi}^{\mathsf{T}} appear, where [P]ij=⟨φ(xi),φ(xj)⟩[P]_{ij}=\langle\varphi(x_i),\varphi(x_j)\rangle. Thus, considering the mapping

φ:x⟼⨂i=1dψ([x]i),\varphi:x\longmapsto\bigotimes_{i=1}^{d}\psi([x]_i),

we can derive a kernel function kk defined as the inner product

k:(x,x′)⟼⟨φ(x),φ(x′)⟩.k:(x,x')\longmapsto\langle\varphi(x),\varphi(x')\rangle.

Therefore we are guaranteed to build a symmetric positive semidefinite kernel. Assuming the 1D mappings ψ\psi to be continuous on compact domains (such as intervals of R\mathbb{R}), then the kernel we define satisfies the assumptions [21] under which Mercer-type spectral results apply. This allows us to leverage properties of kernels [24]. Moreover it makes spectral truncation within the mm-tensor framework a truncated kernel PCA [25]. Keeping only the first rr principal components in feature space assures us to preserve the optimal rr-dimensional representation in feature space for a given mapping.

Spectral truncation improves the conditioning of the regression operator by setting to zero the singular values below a set threshold τ\tau or up to a prescribed rank rr. We apply it to mm-tensor regression through the eigenvalues of PP. Let UrU_r denote the matrix built from the first rr eigenvectors of PP. The regularized coefficients are then given by

C^∗=ΦTUrΣr−2UrTy.\widehat{\mathbf{C}}_*=\mathbf{\Phi}^{\mathsf{T}}U_r\Sigma_r^{-2}U_r^{\mathsf{T}}y.

The resulting approximation is computed as the inner product

f^∗(x)=⟨φ(x)ΦT,z∗⟩, with z∗=UrΣr−2UrTy.(17)\widehat{f}_*(x)=\langle\varphi(x)\mathbf{\Phi}^{\mathsf{T}},z_*\rangle,\text{ with }z_*=U_r\Sigma_r^{-2}U_r^{\mathsf{T}}y. \tag*{(17)}

This approach results in a complexity dominated by the computation of the SVD of PP, i.e. O(m3pd)O(m^3pd). Inference cost is the same as for the Tikhonov regularization.

Subsampling

We consider a regularization technique that aims at both enhancing the conditioning of the system and improving inference’s efficiency. We consider a subset of m~<m\widetilde{m}<m rows of Φ\mathbf{\Phi}, corresponding to a subsample P~⊂P\widetilde{P}\subset P that can approximate all rows of Φ\mathbf{\Phi} up to a given tolerance ε\varepsilon, i.e.

∃W∈Rm×m~,∥Φ−WΦ~∥22<ε.(18)\exists W\in\mathbb{R}^{m\times\widetilde{m}},\qquad\left\lVert\mathbf{\Phi}-W\widetilde{\mathbf{\Phi}}\right\rVert_2^2<\varepsilon. \tag*{(18)}

Rows of Φ\Phi are considered Almost Linearly Dependent (ALD) [8] on this subset. We denote Φ~\widetilde{\Phi} the tensor made only of those m~\widetilde{m} rows of Φ\Phi. Those are selected based on the following squared distance δk\delta_k evaluation. By denoting [Φ]k[\Phi]_k the kk-th row of Φ\Phi,

∀k, 1≤k≤m,δk=min⁡w∈Rm~∥[Φ]k−wTΦ~∥22<ε.\forall k,\ 1 \le k \le m,\quad\delta_k = \min_{\mathbf{w}\in\mathbb{R}^{\widetilde{m}}} \left\|[\Phi]_k-\mathbf{w}^{\mathsf{T}}\widetilde{\Phi}\right\|_2^2 < \varepsilon.

δk\delta_k evaluates the distance of each row [Φ]k[\Phi]_k to the subspace spanned by the rows of Φ~\widetilde{\Phi}. Decomposition (5.3) provides a bound with respect to the ℓ2\ell_2 optimal provided by the previously introduced spectral truncation [8]. Sampling from the rows preserves the rank-1 structure, which is lost in spectral truncation. By separating the subset Φ~\widetilde{\Phi} and the remainder that we denote Φ‾\overline{\Phi} in (4.2) and applying the same separation and reordering in y\mathbf{y}, we have

[Φ~Φ‾]C=[y~y‾].\begin{bmatrix} \widetilde{\Phi}\\ \overline{\Phi} \end{bmatrix}\mathbf{C} = \begin{bmatrix} \widetilde{\mathbf{y}}\\ \overline{\mathbf{y}} \end{bmatrix}.

We then only solve for the first subset, i.e. we seek C~\widetilde{\mathbf{C}} in the minimization problem

C~=argmin⁡C(∥Φ~C−y~∥22).\widetilde{\mathbf{C}}=\underset{\mathbf{C}}{\operatorname{argmin}}\left(\left\|\widetilde{\Phi}\mathbf{C}-\widetilde{\mathbf{y}}\right\|_2^2\right).

The conditioning is enhanced by removing close-to-correlated samples. It also truncates the spectrum so rank⁡(Φ~)=m~\operatorname{rank}(\widetilde{\Phi})=\widetilde{m}. This subsystem approach is the only regularization that manages to reduce the size of the system to solve and provide a gain with respect to mm along with the linearization of inference complexity with dd.

The subset selection can be done in one of two ways: a greedy or streamed one. The former is developed analogously to what is done by Gelß et al. [10] while the latter is an adaptation of the kernel recursive least squares developed by Engel et al. [8] for signal processing. The approach proposed by Engel et al. is enhanced by incrementally building the Cholesky factor instead of relying on the kernel matrix, as inspired by Baddoo et al. [3]. The approximation is evaluated as

f~(x)=⟨φ(x)Φ~T,z~⟩,withz~=(Φ~Φ~T)−1y~.\widetilde{f}(\mathbf{x})=\langle\varphi(\mathbf{x})\widetilde{\Phi}^{\mathsf{T}},\widetilde{\mathbf{z}}\rangle,\quad\text{with}\quad\widetilde{\mathbf{z}}=(\widetilde{\Phi}\widetilde{\Phi}^{\mathsf{T}})^{-1}\widetilde{\mathbf{y}}.

The computational gain at the online stage can reveal massive compared to the least squares formulation if m~≪m\widetilde{m}\ll m. With the subsampling approach, inference cost scales as O(m~pd)O(\widetilde{m}pd). This formulation outperforms all previous ones at a small and controllable cost in terms of error. Algorithms for the greedy and streamed subsampling formulations are given in appendix section B. The streamed construction results in a complexity bounded by O(m2pd)O(m^2pd) by considering ∀i\forall i, pi=pp_i=p.

Summary

Table 5.1 summarizes the theoretical computational complexity of each regression approach at construction and inference stages. We have considered a number of samples scaling linearly with the dimension dd with a factor α\alpha, so m=αdm=\alpha d.

Numerical example

We demonstrate the scaling of our approach on the Rosenbrock function. It is defined for arbitrary dimension dd over the domain D=[−5,10]d\mathcal{D}=[-5,10]^d as

f(x)=∑i=1d−1100([x]i+1−[x]i2)2+([x]i−1)2.f(\mathbf{x})=\sum_{i=1}^{d-1}100\left([\mathbf{x}]_{i+1}-[\mathbf{x}]_i^2\right)^2+\left([\mathbf{x}]_i-1\right)^2.

Proposed model. We approximate the Rosenbrock function with growing dimension d∈{10,20,30,50,100,200}d\in\{10,20,30,50,100,200\} with polynomial mappings of degree 4. Then we evaluate conditioning when augmenting the degree of approximation, i.e. varying qq in the mapping defined as

φ(x)=⨂i=1d[1c[x]ic[x]i2⋯c[x]iq].\varphi(\mathbf{x})=\bigotimes_{i=1}^{d}\left[1\quad c[\mathbf{x}]_i\quad c[\mathbf{x}]_i^2\quad\cdots\quad c[\mathbf{x}]_i^q\right].

The scaling factor cc is computed following the reasoning of subsection A.2.1, here c=(q10q)−1c=(q10^q)^{-1}. The training set P\mathcal{P} of m=αdm=\alpha d elements for α=150\alpha=150, is drawn randomly from a Latin Hypercube Sample (LHS) of 5m5m elements, i.e. we consider linear scaling of the sample with dimension so as to remain in the underdetermined regime. The m-tensor regression is compared to the polynomial kernel

k(x,y)=(1+xTy)q.(19)k(\mathbf{x},\mathbf{y})=(1+\mathbf{x}^{\mathsf{T}}\mathbf{y})^q. \tag*{(19)}

This kernel is sufficient to capture the function. We use it in vanilla kernel regression built as

f~(x)=k(x,P)z,withz=K(P,P)−1y.(20)\widetilde{f}(\mathbf{x})=k(\mathbf{x},\mathcal{P})\mathbf{z},\quad\text{with}\quad\mathbf{z}=K(\mathcal{P},\mathcal{P})^{-1}\mathbf{y}. \tag*{(20)}

The same kernel is used in the kernel Feature Space Approximation (kFSA) method [10] which builds greedily a subsample P~\widetilde{\mathcal{P}} based on a threshold distance in feature space just as our subsampling approach but with an implicit feature map. It is compared with the streamed subsampling approach. We do not include MANDy-like regression as is revealed too heavy on memory. We used the implementations of P. Gelß for MANDy and kFSA as references2. The chosen kernel captures only the polynomial terms that are present in the Rosenbrock function whereas the mapping φ\varphi captures more terms, therefore, we should expect slightly worse results for m-tensor regression based on this mapping.

Error evaluation. The error is evaluated from a test set of 2m2m unseen points from the original LHS. The error is computed as the ℓ2\ell_2 norm of errors over the testing set of points. Let y=[y1y2…y2m]\mathbf{y}=[y_1\quad y_2\quad\ldots\quad y_{2m}] denote the vector of exact outputs for each input in the testing set. Its approximated counterpart is denoted y~\widetilde{\mathbf{y}}, the error we observe is

E=∥y−y~∥2∥y∥2.E=\frac{\lVert\mathbf{y}-\widetilde{\mathbf{y}}\rVert_2}{\lVert\mathbf{y}\rVert_2}.

Results. Figure 6.1 displays the results of the benchmark we conducted in terms of building CPU time, inference time and error of approximation on an unseen test set. In Table 6.1 we give the thresholds selected for each approach and the corresponding number of retained samples (or rank for spectral truncation). Note in the case of spectral truncation that the truncation rank rr is selected as

r=argmin⁡i(1−∑j=1iσj2∑j=1mσj2)st.1−∑j=1iσj2∑j=1mσj2≤ε.r = \underset{i}{\operatorname{argmin}}\left(1-\frac{\sum_{j=1}^{i}\sigma_j^2}{\sum_{j=1}^{m}\sigma_j^2}\right)\quad\text{st.}\quad1-\frac{\sum_{j=1}^{i}\sigma_j^2}{\sum_{j=1}^{m}\sigma_j^2}\leq\varepsilon.

Thresholds for distances in feature spaces were selected to minimize the building error without keeping the full sample3, otherwise least squares m-tensor regression and kernel regression would be more pertinent.

Figure 6.1. (a) Average CPU time to build. (b) Average CPU time to evaluate. (c) Average model error on test set. Figure 6.1: Benchmark of m-tensor regression with kernel regression and kFSA on the Rosenbrock function with varying dimension (dashed lines are cubic and quadratic fits for the building and inference times resp.). The plots show Build CPU time vs. dimension, Inference CPU time vs. dimension, and Approximation L2 error vs. dimension. The methods shown are Kernel reg., MT - lstsq, MT - spec. trunc., MT - subsample, and kFSA.

We demonstrate that our approach outperforms other methods when the dimension grows dramatically. The approach of kFSA relies on a threshold that is harder to interpret since it acts on an implicit feature map, it is easy to settle for one that lowers the number of retained samples but error explodes rapidly (even for comparable amounts to our streamed subsampling approach). If many are kept, we end up confronted to the same result as kernel regression in high dimensions, with a higher overhead to compute. We plotted in dashed lines the best fit for each evolution with the degree given in Table 5.1 to validate our complexity analysis.

Least squaresSpect. Trunc.Subsampling
ConstructionO(α3d3p)O(\alpha^3d^3p)O(αd3p)O(\alpha d^3p)O(α2d3p)O(\alpha^2d^3p) (up. bound)
InferenceO(αd2p)O(\alpha d^2p)O(αd2p)O(\alpha d^2p)O(m~dp)O(\widetilde{m}dp)

Table 5.1. Theoretical complexity evaluations for construction and inference for different regressions.

Dimension10203050100200
m~\tilde{m} kFSA9852724337160921492719461
m~\tilde{m} subsampl.340230512964581889614397
rr spec. trunc.260173121954027935919180
Thresh. kFSA10410^{4}10910^{9}101110^{11}101210^{12}101310^{13}5⋅10145 \cdot10^{14}
Thresh. subsampl.10−610^{-6}10−610^{-6}10−410^{-4}10−310^{-3}2⋅10−22 \cdot10^{-2}2.5⋅10−12.5 \cdot10^{-1}
Thresh. spec. trunc.10−710^{-7}10−710^{-7}10−510^{-5}10−410^{-4}10−310^{-3}10−210^{-2}

Table 6.1. Hyperparameter values and average number of retained samples (or rank) for kFSA, subsampling and spectral truncation.

Figure 6.2a displays the average condition number of the final Gram matrices to be inverted in each method with varying order. Figure 6.2b shows the associated average error. The chosen parameters can be found with the code for the examples. Apart from low orders q∈{2,3}q \in\{2, 3\}, m-tensor regression has a much worse conditioning than kernel regression but the proposed regularizations are effective and lower it by orders of magnitude. The jump in conditionning for kernel-based approaches is due to a switch between the oversampled and the undersampled regime based on the actual dimension of the feature space for the polynomial kernel: (d+qq)\binom{d+q}{q}.

Figure 6.2. Evaluation of the conditioning of the various approaches with respect to the mapping’s or kernel’s degree (continuous line is d=20d = 20 and dashed d=10d = 10). (a) Average condition number of Gram matrices. (b) Average error.

Convergence. We now take interest in the convergence of the model with the size of sample. To that end, we consider 5 models built on LHS of m=αdm = \alpha d elements with d=100d = 100 and α∈{50,100,150,200,250}\alpha\in\{50, 100, 150, 200, 250\}. Each of those models is then tested on 2 unseen LHS of m=αdm = \alpha d elements. We consider m-tensor regression only as the convergence of kernel regression is an already well-studied problem [14]. It should be noted that in comparison with MANDy (function major), kFSA and kernel regression, m-tensor regression aims at building a very large number of features to regress with, as is done with coordinate major MANDy. The features produced by kernel approaches were perfectly fit for the cases we studied but they were not able to manage the growing dimension, either because of stability issues for kernel-based approaches or the larger memory cost for MANDy4. The amount of data needed to keep up with the interpolation limit grows too fast and the amount of features provided to compensate grows very slowly compared with the tensorized feature map. Figure 6.3a shows the difference in growth rate of feature spaces for a polynomial kernel and the tensorized feature map. This demonstrates how tensor regression leverages overfitting to adapt for high dimensional problems with low amounts of data, hence the need for regularization to capture few important features. Both spectral truncation and subsampling lower the effective feature space dimensionality.

Figure 6.3. (a) Comparison of the growth of feature spaces for kernel polynomial regression and tensorized feature map. (b) Error of approximation on unseen data with d=100d = 100 for growing α\alpha (dashed line is the median). Analysis of convergence of the model with the amount of data based on the tensorized feature map.

Figure 6.3b shows the error of the convergence study with growing α\alpha. We can see the relatively slow convergence and the quality of regularization brought by spectral truncation. Subsampling remains around the same order of magnitude for approximately half the inference time. This demonstrates that even with the risk of overfitting, our approach effectively converges with good results at about 1% of error in 100 dimension.

Conclusion and perspectives

In this paper we presented a tensor formalism for high dimensional regression of nonlinear models. The introduced m-tensor formalism is tailored for high dimensional regression in scarce data contexts. By leveraging tensor algebra, we provided properties from kernel methods with good scalability. The formalism smoothly generalizes well-known properties of matrix-based approaches to provide a tensor-structured least squares from a given mapping. We generalized different regularization techniques that aim at making models robust and generalizable from the low amount of data available. Those regularization techniques yield low errors while limiting the scaling when faced with a high number of parameters. The proposed subsampling approach allows for further gains in computational and memory costs.

The m-tensor formalism was shown to circumvent the exponential complexity of high dimensionality with, in the worst case, cubic scaling on the number of parameters. Linear scaling of memory use with the dimension of the problem and a margin for parallel capability are inherited from the separated variables approach. We preserved an explicit feature map instead of an implicit one through a kernel function so as to maintain flexibility along each axis and scale mappings in a systematic way. The resulting non-iterative approach is especially performant in high dimensional contexts compared to state of the art. Its strength is to enrich the feature space exponentially with growing dimension.

The proposed approach was applied on a general benchmark to demonstrate scaling and low relative errors. The behaviour with respect to the dimension, the order of approximation in a polynomial regression and amount of training input are analyzed.

In the future, we will seek different developments, most probably stemming from randomized numerical linear algebra to further accelerate our tools and enhance their scaling. On the application side, the tool seems most adapted to model order reduction, data-driven operator inference, large-scale optimization or classification. The biggest challenge with such a large feature map is that of feature selection, i.e. sparsification of the solution. An expansion of LASSO for ℓ1\ell_1-norm minimization or probabilistic approaches may be of future interest.

Acknowledgements. We acknowledge fundings from the ENSAM RTE Chair, insightful discussions with Antonio Falcò and rich and fruitful exchanges with Jad Mounayer.

Bibliography

Appendix A. Complements for stability analysis

Proofs

In this appendix, we provide proofs for the bounds provided in subsection 4.3 for the numerical stability of our approach.

Proof. (Theorem 4.8) From the assumed structure, we have

φ(x)−φ(x+δx)=⨂i=1dψi([x]i)−⨂i=1dψi([x]i)+ξi([x]i,[δx]i).\varphi(\mathbf{x})-\varphi(\mathbf{x}+\delta\mathbf{x})=\bigotimes_{i=1}^{d}\psi_i([\mathbf{x}]_i)-\bigotimes_{i=1}^{d}\psi_i([\mathbf{x}]_i)+\xi_i([\mathbf{x}]_i,[\delta\mathbf{x}]_i).

Elements of ξi=1d\xi_{i=1}^{d} are assumed weighted by infinitesimal perturbations, then by neglecting all (at least) doubly infinitesimal terms in the product we have

φ(x)−φ(x+δx)≈∑k=1dξk([x]k,[δx]k)⨂i=1i≠kdψi([x]i).\varphi(\mathbf{x})-\varphi(\mathbf{x}+\delta\mathbf{x})\approx\sum_{k=1}^{d}\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\bigotimes_{\substack{i=1\\i\ne k}}^{d}\psi_i([\mathbf{x}]_i).

This leads to the bound in Frobenius norm

∥φ(x+δx)−φ(x)∥F≈∥∑k=1dξk([x]k,[δx]k)⨂i=1i≠kdψi([x]i)∥F,\left\|\varphi(\mathbf{x}+\delta\mathbf{x})-\varphi(\mathbf{x})\right\|_F\approx\left\|\sum_{k=1}^{d}\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\bigotimes_{\substack{i=1\\i\ne k}}^{d}\psi_i([\mathbf{x}]_i)\right\|_F,
≲∥∑k=1dξk([x]k,[δx]k)⨂i=1d−11p∥F,\lesssim\left\|\sum_{k=1}^{d}\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\bigotimes_{i=1}^{d-1}\mathbf{1}_p\right\|_F,
≲∑k=1d∑i1=1p∑i2=1p⋯∑id=1p[ξk([x]k,[δx]k)]i12,\lesssim\sum_{k=1}^{d}\sqrt{\sum_{i_1=1}^{p}\sum_{i_2=1}^{p}\cdots\sum_{i_d=1}^{p}\left[\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\right]_{i_1}^{2}},
≲∑k=1d∑i=1p[ξk([x]k,[δx]k)]i2pd−1,\lesssim\sum_{k=1}^{d}\sqrt{\sum_{i=1}^{p}\left[\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\right]_{i}^{2}p^{d-1}},
≲pd−1∑k=1d∥ξk([x]k,[δx]k)∥F.\lesssim\sqrt{p^{d-1}}\sum_{k=1}^{d}\left\|\xi_k([\mathbf{x}]_k,[\delta\mathbf{x}]_k)\right\|_F.

We assumed a worst normalized case for the bound on ψi=1d\psi_{i=1}^{d} so as to simplify our bound for interpretation. □

Proof. (Lemma 4.9) The lemma stems from the bound of Theorem 4.8 and assumes a constant infinitesimal perturbation [δx]i=1d=O(ϵmachine)[\delta\mathbf{x}]_{i=1}^{d}=O(\epsilon_{\mathrm{machine}}). Then we assumed the element-wise bound [ξi=1d([x]i,[δx]i)]j=1p≤cϵmachine\left[\xi_{i=1}^{d}([\mathbf{x}]_i,[\delta\mathbf{x}]_i)\right]_{j=1}^{p}\le c\epsilon_{\mathrm{machine}} which, plugged into the bound of Theorem 4.8 leads to

∥φ(x+δx)−φ(x)∥F≲pd−1∑k=1d∑i=1pc2ϵmachine2=dcϵmachinepd.\left\|\varphi(\mathbf{x}+\delta\mathbf{x})-\varphi(\mathbf{x})\right\|_F\lesssim\sqrt{p^{d-1}}\sum_{k=1}^{d}\sqrt{\sum_{i=1}^{p}c^2\epsilon_{\mathrm{machine}}^2}=dc\epsilon_{\mathrm{machine}}\sqrt{p^d}.

The bounding constant cϵc_\epsilon is dependent on the choice of mapping and its domain of definition. □

Proof. (Theorem 4.10) We assumed normalized mappings ψi=1d\psi_{i=1}^{d} with separable perturbation-induced terms ξi=1d\xi_{i=1}^{d} and settled that there exists a mapping-dependent constant cc such that ∥ξi(x,δx)∥F≤cp\lVert\boldsymbol{\xi}_i(x,\delta x)\rVert_F \le c\sqrt{p}, which merely assumes ψi=1d\psi_{i=1}^d remains bounded over its domain of definition. Then by denoting

f(x)=φ(x) C,f~(x)=φ(x)(C+δC)andδφ(x,δx)=φ(x)−φ(x+δx),f(x)=\varphi(x)\,\mathbf{C},\qquad\widetilde{f}(x)=\varphi(x)(\mathbf{C}+\delta\mathbf{C})\qquad\text{and}\qquad\delta\varphi(x,\delta x)=\varphi(x)-\varphi(x+\delta x),

the backward error is given from its definition [27] as

∥f~(x)−f(x+δx)∥∥f(x+δx)∥=∥φ(x)C+φ(x)δC−φ(x+δx)C∥∥φ(x+δx)C∥=∥φ(x)C+φ(x)δC−(φ(x)+δφ(x,δx))C∥∥(φ(x)+δφ(x,δx))C∥=∥φ(x)δC−δφ(x,δx)C∥∥(φ(x)+δφ(x,δx))C∥≤∥δC∥∥C∥∥φ(x)∥∥φ(x)+δφ(x,δx)∥+∥δφ(x,δx)∥∥φ(x)+δφ(x,δx)∥.\begin{aligned} \frac{\lVert\widetilde{f}(x)-f(x+\delta x)\rVert}{\lVert f(x+\delta x)\rVert} = \frac{\lVert\varphi(x)\mathbf{C}+\varphi(x)\delta\mathbf{C}-\varphi(x+\delta x)\mathbf{C}\rVert}{\lVert\varphi(x+\delta x)\mathbf{C}\rVert} \\ &= \frac{\lVert\varphi(x)\mathbf{C}+\varphi(x)\delta\mathbf{C}-(\varphi(x)+\delta\varphi(x,\delta x))\mathbf{C}\rVert}{\lVert(\varphi(x)+\delta\varphi(x,\delta x))\mathbf{C}\rVert} \\ &= \frac{\lVert\varphi(x)\delta\mathbf{C}-\delta\varphi(x,\delta x)\mathbf{C}\rVert}{\lVert(\varphi(x)+\delta\varphi(x,\delta x))\mathbf{C}\rVert} \\ &\le \frac{\lVert\delta\mathbf{C}\rVert}{\lVert\mathbf{C}\rVert} \frac{\lVert\varphi(x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert} + \frac{\lVert\delta\varphi(x,\delta x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert}. \end{aligned}

We note that while δφ(x,δx)≪φ(x)\delta\varphi(x,\delta x)\ll\varphi(x), the criterion may be approximated as

∥δC∥∥C∥∥φ(x)∥∥φ(x)+δφ(x,δx)∥+∥δφ(x,δx)∥∥φ(x)+δφ(x,δx)∥≈∥δC∥∥C∥.(21)\frac{\lVert\delta\mathbf{C}\rVert}{\lVert\mathbf{C}\rVert} \frac{\lVert\varphi(x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert} + \frac{\lVert\delta\varphi(x,\delta x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert} \approx \frac{\lVert\delta\mathbf{C}\rVert}{\lVert\mathbf{C}\rVert}. \tag*{(21)}

From the bound provided in Theorem 4.8 and considering the bounding constant cc introduced earlier, we have

∥δφ(x,δx)∥≲dcpd.\lVert\delta\varphi(x,\delta x)\rVert\lesssim dc\sqrt{p^d}.

Assuming the normalized bound ψi=1d≤1p\psi_{i=1}^d\le\mathbf{1}_p, i.e. ∥φ(x)∥≤pd\lVert\varphi(x)\rVert\le\sqrt{p^d}, the left-hand-side of (A.1) is bounded as

∥δC∥∥C∥∥φ(x)∥∥φ(x)+δφ(x,δx)∥+∥δφ(x,δx)∥∥φ(x)+δφ(x,δx)∥≤∥δC∥∥C∥11+dc+dc1+dc.\frac{\lVert\delta\mathbf{C}\rVert}{\lVert\mathbf{C}\rVert} \frac{\lVert\varphi(x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert} + \frac{\lVert\delta\varphi(x,\delta x)\rVert}{\lVert\varphi(x)+\delta\varphi(x,\delta x)\rVert} \le \frac{\lVert\delta\mathbf{C}\rVert}{\lVert\mathbf{C}\rVert}\frac{1}{1+dc} + \frac{dc}{1+dc}.

Thus, guaranteeing dc≪1dc\ll1 lets the backward stability criterion tend only to the relative model error in C\mathbf{C}.

Proof. (Theorem 4.11) We assume the sample P\mathcal{P} to be sufficient and φ\varphi to be well suited to approximate ff, therefore

f(x)=φ(x)C=φ(x)ΦT(ΦΦT)−1y.f(x)=\varphi(x)\mathbf{C}=\varphi(x)\boldsymbol{\Phi}^{\mathsf{T}}(\boldsymbol{\Phi}\boldsymbol{\Phi}^{\mathsf{T}})^{-1}y.

Then, the model error δC\delta\mathbf{C} with the introduction of noise behaves as

Φ(C+δC)=y+δy.\boldsymbol{\Phi}(\mathbf{C}+\delta\mathbf{C})=y+\delta y.

So, following the first assumption, the model computation leads to

δC=ΦT(ΦΦT)−1δy.\delta\mathbf{C}=\boldsymbol{\Phi}^{\mathsf{T}}(\boldsymbol{\Phi}\boldsymbol{\Phi}^{\mathsf{T}})^{-1}\delta y.

Hence the bound

∥δC∥≤∥δy∥σr,\lVert\delta\mathbf{C}\rVert\le\frac{\lVert\delta y\rVert}{\sigma_r},

since we leverage the mode-1 unfolding’s pseudoinverse, whose norm is the reciprocal of the lowest nonzero singular value σr\sigma_r.

Stability for given mappings

We state in the paper that the choice of mapping implies the study of input perturbation. We provide that analysis for the generic canonical polynomial mapping and a trigonometric polynomial mapping.

Polynomial mapping

We consider perturbation δx\delta x in the input to assess stability as defined in the case of the canonical 1D degree qq polynomial basis, so we consider

ψ(x+δx)=[1x+δx(x+δx)2…(x+δx)q].(22)\boldsymbol{\psi}(x+\delta x)=\left[1\quad x+\delta x\quad(x+\delta x)^2\quad\ldots\quad(x+\delta x)^q\right]. \tag*{(22)}

We immediately see how the choice of basis and normalization will influence stability. The dd-dimensional tensorization of such bases will lead to the evaluation

φ(x+δx)=⨂i=1dψ([x]i+[δx]i).(23)\boldsymbol{\varphi}(\mathbf{x}+\boldsymbol{\delta x})=\bigotimes_{i=1}^{d}\boldsymbol{\psi}([x]_i+[\delta x]_i). \tag*{(23)}

We manage to identify and separate the term due to input perturbation along each dimension by developping the basis (A.2) as

ψ(x+δx)=[1x+δxx2+2xδx+δx2…∑k=0q(qk)xkδxq−k].\boldsymbol{\psi}(x+\delta x)=\left[1\quad x+\delta x\quad x^2+2x\delta x+\delta x^2\quad\ldots\quad\sum_{k=0}^{q}\binom{q}{k}x^k\delta x^{q-k}\right].

In a first order approximation, we may separate that basis as ψ(x+δx)≈ψ(x)+ξ(x,δx)\boldsymbol{\psi}(x+\delta x)\approx\boldsymbol{\psi}(x)+\boldsymbol{\xi}(x,\delta x) where

ξ(x,δx)=[0δx2xδx…qxq−1δx].(24)\boldsymbol{\xi}(x,\delta x)=\left[0\quad\delta x\quad2x\delta x\quad\ldots\quad qx^{q-1}\delta x\right]. \tag*{(24)}

Therefore the multidimensional basis φ\boldsymbol{\varphi} inherits the partition

φ(x+δx)≈φ(x)+δφ(x,δx)=φ(x)+∑i=1dξ([x]i,[δx]i)⨂j=1j≠idψ([x]j).(25)\boldsymbol{\varphi}(\mathbf{x}+\boldsymbol{\delta x})\approx\boldsymbol{\varphi}(\mathbf{x})+\delta\boldsymbol{\varphi}(\mathbf{x},\boldsymbol{\delta x})=\boldsymbol{\varphi}(\mathbf{x})+\sum_{i=1}^{d}\boldsymbol{\xi}([x]_i,[\delta x]_i)\bigotimes_{\substack{j=1\\j\ne i}}^{d}\boldsymbol{\psi}([x]_j). \tag*{(25)}

We stated in Theorem 4.10 that we need to identify a bounding constant cc from ξi=1d\boldsymbol{\xi}_{i=1}^{d} to assess the scaling to apply to remain stable. Let each [x]ii=1d[x]_i{}_{i=1}^{d} be defined over an interval [ai,bi]i=1d⊂R[a_i,b_i]_{i=1}^{d}\subset\mathbb{R}, then we can consider

∥ξi([x]i,[δx]i)∥F<qmax⁡(∣ai∣,∣bi∣)q−1[δx]iq.\left\|\boldsymbol{\xi}_i([x]_i,[\delta x]_i)\right\|_F<q\max(|a_i|,|b_i|)^{q-1}[\delta x]_i\sqrt{q}.

with quite a margin. Therefore, we may uniformly scale down ψi=1d\boldsymbol{\psi}_{i=1}^{d} with a factor O(1/qmax⁡(∣ai∣,∣bi∣)q−1)O(1/q\max(|a_i|,|b_i|)^{q-1}). Note that for this mapping to be normalized element-wise, it is required that

max⁡(∣ai∣,∣bi∣)≤1.\max(|a_i|,|b_i|)\le1.

The scale-down approach will not affect conditioning of the regression (which can be tackled with any proposed regularization technique) and guarantees stability as dc≪1dc\ll1 seeing Theorem 4.10.

Trigonometric mapping

For trigonometric approximation, we consider the 1D mapping

ψ(x+δx)=[1sin⁡(x+δx)sin⁡2(x+δx)…sin⁡q(x+δx)].(26)\boldsymbol{\psi}(x+\delta x)=\left[1\quad\sin(x+\delta x)\quad\sin^2(x+\delta x)\quad\ldots\quad\sin^q(x+\delta x)\right]. \tag*{(26)}

This can be analogously developed for a basis in cos⁡1≤i≤q(x+δx)\cos^{1\le i\le q}(x+\delta x). Those are naturally normalized element-wise. We start by noting that

sin⁡(x+δx)=sin⁡(x)−cos⁡(x)tan⁡(δx) and cos⁡(x+δx)=cos⁡(x)−sin⁡(x)tan⁡(δx).\sin(x+\delta x)=\sin(x)-\cos(x)\tan(\delta x)\text{ and }\cos(x+\delta x)=\cos(x)-\sin(x)\tan(\delta x).

Then by applying the polynomial case we can identify the structure of (A.5) with, for the polynomial sine basis,

ξ(x,δx)=[0−cos⁡(x)tan⁡(δx)⋯−qsin⁡q−1(x)cos⁡(x)tan⁡(δx)].\xi(x,\delta x) = [0 \quad-\cos(x)\tan(\delta x) \quad\cdots\quad-q\sin^{q-1}(x)\cos(x)\tan(\delta x)].

Choosing a loose bound from an element-wise worst case, we can provide

∥ξ(x,δx)∥F<q(1−1q)q−12tan⁡(δx)p.\lVert\xi(x,\delta x)\rVert_F < \sqrt{q}\left(1-\frac{1}{q}\right)^{\frac{q-1}{2}}\tan(\delta x)\sqrt{p}.

so that scaling uniformly with a factor O(q−1/2(1−q−1)(1−q)/2)O(q^{-1/2}(1-q^{-1})^{(1-q)/2}) each 1D mapping will preserve the stability criterion of Theorem 4.10. This value comes from considering

[ξid(x,δx)]j=1p=max⁡x(∣−qsin⁡q−1(x)cos⁡(x)tan⁡(δx)∣)[\xi_i^d(x,\delta x)]_{j=1}^{p}=\max_x\left(\left|-q\sin^{q-1}(x)\cos(x)\tan(\delta x)\right|\right)

as a function of qq.

Algorithms to subsample the operator

In this section we provide algorithms to compute subsampled m-tensors. We provide two ways of constructing it. The first is the streamed way, inspired from online learning of streamed data. We qualify the second as the greedy decomposition. We first review the streamed way and then provide arguments for the more costful greedy decomposition. We note that review of randomized numerical linear algebra and the work of Mahoney and Drineas on CUR matrix decomposition [20] lead us to seek a near optimal greedy algorithm leveraging randomized approaches with a low computational cost and preserving the efficiency of the streamed approach instead of the current greedy approach, closer to the pseudoskeleton approach of Goreinov et al. [12]. We settle notations for this section: we consider an m-tensor T\mathbf{T} with c-dim mm and provide its decomposition based on a subsample with a tolerance ε\varepsilon as

∥T−WT~∥2≤ε.\lVert\mathbf{T}-\mathbf{W}\widetilde{\mathbf{T}}\rVert^2\leq\varepsilon.

In the remainder of the section, we give a geometric interpretation to the incremental construction of the subset of rows from a given m-tensor. We consider each row to be a point in a high dimensional space. Providing the distance definition from the inner product of two of those points.

Streamed decomposition

The streamed construction of the subset considers that we sweep once through the rows of an m-tensor T\mathbf{T} or treat rows as they are streamed to select the subset on-the-fly.

Elements 1 and 2. The first provided row [T]1[\mathbf{T}]_1 is used by default to initialize T~\widetilde{\mathbf{T}}. Weights W1W_1 are initialized as an array containing only 1. We define

L1=∥[T]1∥.L_1=\lVert[\mathbf{T}]_1\rVert.

From that given point, we build a subspace span⁡({[T]1})\operatorname{span}(\{[\mathbf{T}]_1\}). For the next point, we evaluate the distance to that subspace. For a new row [T]2[\mathbf{T}]_2, we compute δ2\delta_2 defined as

δ2=min⁡w∈R∥[T]2−w[T]1∥2(27)\delta_2=\min_{w\in\mathbb{R}}\lVert[\mathbf{T}]_2-w[\mathbf{T}]_1\rVert^2 \tag*{(27)}

where the minimizing ww is obtained by expanding the norm in the definition of δ\delta and deriving the minimum of a quadratic polynomial in ww, yielding

w=⟨[T]1,[T]2⟩∥[T]1∥2.w=\frac{\langle[\mathbf{T}]_1,[\mathbf{T}]_2\rangle}{\lVert[\mathbf{T}]_1\rVert^2}.

Using that minimizer, δ\delta will be given by

δ2=∥[T]2∥2−(⟨[T]2,[T]1⟩∥[T]1∥2)2.\delta_2 = \lVert[\mathbf{T}]_2\rVert^2-\left(\frac{\langle[\mathbf{T}]_2,[\mathbf{T}]_1\rangle}{\lVert[\mathbf{T}]_1\rVert^2}\right)^2.

By comparing δ2\delta_2 to the precision criterion ε\varepsilon, the point is kept or not. If it is kept, [T]2[\mathbf{T}]_2 is appended to T~\widetilde{\mathbf{T}} and LL is updated as

L2=[L10s∥[T]2∥2−s2],with s=⟨[T]1,[T]2⟩L1.L_2=\begin{bmatrix}L_1&0\\s&\sqrt{\lVert[\mathbf{T}]_2\rVert^2-s^2}\end{bmatrix}, \qquad\text{with }s=\frac{\langle[\mathbf{T}]_1,[\mathbf{T}]_2\rangle}{L_1}.

The weight matrix WW is updated as

W2=[W1001]if δ2≥ε,W2=[W1w]otherwise.W_2=\begin{bmatrix}W_1&0\\0&1\end{bmatrix}\quad\text{if }\delta_2\geq\varepsilon,\qquad W_2=\begin{bmatrix}W_1\\w\end{bmatrix}\quad\text{otherwise}.

Element kk. Consider we retained k~\widetilde{k} elements in T~\widetilde{\mathbf{T}} until that point. This means we need to evaluate the distance of [T]k[\mathbf{T}]_k to a k~\widetilde{k}-dimensional subspace. We define the vector b\mathbf{b} from the already selected rows and the new one as

b=T~×[T]kT.\mathbf{b}=\widetilde{\mathbf{T}}\times[\mathbf{T}]_k^{\mathsf{T}}.

The squared distance δk\delta_k between [T]k[\mathbf{T}]_k and span⁡(T~)\operatorname{span}(\widetilde{\mathbf{T}}) is given as

δk=min⁡w∥[T]k−w⋅T~∥2=∥[T]k∥2−bTP~−1b,(28)\delta_k=\min_{\mathbf{w}}\left\lVert[\mathbf{T}]_k-\mathbf{w}\cdot\widetilde{\mathbf{T}}\right\rVert^2=\lVert[\mathbf{T}]_k\rVert^2-\mathbf{b}^{\mathsf{T}}\widetilde{P}^{-1}\mathbf{b}, \tag*{(28)}

where P~=T~×T~T\widetilde{P}=\widetilde{\mathbf{T}}\times\widetilde{\mathbf{T}}^{\mathsf{T}} admits a Cholesky decomposition with factor Lk~L_{\widetilde{k}}. Therefore by computing the vector s=Lk~−1b\mathbf{s}=L_{\widetilde{k}}^{-1}\mathbf{b} by downward backsubstitution, the squared distance δk\delta_k can be efficiently computed from bTP~−1b=sTs=∥s∥2\mathbf{b}^{\mathsf{T}}\widetilde{P}^{-1}\mathbf{b}=\mathbf{s}^{\mathsf{T}}\mathbf{s}=\lVert\mathbf{s}\rVert^2. If δk>ε\delta_k>\varepsilon, [T]k[\mathbf{T}]_k is appended to T~\widetilde{\mathbf{T}}. The Cholesky factor is updated as

Lk~+1=[Lk~0sT∥[T]k∥2−∥s∥2].L_{\widetilde{k}+1}=\begin{bmatrix}L_{\widetilde{k}}&0\\\mathbf{s}^{\mathsf{T}}&\sqrt{\lVert[\mathbf{T}]_k\rVert^2-\lVert\mathbf{s}\rVert^2}\end{bmatrix}.

The weight matrix WW is updated as

Wk+1=[Wk001]if δk≥ε,Wk+1=[WkwT]otherwise,W_{k+1}=\begin{bmatrix}W_k&0\\0&1\end{bmatrix}\quad\text{if }\delta_k\geq\varepsilon,\qquad W_{k+1}=\begin{bmatrix}W_k\\\mathbf{w}^{\mathsf{T}}\end{bmatrix}\quad\text{otherwise},

with w=(Lk~T)−1s\mathbf{w}=(L_{\widetilde{k}}^{\mathsf{T}})^{-1}\mathbf{s} computed by upward backsubstitution. This construction loops only once on the rows of T\mathbf{T} and leverages the incrementally constructed Cholesky factors Lk~L_{\widetilde{k}}. It is fit for streamed data if the criterion on squared distance ε\varepsilon can be chosen a priori. Algorithm B.1 sums up the approach.

Greedy decomposition

From the same notations, we propose an iterative approach during which we add the best choice among all rows of T\mathbf{T} at each step, i.e. the greedy version.

Element 1. The first row of T~\widetilde{\mathbf{T}} is selected so that its span minimizes the sum of distances with the other rows. To evaluate the distance of all points to the subspaces spanned by each points, we build the matrix Δ1∈Rm×m\Delta_1\in\mathbb{R}^{m\times m} as

[Δ1]ij=δij1,δij1=min⁡w∈R∥[T]i−w[T]j∥2.(29)[\Delta_1]_{ij}=\delta_{ij}^{1},\qquad\delta_{ij}^{1}=\min_{\mathbf{w}\in\mathbb{R}}\left\lVert[\mathbf{T}]_i-\mathbf{w}[\mathbf{T}]_j\right\rVert^2. \tag*{(29)}

Algorithm B.1 Streamed subsample construction

Input: T\mathbf{T}, ε\varepsilon

Output: T~\widetilde{\mathbf{T}}, WW

T~←[T]1\widetilde{\mathbf{T}} \leftarrow[\mathbf{T}]_1 ▷ Initialize reduced m-tensor L1←∥[T]1∥L_1 \leftarrow\|[\mathbf{T}]_1\| ▷ Initialize Cholesky factor k~←1\widetilde{k} \leftarrow1 ▷ Initialize row index in reduced m-tensor W←[1]W \leftarrow[1] ▷ Initialize weights

for any new [T]k[\mathbf{T}]_k, k>1k>1 do ▷ Loop on rows of initial T\mathbf{T} or streamed data &nbsp;&nbsp;b←T~×[T]k\mathbf{b} \leftarrow\widetilde{\mathbf{T}} \times[\mathbf{T}]_k ▷ Compute b\mathbf{b} &nbsp;&nbsp;s←Lk~−1b\mathbf{s} \leftarrow L_{\widetilde{k}}^{-1}\mathbf{b} ▷ Compute s\mathbf{s} by backsubstitution &nbsp;&nbsp;δk←∥[T]k∥2−sTs\delta_k \leftarrow\|[\mathbf{T}]_k\|^2-\mathbf{s}^{\mathsf{T}}\mathbf{s} ▷ Evaluate δk\delta_k &nbsp;&nbsp;if δk>ε\delta_k>\varepsilon then ▷ Compare distance to threshold &nbsp;&nbsp;&nbsp;&nbsp;T~←[T~ [T]kT]T\widetilde{\mathbf{T}} \leftarrow[\widetilde{\mathbf{T}}\ [\mathbf{T}]_k^{\mathsf{T}}]^{\mathsf{T}} ▷ Update reduced m-tensor T~\widetilde{\mathbf{T}} &nbsp;&nbsp;&nbsp;&nbsp;k~←k~+1\widetilde{k} \leftarrow\widetilde{k}+1 ▷ Update number of kept tensors k~\widetilde{k} &nbsp;&nbsp;&nbsp;&nbsp;Lk~←[Lk~−10sT∥[T]k∥2−sTs]L_{\widetilde{k}} \leftarrow\begin{bmatrix} L_{\widetilde{k}-1} & 0 \\ \mathbf{s}^{\mathsf{T}} & \sqrt{\|[\mathbf{T}]_k\|^2-\mathbf{s}^{\mathsf{T}}\mathbf{s}} \end{bmatrix} ▷ Update Cholesky factor LL &nbsp;&nbsp;&nbsp;&nbsp;W←[W001]W \leftarrow\begin{bmatrix} W & 0 \\ 0 & 1 \end{bmatrix} ▷ Update weights WW &nbsp;&nbsp;else &nbsp;&nbsp;&nbsp;&nbsp;W←[W  (Lk~T)−1s]TW \leftarrow[W\ \ (L_{\widetilde{k}}^{\mathsf{T}})^{-1}\mathbf{s}]^{\mathsf{T}} ▷ Update weights WW &nbsp;&nbsp;end if end for return T~,W\widetilde{\mathbf{T}}, W

Each element is defined analogously to the squared distance (B.1). We compute the contraction of each column vector of Δ1\Delta_1 and select the first row of T~\widetilde{\mathbf{T}} so as to minimize that sum. If all distances in the column vector corresponding to the selected point were below the precision tolerance ε\varepsilon, then T~\widetilde{\mathbf{T}} would be sufficient and the algorithm would end there. Note that i) the elements of Δ1\Delta_1 can be built from the elements of P=T×TTP=\mathbf{T}\times\mathbf{T}^{\mathsf{T}} and ii) Δ1\Delta_1 is not symmetric.

Element kk. The kk-th row of T~\widetilde{\mathbf{T}}, k>1k>1 is selected so that the subspace

span⁡({[T~]i, 1≥i≥k})\operatorname{span}\left(\left\{[\widetilde{\mathbf{T}}]_i,\ 1\ge i\ge k\right\}\right)

minimizes the distances to all remaining points. In order to evaluate these distances, we denote T‾k\overline{\mathbf{T}}_k the m-tensor T\mathbf{T} with rows previously selected in T~\widetilde{\mathbf{T}} masked. We define

∀ j, 1≤j≤m−k,T~j=[T~  [T‾k]j]T\forall\ j,\ 1\le j\le m-k,\qquad\widetilde{\mathbf{T}}_j=\left[\widetilde{\mathbf{T}}\ \ [\overline{\mathbf{T}}_k]_j\right]^{\mathsf{T}}

as each possible augmentation of the subsample. At step kk we define the matrix Δk∈R(m−k)×(m−k)\Delta_k\in\mathbb{R}^{(m-k)\times(m-k)} element-wise as

[Δk]ij=min⁡w∥[T‾i]j−wTT~j∥2.(30)[\Delta_k]_{ij}=\min_{\mathbf{w}}\left\|[\overline{\mathbf{T}}_i]_j-\mathbf{w}^{\mathsf{T}}\widetilde{\mathbf{T}}_j\right\|^2. \tag*{(30)}

Each element is constructed analogously to (B.2). We contract the columns of Δk\Delta_k to obtain a vector δk\boldsymbol{\delta}_k whose elements are sums of squared distances. We select the index of the best choice in the rows of T‾k\overline{\mathbf{T}}_k as the minimizer

ı^=argmin⁡i([δk]i).\hat{\imath}=\operatorname*{argmin}_i([\boldsymbol{\delta}_k]_i).

The corresponding row [Tˉk]ı^[\bar{\mathbf{T}}_{k}]_{\hat{\imath}} is appended to T~\tilde{\mathbf{T}} and masked for following iterations. If all distances in the ı^\hat{\imath}-th column of Δk\Delta_{k} are below ε\varepsilon, the precision criterion is reached and the algorithm is stopped. Otherwise, operators are updated and the loop continues.

Once the optimal T~\tilde{\mathbf{T}} of size m~\tilde{m} is computed, we evaluate the weight matrix using the projector onto the span of T~\tilde{\mathbf{T}} denoted by ΠT~\Pi_{\tilde{\mathbf{T}}} and defined as

ΠT~=T~⊤×(T~×T~⊤)−1×T~.\Pi_{\tilde{\mathbf{T}}} = \tilde{\mathbf{T}}^{\top} \times\left(\tilde{\mathbf{T}} \times\tilde{\mathbf{T}}^{\top}\right)^{-1} \times\tilde{\mathbf{T}}.

We identify the weights in the projection of T\mathbf{T}

T×ΠT~=WT~.(31)\mathbf{T} \times\Pi_{\tilde{\mathbf{T}}} = \mathbf{W}\tilde{\mathbf{T}}. \tag*{(31)}

We provide Algorithm B.2 to build the greedy subsample from a full m-tensor.

Algorithm B.2 Greedy subsample construction

Input: T\mathbf{T}, ε\varepsilon Output: T~\tilde{\mathbf{T}}, W\mathbf{W}

Build matrix Δ1\Delta_{1} from (B.3)

[δ1]i←∑j=1m[Δ1]ji[\delta_{1}]_{i} \leftarrow\sum_{j=1}^{m}[\Delta_{1}]_{ji} ▷ Sum columns of Δ1\Delta_{1}

T~←[T]ı^\tilde{\mathbf{T}} \leftarrow[\mathbf{T}]_{\hat{\imath}}, ı^=arg min⁡i([δ1]i)\hat{\imath} = \operatorname*{arg\,min}_{i}([\delta_{1}]_{i}) ▷ Select first element of T~\tilde{\mathbf{T}}

L1←[∥T~∥]L_{1} \leftarrow[\lVert\tilde{\mathbf{T}}\rVert] ▷ Initialize Cholesky factor

Define Tˉ1\bar{\mathbf{T}}_{1} by masking ı^\hat{\imath}-th row of T\mathbf{T}

for kk, 1<k≤m1 < k \le m do ▷ Loop on rows of T\mathbf{T}

Build matrix Δk\Delta_{k} from (B.4)

[δk]i←∑j=1m−k[Δk]ji[\delta_{k}]_{i} \leftarrow\sum_{j=1}^{m-k}[\Delta_{k}]_{ji} ▷ Sum columns of Δk\Delta_{k} in vector δk\delta_{k}

ı^=arg min⁡i([δk]i)\hat{\imath} = \operatorname*{arg\,min}_{i}([\delta_{k}]_{i}) ▷ Find optimal column index ı^\hat{\imath}

T~←[T~ [Tˉ]ı^]\tilde{\mathbf{T}} \leftarrow[\tilde{\mathbf{T}}\ [\bar{\mathbf{T}}]_{\hat{\imath}}] ▷ Append ı^\hat{\imath}-th row of Tˉ\bar{\mathbf{T}} as kk-th row of T~\tilde{\mathbf{T}}

if ∀j\forall j, 1≤j≤m−k1 \le j \le m-k, [Δ]jı^≤ε[\Delta]_{j\hat{\imath}} \le\varepsilon then ▷ All dist. to current subspace under ε\varepsilon

Break loop

else

Update Tˉk+1\bar{\mathbf{T}}_{k+1} by masking ı^\hat{\imath}-th row of Tˉk\bar{\mathbf{T}}_{k}

end if

end for

Compute weights W\mathbf{W} from (B.5)

return T~\tilde{\mathbf{T}}, W\mathbf{W}

References

  1. [1]A. Ammar, F. Chinesta, and A. Falcò. “On the Convergence of a Greedy Rank-One Update Algorithm for a Class of Linear Systems”. In: Arch Comput Methods Eng 17 (2010), pp. 473–486. DOI: 10.1007/s11831-010-9048-z.DOI
  2. [2]A. Ammar et al. “A new family of solvers for some classes of multidimensional partial differential equations encountered in kinetic theory modeling of complex fluids”. In: Journal of Non-Newtonian Fluid Mechanics 139.3 (2006), pp. 153–176. ISSN: 0377-0257. DOI: 10.1016/j.jnnfm.2006.07.007.DOI
  3. [3]P.J. Baddoo et al. “Kernel learning for robust dynamic mode decomposition: linear and nonlinear disambiguation optimization”. In: Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 478.2260 (2022), p. 20210830. DOI: 10.1098/rspa.2021.0830.DOI
  4. [4]R. Bellman, Rand Corporation, and Karreman Mathematics Research Collection. Dynamic Programming. Rand Corporation research study. Princeton University Press, 1957. ISBN: 9780691079516.
  5. [5]G. Beylkin and M.J. Mohlenkamp. “Algorithms for Numerical Analysis in High Dimensions”. In: SIAM Journal on Scientific Computing 26.6 (2005), pp. 2133–2159. DOI: 10.1137/040604959.DOI
  6. [6]D. Borzacchiello, J.V. Aguado, and F. Chinesta. “Non-intrusive Sparse Subspace Learning for Parametrized Problems”. In: Archives of Computational Methods in Engineering 26 (2019), pp. 303–326. ISSN: 1886-1784. DOI: 10.1007/s11831-017-9241-4.
  7. [7]S.L. Brunton and N.J. Kutz. Data-Driven Science and Engineering: Machine Learning, Dynamical Systems, and Control. 2nd ed. Cambridge University Press, 2022. DOI: 10.1017/9781009089517.DOI
  8. [8]Y. Engel, S. Mannor, and R. Meir. “The kernel recursive least-squares algorithm”. In: IEEE Transactions on Signal Processing 52.8 (2004), pp. 2275–2285. DOI: 10.1109/TSP.2004.830895.DOI
  9. [9]T.G. Kolda G. Ballard. Tensor Decompositions for Data Science. Cambridge University Press, 2025. ISBN: 9781009471671.DOI
  10. [10]P. Gels et al. “Feature space approximation for kernel-based supervised learning”. In: Knowledge-Based Systems 221 (2021), p. 106935. ISSN: 0950-7051. DOI: 10.1016/j.knosys.2021.106935.
  11. [11]P. Gels et al. “Multidimensional Approximation of Nonlinear Dynamical Systems”. In: Journal of Computational and Nonlinear Dynamics 14.6 (2019), 061 006. ISSN: 1555-1415. DOI: 10.1115/1.4043148.
  12. [12]S.A. Goreinov, E.E. Tyrtyshnikov, and N.L. Zamarashkin. “A theory of pseudoskeleton approximation”. In: Linear Algebra and its Applications 261.1 (1997), pp. 1–21. ISSN: 0024-3795. DOI: 10.1016/S0024-3795(96)00301-1.DOI
  13. [13]W. Hackbusch. Tensor Spaces and Numerical Tensor Calculus. 2nd ed. Vol. 42. Springer Cham, 2019. ISBN: 978-3-030-35553-1. DOI: 10.1007/978-3-030-35554-8.DOI
  14. [14]A. Christmann I. Steinwart. Support Vector Machines. 1st ed. Springer New York, 2008. ISBN: 978-0-387-77242-4. DOI: 10.1007/978-0-387-77242-4.DOI
  15. [15]R. Ibáñez et al. “A Multidimensional Data-Driven Sparse Identification Technique: The Sparse Proper Generalized Decomposition”. In: Complexity 2018 (2018), pp. 1–11. DOI: 10.1155/2018/5608286.DOI
  16. [16]K.L. Judd et al. “Smolyak method for solving dynamic economic models: Lagrange interpolation, anisotropic grid and adaptive domain”. In: Journal of Economic Dynamics and Control 44.C (2014), pp. 92–123. DOI: 10.1016/j.jedc.2014.03.00.
  17. [17]S. Klus and P. Gels. “Tensor-Based Algorithms for Image Classification”. In: Algorithms 12.11 (2019). ISSN: 1999-4893. DOI: 10.3390/a12110240.DOI
  18. [18]T.G. Kolda and B.W. Bader. “Tensor Decompositions and Applications”. In: SIAM Review 51.3 (2009), pp. 455–500. DOI: 10.1137/07070111X.DOI
  19. [19]C.F. Van Loan. “The ubiquitous Kronecker product”. In: Journal of Computational and Applied Mathematics 123.1 (2000). Numerical Analysis 2000. Vol. III: Linear Algebra, pp. 85–100. ISSN: 0377-0427. DOI: 10.1016/S0377-0427(00)000393-9.DOI
  20. [20]M.W. Mahoney and P. Drineas. “CUR matrix decompositions for improved data analysis”. In: Proceedings of the National Academy of Sciences 106.3 (2009), pp. 697–702. DOI: 10.1073/pnas.0803205106.DOI
  21. [21]J. Mercer. “XVI. Functions of positive and negative type, and their connection the theory of integral equations”. In: Philosophical Transactions of the Royal Society of London. Series A, Containing Papers of a Mathematical or Physical Character 209.441-458 (1909), pp. 415–446. DOI: 10.1098/rsta.1909.0016.DOI
  22. [22]I.V. Oseledets. “Tensor-Train Decomposition”. In: SIAM Journal on Scientific Computing 33.5 (2011), pp. 2295–2317. DOI: 10.1137/090752286.DOI
  23. [23]R. Penrose. “A generalized inverse for matrices”. In: Mathematical Proceedings of the Cambridge Philosophical Society 51.3 (1955), pp. 406–413. DOI: 10.1017/S0305004100030401.DOI
  24. [24]B. Schölkopf and A.J. Smola. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2001. ISBN: 9780262256933. DOI: 10.7551/mitpress/4175.001.0001.DOI
  25. [25]B. Schölkopf, A.J. Smola, and K.-R. Müller. “Nonlinear Component Analysis as a Kernel Eigenvalue Problem”. In: Neural Computation 10.5 (1998), pp. 1299–1319. ISSN: 0899-7667. DOI: 10.1162/089976698300017467.DOI
  26. [26]V.I. Slyusar. “A family of face products of matrices and its properties.” In: Cybern Syst Anal (1999), pp. 379–384. DOI: 10.1007/BF02733426.DOI
  27. [27]L.N. Trefethen and D. Bau. Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1997. DOI: 10.1137/1.9780898719574.DOI

Paper details

vlnc:W_7rm7t9xx
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents