Discussion :

[Nesbit]

Et pour {1,4,6,8,10} c'est optimal? (discussion avec moi-même : la réponse est oui! )

Bien sûr que "oui".

C'est dommage l'algorithme est tout bête, je m'attendais à quelque chose de plus joli.

J'ai du mal à prouver ou réfuter l'algo donné par prgasp77. Je continue avec ça après manger. A toute.

[pseudocode]

C'est plutôt 19/7 = 2.71429..., n'est-ce pas ?
Donc devrait être "5 espacements de taille 3 et 2 espacements de taille 2".

Ca marche aussi. C'est simplement la définition de espacement qui n'est pas la même.

Moi je compte l'espace vide entre les échantillons.

1 2 3 4 5 6 7 8 9
  X <-------> Y     
  
X: position = 2
Y: position = 8
Espacement entre X et Y = 5

[prgasp77]

?

[Nesbit]

Je continue...

Donc, pour rappeler, j'ai trouvé que la solution optimale contient et doit contenir (n-r) nombres de valeur q et r nombres de valeur (q+1) où q=N/n et r=N%n.

Reprenons l'exemple de prgasp77: choisir 7 parmi 19 points.
On a N=19, n=7, q=N/n=2, r=N%n=5. La solution contient donc deux (i.e. n-r) 'espacements' de 2 (i.e. q) et cinq (i.e. r) 'espacements' de 3 (i.e. q+1). On retrouve bien le résultat que pseudocode a confirmé.

Pour répondre donc à la question initiale, une solution optimale pour choisir n points parmi N points {1,2,...,N} est
{q, 2q, 3q,..., (n-r)q, (n-r)q+(q+1), (n-r)q+2(q+1),..., (n-r)q+r(q+1)}.

Maintenant, deux questions se posent:

1. La solution donné par prgasp77 est-elle optimale ?
Les 'espacements' donnés par celle-là sont:

Si on arrive à montrer que parmi les x_i, il y a (n-r) valeur de q et r valeur de q+1, alors elle est optimale.

2. On sait qu'une des solutions optimales est (exprimée avec la notion 'espacement'): q,q,..,q,q+1,q+1,...,q+1 (il y a n-r fois q et r fois q+1). Maintenant, si on ajoute une contrainte: il faut que les (q+1) soient le plus uniformément répartis possible, alors cette solution n'est plus optimale. Comment fait-on ?

[pseudocode]

Pour info, Stuart P. LLoyd a montré il y a plus de 50 ans que l'arrondi au plus proche voisin donnait un quantificateur régulier optimal (au sens de l'erreur quadratique moyenne).

[prgasp77]

Pour info, Stuart P. LLoyd a montré il y a plus de 50 ans que l'arrondi au plus proche voisin donnait un quantificateur régulier optimal (au sens de l'erreur quadratique moyenne).

Ça me dit quelque chose ... a-t-il été aidé dans sa tâche par un certain Marshal ? Il était question de minimiser l'erreur quadratique d'un quantificateur, n'est-ce pas ?

[pseudocode]

Ça me dit quelque chose ... a-t-il été aidé dans sa tâche par un certain Marshal ? Il était question de minimiser l'erreur quadratique d'un quantificateur, n'est-ce pas ?

Ca ne me dit rien. Je faisais référence au papier "Least Squares Quantization in PCM" qui est à la base de l'algo Lloyd-Max.

[prgasp77]

C'est bien ce à quoi je faisais référence (en tout les cas, essayais de), le Marshal est sorti de mon imagination >_<