BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Anthony Nouy

Anthony Nouy appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.NANumerical Analysismath.FAMachine Learningmath.DGmath.OCmath.STStatistics Theory

Catalog footprint

What is connected

18works
8topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

18 published item(s)

preprint2022arXiv

A PAC algorithm in relative precision for bandit problem with costly sampling

This paper considers the problem of maximizing an expectation function over a finite set, or finite-arm bandit problem. We first propose a naive stochastic bandit algorithm for obtaining a probably approximately correct (PAC) solution to this discrete optimization problem in relative precision, that is a solution which solves the optimization problem up to a relative error smaller than a prescribed tolerance, with high probability. We also propose an adaptive stochastic bandit algorithm which provides a PAC-solution with the same guarantees. The adaptive algorithm outperforms the mean complexity of the naive algorithm in terms of number of generated samples and is particularly well suited for applications with high sampling cost.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

A new splitting algorithm for dynamical low-rank approximation motivated by the fibre bundle structure of matrix manifolds

In this paper, we propose a new splitting algorithm for dynamical low-rank approximation motivated by the fibre bundle structure of the set of fixed rank matrices. We first introduce a geometric description of the set of fixed rank matrices which relies on a natural parametrization of matrices. More precisely, it is endowed with the structure of analytic principal bundle, with an explicit description of local charts. For matrix differential equations, we introduce a first order numerical integrator working in local coordinates. The resulting algorithm can be interpreted as a particular splitting of the projection operator onto the tangent space of the low-rank matrix manifold. It is proven to be exact in some particular case. Numerical experiments confirm this result and illustrate the robustness of the proposed algorithm.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Approximation of Smoothness Classes by Deep Rectifier Networks

We consider approximation rates of sparsely connected deep rectified linear unit (ReLU) and rectified power unit (RePU) neural networks for functions in Besov spaces $B^α_{q}(L^p)$ in arbitrary dimension $d$, on general domains. We show that \alert{deep rectifier} networks with a fixed activation function attain optimal or near to optimal approximation rates for functions in the Besov space $B^α_τ(L^τ)$ on the critical embedding line $1/τ=α/d+1/p$ for \emph{arbitrary} smoothness order $α>0$. Using interpolation theory, this implies that the entire range of smoothness classes at or above the critical line is (near to) optimally approximated by deep ReLU/RePU networks.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Learning with tree tensor networks: complexity estimates and model selection

Tree tensor networks, or tree-based tensor formats, are prominent model classes for the approximation of high-dimensional functions in computational and data science. They correspond to sum-product neural networks with a sparse connectivity associated with a dimension tree and widths given by a tuple of tensor ranks. The approximation power of these models has been proved to be (near to) optimal for classical smoothness classes. However, in an empirical risk minimization framework with a limited number of observations, the dimension tree and ranks should be selected carefully to balance estimation and approximation errors. We propose and analyze a complexity-based model selection method for tree tensor networks in an empirical risk minimization framework and we analyze its performance over a wide range of smoothness classes. Given a family of model classes associated with different trees, ranks, tensor product feature spaces and sparsity patterns for sparse tensor networks, a model is selected (à la Barron, Birgé, Massart) by minimizing a penalized empirical risk, with a penalty depending on the complexity of the model class and derived from estimates of the metric entropy of tree tensor networks. This choice of penalty yields a risk bound for the selected predictor. In a least-squares setting, after deriving fast rates of convergence of the risk, we show that our strategy is (near to) minimax adaptive to a wide range of smoothness classes including Sobolev or Besov spaces (with isotropic, anisotropic or mixed dominating smoothness) and analytic functions. We discuss the role of sparsity of the tensor network for obtaining optimal performance in several regimes. In practice, the amplitude of the penalty is calibrated with a slope heuristics method. Numerical experiments in a least-squares regression setting illustrate the performance of the strategy.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Randomized linear algebra for model reduction. Part II: minimal residual methods and dictionary-based approximation

A methodology for using random sketching in the context of model order reduction for high-dimensional parameter-dependent systems of equations was introduced in [Balabanov and Nouy 2019, Part I]. Following this framework, we here construct a reduced model from a small, efficiently computable random object called a sketch of a reduced model, using minimal residual methods. We introduce a sketched version of the minimal residual based projection as well as a novel nonlinear approximation method, where for each parameter value, the solution is approximated by minimal residual projection onto a subspace spanned by several vectors picked (online) from a dictionary of candidate basis vectors. It is shown that random sketching technique can improve not only efficiency but also numerical stability. A rigorous analysis of the conditions on the random sketch required to obtain a given accuracy is presented. These conditions may be ensured a priori with high probability by considering for the sketching matrix an oblivious embedding of sufficiently large size. Furthermore, a simple and reliable procedure for a posteriori verification of the quality of the sketch is provided. This approach can be used for certification of the approximation as well as for adaptive selection of the size of the random sketching matrix.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Randomized linear algebra for model reduction. Part I: Galerkin methods and error estimation

