la búsqueda de la matriz a través de la optimización

Question

Busco algoritmo para resolver el siguiente problema:

Tengo dos conjuntos de vectores, y yo quiero encontrar la matriz que mejor aproximación de la transformación de los vectores de entrada para los vectores de salida.

vectores son 3x1, por lo que la matriz es de 3x3.

Este es el problema general. Mi problema particular es que tengo un conjunto de colores RGB, y otro conjunto que contiene el color deseado. Estoy tratando de encontrar una transformación de RGB a RGB que me daría colores más cercanos a los deseados.

Hay correspondencia entre la entrada y vectores de salida, por lo que el cálculo de una función de error que debe ser minimizada es la parte fácil. Pero, ¿cómo puedo minimizar esta función?

Answer 1

No se especifica un idioma, pero existen algunas cosas me abordar el problema en Matlab.

• v1 es una matriz 3XN, que contiene sus colores de entrada en vectores verticales
• v2 es también una matriz que contiene su 3XN colores de salida

¿Quieres resolver el sistema

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

Sin embargo, v1 no es directamente invertible, ya que no es una matriz cuadrada. Matlab va a resolver este automáticamente con la operación mrdivide (M = v2 / v1), donde M es la mejor solución en forma.

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

Este da una solución más independiente del idioma en la forma de resolver el problema.

Answer 2

Este es un problema de álgebra lineal clásica, la frase clave para buscar en está "regresión lineal múltiple".

He tenido que codificar alguna variación de esto muchas veces a lo largo de los años. Por ejemplo, el código para calibrar una pantalla táctil tableta digitalizadora o el lápiz utiliza el mismo matemáticas.

---

Esta es la matemática:

Let p ser un vector de entrada y q el correspondiente vector de salida.

La transformación que queremos es una matriz 3x3; llamarlo .

Para una sola entrada y salida vector p y q , no es un vector de error e

e = q - A x p

El cuadrado de la magnitud del error es un valor escalar:

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

(donde el operador T es la transposición).

Lo que realmente desea reducir al mínimo es la suma de e valores por encima de los conjuntos:

E = sum ( e )

Este mínimo satisface la ecuación de matriz D = 0 donde

D (i, j) = la derivada parcial de E con respecto a A (i, j)

Supongamos que tiene entrada y salida N vectores.

Su conjunto de entrada 3-vectores es una matriz 3XN; llamar a esta matriz P . La columna i-ésima de P es el vector de entrada i-ésimo.

Así es el conjunto de salida 3-vectores; llamar a esta matriz Q .

Cuando se muelen a través de todo el álgebra, la solución es

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

(donde ^ -1 es el operador inversa - lo de no superíndices o subíndices)

---

Aquí está el algoritmo:

Crea la matriz 3XN P a partir del conjunto de vectores de entrada.

Crea la matriz 3XN Q a partir del conjunto de vectores de salida.

Matrix Multiply R = P x transpuesta ( P )

Calcule la inverseof R

Matrix Multiply A = Q x transpuesta ( P ) x inversa ( R )

mediante la multiplicación de la matriz y rutinas matriz de inversión de la biblioteca de álgebra lineal de elección.

---

Sin embargo , una matriz de transformada afín 3x3 es capaz de escalar y rotar los vectores de entrada, pero no haciendo cualquier traducción! Esto podría no ser lo suficientemente general para su problema. Por lo general es una buena idea para añadir un "1" en el extremo de cada uno de los 3-vectores para hacer luego un 4-vector, y buscar el mejor 3x4 matriz de transformada que minimiza el error. Esto no puede hacer daño; sólo puede conducir a un mejor ajuste de los datos.

Answer 3

Algunos álgebra lineal debería ser suficiente:

Escribir la diferencia media al cuadrado entre entradas y salidas (la suma de los cuadrados de cada diferencia entre cada entrada y valor de salida). Asumo esto como definición de "mejor aproximada"

Esta es una función cuadrática de sus coeficientes de la matriz 9 desconocidas.

Para minimizarlo, derivar con respecto a cada uno de ellos.

Usted recibirá un sistema lineal de ecuaciones 9 que tienen que resolver para obtener la solución (o una variedad única de espacio en función del conjunto de entrada)

Cuando la función de diferencia no es cuadrática, se puede hacer lo mismo, pero hay que utilizar un método iterativo para resolver el sistema de ecuaciones.