trovando matrice attraverso l'ottimizzazione

Question

Sto cercando algoritmo per risolvere il seguente problema:

Ho due insiemi di vettori, e voglio trovare la matrice che meglio approssimano la trasformazione dai vettori di ingresso per i vettori di uscita.

vettori sono 3x1, così matrice è 3x3.

Questo è il problema generale. Il mio problema particolare è che ho un insieme di colori RGB, e un altro set che contiene il colore desiderato. Sto cercando di trovare una RGB a RGB trasformazione che mi avrebbe dato i colori più vicini a quelli desiderati.

C'è corrispondenza tra l'ingresso e vettori uscita, quindi calcolare una funzione di errore che deve essere minimizzato è la parte facile. Ma come posso ridurre al minimo questa funzione?

Answer 1

Non si specifica una lingua, ma ecco come vorrei affrontare il problema in Matlab.

• v1 è una matrice 3XN, contenente i colori di input in vettori verticali
• v2 è anche una matrice contenente il 3XN colori di output

Si vuole risolvere il sistema

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

Tuttavia, v1 non è direttamente invertibile, dato che non è una matrice quadrata. Matlab risolverà automaticamente con il funzionamento mrdivide (M = v2 / v1), dove M è la soluzione migliore vestibilità.

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

Questo dà una soluzione più indipendente dal linguaggio su come risolvere il problema.

Answer 2

Questo è un classico problema di algebra lineare, la frase chiave per cercare è "regressione lineare multipla".

Ho dovuto codificare qualche variazione di questo molte volte nel corso degli anni. Ad esempio, il codice per calibrare un digitalizzatore tablet o lo stilo touch-screen utilizza la stessa matematica.

---

Ecco la matematica:

Let p essere un vettore di ingresso e q il corrispondente vettore d'uscita.

La trasformazione che si desidera è una matrice 3x3; chiamare A .

Per un singolo vettore di ingresso ed uscita p e q , v'è un vettore errore di e

e = q - A x p

La piazza della grandezza dell'errore è un valore scalare:

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

(in cui l'operatore T è trasposizione).

Che cosa si vuole veramente ridurre al minimo è la somma di e i valori oltre i set:

E = somma ( e )

This minime soddisfa l'equazione matriciale D = 0 dove

D (i, j) = la derivata parziale della E rispetto alla A (i, j)

Diciamo che sono vettori di ingresso e di uscita N.

L'apparecchio di ingresso 3-vettori è una matrice 3XN; chiamare questa matrice P . La colonna esimo P è il vettore di ingresso-esimo.

Quindi, è l'insieme di uscita 3-vettori; chiamare questa matrice D .

Quando si macinare attraverso tutta l'algebra, la soluzione è

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

(dove ^ -1 è l'operatore inversa - dispiace per non apice o un pedice)

---

Ecco l'algoritmo:

Crea matrice 3XN P dal set di vettori d'ingresso.

Crea matrice 3XN D dal set di vettori di uscita.

Matrix Moltiplica R = P x trasposizione ( P )

Si calcoli l'inverseOf R

Matrix Moltiplica A = Q x trasposizione ( P ) x inversa ( R )

utilizzando la moltiplicazione di matrici e le routine matrice di inversione della libreria di algebra lineare di scelta.

---

Tuttavia , una trasformazione affine 3x3 matrice è in grado di scalatura e rotazione dei vettori d'ingresso, ma non fare qualsiasi traduzione! Questo potrebbe non essere sufficientemente generali per il vostro problema. Di solito è una buona idea per aggiungere un "1" alla fine di ciascuno dei 3 vettori per fare poi un 4-vettore, e cercare il miglior 3x4 trasformare matrice che minimizza l'errore. Questo non può far male; può solo portare ad una migliore vestibilità dei dati.

Answer 3

Alcuni algebra lineare dovrebbe essere sufficiente:

Valuta la differenza media al quadrato tra ingressi e uscite (la somma dei quadrati delle differenze tra ogni ogni ingresso e il valore di uscita). Presumo che questo come definizione di "best approssimativa"

Questa è una funzione quadratica delle vostre 9 coefficienti di matrice sconosciuti.

Per ridurre al minimo esso, ricavare con rispetto a ciascuno di loro.

Si otterrà un sistema lineare di equazioni 9 bisogna risolvere per ottenere la soluzione (unica o di una varietà di spazio a seconda del set di input)

Quando la funzione di differenza non è quadratica, si può fare lo stesso, ma è necessario utilizzare un metodo iterativo per risolvere il sistema di equazioni.