Schneller / effizienter Weg, um trennbare ganzzahlige 2D-Filterkoeffizienten zu zerlegen

21

Ich möchte schnell feststellen können, ob ein gegebener 2D-Kern mit ganzzahligen Koeffizienten in zwei 1D-Kernel mit ganzzahligen Koeffizienten zerlegbar ist. Z.B

 2   3   2
 4   6   4
 2   3   2

ist trennbar in

 2   3   2

und

 1
 2
 1

Der eigentliche Test der Trennbarkeit scheint mit Integer-Arithmetik recht einfach zu sein, die Zerlegung in 1D-Filter mit Integer-Koeffizienten erweist sich jedoch als schwieriger. Die Schwierigkeit scheint in der Tatsache zu liegen, dass Verhältnisse zwischen Zeilen oder Spalten nicht ganzzahlig sein können (rationale Brüche), z. B. haben wir im obigen Beispiel Verhältnisse von 2, 1/2, 3/2 und 2/3.

Ich möchte nicht wirklich einen Hochleistungsansatz wie SVD verwenden, weil (a) er für meine Bedürfnisse relativ rechenintensiv ist und (b) es immer noch nicht unbedingt hilft, ganzzahlige Koeffizienten zu bestimmen .

Irgendwelche Ideen ?


WEITERE INFORMATIONEN

Koeffizienten können positiv, negativ oder null sein, und es kann pathologische Fälle geben, in denen die Summe eines oder beider 1D-Vektoren null ist, z

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

ist trennbar in

 1  -2   1

und

-1
 0
 1
Paul R
quelle
1
Ich erinnere mich, dass ich im College versucht habe, das herauszufinden. Ich hätte es fast geschafft, aber ich kann mich nicht erinnern, wie. =) Ich kann nicht aufhören darüber nachzudenken, jetzt wo du es erwähnt hast!
Phonon
@Phonon: heh - denk weiter nach - ich könnte hier Inspiration gebrauchen. ;-)
Paul R
Ist es möglich, dasselbe zu tun, außer für Double- oder Float-Werte?
Diego Catalano
@DiegoCatalano: Siehe Denis 'Antwort unten und die Frage, auf die er auf math.stackexchange.com verweist. Ich denke, das könnte für den allgemeineren Fall von Gleitkommakoeffizienten funktionieren.
Paul R
@PaulR, Wie könnte man Sie per E-Mail kontaktieren? Danke dir.
Royi

Antworten:

11

Ich habe die @PhononAntwort genommen und etwas modifiziert, so dass der GCD-Ansatz nur für die obere Zeile und die linke Spalte und nicht für Zeilen- / Spaltensummen verwendet wird. Dies scheint pathologische Fälle etwas besser zu behandeln. Es kann immer noch fehlschlagen, wenn die obere Zeile oder die linke Spalte Nullen sind. Diese Fälle können jedoch überprüft werden, bevor diese Methode angewendet wird.

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

Vielen Dank @Phononund @Jason Rfür die originellen Ideen dazu.

Paul R
quelle
10

Ich habs! Das Posten von MATLAB-Code wird heute Abend oder morgen eine Erklärung veröffentlichen

% 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
quelle
Danke - das ist großartig - ich lag letzte Nacht wach und dachte darüber nach, die Koeffizienten usw. zu faktorisieren, aber die Verwendung der GCD wie diese ist viel einfacher und eleganter. Leider gibt es immer noch eine Falte zum Ausbügeln - es muss sowohl mit positiven als auch negativen Koeffizienten gearbeitet werden, und dies kann zu degenerierten Fällen führen, z A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;. Das Problem hier ist das sum(A) = 0so Sb = [0 0 0 0 0]. Ich werde versuchen, Ihren Algorithmus so zu ändern, dass er die Summe der absoluten Werte der Koeffizienten verwendet, und prüfen, ob dies hilft. Danke nochmal für deine Hilfe.
Paul R
OK - es sieht aus wie Sie immer noch die GCDS bekommen können und die Skalierung tun , indem Sie abs(M), das heißt Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);und dann weiter wie oben, aber ich kann noch nicht sehen , wie die Zeichen wiederherzustellen Sa, Sbam Ende. Ich habe ein pathologisches Beispiel hinzugefügt, das das Problem in der ursprünglichen Frage oben veranschaulicht.
Paul R
Ich glaube, ich habe jetzt eine funktionierende Lösung - ich habe sie als separate Antwort veröffentlicht, aber der Verdienst geht an Sie für die zugrunde liegende Idee. Danke noch einmal !
Paul R
7

