Быстрый / эффективный способ разложения разделяемых целочисленных коэффициентов 2D-фильтра

21

Я хотел бы иметь возможность быстро определить, можно ли разделить данное двумерное ядро ​​целочисленных коэффициентов на два одномерных ядра с целочисленными коэффициентами. Например

 2   3   2
 4   6   4
 2   3   2

делится на

 2   3   2

а также

 1
 2
 1

Фактический тест на разделимость кажется довольно простым с использованием целочисленной арифметики, но разложение на 1D-фильтры с целыми коэффициентами оказывается более сложной задачей. Трудность заключается в том, что отношения между строками или столбцами могут быть нецелыми (рациональные дроби), например, в приведенном выше примере мы имеем отношения 2, 1/2, 3/2 и 2/3.

Я действительно не хочу использовать тяжелый подход, такой как SVD, потому что (a) это относительно вычислительно дорого для моих нужд и (b) это все еще не обязательно помогает определить целые коэффициенты.

Любые идеи ?


ДАЛЬНЕЙШАЯ ИНФОРМАЦИЯ

Коэффициенты могут быть положительными, отрицательными или нулевыми, и могут быть патологические случаи, когда сумма одного или обоих одномерных векторов равна нулю, например

-1   2  -1
 0   0   0
 1  -2   1

делится на

 1  -2   1

а также

-1
 0
 1
Пол Р
источник
1
Я помню, как пытался понять это еще в колледже. Я почти преуспел, но я не помню как. =) Я не могу перестать думать об этом сейчас, когда вы упомянули об этом!
Фонон
@Phonon: хе - ну, продолжай думать - я мог бы использовать вдохновение на этот. ;-)
Paul R
Можно ли сделать то же самое, но для значений типа double или float?
Диего Каталано
@DiegoCatalano: см. Ответ Дениса ниже и вопрос, на который он ссылается на math.stackexchange.com - я думаю, это может сработать для более общего случая коэффициентов с плавающей запятой.
Пол Р
@PaulR, как можно с тобой связаться по электронной почте? Спасибо.
Ройи

Ответы:

11

Я взял @Phononответ и несколько изменил его, чтобы он использовал подход GCD только для верхней строки и левого столбца, а не для сумм строк / столбцов. Это, кажется, справляется с патологическими случаями немного лучше. Он все еще может потерпеть неудачу, если верхняя строка или левый столбец - все нули, но эти случаи могут быть проверены до применения этого метода.

function [X, Y, valid] = separate(M)    % separate 2D kernel M into X and Y vectors 
  X = M(1, :);                          % init X = top row of M
  Y = M(:, 1);                          % init Y = left column of M
  nx = numel(X);                        % nx = no of columns in M
  ny = numel(Y);                        % ny = no of rows in M
  gx = X(1);                            % gx = GCD of top row
  for i = 2:nx
    gx = gcd(gx, X(i));
  end
  gy = Y(1);                            % gy = GCD of left column
  for i = 2:ny
    gy = gcd(gy, Y(i));
  end
  X = X / gx;                           % scale X by GCD of X
  Y = Y / gy;                           % scale Y by GCD of Y
  scale = M(1, 1) / (X(1) * Y(1));      % calculate scale factor
  X = X * scale;                        % apply scale factor to X
  valid = all(all((M == Y * X)));       % result valid if we get back our original M
end

Большое спасибо @Phononи @Jason Rза оригинальные идеи для этого.

Пол Р
источник
10

Понял! Размещая код MATLAB, выложу объяснение сегодня вечером или завтра

% Two original arrays
N = 3;
range = 800;
a = round( range*(rand(N,1)-0.5) )
b = round( range*(rand(1,N)-0.5) )

% Create a matrix;
M = a*b;
N = size(M,1);

% Sanity check
disp([num2str(rank(M)) ' <- this should be 1!']);

% Sum across rows and columns
Sa = M * ones(N,1);
Sb = ones(1,N) * M;

% Get rid of zeros
SSa = Sa( Sa~=0 );
SSb = Sb( Sb~=0 );

if isempty(SSa) | isempty(SSb)
    break;
end

% Sizes of array without zeros
Na = numel(SSa);
Nb = numel(SSb);

% Find Greatest Common Divisor of Sa and Sb.
Ga = SSa(1);
Gb = SSb(1);

for l=2:Na
    Ga = gcd(Ga,SSa(l));
end

for l=2:Nb
    Gb = gcd(Gb,SSb(l));
end

%Divide by the greatest common divisor
Sa = Sa / Ga;
Sb = Sb / Gb;

%Scale one of the vectors
MM = Sa * Sb;
Sa = Sa * (MM(1) / M(1));

