matrice trouver grâce à l'optimisation

Question

Je cherche algorithme pour résoudre le problème suivant:

J'ai deux ensembles de vecteurs, et je veux trouver la matrice qui correspond le mieux approximative de la transformation des vecteurs d'entrée aux vecteurs de sortie.

vecteurs sont 3x1, de sorte que la matrice est 3x3.

Ceci est le problème général. Mon problème particulier est que j'ai un ensemble de couleurs RVB, et un autre jeu qui contient la couleur désirée. Je suis en train de trouver un RGB à la transformation RVB me donner des couleurs plus proches de celles souhaitées.

Il y a correspondance entre l'entrée et les vecteurs de sortie, de sorte que le calcul d'une fonction d'erreur qui devrait être réduite au minimum est la partie facile. Mais comment puis-je réduire cette fonction?

Answer 1

Vous ne spécifiez pas une langue, mais voici comment j'aborder le problème dans Matlab.

• v1 est une matrice 3XN, contenant les couleurs d'entrée dans des vecteurs verticaux
• v2 est une matrice contenant 3XN les couleurs de votre sortie

Vous voulez résoudre le système

M*v1 = v2
M = v2*inv(v1)

Cependant, v1 est pas directement inversible, puisque ce n'est pas une matrice carrée. Matlab résoudra cela automatiquement l'opération de mrdivide (M = v2 / v1), où M est la meilleure solution en forme.

eg: 
>> v1 = rand(3,10);
>> M = rand(3,3);
>> v2 = M * v1;
>> v2/v1 - M

ans =

   1.0e-15 *

    0.4510    0.4441   -0.5551
    0.2220    0.1388   -0.3331
    0.4441    0.2220   -0.4441

>> (v2 + randn(size(v2))*0.1)/v1 - M
ans =

    0.0598   -0.1961    0.0931
   -0.1684    0.0509    0.1465
   -0.0931   -0.0009    0.0213

Cette donne une solution plus agnostique langue sur la façon de résoudre le problème.

Answer 2

Ceci est un problème d'algèbre linéaire classique, la phrase clé de recherche sur est « régression linéaire multiple ».

J'ai dû coder une variation de nombreuses reprises au fil des ans. Par exemple, le code pour calibrer un écran tactile digitizer tablet ou stylet utilise le même calcul.

---

Voici le calcul:

Soit p est un vecteur d'entrée et q le vecteur de sortie correspondant.

La transformation que vous voulez est une matrice 3x3; appeler .

Pour une seule entrée et le vecteur de sortie p et q , il y a un vecteur d'erreur e

e = q - A x p

Le carré de l'amplitude de l'erreur est une valeur scalaire:

e T x e = ( q - A x p ) T x ( q - A x p )

(où l'opérateur T est transposé).

Qu'est-ce que vous voulez vraiment réduire au minimum la somme est de e valeurs sur les jeux:

E = somme ( e )

Cela satisfait minimum de l'équation matricielle D = 0 où

D (i, j) = la dérivée partielle de E par rapport à A (i, j)

Supposons que vous avez entrée N et des vecteurs de sortie.

Votre ensemble d'entrée 3 est une matrice des vecteurs 3xN; appeler cette matrice P . La colonne i de P est le vecteur d'entrée i.

est l'ensemble des vecteurs de sortie 3; appeler cette matrice Q .

Lorsque vous rectifiez à travers toutes l'algèbre, la solution est

A = Q x P T x ( P x P T ) ^ -1

(où ^ -1 est l'opérateur inverse - désolé pas d'exposants ou indices)

---

Voici l'algorithme:

Créer la matrice 3xN P à partir de l'ensemble de vecteurs d'entrée.

Créer la matrice 3xN Q à partir de l'ensemble de vecteurs de sortie.

Matrice Multiplier R = P x transposer ( P )

Calculer la inverseOf R

Matrice Multiplier A = Q x transposer ( P ) x inverse ( R )

en utilisant la multiplication de la matrice et des routines d'inversion de la matrice de votre bibliothèque d'algèbre linéaire de choix.

---

Cependant , une matrice de transformation affine 3x3 est capable d'évoluer et faire tourner les vecteurs d'entrée, mais pas faire toute traduction! Cela pourrait ne pas être assez général pour votre problème. Il est généralement une bonne idée d'ajouter un « 1 » à la fin de chacun des 3 vecteurs pour faire ensuite un 4-vecteur, et rechercher la meilleure 3x4 matrice de transformation qui minimise l'erreur. Cela ne peut pas faire du mal; il ne peut conduire à un meilleur ajustement des données.

Answer 3

Certains algèbre linéaire devrait être suffisant:

Ecrire la différence quadratique moyenne entre les entrées et les sorties (la somme des carrés de chaque différence entre chaque valeur d'entrée et de sortie). Je suppose que ce que la définition de « meilleure approximation »

Ceci est une fonction quadratique de vos 9 coefficients de matrice inconnus.

Pour minimiser, dériver par rapport à chacun d'eux.

Vous obtiendrez un système linéaire de 9 équations que vous avez à résoudre pour obtenir la solution (unique ou une variété de l'espace en fonction de l'ensemble d'entrée)

Lorsque la fonction de différence n'est pas quadratique, vous pouvez faire la même chose, mais vous devez utiliser une méthode itérative pour résoudre le système d'équations.