Nombre cardinal | EPFL Graph Search

vignette|Le nombre cardinal des deux ensembles X et Y est 4 En linguistique, les nombres entiers naturels zéro, un, deux, trois, etc. s’appellent des adjectifs numéraux cardinaux. En théorie des ensembles, le nombre cardinal ou cardinal d'un ensemble E (fini ou infini) est, intuitivement, le « nombre » d'éléments lui appartenant. On peut définir formellement ce « nombre » comme la classe de tous les ensembles équipotents à E (c'est-à-dire en bijection avec E), ou, de manière fort différente, comme le plus petit ordinal équipotent à E. Le cas fini Les saisons, les points cardinaux, les fils Aymon, forment trois ensembles partageant une certaine qualité, qu'ils ne partagent pas avec l'ensemble des doigts de la main : on peut mettre en évidence cette qualité en faisant correspondre un à un les éléments respectifs de ces ensembles et dire qu'ils sont de cardinal « quatre ». « Quatre » serait alors la signature de la propriété en question. De la même façon l'ensemble des doig

New Results on Optimizing Rooted Triplets Consistency

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem (MaxRTC) and the minimum rooted triplets inconsistency problem (MinRTI) in which the input is a set R of rooted triplets, and where the objectives are to find a largest cardinality subset of R which is consistent and a smallest cardinality subset of R whose removal from R results in a consistent set, respectively. We first show that a simple modification to Wu’s Best-Pair-Merge-First heuristic [25] results in a bottom-up-based 3-approximation for MaxRTC. We then demonstrate how any approximation algorithm for MinRTI could be used to approximate MaxRTC, and thus obtain the first polynomial-time approximation algorithm for MaxRTC with approximation ratio smaller than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any tree is approximately one third, and then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both MaxRTC and MinRTI are NP-hard even if restricted to minimally dense instances. Finally, we prove that MinRTI cannot be approximated within a ratio of (log n) in polynomial time, unless P = NP.

Springer2008

Scalable Learning-Based Sampling Optimization For Compressive Dynamic MRI

Volkan Cevher, Armin Eftekhari, Baran Gözcü, Thomas Sanchez, Ruud van Heeswijk

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.

IEEE2020

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