Publications related to Approximation theory

Retraction-based numerical methods for continuation, interpolation and time integration on manifolds

The goal of this thesis is the development and the analysis of numerical methods for problems where the unknown is a curve on a smooth manifold. In particular, the thesis is structured around the three following problems: homotopy continuation, curve inter ...

EPFL2023

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Proximal Point Imitation Learning

Volkan Cevher, Luca Viano, Igor Krawczuk, Angeliki Kamoutsi

This work develops new algorithms with rigorous efficiency guarantees for infinite horizon imitation learning (IL) with linear function approximation without restrictive coherence assumptions. We begin with the minimax formulation of the problem and then o ...

2022

DIVIDE-AND-CONQUER METHODS FOR FUNCTIONS OF MATRICES WITH BANDED OR HIERARCHICAL LOW-RANK STRUCTURE\ast

Daniel Kressner, Stefano Massei, Alice Cortinovis

This work is concerned with approximating matrix functions for banded matrices, hierarchically semiseparable matrices, and related structures. We develop a new divide-and-conquer method based on (rational) Krylov subspace methods for performing low-rank up ...

SIAM PUBLICATIONS2022

Model order reduction based on functional rational approximants for parametric PDEs with meromorphic structure

Davide Pradovera

Many engineering fields rely on frequency-domain dynamical systems for the mathematical modeling of physical (electrical/mechanical/etc.) structures. With the growing need for more accurate and reliable results, the computational burden incurred by frequen ...

EPFL2021

Function Integration, Reconstruction And Approximation Using Rank-1 Lattices

Fabio Nobile, Giovanni Migliorati

We consider rank-1 lattices for integration and reconstruction of functions with series expansion supported on a finite index set. We explore the connection between the periodic Fourier space and the non-periodic cosine space and Chebyshev space, via tent ...

2021

Functional Tucker Approximation Using Chebyshev Interpolation

Daniel Kressner, Christoph Max Strössner

This work is concerned with approximating a trivariate function defined on a tensor-product domain via function evaluations. Combining tensorized Chebyshev interpolation with a Tucker decomposition of low multilinear rank yields function approximations tha ...

SIAM PUBLICATIONS2021

Fast Least-Squares Padé approximation of problems with normal operators and meromorphic structure

Fabio Nobile, Francesca Bonizzoni, Davide Pradovera

In this work, we consider the approximation of Hilbert space-valued meromorphic functions that arise as solution maps of parametric PDEs whose operator is the shift of an operator with normal and compact resolvent, e.g., the Helmholtz equation. In this res ...

2020

Least-Squares Padé approximation of parametric and stochastic Helmholtz maps

Fabio Nobile, Francesca Bonizzoni, Davide Pradovera

The present work deals with rational model order reduction methods based on the single-point Least-Square (LS) Padé approximation techniques introduced in Bonizzoni et al. (ESAIM Math. Model. Numer. Anal., 52(4), 1261–1284 2018, Math. Comput. 89, 1229–1257 ...

2020

Continuous-Domain Signal Reconstruction Using L-p-Norm Regularization

Michaël Unser, Pakshal Narendra Bohra

We focus on the generalized-interpolation problem. There, one reconstructs continuous-domain signals that honor discrete data constraints. This problem is infinite-dimensional and ill-posed. We make it well-posed by imposing that the solution balances data ...

2020

Distributed sampling for rational approximation of the acoustic scattering of an airfoil

Francesca Bonizzoni, Davide Pradovera

In this paper we compute a reduced order model for a time‐harmonic external acoustic scattering problem with parametric frequency. The employed technique is minimal rational interpolation, an explicit moment‐matching method for Hilbert space‐valued meromor ...

2019

Approximation of Non-decaying Signals from Shift-Invariant Subspaces

Michaël Unser, Quy Ha Nguyen

In our recent work, the sampling and reconstruction of non-decaying signals, modeled as members of weighted-L-p spaces, were shown to be stable with an appropriate choice of the generating kernel for the shift-invariant reconstruction space. In this paper, ...

2019

Convergence analysis of Padé approximations for Helmholtz frequency response problems

Fabio Nobile, Francesca Bonizzoni

The present work concerns the approximation of the solution map

S

associated to the parametric Helmholtz boundary value problem, i.e., the map which associates to each (real) wavenumber belonging to a given interval of interest the corresponding solution ...

2018

Distributed Signal Processing via Chebyshev Polynomial Approximation

Pascal Frossard, David Shuman, Pierre Vandergheynst, Daniel Kressner

Unions of graph multiplier operators are an important class of linear operators for processing signals defined on graphs. We present a novel method to efficiently distribute the application of these operators. The proposed method features approximations of ...

2018

Conic Programming Reformulations of Two-Stage Distributionally Robust Linear Programs over Wasserstein Balls

Daniel Kuhn, Grani Adiwena Hanasusanto

Adaptive robust optimization problems are usually solved approximately by restricting the adaptive decisions to simple parametric decision rules. However, the corresponding approximation error can be substantial. In this paper we show that two-stage robust ...

2018

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...

ASSOC COMPUTING MACHINERY2018

Convergence rates of moment-sum-of-squares hierarchies for optimal control problems

Colin Neil Jones, Milan Korda

We study the convergence rate of the moment-sum-of-squares hierarchy of semidefinite programs for optimal control problems with polynomial data. It is known that this hierarchy generates polynomial under-approximations to the value function of the optimal ...

Elsevier Science Bv2017

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature

Justin Dean Ward

We design new approximation algorithms for the problems of optimizing submodular and supermodular functions subject to a single matroid constraint. Specifically, we consider the case in which we wish to maximize a monotone increasing submodular function or ...

INFORMS2017

Maximizing Symmetric Submodular Functions

Moran Feldman

Symmetric submodular functions are an important family of submodular functions capturing many interesting cases, including cut functions of graphs and hypergraphs. Maximization of such functions subject to various constraints receives little attention by c ...

Association for Computing Machinery2017