Problème d'optimisation avec des matrices
dans Analyse
Bonjour je bloque sur un problème et j'aurais besoin d'aide (je ne sais pas vraiment si ce problème s'inscrit dans le domaine de l'analyse).
Imaginons un ensemble de points du plan assez grand $X \in \mathbb{R}^{n \times 2}$ (avec $n=10 000$ par exemple) et un autre ensemble plus petit $Y \in \mathbb{R}^{p \times 2}$ (avec $p=100$ plus petit). On voudrait trouver les $p$ points de $X$ qui sont les plus proches des points de $Y$. On cherche donc à minimiser $\sum_{i \leq p} || (\Pi X)_i - Y_i ||_2^2,\ $ où $\Pi \in \mathbb{R}^{p \times n}$ est une matrice de sélection. Imaginons que $n=5$ , $p=3$ et que la solution est donnée par le 1er, le 4ème et le 5ème point de $X$. Par exemple : $X= \begin{pmatrix}
0.5 & 0.4 \\
1 & 2 \\
1 & 2 \\
-1 & 4 \\
3 & 0.7 \\
\end{pmatrix}\ $ et $\ Y= \begin{pmatrix}
0.49 & 0.39 \\
-1.1 & 3.9 \\
2.9 & 0.71\\
\end{pmatrix},\ $ alors $\ \Pi = \begin{pmatrix}
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{pmatrix}$
Imaginons un ensemble de points du plan assez grand $X \in \mathbb{R}^{n \times 2}$ (avec $n=10 000$ par exemple) et un autre ensemble plus petit $Y \in \mathbb{R}^{p \times 2}$ (avec $p=100$ plus petit). On voudrait trouver les $p$ points de $X$ qui sont les plus proches des points de $Y$. On cherche donc à minimiser $\sum_{i \leq p} || (\Pi X)_i - Y_i ||_2^2,\ $ où $\Pi \in \mathbb{R}^{p \times n}$ est une matrice de sélection. Imaginons que $n=5$ , $p=3$ et que la solution est donnée par le 1er, le 4ème et le 5ème point de $X$. Par exemple : $X= \begin{pmatrix}
0.5 & 0.4 \\
1 & 2 \\
1 & 2 \\
-1 & 4 \\
3 & 0.7 \\
\end{pmatrix}\ $ et $\ Y= \begin{pmatrix}
0.49 & 0.39 \\
-1.1 & 3.9 \\
2.9 & 0.71\\
\end{pmatrix},\ $ alors $\ \Pi = \begin{pmatrix}
1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1
\end{pmatrix}$
Réponses
-
Bonjour
Je ne connais pas ce genre de problème et je me demande s'il n'aurait pas sa place dans la rubrique combinatoire et graphe.
Une solution serait de programmer le calcul pour chaque $\Pi$ possible. Malheureusement le nombre de possibilités est Binomial(n,p) (ou A(n,p)? ) mais de toute façon c'est trop grand. -
Bonjour,
Donc si je comprends bien, on a $n=10^4$ points marqués $P_i$ dans le plan.
On cherche à calculer l'application qui à tout point $M$ associe le $i$ tel que $d(M,P_i)$ est minimal. (Diagramme de Voronoi : https://en.wikipedia.org/wiki/Voronoi_diagram )
Et puis on cherche à le faire efficacement, parce qu'on va répéter $p=100$ fois.
C'est ça ? -
Bonjour Marsup merci de ta réponse. Je ne suis pas sûr d'avoir bien compris. On a $n=10e4$ points marqués dans le plan $P_i$ ainsi que $p=100$ autres points $M_j$ marqués dans le plan également. Pour un index $j$ donné on cherche l'index $i$ qui minimise $d(M_i,P_j)$.
Connectez-vous ou Inscrivez-vous pour répondre.
Bonjour!
Catégories
- 163.1K Toutes les catégories
- 7 Collège/Lycée
- 21.9K Algèbre
- 37.1K Analyse
- 6.2K Arithmétique
- 52 Catégories et structures
- 1K Combinatoire et Graphes
- 11 Sciences des données
- 5K Concours et Examens
- 11 CultureMath
- 47 Enseignement à distance
- 2.9K Fondements et Logique
- 10.3K Géométrie
- 62 Géométrie différentielle
- 1.1K Histoire des Mathématiques
- 68 Informatique théorique
- 3.8K LaTeX
- 39K Les-mathématiques
- 3.5K Livres, articles, revues, (...)
- 2.7K Logiciels pour les mathématiques
- 24 Mathématiques et finance
- 312 Mathématiques et Physique
- 4.9K Mathématiques et Société
- 3.3K Pédagogie, enseignement, orientation
- 10K Probabilités, théorie de la mesure
- 772 Shtam
- 4.2K Statistiques
- 3.7K Topologie
- 1.4K Vie du Forum et de ses membres