We propose a probabilistic way for reducing the cost of classical projection-based model order reduction methods for parameter-dependent linear equations. A reduced order model is here approximated from its random sketch, which is a set of low-dimensional random projections of the reduced approximation space and the spaces of associated residuals. This approach exploits the fact that the residuals associated with approximations in low-dimensional spaces are also contained in low-dimensional spaces. We provide conditions on the dimension of the random sketch for the resulting reduced order model to be quasi-optimal with high probability. Our approach can be used for reducing both complexity and memory requirements. The provided algorithms are well suited for any modern computational environment. Major operations, except solving linear systems of equations, are embarrassingly parallel. Our version of proper orthogonal decomposition can be computed on multiple workstations with a communication cost independent of the dimension of the full order model. The reduced order model can even be constructed in a so-called streaming environment, i.e., under extreme memory constraints. In addition, we provide an efficient way for estimating the error of the reduced order model, which is not only more efficient than the classical approach but is also less sensitive to round-off errors. Finally, the methodology is validated on benchmark problems.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Singular Value Decomposition in Sobolev Spaces: Part I

A well known result from functional analysis states that any compact operator between Hilbert spaces admits a singular value decomposition (SVD). This decomposition is a powerful tool that is the workhorse of many methods both in mathematics and applied fields. A prominent application in recent years is the approximation of high-dimensional functions in a low-rank format. This is based on the fact that, under certain conditions, a tensor can be identified with a compact operator and SVD applies to the latter. One key assumption for this application is that the tensor product norm is not weaker than the injective norm. This assumption is not fulfilled in Sobolev spaces, which are widely used in the theory and numerics of partial differential equations. Our goal is the analysis of the SVD in Sobolev spaces. This work consists of two parts. In this manuscript (part I), we address low-rank approximations and minimal subspaces in H1. We analyze the H1-error of the SVD performed in the ambient L2-space. In part II, we will address variants of the SVD in norms stronger than the L2-norm. We will provide a few numerical examples that support our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Singular Value Decomposition in Sobolev Spaces: Part II

Under certain conditions, an element of a tensor product space can be identified with a compact operator and the singular value decomposition (SVD) applies to the latter. These conditions are not fulfilled in Sobolev spaces. In the previous part of this work (part I), we introduced some preliminary notions in the theory of tensor product spaces. We analyzed low-rank approximations in H1 and the error of the SVD performed in the ambient L2 space. In this work (part II), we continue by considering variants of the SVD in norms stronger than the L2-norm. Overall and, perhaps surprisingly, this leads to a more difficult control of the H1-error. We briefly consider an isometric embedding of H1 that allows direct application of the SVD to H1-functions. Finally, we provide a few numerical examples that support our theoretical findings.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Stochastic methods for solving high-dimensional partial differential equations

We propose algorithms for solving high-dimensional Partial Differential Equations (PDEs) that combine a probabilistic interpretation of PDEs, through Feynman-Kac representation, with sparse interpolation. Monte-Carlo methods and time-integration schemes are used to estimate pointwise evaluations of the solution of a PDE. We use a sequential control variates algorithm, where control variates are constructed based on successive approximations of the solution of the PDE. Two different algorithms are proposed, combining in different ways the sequential control variates algorithm and adaptive sparse interpolation. Numerical examples will illustrate the behavior of these algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Weakly intrusive low-rank approximation method for nonlinear parameter-dependent equations

This paper presents a weakly intrusive strategy for computing a low-rank approximation of the solution of a system of nonlinear parameter-dependent equations. The proposed strategy relies on a Newton-like iterative solver which only requires evaluations of the residual of the parameter-dependent equation and of a preconditioner (such as the differential of the residual) for instances of the parameters independently. The algorithm provides an approximation of the set of solutions associated with a possibly large number of instances of the parameters, with a computational complexity which can be orders of magnitude lower than when using the same Newton-like solver for all instances of the parameters. The reduction of complexity requires efficient strategies for obtaining low-rank approximations of the residual, of the preconditioner, and of the increment at each iteration of the algorithm. For the approximation of the residual and the preconditioner, weakly intrusive variants of the empirical interpolation method are introduced, which require evaluations of entries of the residual and the preconditioner. Then, an approximation of the increment is obtained by using a greedy algorithm for low-rank approximation, and a low-rank approximation of the iterate is finally obtained by using a truncated singular value decomposition. When the preconditioner is the differential of the residual, the proposed algorithm is interpreted as an inexact Newton solver for which a detailed convergence analysis is provided. Numerical examples illustrate the efficiency of the method.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

