Improving Speed and Reducing Memory Consumption with Creation of 2D Sparse Convolution Matrix

Royi Avital 님이 질문을 제출함. 22 Jan 2019

최근 활동 Royi Avital 님이 댓글을 추가함. 23 Jan 2019

조회 수: 8(최근 30일)

In a previous question of mine, Creating Convolution Matrix of 2D Kernel for Different Shapes of Convolution, among answers of the great Matt I came up with the following code:

function [ mK ] = CreateConvMtx2DSparse( mH, numRows, numCols, convShape )
CONVOLUTION_SHAPE_FULL  = 1;
CONVOLUTION_SHAPE_SAME  = 2;
CONVOLUTION_SHAPE_VALID = 3;
numColsKernel   = size(mH, 2);
numBlockMtx     = numColsKernel;
cBlockMtx = cell(numBlockMtx, 1);
for ii = 1:numBlockMtx
    cBlockMtx{ii} = CreateConvMtxSparse(mH(:, ii), numRows, convShape);
end
switch(convShape)
    case(CONVOLUTION_SHAPE_FULL)
        % For convolution shape - 'full' the Doubly Block Toeplitz Matrix
        % has the first column as its main diagonal.
        diagIdx     = 0;
        numRowsKron = numCols + numColsKernel - 1;
    case(CONVOLUTION_SHAPE_SAME)
        % For convolution shape - 'same' the Doubly Block Toeplitz Matrix
        % has the first column shifted by the kernel horizontal radius.
        diagIdx     = floor(numColsKernel / 2);
        numRowsKron = numCols;
    case(CONVOLUTION_SHAPE_VALID)
        % For convolution shape - 'valid' the Doubly Block Toeplitz Matrix
        % has the first column shifted by the kernel horizontal length.
        diagIdx     = numColsKernel - 1;
        numRowsKron = numCols - numColsKernel + 1;
end
vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
    diagIdx = diagIdx - 1;
    mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end
end

The code is running pretty fast.

But I think there might be ways to improve it farther, specifically in the following lines:

vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
    diagIdx = diagIdx - 1;
    mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end

This code snippet basically creates a block matrix form the sparse matrices in the cell array cBlockMtx. Where the diagonal of the first element in cBlockMtx is defiend by diagIdx.

Is there a more efficient way to generate this matrix? The main issue is that each time generating kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii}) requires a lot of memory.

댓글 수: 2

Matt J 22 Jan 2019

I believe you already found a more efficient alternative here?

Royi Avital 23 Jan 2019

Well, I tried this:

function [ mK ] = CreateConvMtx2DI( mH, numRows, numCols, convShape )
CONVOLUTION_SHAPE_FULL  = 1;
CONVOLUTION_SHAPE_SAME  = 2;
CONVOLUTION_SHAPE_VALID = 3;
numColsKernel   = size(mH, 2);
numBlockMtx     = numColsKernel;
cBlockMtx = cell(numBlockMtx + 1, 1);
for ii = 1:numBlockMtx
    cBlockMtx{ii} = CreateConvMtx1D(mH(:, ii), numRows, convShape);
end
cBlockMtx{numBlockMtx + 1} = sparse([], [], [], size(cBlockMtx{numBlockMtx}, 1), size(cBlockMtx{numBlockMtx}, 2), 0);
switch(convShape)
    case(CONVOLUTION_SHAPE_FULL)
        % For convolution shape - 'full' the Doubly Block Toeplitz Matrix
        % has the first column as its main diagonal.
        diagIdx     = 0;
        numRowsKron = numCols + numColsKernel - 1;
    case(CONVOLUTION_SHAPE_SAME)
        % For convolution shape - 'same' the Doubly Block Toeplitz Matrix
        % has the first column shifted by the kernel horizontal radius.
        diagIdx     = floor(numColsKernel / 2);
        numRowsKron = numCols;
    case(CONVOLUTION_SHAPE_VALID)
        % For convolution shape - 'valid' the Doubly Block Toeplitz Matrix
        % has the first column shifted by the kernel horizontal length.
        diagIdx     = numColsKernel - 1;
        numRowsKron = numCols - numColsKernel + 1;
end
vC = (numBlockMtx + 1) * ones(numRowsKron, 1);
vR = (numBlockMtx + 1) * ones(numCols, 1);
vC(1:(numBlockMtx - diagIdx)) = (diagIdx + 1):numBlockMtx;
vR(1:(diagIdx + 1)) = (diagIdx + 1):-1:1;
mK = cell2mat(cBlockMtx(toeplitz(vC, vR)));
end

Namely I replaced:

vI = ones(min(numRowsKron, numCols), 1);
mK = kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{1});
for ii = 2:numBlockMtx
    diagIdx = diagIdx - 1;
    mK = mK + kron(spdiags(vI, diagIdx, numRowsKron, numCols), cBlockMtx{ii});
end

With:

vC = (numBlockMtx + 1) * ones(numRowsKron, 1);
vR = (numBlockMtx + 1) * ones(numCols, 1);
vC(1:(numBlockMtx - diagIdx)) = (diagIdx + 1):numBlockMtx;
vR(1:(diagIdx + 1)) = (diagIdx + 1):-1:1;
mK = cell2mat(cBlockMtx(toeplitz(vC, vR)));

It turned out to be slower (x2 slower). So I will be happy to have another idea...

로그인 to comment.

제품

MATLAB

답변 수: 0

이 질문에 답변하려면 로그인을(를) 수행하십시오.

제품

MATLAB

Translated by

이 질문을 팔로우합니다.

Royi Avital (view profile)