Publications associées à Norme d'opérateur

Non-normal forms

In this thesis, we propose to formally derive amplitude equations governing the weakly nonlinear evolution of non-normal dynamical systems, when they respond to harmonic or stochastic forcing, or to an initial condition. This approach reconciles the non-mo ...

EPFL2024

Near-Minimax Optimal Estimation With Shallow ReLU Neural Networks

Rahul Parhi

We study the problem of estimating an unknown function from noisy data using shallow ReLU neural networks. The estimators we study minimize the sum of squared data-fitting errors plus a regularization term proportional to the squared Euclidean norm of the ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2023

Fairness and Explainability in Clustering Problems

Xinrui Jia

In this thesis we present and analyze approximation algorithms for three different clustering problems. The formulations of these problems are motivated by fairness and explainability considerations, two issues that have recently received attention in the ...

EPFL2023

Geometric Considerations in Lattice Programming

Moritz Andreas Venzin

We provide faster algorithms and fine-grained reductions for lattice problems in general norms. ...

EPFL2023

Convergence of adaptive algorithms for constrained weakly convex optimization

Volkan Cevher, Ahmet Alacaoglu, Yurii Malitskyi

We analyze the adaptive first order algorithm AMSGrad, for solving a constrained stochastic optimization problem with a weakly convex objective. We prove the

\tilde O(t^{-1/2})

rate of convergence for the squared norm of the gradient of Moreau envelope, ...

2021

Proximity Results and Faster Algorithms for Integer Programming Using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b, x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m), and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2020

A Unifying Representer Theorem for Inverse Problems and Machine Learning

Michaël Unser

Regularization addresses the ill-posedness of the training problem in machine learning or the reconstruction of a signal from a limited number of measurements. The method is applicable whenever the problem is formulated as an optimization task. The standar ...

2021

Effective Models and Numerical Homogenization for Wave Propagation in Heterogeneous Media on Arbitrary Timescales

Timothée Noé Pouchon, Assyr Abdulle

A family of effective equations for wave propagation in periodic media for arbitrary timescales O(epsilon-alpha), where epsilon MUCH LESS-THAN1 is the period of the tensor describing the medium, is proposed. The well-posedness of the effective equations of ...

SPRINGER2020

An algebraic least squares reduced basis method for the solution of nonaffinely parametrized Stokes equations

Alfio Quarteroni, Simone Deparis, Andrea Manzoni, Niccolò Dal Santo

In this paper we propose a new, purely algebraic, Petrov-Galerkin reduced basis (RB) method to solve the parametrized Stokes equations, where parameters serve to identify the (variable) domain geometry. Our method is obtained as an algebraic least squares ...

ELSEVIER SCIENCE SA2019

Sphere-of-Influence Graphs in Normed Spaces

János Pach, Márton Naszódi

We showthat any k-th closed sphere-of-influence graph in a d-dimensional normed space has a vertex of degree less than 5dk, thus obtaining a common generalization of results of Furedi and Loeb (Proc AmMath Soc 121(4): 1063-1073, 1994 [1]) and Guibas et al. ...

SPRINGER2018

Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma

Friedrich Eisenbrand

We consider integer programming problems in standard form max{c(T)x : Ax = b; x >= 0, x is an element of Z(n)} where A is an element of Z(mxn), b is an element of Z(m) and c is an element of Z(n). We show that such an integer program can be solved in time ...

ASSOC COMPUTING MACHINERY2018

Functional Decomposition Using Majority

Giovanni De Micheli, Mathias Soeken, Zhufei Chu

Typical operators for the decomposition of Boolean functions in state-of-the-art algorithms are AND, exclusive-OR (XOR), and a 2-to-1 multiplexer (MUX). We propose a logic decomposition algorithm that uses the majority-of-three (MAJ) operation. Such decomp ...

IEEE2018

Lorentz Force from a Current-Carrying Wire on a Charge in Motion under the Assumption of Neutrality in the Symmetrical Frame of Reference

Marcos Rubinstein, Antonio Sunjerga

It is commonly assumed that a wire conducting an electric current is neutral in the laboratory frame of reference (the rest frame of the lattice of positive ions). Some authors consider that the wire is neutral only in a symmetrical frame of reference, in ...

2018

Lower Bounds on Regret for Noisy Gaussian Process Bandit Optimization

Volkan Cevher, Jonathan Mark Scarlett, Ilija Bogunovic

In this paper, we consider the problem of sequentially optimizing a black-box function

f

based on noisy samples and bandit feedback. We assume that

f

is smooth in the sense of having a bounded norm in some reproducing kernel Hilbert space (RKHS), yield ...

2017

General Proximal Gradient Method: A Case for Non-Euclidean Norms

Volkan Cevher, Ya-Ping Hsieh, Marwa El Halabi, Cong Bang Vu, Van Quang Nguyen

In this paper, we consider composite convex minimization problems. We advocate the merit of considering Generalized Proximal gradient Methods (GPM) where the norm employed is not Euclidean. To that end, we show the tractability of the general proximity ope ...

2017

Small subset sums

Gergely Ambrus

Let parallel to.parallel to be a norm in R-d whose unit ball is B. Assume that V subset of B is a finite set of cardinality n, with Sigma(v is an element of V) v = 0. We show that for every integer k with 0

Elsevier Science Inc2016

Effective models for the multidimensional wave equation in heterogeneous media over long time and numerical homogenization

Timothée Noé Pouchon, Assyr Abdulle

A family of effective equations that capture the long time dispersive effects of wave propagation in heterogeneous media in an arbitrary large periodic spatial domain Omega subset of R-d is proposed and analyzed. For a wave equation with highly oscillatory ...

World Scientific Publ Co Pte Ltd2016

Dissipative Boundary Conditions for Nonlinear 1-D Hyperbolic Systems: Sharp Conditions Through an Approach via Time-Delay Systems

Hoài-Minh Nguyên

We analyze dissipative boundary conditions for nonlinear hyperbolic systems in one space dimension. We show that a known sufficient condition for exponential stability with respect to the H-2-norm is not sufficient for the exponential stability with respec ...

Society for Industrial and Applied Mathematics2015

Homogenization of a multiscale viscoelastic model with nonlocal damping, application to the human lungs

Paul Isaac Denis Louis Marie Cazeaux

We are interested in the mathematical modeling of the deformation of the human lung tissue, called the lung parenchyma, during the respiration process. The parenchyma is a foam-like elastic material containing millions of air-filled alveoli connected by a ...

World Scientific Publ Co Pte Ltd2015

Approximate Matrix Multiplication with Application to Linear Embeddings

Anastasios Kyrillidis, Michail Vlachos

In this paper, we study the problem of approximately computing the product of two real matrices. In particular, we analyze a dimensionality-reduction-based approximation algorithm due to Sarlos [1], introducing the notion of nuclear rank as the ratio of th ...

Ieee2014