快速/有效的方法来分解没有SVD的可分离整数2D滤波器系数

 2   3   2
 4   6   4
 2   3   2

 2   3   2

 1
 2
 1

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

 1  -2   1

#1 楼

我已经回答了@Phonon的答案，并对其进行了一些修改，以便它仅对最上面一行和最左边一列使用GCD方法，而不是对行/列总和使用GCD方法。这似乎可以更好地处理病理病例。如果顶行或左列全为零，则仍然可能失败，但是可以在应用此方法之前检查这些情况。

@Phonon对此的原始想法。

#2 楼

得到它了！发布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

#3 楼

也许我正在解决这个问题，但似乎可以： mathbf {a_i} $，$ i = 0，1，\ ldots，N-1 $。

对于每一行索引$ j> 0 $：


将$ \ mathbf {a_j} $除以$ \ mathbf {a_0} $，可得出$ j $行中每个元素与零行$ \ mathbf {r_j} $中对应元素之比。这需要使用浮点数或其他分数运算来完成。
检查$ \ mathbf {r_j} $中的元素以确定它们是否恒定。在此比较中，您需要允许一些公差，以便进行浮点舍入。
如果$ \ mathbf {r_j} $中的值是常数，则$ \ mathbf {a_j} $行是标量$ \ mathbf {a_0} $行的倍数。将行$ j $与行$ 0 $的比率存储在列表$ \ mathbf {x} $中。 $ \ mathbf {a_0} $，因此您将无法以这种方式分解矩阵。停止检查。


如果在上述测试中所有行均被视为行0的常数倍，则获取行比标量$ \ mathbf {x} $的列表，然后用最小比率对其进行归一化：

$$
x_ {k，norm} = \ frac {x_k} {\ min_ {i = 0} ^ {N-1} x_i}
$$


这样做之后，比率$ \ mathbf {x_ {norm}} $的归一化列表将为值最小的行包含值1。规范。您想查看是否可以通过某种方式缩放此列表以产生包含所有整数系数的列表。蛮力方法只能进行线性搜索，即计算：
$$
\ mathbf {x_ {scaled}} = K \ mathbf {x_ {norm}}，K = 1、2，\ ldots，M
$$$
对于$ K $的每个值，在计算比例比例列表后，您需要检查每个值以查看它们是否为整数值（再次具有一定的容差）。将$ M $设置为等于您愿意在行间比率中寻找的最大分母。

不是最优雅的方法，可能有更好的方法，但是它应该可以工作，易于实现，并且对于中等大小的矩阵应该相对较快。

#4 楼

另一种方法是找到与内核$ A $的可分离近似值$ x \ otimes y \ otimes z $
，并查看其接近程度。
两种方法可以做到这一点，即最小化
$ | A-x \ otimes y \ otimes z | $：
1）蛮力优化$ x \ y \ z $;这需要时间〜固定的$ y $和$ z $的长度之和，而不是其长度的乘积
2，最优的$ x $只是一个投影，因此请优化
$ x \ y \ z \ x \ y \ z \ ... $。

（摘自数学上的近似卷积作为可分离卷积的和
。 stackexchange。）