Tensor-based numerical method for stochastic homogenisation

This paper addresses the complexity reduction of stochastic homogenisation of a class of random materials for a stationary diffusion equation. A cost-efficient approximation of the correctors is built using a method designed to exploit quasi-periodicity. Accuracy and cost reduction are investigated for local perturbations or small transformations of periodic materials as well as for materials with no periodicity but a mesoscopic structure, for which the limitations of the method are shown. Finally, for materials outside the scope of this method, we propose to use the approximation of homogenised quantities as control variates for variance reduction of a more accurate and costly Monte Carlo estimator (using a multi-fidelity Monte Carlo method). The resulting cost reduction is illustrated in a numerical experiment with a control variate from weakly stochastic homogenisation for comparison, and the limits of this variance reduction technique are tested on materials without periodicity or mesoscopic structure.

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Principal bundle structure of matrix manifolds

In this paper, we introduce a new geometric description of the manifolds of matrices of fixed rank. The starting point is a geometric description of the Grassmann manifold $\mathbb{G}_r(\mathbb{R}^k)$ of linear subspaces of dimension $r<k$ in $\mathbb{R}^k$ which avoids the use of equivalence classes. The set $\mathbb{G}_r(\mathbb{R}^k)$ is equipped with an atlas which provides it with the structure of an analytic manifold modelled on $\mathbb{R}^{(k-r)\times r}$. Then we define an atlas for the set $\mathcal{M}_r(\mathbb{R}^{k \times r})$ of full rank matrices and prove that the resulting manifold is an analytic principal bundle with base $\mathbb{G}_r(\mathbb{R}^k)$ and typical fibre $\mathrm{GL}_r$, the general linear group of invertible matrices in $\mathbb{R}^{k\times k}$. Finally, we define an atlas for the set $\mathcal{M}_r(\mathbb{R}^{n \times m})$ of non-full rank matrices and prove that the resulting manifold is an analytic principal bundle with base $\mathbb{G}_r(\mathbb{R}^n) \times \mathbb{G}_r(\mathbb{R}^m)$ and typical fibre $\mathrm{GL}_r$. The atlas of $\mathcal{M}_r(\mathbb{R}^{n \times m})$ is indexed on the manifold itself, which allows a natural definition of a neighbourhood for a given matrix, this neighbourhood being proved to possess the structure of a Lie group. Moreover, the set $\mathcal{M}_r(\mathbb{R}^{n \times m})$ equipped with the topology induced by the atlas is proven to be an embedded submanifold of the matrix space $\mathbb{R}^{n \times m}$ equipped with the subspace topology. The proposed geometric description then results in a description of the matrix space $\mathbb{R}^{n \times m}$, seen as the union of manifolds $\mathcal{M}_r(\mathbb{R}^{n \times m})$, as an analytic manifold equipped with a topology for which the matrix rank is a continuous map.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Interpolation of inverse operators for preconditioning parameter-dependent equations

We propose a method for the construction of preconditioners of parameter-dependent matrices for the solution of large systems of parameter-dependent equations. The proposed method is an interpolation of the matrix inverse based on a projection of the identity matrix with respect to the Frobenius norm. Approximations of the Frobenius norm using random matrices are introduced in order to handle large matrices. The resulting statistical estimators of the Frobenius norm yield quasi-optimal projections that are controlled with high probability. Strategies for the adaptive selection of interpolation points are then proposed for different objectives in the context of projection-based model order reduction methods: the improvement of residual-based error estimators, the improvement of the projection on a given reduced approximation space, or the recycling of computations for sampling based model order reduction methods.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Geometric Structures in Tensor Representations (Final Release)

