поиск матрицы через оптимизацию

Question

Я ищу алгоритм для решения следующей проблемы:

У меня есть два набора векторов, и я хочу найти матрицу, которая наилучшим образом приближает преобразование от входных векторов к выходным векторам.

векторы 3x1, поэтому матрица 3x3.

Это общая проблема. Моя конкретная проблема - у меня есть набор цветов RGB и другой набор, который содержит желаемый цвет. Я пытаюсь найти преобразование RGB в RGB, которое позволило бы мне приблизить цвета к желаемым.

Существует соответствие между входным и выходным векторами, поэтому вычисление функции ошибки, которая должна быть минимизирована, является легкой частью. Но как я могу минимизировать эту функцию?

Answer 1

Это классическая задача линейной алгебры, ключевая фраза для поиска - «множественная линейная регрессия».

Мне приходилось кодировать некоторые вариации этого много раз за эти годы. Например, код для калибровки планшета планшета или сенсорного экрана стилуса использует ту же математику.

---

Вот математика:

Пусть p будет входным вектором, а q соответствующим выходным вектором.

Требуемое преобразование - это матрица 3x3; назовите это A .

Для одного вектора входа и выхода p и q существует вектор ошибки e

e = q - A x p

Квадрат величины ошибки является скалярным значением:

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

(где оператор T транспонирован).

Что вы действительно хотите минимизировать, так это сумма значений e по наборам:

E = сумма ( e )

Этот минимум удовлетворяет матричному уравнению D = 0, где

D (i, j) = частная производная E относительно A (i, j)

Скажем, у вас есть N входных и выходных векторов.

Ваш набор входных 3-векторов представляет собой матрицу 3xN; Назовите эту матрицу P . I-й столбец P - это i-й входной вектор.

Таков набор выходных 3-векторов; Назовите эту матрицу Q .

Когда вы шлифуете всю алгебру, решение будет

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

(где ^ -1 - обратный оператор - извините за отсутствие индексов или индексов)

---

Вот алгоритм:

Создать матрицу 3xN P из набора входных векторов.

Создать матрицу 3xN Q из набора выходных векторов.

Матричное умножение R = P x транспонирование ( P )

Вычислить обратную величину R

Матричное умножение A = Q x транспонирование ( P ) x обратное ( R )

с использованием процедур умножения матриц и обращения матриц выбранной вами библиотеки линейной алгебры.

---

Однако , матрица аффинного преобразования 3x3 способна масштабировать и вращать входные векторы, но не выполняет какой-либо перевод! Это может быть недостаточно общим для вашей проблемы. Обычно хорошей идеей является добавление «1» в конце каждого из 3-векторов, чтобы затем получить 4-вектор, и поиск лучшей матрицы преобразования 3х4, которая минимизирует ошибку. Это не может повредить; это может только привести к лучшему соответствию данных.

Answer 2

Достаточно линейной алгебры:

Запишите среднеквадратичную разницу между входами и выходами (сумма квадратов каждой разности между каждым входным и выходным значением). Я предполагаю, что это определение «наилучшего приближенного» * ​​1003 *

Это квадратичная функция ваших 9 неизвестных матричных коэффициентов.

Чтобы свести его к минимуму, выведите его по каждому из них.

Вы получите линейную систему из 9 уравнений, которую нужно решить, чтобы получить решение (уникальное или пространственное разнообразие в зависимости от входного набора)

Если разностная функция не является квадратичной, вы можете сделать то же самое, но вы должны использовать итерационный метод для решения системы уравнений.

Answer 3

Вы не указываете язык, но вот как я мог бы подойти к этой проблеме в Matlab.

• v1 - это матрица 3xn, содержащая введенные вами цвета в вертикальных векторах
• v2 - это также матрица 3xn, содержащая ваши выходные цвета

Вы хотите решить систему

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

Тем не менее, v1 не является напрямую обратимым, поскольку это не квадратная матрица. Matlab решит это автоматически с помощью операции mrdivide (M = v2 / v1), где M - наилучшее решение.

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

Этот дает более независимое от языка решение о том, как решить проблему.