TY - JOUR

T1 - Greedy algorithms for optimal measurements selection in state estimation using reduced models

AU - Binev, Peter

AU - Cohen, Albert

AU - Mula, Olga

AU - Nichols, James

N1 - Publisher Copyright:
Copyright © by SIAM and ASA.

PY - 2018

Y1 - 2018

N2 - We consider the problem of optimal recovery of an unknown function u in a Hilbert space V from measurements of the form ℓj(u), j = 1; : : : ;m, where the j are known linear functionals on V . We are motivated by the setting where u is a solution to a PDE with some unknown parameters, therefore lying on a certain manifold contained in V . Following the approach adopted in [Maday, Patera, Penn and Yano, Int. J. Numer. Methods Engrg., 102 (2015), pp. 933-965, Binev, Cohen, Dahmen, DeVore, Petrova, and Wojtaszczyk, SIAM J. Uncertainty Quantification, 5 (2017), pp. 1-29], the prior on the unknown function can be described in terms of its approximability by finitedimensional reduced model spaces (Vn)n≥1 where dim(Vn) = n. Examples of such spaces include classical approximation spaces, e.g., finite elements or trigonometric polynomials, as well as reduced basis spaces which are designed to match the solution manifold more closely. The error bounds for optimal recovery under such priors are of the form μ(Vn;Wm)"n, where "n is the accuracy of the reduced model Vn and μ(Vn;Wm) is the inverse of an inf-sup constant that describe the angle between Vn and the space Wm spanned by the Riesz representers of (ℓ1; : : : ; ℓm). This paper addresses the problem of properly selecting the measurement functionals, in order to control at best the stability constant μ(Vn;Wm), for a given reduced model space Vn. Assuming that the j can be picked from a given dictionary D we introduce and analyze greedy algorithms that perform a suboptimal selection in reasonable computational time. We study the particular case of dictionaries that consist either of point value evaluations or local averages, as idealized models for sensors in physical systems. Our theoretical analysis and greedy algorithms may therefore be used in order to optimize the position of such sensors.

AB - We consider the problem of optimal recovery of an unknown function u in a Hilbert space V from measurements of the form ℓj(u), j = 1; : : : ;m, where the j are known linear functionals on V . We are motivated by the setting where u is a solution to a PDE with some unknown parameters, therefore lying on a certain manifold contained in V . Following the approach adopted in [Maday, Patera, Penn and Yano, Int. J. Numer. Methods Engrg., 102 (2015), pp. 933-965, Binev, Cohen, Dahmen, DeVore, Petrova, and Wojtaszczyk, SIAM J. Uncertainty Quantification, 5 (2017), pp. 1-29], the prior on the unknown function can be described in terms of its approximability by finitedimensional reduced model spaces (Vn)n≥1 where dim(Vn) = n. Examples of such spaces include classical approximation spaces, e.g., finite elements or trigonometric polynomials, as well as reduced basis spaces which are designed to match the solution manifold more closely. The error bounds for optimal recovery under such priors are of the form μ(Vn;Wm)"n, where "n is the accuracy of the reduced model Vn and μ(Vn;Wm) is the inverse of an inf-sup constant that describe the angle between Vn and the space Wm spanned by the Riesz representers of (ℓ1; : : : ; ℓm). This paper addresses the problem of properly selecting the measurement functionals, in order to control at best the stability constant μ(Vn;Wm), for a given reduced model space Vn. Assuming that the j can be picked from a given dictionary D we introduce and analyze greedy algorithms that perform a suboptimal selection in reasonable computational time. We study the particular case of dictionaries that consist either of point value evaluations or local averages, as idealized models for sensors in physical systems. Our theoretical analysis and greedy algorithms may therefore be used in order to optimize the position of such sensors.

KW - Data assimilation

KW - Greedy algorithms

KW - Inf-sup stability

KW - Reduced models

KW - Sensor placement

UR - http://www.scopus.com/inward/record.url?scp=85053406958&partnerID=8YFLogxK

U2 - 10.1137/17M1157635

DO - 10.1137/17M1157635

M3 - Article

SN - 2166-2525

VL - 6

SP - 1101

EP - 1126

JO - SIAM-ASA Journal on Uncertainty Quantification

JF - SIAM-ASA Journal on Uncertainty Quantification

IS - 3

ER -