Concept# Cardinality

Summary

In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = {2, 4, 6} contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized to infinite sets, which allows one to distinguish between different types of infinity, and to perform arithmetic on them. There are two approaches to cardinality: one which compares sets directly using bijections and injections, and another which uses cardinal numbers.
The cardinality of a set is also called its size, when no confusion with other notions of size is possible.
The cardinality of a set A is usually denoted |A|, with a vertical bar on each side; this is the same notation as absolute value, and the meaning depends on context. The cardinality of a set A may alternatively be denoted by n(A), A, \operatorname{card}(A), or

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications

Loading

Related people

Loading

Related units

Loading

Related concepts

Loading

Related courses

Loading

Related lectures

Loading

Related units

No results

Related publications (7)

Related people

No results

Loading

Loading

Loading

Related courses (6)

CS-101: Advanced information, computation, communication I

Discrete mathematics is a discipline with applications to almost all areas of study. It provides a set of indispensable tools to computer science in particular. This course reviews (familiar) topics as diverse as mathematical reasoning, combinatorics, discrete structures & algorithmic thinking.

COM-401: Cryptography and security

This course introduces the basics of cryptography. We review several types of cryptographic primitives, when it is safe to use them and how to select the appropriate security parameters. We detail how they work and sketch how they can be implemented.

COM-501: Advanced cryptography

This course reviews some failure cases in public-key cryptography. It introduces some cryptanalysis techniques. It also presents fundamentals in cryptography such as interactive proofs. Finally, it presents some techniques to validate the security of cryptographic primitives.

Related lectures (18)

Related concepts (70)

Real number

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values c

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory,

Cardinal number

In mathematics, a cardinal number, or cardinal for short, is what is commonly called the number of elements of a set. In the case of a finite set, its cardinal number, or cardinality is therefore

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.

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, , , ,

Compressed sensing applied to magnetic resonance imaging (MRI) allows to reduce the scanning time by enabling images to be reconstructed from highly undersampled data. In this paper, we tackle the problem of designing a sampling mask for an arbitrary reconstruction method and a limited acquisition budget. Namely, we look for an optimal probability distribution from which a mask with a fixed cardinality is drawn. We demonstrate that this problem admits a compactly supported solution, which leads to a deterministic optimal sampling mask. We then propose a stochastic greedy algorithm that (i) provides an approximate solution to this problem, and (ii) resolves the scaling issues of [1, 2]. We validate its performance on in vivo dynamic MRI with retrospective undersampling, showing that our method preserves the performance of [1, 2] while reducing the computational burden by a factor close to 200. Our implementation is available at https://github.com/t-sanchez/stochasticGreedyMRI.