Vielleicht verharmlost ich das Problem, aber es sieht so aus, als könntest du:

  • NMEINeinichich=0,1,,N-1
  • j>0

    • einjein0jrj
    • rj
    • rjeinjein0j0x
    • einjein0
  • x

xk,nOrm=xkMindestich=0N-1xich
  • Danach enthält die normalisierte Liste der Verhältnisse den Wert 1 für die Zeile mit der kleinsten Norm. Sie möchten sehen, ob Sie diese Liste auf irgendeine Weise skalieren können, um eine Liste zu erhalten, die alle ganzzahligen Koeffizienten enthält. Ein Brute-Force-Ansatz könnte einfach eine lineare Suche durchführen, berechnen: Für jeden Wert von , nachdem Sie die skalierte Liste der Verhältnisse berechnet haben, müssen Sie jedes überprüfen, um festzustellen, ob es ganzzahlig ist (ebenfalls mit einer gewissen Toleranz). Setzen Sie gleich dem größten Nenner, nach dem Sie in den Zeilenverhältnissen suchen möchten. x s c a l e d =K x n o r m ,K=1,2,...,MKMxnOrm
    xsceinled=KxnOrm,K=1,2,,M
    KM

Nicht die eleganteste Methode, und es gibt wahrscheinlich einen besseren Weg, aber es sollte funktionieren, ist ziemlich einfach zu implementieren und sollte für Matrizen mit bescheidener Größe relativ schnell sein.

Jason R
quelle
Danke - ich denke, ich war wahrscheinlich auf dem Weg in diese Richtung, bevor ich mich im Detail festgefahren habe. Mir ist nicht zu 100% klar, dass Sie mit dieser Methode immer zu einer Lösung kommen, aber ich sollte diese Methode wahrscheinlich verschlüsseln und mit ein paar Beispielen ausprobieren. Ich habe eine Vermutung, dass es sowohl zeilenweise als auch spaltenweise angewendet werden muss, um zu sehen, welche die "beste" Lösung ergibt. Vielen Dank, dass Sie sich die Zeit genommen haben, die Details zu formulieren. Ich werde mich damit beschäftigen und Sie informieren, wie es funktioniert.
Paul R
Konnten Sie nicht den größten gemeinsamen Teiler der ersten Elemente der Zeilen finden und damit Ihren Basisvektor bestimmen?
Jim Clay
@JimClay: Ja, das ist es, was Sie am Ende effektiv tun, wenn Sie diese Funktionalität zur Verfügung haben.
Jason R
3

xyzEIN|EIN-xyz|
x y z
yzxx y z x y z ... im Gegenzug.

(Aus der ungefähren Faltung als Summe trennbarer Faltungen in math.stackexchange.)

denis
quelle
1
Versuchen Sie, Fragen nicht mit ungeklärten Links zu beantworten. Es ist besser, die erforderlichen Details in Ihrer Antwort zu erläutern und den Link nur als Referenz anzugeben. Auf diese Weise bleiben die wesentlichen Details der Antwort erhalten, wenn der Link unterbrochen wird.
Sam Maloney
@SamMaloney: Ich sehe keinen Grund, warum das notwendig ist. Der Link erklärt alles im Detail. Es wird weiterhin in der F & A-Suche angezeigt. Also warum nicht?
Naresh
1
@Naresh Ich erwähne es nur, weil eines der Ziele der Stack-Exchange-Sites darin besteht, ein Repository mit beantworteten Fragen zum späteren Nachschlagen aufzubauen. Obwohl ich verstehe, dass dieser bestimmte Link zu einer anderen SE-Site führt und ziemlich sicher sein sollte, ist es eine allgemeine bewährte Methode, nicht mit Links zu rechnen, die in einigen Jahren noch funktionieren. . Geben einen allgemeinen Überblick über diese „zwei einfache Methoden in der Antwort würde sicherstellen , dass Informationen zurückgehalten wird , auch wenn etwas auf die verknüpfte Frage geschieht , wie gesagt aber das war eher eine allgemeine Bemerkung über bewährte Praktiken in Bezug auf Links in Antworten.
Sam Maloney