Как я могу векторизовать матрицу / ввод, чтобы scipy.optimize.minimize мог работать с ней? - PullRequest
Новая
       8

Как я могу векторизовать матрицу / ввод, чтобы scipy.optimize.minimize мог работать с ней?

0 голосов
/ 11 января 2019

Я столкнулся с проблемой при преобразовании неограниченной проблемы в scipy.optimize.minimize. Я хочу запустить метод L-BFGS.

Базовая проблема выглядела так:

мин || A - XY ||

s.t. X, Y

в то время как A является заданной матрицей и X $ \ in \ R ^ {nxl} $ и Y $ \ in \ R ^ {lxm} Поскольку scipy принимает только входные данные вектора, я попытался интерпретировать XY как большую переменную: Z = (X, Y), где я уже поместил столбцы X и Y друг под другом.

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

Вот мой код: 

import numpy as np
from scipy.optimize import minimize
R=np.array(np.arange(12)).reshape(3, 4)
Z0 = np.array(np.random.random(14))
#X=3x2 = 6
#Y=2x4 = 8
def whatineed (Z):
    return np.linalg.norm(R - np.dot(Z[:6].reshape(3,2),Z[6:].reshape(2,4)))

A = minimize(fun=whatineed, x0=Z0, method='L-BFGS-B', options={'disp': 1})

#print A

Выше приведен только (казалось бы?) Рабочий фиктивный код. Это дало мне / результат: 

x: array([ 1.55308851, -0.50000733,  1.89812395,  1.44382572,  2.24315938, 3.38765876,  0.62668062,  1.23575295,  1.8448253 ,  2.45389762, 1.94655245,  1.83844053,  1.73032859,  1.62221667])

Если я запускаю его с большим, он вообще не работает. 

RUNNING THE L-BFGS-B CODE

           * * *

Machine precision = 2.220D-16
 N =       377400     M =           10
 This problem is unconstrained.

At X0         0 variables are exactly at the bounds

не двигаясь дальше. R в действительности является более или менее разреженной матрицей. Но я действительно не знаю, ГДЕ для начала. Это мой код функции? Это редкость R? И то и другое? Что обходится?

Обновление: Солвер работает с ОЧЕНЬ маленьким измерением. Если я иду немного больше, эта ошибка происходит: 

ABNORMAL_TERMINATION_IN_LNSRCH                              

 Line search cannot locate an adequate point after 20 function
  and gradient evaluations.  Previous x, f and g restored.
 Possible causes: 1 error in function or gradient evaluation;
                  2 rounding error dominate computation.

 Cauchy                time 0.000E+00 seconds.
 Subspace minimization time 0.000E+00 seconds.
 Line search           time 0.000E+00 seconds.

 Total User time 0.000E+00 seconds.

Как вы можете видеть во время пользователя, проблема довольно мала и перестает работать. Запуск его от руки (L-BFGS) не приводит ни к каким шагам / спускам вообще.

1 Ответ

0 голосов
/ 12 января 2019

Если мы пытаемся решить 

min_{B is rank <= k} ‖ A - B ‖_2

решение , как известно, имеет ранг k усеченный SVD A .

Вместо этого мы пытаемся решить 

min_{X,Y} ‖ A - XY ‖_2

где X имеет форму n × k и Y имеет форму k × n (я использую k потому что его легче читать, чем l )

Заявка: Это эквивалентные проблемы. Чтобы увидеть это, нам нужно показать, что:

  1. XY - ранг <= <em>k (с указанными выше формами).
  2. любого ранга k может быть записана как произведение XY (с указанными выше формами).

Доказательство:

  1. Первое следует из того факта, что Y имеет ранг <= <em>k и что нулевой темп XY содержится в нулевом пространстве Y

  2. Второе следует из записи SVD ранга <= <em>k matrix B = UDV * и наблюдения того, что (UD) имеет форму n × k и V имеет форму k × n , где мы отбросили все, кроме первых k особых значений из разложения, поскольку они гарантированно равны нулю.

Осуществление Для решения поставленной задачи OP нам нужно только вычислить SVD A и урезать его до ранга k . Вы можете использовать np.linalg.svd или sp.sparse.linalg.svds в зависимости от того, является ли ваша матрица разреженной. Для простой версии ранг k svd может быть вычислен как: 

m,n = 10,20
A = np.random.randn(m,n)

k = 6
u,s,vt = np.linalg.svd(A)

X = u[:,:k]*s[:k]
Y = vt[:k]

print(X.shape, Y.shape)
print(np.linalg.norm(A-X@Y,2))

Синтаксис sp.sparse.linalg.svds почти такой же, за исключением того, что вы можете заранее указать ранг, который хотите.

...