Szybki / wydajny sposób dekompozycji liczb całkowitych oddzielnych współczynników filtra 2D


21

Chciałbym móc szybko ustalić, czy dane jądro 2D o współczynnikach całkowitych można rozdzielić na dwa jądra 1D o współczynnikach całkowitych. Na przykład

 2   3   2
 4   6   4
 2   3   2

można podzielić na

 2   3   2

i

 1
 2
 1

Rzeczywisty test separowalności wydaje się dość prosty przy użyciu arytmetyki liczb całkowitych, ale rozkład na filtry 1D o współczynnikach całkowitych okazuje się trudniejszym problemem. Trudność wydaje się polegać na tym, że stosunki między rzędami lub kolumnami mogą być niecałkowite (ułamki wymierne), np. W powyższym przykładzie mamy stosunki 2, 1/2, 3/2 i 2/3.

Naprawdę nie chcę stosować podejścia o dużej obciążalności, takiego jak SVD, ponieważ (a) jest to stosunkowo kosztowne obliczeniowo dla moich potrzeb i (b) nadal niekoniecznie pomaga w określeniu współczynników całkowitych .

Jakieś pomysły ?


DALSZA INFORMACJA

Współczynniki mogą być dodatnie, ujemne lub zerowe i mogą wystąpić przypadki patologiczne, w których suma jednego lub obu wektorów 1D wynosi zero, np.

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

można podzielić na

 1  -2   1

i

-1
 0
 1

1
Pamiętam, jak próbowałem to rozwiązać na studiach. Prawie mi się udało, ale nie pamiętam jak. =) Nie mogę przestać o tym myśleć, skoro o tym wspomniałeś!
Phonon

@Phonon: heh - dobrze myślę - przydałaby mi się inspiracja. ;-)
Paul R

Czy można zrobić to samo, ale dla wartości podwójnych lub zmiennoprzecinkowych?
Diego Catalano

@DiegoCatalano: patrz odpowiedź Denisa poniżej i pytanie, do którego prowadzi na math.stackexchange.com - myślę, że może to działać w bardziej ogólnym przypadku współczynników zmiennoprzecinkowych.
Paul R

@PaulR, w jaki sposób można się z Tobą skontaktować przez e-mail? Dziękuję Ci.
Royi,

Odpowiedzi:


11

Wziąłem @Phononodpowiedź i nieco ją zmodyfikowałem, aby używała metody GCD tylko w górnym wierszu i lewej kolumnie, a nie w sumach wierszy / kolumn. Wydaje się, że to trochę lepiej radzi sobie z przypadkami patologicznymi. Nadal może się nie powieść, jeśli wszystkie górne wiersze lub lewe kolumny są zerami, ale przypadki te można sprawdzić przed zastosowaniem tej metody.

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

Wielkie dzięki @Phononi @Jason Rdla oryginalnych pomysłów na to.


10

Rozumiem! Publikując kod MATLAB, opublikuję wyjaśnienie dziś wieczorem lub jutro

% 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

Dzięki - to wspaniale - nie spałam zeszłej nocy, myśląc o uwzględnieniu współczynników itp., Ale użycie GCD w ten sposób jest o wiele prostsze i bardziej eleganckie. Niestety jest jeszcze jedna zmarszczka do usunięcia - musi działać zarówno z dodatnimi, jak i ujemnymi współczynnikami, co może prowadzić do zdegenerowanych przypadków, np A=[-2 1 0 -1 2]; B=[2 -3 6 0 -1]; M=A'*B;. Problem w tym, że sum(A) = 0tak Sb = [0 0 0 0 0]. Spróbuję zmodyfikować algorytm, aby używał sumy wartości bezwzględnych współczynników i sprawdził, czy to pomoże. Jeszcze raz dziękuję za pomoc.
Paul R

OK - wygląda na to, nadal można uzyskać GCDs i zrobić skalowanie za pomocą abs(M)IE Sa=abs(M)*ones(N,1); Sb=ones(1,N)*abs(M);, a następnie kontynuować jak wyżej, ale nie mogę jeszcze zobaczyć, jak przywrócić znaki do Sa, Sbna końcu. Dodałem patologiczny przykład, który ilustruje problem w pierwotnym pytaniu powyżej.
Paul R

Wydaje mi się, że mam już działające rozwiązanie - opublikowałem je jako osobną odpowiedź, ale uznanie dla ciebie leży u podstaw pomysłu. Dzięki jeszcze raz !
Paul R

7

Może trywializuję problem, ale wygląda na to, że możesz:

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

    • aja0jrj
    • rj
    • rjajza0jot0x
    • zajotza0
  • x

xk,norm=xkminja=0N.-1xja
  • xnorm
    xsdozalmire=K.xnorm,K.=1,2),,M.
    K.M.

Nie jest to najbardziej elegancka metoda i prawdopodobnie istnieje lepszy sposób, ale powinna działać, jest dość prosta do wdrożenia i powinna być stosunkowo szybka w przypadku matryc o skromnych rozmiarach.


Dzięki - myślę, że prawdopodobnie zmierzałem w tym kierunku, zanim zagłębiłem się w szczegóły. Nie jest dla mnie w 100% jasne, że zawsze znajdziesz rozwiązanie za pomocą tej metody, ale tak czy inaczej, prawdopodobnie powinienem to zakodować i spróbować z kilkoma przykładami. Mam przeczucie, że może być konieczne zastosowanie zarówno wiersza, jak i kolumny, aby zobaczyć, co daje „najlepsze” rozwiązanie. Dziękujemy za poświęcenie czasu na wyjaśnienie szczegółów - zajmę się tym i dam znać, jak to działa.
Paul R

Czy nie możesz znaleźć największego wspólnego dzielnika pierwszych elementów wierszy i użyć go do określenia wektora bazowego?
Jim Clay

@JimClay: Tak, to jest właśnie to, co robisz na końcu, jeśli masz tę funkcjonalność dostępną.
Jason R

3

xyzA|Axyz|
x y z
yzxx y z x y z ... z kolei.

(Od przybliżonych splotów jako sumy rozdzielnych splotów na matematyce. Wymiana_kumulacji.)


1
Staraj się nie odpowiadać na pytania za pomocą niewyjaśnionych linków. Lepiej wyjaśnij niezbędne szczegóły w swojej odpowiedzi i dołącz link tylko w celach informacyjnych; w ten sposób, jeśli link się zepsuje, podstawowe szczegóły odpowiedzi są nadal dostępne.
Sam Maloney,

@SMMaloney: Nie widzę powodu, dla którego jest to konieczne. Link wyjaśnia wszystko szczegółowo. Nadal będzie pojawiał się podczas wyszukiwania pytań i odpowiedzi. Dlaczego nie
Naresh

1
@Naresh Wspominam o tym tylko dlatego, że jednym z celów witryn wymiany stosów jest zbudowanie repozytorium odpowiedzi na pytania na przyszłość. Chociaż więc rozumiem, że ten konkretny link prowadzi do innej strony SE i powinien być dość bezpieczny, ogólnie najlepszą praktyką jest nie liczyć na linki działające jeszcze za kilka lat. . Daje ogólny zarys tych „dwóch prostych metod w odpowiedzi zapewni, że informacja jest zachowywana nawet jeśli coś dzieje się z połączonego pytanie Jak powiedziałem jednak, było to bardziej ogólny komentarz na temat najlepszych praktyk w zakresie ogniw w odpowiedzi.
Sam Maloney
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.