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 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. ) are used for tensors. Uppercase symbols (e.g. ) are used for matrices. Lowercase bold symbols (e.g. ) are used for vectors. The notation denotes the -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 of order will be denoted as . We denote the identity of size as and the vector of ones of size as .
Least squares approximation of a scalar function
In order to provide a general approach, let denote a -dimensional domain, defined as the cartesian product of one-dimensional intervals in , i.e. , . The aim is to approximate a scalar function defined over that domain. Let denote basis functions to be chosen, we give an approximation of with the form
where coefficients are the best fit (in the least squares sense) for the chosen basis functions. The number of terms depends on the choice of bases as well. Let denote a set of distinct samples in such that
Consider we are given the evaluation of at each sample of . We denote the vector defined as
Let denote the evaluation of bases used in (2.1) over the set . With denoting the -th row of , we have
Then, the least squares solution is the one that, for any given bases , minimizes the squared error with respect to :
This minimization problem admits an explicit solution based on whether has linearly independent columns (2.3) or rows (2.4) that we build using the Moore-Penrose inverse formulation [23]:
We use this widely used explicit formulation of least squares solution to determine the coefficients of the approximation. Without any prior knowledge of , the aim is then to define basis functions such that is well approximated. To that end, one can choose to tailor the functions in order to minimize or provide a rich enough set of bases so that all features of 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 are sought as products of one-dimensional functions. We denote those one-dimensional functions and define multidimensional bases as
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 denote the vector of one-dimensional basis functions deemed rich enough to represent the problem in one dimension given as
All combinations of one-dimensional bases would be found without redundancy in the elements of the tensor defined as
We note that is a rank-1 tensor of order . 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 in (1) can be written as the inner product
Here is an order tensor of coefficients. The least squares coefficient tensor is the one minimizing the error with respect to :
If we were to vectorize this tensor formulation, we would find the expression given for (1) with . 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 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 , we define their row-wise tensor product, building an order tensor as
We show in this paper how well-suited tensors built that way are for multilinear regression. We refer to the matrices as cores of the m-tensor . 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 , results in a dense matrix in . That unfolding is exactly equal to the face-splitting product of its cores defined using notations introduced by Slyusar [26] as
:::`
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 built as the -tensor product of cores , its transpose is given as
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 be two arbitrary tensors. Their inner product is defined as
That computation scales as considering , . This definition naturally leads to the norm . 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 defined as rank-1 tensors, respectively
where , , . Then the complexity of their inner product falls to considering , for ease of notation.
Proof. From the rank-1 structure of and and Definition 4.4, we have
This simplifies the -dimensional problem and allows to separately evaluate vector inner products, hence the 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 -way contracted product.
Definition 4.6. (D-way contracted product). Let and , their -way contracted product, denoted , is given as
In a general setting, that product is computed with complexity , by considering for ease of notation that and , . We can however give a special case when considering m-tensors.
Proposition 4.7. Let and be -tensors respectively based on cores and . Their -way contracted product is computed as
Considering, for ease of notation that and , , the complexity of this product is .
Proof. Starting from the general case of -way contracted product given in Definition 4.6 and proceeding element-wise, we identify inner products of rank-1 tensors, whose complexity scales as as proven for Proposition 4.5. Considering we have of those products to compute. This amounts to computing the Hadamard product of Gram matrices as given in the proposition, hence the complexity considering and , , .
Least squares approximation
From those definitions we can build our framework. Provided the set of sampled parameters and corresponding evaluations of in a vector , we define the basis functions tensor as
This structure amounts to combining one-dimensional bases for all input parameters. This gives us a large approximation capability, unreachable with a matrix-based regression. We define the cores
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 -tensor regression operator as
We can now reformulate the regression problem in -tensorial setting. We seek the regression coefficients such that
A least squares solution to this problem can be built explicitly based on the general pseudoinverse formulation (2.4). Provided that has linearly independent rows, we have the solution
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 will prevent it to have linearly independent columns as it would require to grow exponentially with . 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 as
This expression shows explicitly how it results only in efficient operations. In fact, by computing
we evaluate only by computing and its inner product with :
This evaluation’s complexity scales as . 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 is built upon a sample of elements and a tensorized mapping . We assume the mappings to be able to capture , i.e.
In that section we drop the for ease of reading. All proofs are developed in section A. We assume the function , evaluated over in the vector and denote the approximation we build . We will consider input perturbation 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 ). Let denote a 1D mapping error due to input perturbation such that the separated variables representation yields
Let the 1D mappings be normalized element-wise, then the evaluation error of is bounded as
Theorem 4.8 demonstrates the necessity to analyze the behaviour of the terms 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 of be perturbed with , then there exists a mapping-dependent constant such that
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 , , denote normalized 1D mappings with separable perturbation-induced errors of the shape . Let denote a constant such that over its domain of definition
Then if , the backward error tends to
Theorem 4.10 tells us that controlling the bounding constant , 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 . 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 . Thus we may consider the SVD of that unfolding
We can access and through the eigendecomposition of
This gives us an easy read on the effective condition number of given by
where denotes the largest singular value in and its lowest nonzero singular value. Then we can assess noise sensitivity by assuming the perturbations .
Theorem 4.11. (Noise sensitivity). Assuming the sampled points are sufficient and that the basis is well suited to approximate , then the error stemming from data noise is bounded as
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 samples, the rank is at most 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 are. In this section, we denote .
Tikhonov regularization
Analogously to the matrix case, Tikhonov regularization for -tensors is given as
This results in a uniform lifting of the eigenvalues of , hence the conditioning improvement. The approximation of with Tikhonov regularization is then given by evaluating the inner product
This approaches’ complexity is dominated by the inversion scaling as and the construction of itself, scaling as . Inference, given in (16), has a complexity .
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 appear, where . Thus, considering the mapping
we can derive a kernel function defined as the inner product
Therefore we are guaranteed to build a symmetric positive semidefinite kernel. Assuming the 1D mappings to be continuous on compact domains (such as intervals of ), 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 -tensor framework a truncated kernel PCA [25]. Keeping only the first principal components in feature space assures us to preserve the optimal -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 or up to a prescribed rank . We apply it to -tensor regression through the eigenvalues of . Let denote the matrix built from the first eigenvectors of . The regularized coefficients are then given by
The resulting approximation is computed as the inner product
This approach results in a complexity dominated by the computation of the SVD of , i.e. . 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 rows of , corresponding to a subsample that can approximate all rows of up to a given tolerance , i.e.
Rows of are considered Almost Linearly Dependent (ALD) [8] on this subset. We denote the tensor made only of those rows of . Those are selected based on the following squared distance evaluation. By denoting the -th row of ,
evaluates the distance of each row to the subspace spanned by the rows of . Decomposition (5.3) provides a bound with respect to the 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 and the remainder that we denote in (4.2) and applying the same separation and reordering in , we have
We then only solve for the first subset, i.e. we seek in the minimization problem
The conditioning is enhanced by removing close-to-correlated samples. It also truncates the spectrum so . 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 along with the linearization of inference complexity with .
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
The computational gain at the online stage can reveal massive compared to the least squares formulation if . With the subsampling approach, inference cost scales as . 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 by considering , .
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 with a factor , so .
Numerical example
We demonstrate the scaling of our approach on the Rosenbrock function. It is defined for arbitrary dimension over the domain as
Proposed model. We approximate the Rosenbrock function with growing dimension with polynomial mappings of degree 4. Then we evaluate conditioning when augmenting the degree of approximation, i.e. varying in the mapping defined as
The scaling factor is computed following the reasoning of subsection A.2.1, here . The training set of elements for , is drawn randomly from a Latin Hypercube Sample (LHS) of 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
This kernel is sufficient to capture the function. We use it in vanilla kernel regression built as
The same kernel is used in the kernel Feature Space Approximation (kFSA) method [10] which builds greedily a subsample 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 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 unseen points from the original LHS. The error is computed as the norm of errors over the testing set of points. Let denote the vector of exact outputs for each input in the testing set. Its approximated counterpart is denoted , the error we observe is
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 is selected as
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 squares | Spect. Trunc. | Subsampling | |
| Construction | (up. bound) | ||
| Inference |
Table 5.1. Theoretical complexity evaluations for construction and inference for different regressions.
| Dimension | 10 | 20 | 30 | 50 | 100 | 200 |
| kFSA | 985 | 2724 | 3371 | 6092 | 14927 | 19461 |
| subsampl. | 340 | 2305 | 1296 | 4581 | 8896 | 14397 |
| spec. trunc. | 260 | 1731 | 2195 | 4027 | 9359 | 19180 |
| Thresh. kFSA | ||||||
| Thresh. subsampl. | ||||||
| Thresh. spec. trunc. |
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 , 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: .
Figure 6.2. Evaluation of the conditioning of the various approaches with respect to the mapping’s or kernel’s degree (continuous line is and dashed ). (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 elements with and . Each of those models is then tested on 2 unseen LHS of 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 for growing (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 . 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 -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
Elements of are assumed weighted by infinitesimal perturbations, then by neglecting all (at least) doubly infinitesimal terms in the product we have
This leads to the bound in Frobenius norm
We assumed a worst normalized case for the bound on 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 . Then we assumed the element-wise bound which, plugged into the bound of Theorem 4.8 leads to
The bounding constant is dependent on the choice of mapping and its domain of definition. □
Proof. (Theorem 4.10) We assumed normalized mappings with separable perturbation-induced terms and settled that there exists a mapping-dependent constant such that , which merely assumes remains bounded over its domain of definition. Then by denoting
the backward error is given from its definition [27] as
We note that while , the criterion may be approximated as
From the bound provided in Theorem 4.8 and considering the bounding constant introduced earlier, we have
Assuming the normalized bound , i.e. , the left-hand-side of (A.1) is bounded as
Thus, guaranteeing lets the backward stability criterion tend only to the relative model error in .
Proof. (Theorem 4.11) We assume the sample to be sufficient and to be well suited to approximate , therefore
Then, the model error with the introduction of noise behaves as
So, following the first assumption, the model computation leads to
Hence the bound
since we leverage the mode-1 unfolding’s pseudoinverse, whose norm is the reciprocal of the lowest nonzero singular value .
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 in the input to assess stability as defined in the case of the canonical 1D degree polynomial basis, so we consider
We immediately see how the choice of basis and normalization will influence stability. The -dimensional tensorization of such bases will lead to the evaluation
We manage to identify and separate the term due to input perturbation along each dimension by developping the basis (A.2) as
In a first order approximation, we may separate that basis as where
Therefore the multidimensional basis inherits the partition
We stated in Theorem 4.10 that we need to identify a bounding constant from to assess the scaling to apply to remain stable. Let each be defined over an interval , then we can consider
with quite a margin. Therefore, we may uniformly scale down with a factor . Note that for this mapping to be normalized element-wise, it is required that
The scale-down approach will not affect conditioning of the regression (which can be tackled with any proposed regularization technique) and guarantees stability as seeing Theorem 4.10.
Trigonometric mapping
For trigonometric approximation, we consider the 1D mapping
This can be analogously developed for a basis in . Those are naturally normalized element-wise. We start by noting that
Then by applying the polynomial case we can identify the structure of (A.5) with, for the polynomial sine basis,
Choosing a loose bound from an element-wise worst case, we can provide
so that scaling uniformly with a factor each 1D mapping will preserve the stability criterion of Theorem 4.10. This value comes from considering
as a function of .
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 with c-dim and provide its decomposition based on a subsample with a tolerance as
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 or treat rows as they are streamed to select the subset on-the-fly.
Elements 1 and 2. The first provided row is used by default to initialize . Weights are initialized as an array containing only 1. We define
From that given point, we build a subspace . For the next point, we evaluate the distance to that subspace. For a new row , we compute defined as
where the minimizing is obtained by expanding the norm in the definition of and deriving the minimum of a quadratic polynomial in , yielding
Using that minimizer, will be given by
By comparing to the precision criterion , the point is kept or not. If it is kept, is appended to and is updated as
The weight matrix is updated as
Element . Consider we retained elements in until that point. This means we need to evaluate the distance of to a -dimensional subspace. We define the vector from the already selected rows and the new one as
The squared distance between and is given as
where admits a Cholesky decomposition with factor . Therefore by computing the vector by downward backsubstitution, the squared distance can be efficiently computed from . If , is appended to . The Cholesky factor is updated as
The weight matrix is updated as
with computed by upward backsubstitution. This construction loops only once on the rows of and leverages the incrementally constructed Cholesky factors . It is fit for streamed data if the criterion on squared distance 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 at each step, i.e. the greedy version.
Element 1. The first row of 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 as
Algorithm B.1 Streamed subsample construction
Input: ,
Output: ,
▷ Initialize reduced m-tensor ▷ Initialize Cholesky factor ▷ Initialize row index in reduced m-tensor ▷ Initialize weights
for any new , do ▷ Loop on rows of initial or streamed data ▷ Compute ▷ Compute by backsubstitution ▷ Evaluate if then ▷ Compare distance to threshold ▷ Update reduced m-tensor ▷ Update number of kept tensors ▷ Update Cholesky factor ▷ Update weights else ▷ Update weights end if end for return
Each element is defined analogously to the squared distance (B.1). We compute the contraction of each column vector of and select the first row of so as to minimize that sum. If all distances in the column vector corresponding to the selected point were below the precision tolerance , then would be sufficient and the algorithm would end there. Note that i) the elements of can be built from the elements of and ii) is not symmetric.
Element . The -th row of , is selected so that the subspace
minimizes the distances to all remaining points. In order to evaluate these distances, we denote the m-tensor with rows previously selected in masked. We define
as each possible augmentation of the subsample. At step we define the matrix element-wise as
Each element is constructed analogously to (B.2). We contract the columns of to obtain a vector whose elements are sums of squared distances. We select the index of the best choice in the rows of as the minimizer
The corresponding row is appended to and masked for following iterations. If all distances in the -th column of are below , the precision criterion is reached and the algorithm is stopped. Otherwise, operators are updated and the loop continues.
Once the optimal of size is computed, we evaluate the weight matrix using the projector onto the span of denoted by and defined as
We identify the weights in the projection of
We provide Algorithm B.2 to build the greedy subsample from a full m-tensor.
Algorithm B.2 Greedy subsample construction
Input: , Output: ,
Build matrix from (B.3)
▷ Sum columns of
, ▷ Select first element of
▷ Initialize Cholesky factor
Define by masking -th row of
for , do ▷ Loop on rows of
Build matrix from (B.4)
▷ Sum columns of in vector
▷ Find optimal column index
▷ Append -th row of as -th row of
if , , then ▷ All dist. to current subspace under
Break loop
else
Update by masking -th row of
end if
end for
Compute weights from (B.5)
return ,
References
- [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]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]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]R. Bellman, Rand Corporation, and Karreman Mathematics Research Collection. Dynamic Programming. Rand Corporation research study. Princeton University Press, 1957. ISBN: 9780691079516.
- [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]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]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]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]T.G. Kolda G. Ballard. Tensor Decompositions for Data Science. Cambridge University Press, 2025. ISBN: 9781009471671.DOI
- [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]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]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]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]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]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]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]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]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]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]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]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]I.V. Oseledets. “Tensor-Train Decomposition”. In: SIAM Journal on Scientific Computing 33.5 (2011), pp. 2295–2317. DOI: 10.1137/090752286.DOI
- [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]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]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]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]L.N. Trefethen and D. Bau. Numerical Linear Algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics, 1997. DOI: 10.1137/1.9780898719574.DOI


