Cardinalité (mathématiques) | EPFL Graph Search

En mathématiques, la cardinalité est une notion de taille pour les ensembles. Lorsqu'un ensemble est fini, c'est-à-dire si ses éléments peuvent être listés par une suite finie, son cardinal est la longueur de cette suite, autrement dit il s'agit du nombre d'éléments de l'ensemble. En particulier, le cardinal de l'ensemble vide est zéro. La généralisation de cette notion aux ensembles infinis est fondée sur la relation d'équipotence : deux ensembles sont dits équipotents s'il existe une bijection de l'un dans l'autre. Par exemple, un ensemble infini est dit dénombrable s'il est en bijection avec l'ensemble des entiers naturels. C'est le cas de l'ensemble des entiers relatifs ou de celui des rationnels mais pas de celui des réels, d'après l'argument de la diagonale de Cantor. L'ensemble des réels a un cardinal strictement plus grand, ce qui signifie qu'il existe une injection dans un sens mais pas dans l'autre. Le théorème de Cantor généralise ce résultat en montrant que tout ensemble

MATHICSE Technical Report : Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Giovanni Migliorati, Fabio Nobile

We analyze the accuracy of the discrete least-squares approximation of a function u in multivariate polynomial spaces

P_\Lambda := span\{y \mapsto y^\nu | \nu \in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma := [-1,1]^d

, based on the sampling of this function at points

y^1,...,y^m \in \Gamma

. The samples are independently drawn according to a given probability density

\rho

belonging to the class of multivariate beta densities, which includes the uniform and Chebyshev densities as particular cases. Motivated by recent results on high-dimensional parametric and stochastic PDEs, we restrict our attention to polynomial spaces associated with downward closed sets

\Lambda

of prescribed cardinality n and we optimize the choice of the space for the given sample. This implies in particular that the selected polynomial space depends on the sample. We are interested in comparing the error of this least-squares approximation measured in

L^2(\Gamma,\rho)

with the best achievable polynomial approximation error when using downward closed sets of cardinality n. We establish conditions between the dimension n and the size m of the sample, under which these two errors are proven to be comparable. Our main finding is that the dimension d enters only moderately in the resulting trade-off between m and n, in terms of a logarithmic factor ln(d), and is even absent when the optimization is restricted to a relevant subclass of downward closed sets, named anchored sets. In principle, this allows one to use these methods in arbitrarily high or even infinite dimension. Our analysis builds upon [3] which considered fixed and non-optimized downward closed multi-index sets. Potential applications of the proposed results are found in the development and analysis of efficient numerical methods for computing the solution of high-dimensional parametric or stochastic PDEs, but is not limited to this area.

MATHICSE2015

Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Giovanni Migliorati, Fabio Nobile

We analyze the accuracy of the discrete least-squares approximation of a function

u

in multivariate polynomial spaces

P_\Lambda:=span\{y\mapsto y^\nu \,: \, \nu\in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma:=[-1,1]^d

, based on the sampling of this function at points

y^1,\dots,y^m \in \Gamma

. The samples are independently drawn according to a given probability density

\rho

belonging to the class of multivariate beta densities, which includes the uniform density as a particular case. Motivated by recent results in high-dimensional parametric and stochastic PDEs, we restrict our attention to polynomial spaces associated with \emph{downward closed} sets

\Lambda

of \emph{prescribed} cardinality

n

and we optimize the choice of the space for the given sample. This implies in particular that the selected polynomial space depends on the sample. We are interested in comparing the error of this least-squares approximation measured in

L^2(\Gamma,\rho)

with the best achievable polynomial approximation error when using downward closed sets of cardinality

n

. We establish conditions between the dimension

n

and the size

m

of the sample, under which these two errors are proven to be comparable. We show that the dimension

d

enters only moderately in the resulting trade-off between

m

and

n

, in terms of a logarithmic factor

\ln(d)

, and is even absent when the optimization is restricted to a relevant subclass of downward closed sets. In principle, this allows one to use these methods in high dimension. Our analysis builds upon (Chkifa et al. in ESAIM Math Model Numer Anal 49(3):815–837, 2015), which considered fixed and non-optimized downward closed multi-index sets. Potential applications of the proposed results are found in the development and analysis of efficient numerical methods for computing the solution of high-dimensional parametric or stochastic PDEs, but is not limited to this area.

2017

MATHICSE Technical Report : Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Giovanni Migliorati, Fabio Nobile

We analyze the accuracy of the discrete least-squares approximation of a function u in multivariate polynomial spaces

P_\Lambda := span\{y \mapsto y^\nu | \nu \in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma := [-1,1]^d

, based on the sampling of this function at points

y^1,...,y^m \in \Gamma

. The samples are independently drawn according to a given probability density

\rho

\Lambda

L^2(\Gamma,\rho)

MATHICSE2015

Discrete least-squares approximations over optimized downward closed polynomial spaces in arbitrary dimension

Giovanni Migliorati, Fabio Nobile

We analyze the accuracy of the discrete least-squares approximation of a function

u

in multivariate polynomial spaces

P_\Lambda:=span\{y\mapsto y^\nu \,: \, \nu\in \Lambda\}

with

\Lambda\subset N_0^d

over the domain

\Gamma:=[-1,1]^d

, based on the sampling of this function at points

y^1,\dots,y^m \in \Gamma

. The samples are independently drawn according to a given probability density

\rho

\Lambda

of \emph{prescribed} cardinality

n

L^2(\Gamma,\rho)

with the best achievable polynomial approximation error when using downward closed sets of cardinality

n

. We establish conditions between the dimension

n

and the size

m

of the sample, under which these two errors are proven to be comparable. We show that the dimension

d

enters only moderately in the resulting trade-off between

m

and

n

, in terms of a logarithmic factor

\ln(d)

2017