disp('Two arrays found:')
Sa
Sb
disp('Sa * Sb = ');
Sa*Sb
disp('Original = ');
M
Phonon
источник
Спасибо - это здорово - вчера я лежал без сна, думая о факторизации коэффициентов и т. Д., Но просто использовать GCD, как это, намного проще и элегантнее. К сожалению, есть еще одна морщина, чтобы сгладить - она ​​должна работать как с положительными, так и с отрицательными коэффициентами, и это может привести к вырожденным случаям, например A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;. Проблема здесь в том, что sum(A) = 0так Sb = [0 0 0 0 0]. Я попытаюсь изменить ваш алгоритм, чтобы он использовал сумму абсолютных значений коэффициентов, и посмотрим, поможет ли это. Еще раз спасибо за помощь.
Пол Р
OK - это выглядит , как вы все еще можете получить ГКД и делать масштабирование с использованием abs(M), то есть , Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);а затем продолжить , как указано выше, но я пока не могу понять , как восстановить знаки Sa, Sbв конце концов. Я добавил патологический пример, который иллюстрирует проблему в оригинальном вопросе выше.
Пол Р
Я думаю, что у меня сейчас есть рабочее решение - я опубликовал его в качестве отдельного ответа, но я благодарен вам за основную идею. Еще раз спасибо !
Пол Р
7

Может быть, я упрощаю проблему, но кажется, что вы могли бы:

  • NMAaii=0,1,,N1
  • j>0

    • aja0jrj
    • rj
    • rjaja0j0x
    • aja0
  • x

xk,norm=xkmini=0N1xi
  • После этого нормализованный список соотношений будет содержать значение 1 для строки с наименьшей нормой. Вы хотите посмотреть, можете ли вы каким-либо образом масштабировать этот список, чтобы получить список, содержащий все целые коэффициенты. Подход методом грубой силы может просто выполнить линейный поиск, то есть вычислить: Для каждого значения , после расчета масштабированного списка соотношений, вам нужно будет проверить каждое из них, чтобы увидеть, являются ли они целочисленными (опять же, с некоторым допуском). Установите равным наибольшему знаменателю, который вы хотите искать в междурядных соотношениях. х лет с л е д =К й п о р м ,К=1,2,...,МКМxnorm
    xscaled=Kxnorm,K=1,2,,M
    KM

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

Джейсон Р
источник
Спасибо - я думаю, что, возможно, я шел в каком-то направлении, пока не увяз в деталях. Для меня не на 100% ясно, что вы всегда найдете решение с использованием этого метода, но в любом случае, я должен, вероятно, написать код и попробовать его на нескольких примерах. У меня есть предчувствие, что, возможно, его придется применять как по строкам, так и по столбцам, чтобы увидеть, какое из них дает «лучшее» решение. Спасибо, что нашли время разобрать детали - я займусь этим и сообщу, как это работает.
Paul R
Не могли бы вы найти наибольший общий делитель первых элементов строк и использовать его для определения базового вектора?
Джим Клэй,
@JimClay: Да, это действительно то, что вы делаете в конце, если у вас есть эта функциональность доступна.
Джейсон Р
3

Другой способ - найти отделимое приближение к вашему ядру и посмотреть, насколько оно близко. Это можно сделать двумя способами: минимизировать : 1) Оптимизация методом грубой силы ; это занимает время ~ сумму, а не произведение их длин 2) для фиксированных и , оптимальный - это просто проекция, поэтому оптимизируйте по очереди.A | A - x y z | x y z y z x x y z x y z . , ,xyzA|Axyz|
x y z
yzxx y z x y z ...

(Из приблизительных сверток как сумм отделимых сверток на math.stackexchange.)

Денис
источник
1
Старайтесь не отвечать на вопросы с необъяснимыми ссылками. Лучше объяснить необходимые детали в своем ответе и включить ссылку только для справки; таким образом, если ссылка не работает, существенные детали ответа все еще там.
Сэм Малони
@SamMaloney: я не вижу причин, почему это необходимо. Ссылка объясняет все подробно. Он все равно появится в поиске вопросов и ответов. Так почему не?
Нареш
1
@Naresh Я упоминаю об этом только потому, что одной из целей сайтов по обмену стека является создание хранилища ответов на вопросы для дальнейшего использования. Поэтому, хотя я понимаю, что эта конкретная ссылка относится к другому сайту SE и должна быть довольно безопасной, лучше всего не полагаться на ссылки, работающие через несколько лет. . Давая общую схему этих «два простых методов в ответе будет гарантировать , что информация сохраняется , даже если что - то случится связанным вопрос , хотя сказал , как я, это было более общего замечание о наилучшей практике в отношении ссылок в ответах.
Сэм Мэлони