The main goal of this paper is to study the geometric structures associated with the representation of tensors in subspace based formats. To do this we use a property of the so-called minimal subspaces which allows us to describe the tensor representation by means of a rooted tree. By using the tree structure and the dimensions of the associated minimal subspaces, we introduce, in the underlying algebraic tensor space, the set of tensors in a tree-based format with either bounded or fixed tree-based rank. This class contains the Tucker format and the Hierarchical Tucker format (including the Tensor Train format). In particular, we show that the set of tensors in the tree-based format with bounded (respectively, fixed) tree-based rank of an algebraic tensor product of normed vector spaces is an analytic Banach manifold. Indeed, the manifold geometry for the set of tensors with fixed tree-based rank is induced by a fibre bundle structure and the manifold geometry for the set of tensors with bounded tree-based rank is given by a finite union of connected components. In order to describe the relationship between these manifolds and the natural ambient space, we introduce the definition of topological tensor spaces in the tree-based format. We prove under natural conditions that any tensor of the topological tensor space under consideration admits best approximations in the manifold of tensors in the tree-based format with bounded tree-based rank. In this framework, we also show that the tangent (Banach) space at a given tensor is a complemented subspace in the natural ambient tensor Banach space and hence the set of tensors in the tree-based format with bounded (respectively, fixed) tree-based rank is an immersed submanifold. This fact allows us to extend the Dirac-Frenkel variational principle in the framework of topological tensor spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Low-rank methods for high-dimensional approximation and model order reduction

Tensor methods are among the most prominent tools for the numerical solution of high-dimensional problems where functions of multiple variables have to be approximated. These methods exploit the tensor structure of function spaces and apply to many problems in computational science which are formulated in tensor spaces, such as problems arising in stochastic calculus, uncertainty quantification or parametric analyses. Here, we present complexity reduction methods based on low-rank approximation methods. We analyze the problem of best approximation in subsets of low-rank tensors and discuss its connection with the problem of optimal model reduction in low-dimensional reduced spaces. We present different algorithms for computing approximations of a function in low-rank formats. In particular, we present constructive algorithms which are based either on a greedy construction of an approximation (with successive corrections in subsets of low-rank tensors) or on the greedy construction of tensor subspaces (for subspace-based low-rank formats). These algorithms can be applied for tensor compression, tensor completion or for the numerical solution of equations in low-rank tensor formats. A special emphasis is given to the solution of stochastic or parameter-dependent models. Different approaches are presented for the approximation of vector-valued or multivariate functions (identified with tensors), based on samples of the functions (black-box approaches) or on the models equations which are satisfied by the functions.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A least-squares method for sparse low rank approximation of multivariate functions

In this paper, we propose a low-rank approximation method based on discrete least-squares for the approximation of a multivariate function from random, noisy-free observations. Sparsity inducing regularization techniques are used within classical algorithms for low-rank approximation in order to exploit the possible sparsity of low-rank approximations. Sparse low-rank approximations are constructed with a robust updated greedy algorithm which includes an optimal selection of regularization parameters and approximation ranks using cross validation techniques. Numerical examples demonstrate the capability of approximating functions of many variables even when very few function evaluations are available, thus proving the interest of the proposed algorithm for the propagation of uncertainties through complex computational models.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A tensor approximation method based on ideal minimal residual formulations for the solution of high-dimensional problems

In this paper, we propose a method for the approximation of the solution of high-dimensional weakly coercive problems formulated in tensor spaces using low-rank approximation formats. The method can be seen as a perturbation of a minimal residual method with residual norm corresponding to the error in a specified solution norm. We introduce and analyze an iterative algorithm that is able to provide a controlled approximation of the optimal approximation of the solution in a given low-rank subset, without any a priori information on this solution. We also introduce a weak greedy algorithm which uses this perturbed minimal residual method for the computation of successive greedy corrections in small tensor subsets. We prove its convergence under some conditions on the parameters of the algorithm. The residual norm can be designed such that the resulting low-rank approximations are quasi-optimal with respect to particular norms of interest, thus yielding to goal-oriented order reduction strategies for the approximation of high-dimensional problems. The proposed numerical method is applied to the solution of a stochastic partial differential equation which is discretized using standard Galerkin methods in tensor product spaces.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Proper Generalized Decomposition for Nonlinear Convex Problems in Tensor Banach Spaces

Tensor-based methods are receiving a growing interest in scientific computing for the numerical solution of problems defined in high dimensional tensor product spaces. A family of methods called Proper Generalized Decompositions methods have been recently introduced for the a priori construction of tensor approximations of the solution of such problems. In this paper, we give a mathematical analysis of a family of progressive and updated Proper Generalized Decompositions for a particular class of problems associated with the minimization of a convex functional over a reflexive tensor Banach space.

0 citations0 reviewsNo code linkedOpen access