# Implementation of Block Orthogonal Matching Pursuit (BOMP) Algorithm - Fix Given Code [closed]

This is my implementation which doesn't work:

function [result,gamma,T]=block_OMP4(phi,signal,N,d,maxIter)
[m n]=size(phi);
r=signal;
gamma=[];
T=[];
i=1;
tol=1e-4;
err=1;
x=zeros(N*d,1);
val=[];
figure,
while  (i<=maxIter && err>tol)

maxv=[];
for j=1:N
startx=(j-1)*d+1;
endx=startx+d-1;
block=phi(:,startx:endx);
t=block'*r;
maxv(j)=norm(t,2);
%
end
[maxvl,maxvindx]=max(maxv);
gamma=union(gamma,maxvindx);
x2=lsqr(phi,r);
xb=zeros(N*d,1);
for i=1:length(gamma)
stratx=(gamma(i)-1)*d;
endx=stratx+d-1;
xb(stratx:endx)=x2(stratx:endx);
x(stratx:endx)=x(stratx:endx)+xb(stratx:endx);
end

y=phi*x;
r=signal-y;

val(i)=norm(r);
err=norm(r)
i=i+1;

end
result=x;
end



Anyone has a working implementation?

• Please add the image and describe what you want to do.
– Royi
Aug 20 '19 at 7:51
• I want to use any image as input and use BOMP to reconstruct from the compressed sample of the input. I used ur code but unable to get the image back. Aug 20 '19 at 9:13
• You need to show the process you build the "Compressed Sampled" image. We'll assist you from there.
– Royi
Aug 20 '19 at 9:16

Answer taken from Implementation of Block Orthogonal Matching Pursuit (BOMP) Algorithm.

The Block Orthogonal Matching Pursuit (BOMP) Algorithm is basically the Orthogonal Matching Pursuit (OMP) Algorithm with single major difference - Instead of selecting single index which maximizes the correlation we chose a set of indices, sub set of columns of the matrix and the solution vector.

A good reference for the algorithm is given in:

The code is given by:

function [ vX ] = SolveLsL0Bomp( mA, vB, numBlocks, paramK, tolVal )
% ----------------------------------------------------------------------------------------------- %
%[ vX ] = SolveLsL0Omp( mA, vB, paramK, tolVal )
% Minimizes Least Squares of Linear System with L0 Constraint Using
% Block Orthogonal Matching Pursuit (OMP) Method.
% \arg \min_{x} {\left\| A x - b \right\|}_{2}^{2} subject to {\left\| x
% \right\|}_{2, 0} \leq K
% Input:
%   - mA                -   Input Matirx.
%                           The model matrix (Fat Matrix). Assumed to be
%                           normlaized. Namely norm(mA(:, ii)) = 1 for any
%                           ii.
%                           Structure: Matrix (m X n).
%                           Type: 'Single' / 'Double'.
%                           Range: (-inf, inf).
%   - vB                -   input Vector.
%                           The model known data.
%                           Structure: Vector (m X 1).
%                           Type: 'Single' / 'Double'.
%                           Range: (-inf, inf).
%   - numBlocks         -   Number of Blocks.
%                           The number of blocks in the problem structure.
%                           Structure: Scalar.
%                           Type: 'Single' / 'Double'.
%                           Range: {1, 2, ...}.
%   - paramK            -   Parameter K.
%                           The L0 constraint parameter. Basically the
%                           maximal number of active blocks in the
%                           solution.
%                           Structure: Scalar.
%                           Type: 'Single' / 'Double'.
%                           Range: {1, 2, ...}.
%   - tolVal            -   Tolerance Value.
%                           Tolerance value for equality of the Linear
%                           System.
%                           Structure: Scalar.
%                           Type: 'Single' / 'Double'.
%                           Range [0, inf).
% Output:
%   - vX                -   Output Vector.
%                           Structure: Vector (n X 1).
%                           Type: 'Single' / 'Double'.
%                           Range: (-inf, inf).
% References
%   1.  An Optimal Condition for the Block Orthogonal Matching Pursuit
%       Algorithm - https://ieeexplore.ieee.org/document/8404118.
%   2.  Block Sparsity: Coherence and Efficient Recovery - https://ieeexplore.ieee.org/document/4960226.
% Remarks:
%   1.  The algorithm assumes 'mA' is normalized (Each column).
%   2.  The number of columns in matrix 'mA' must be an integer
%       multiplication of the number of blocks.
%   3.  For 'numBlocks = numColumns' (Equivalent of 'numElmBlock = 1') the
%       algorithm becomes the classic OMP.
% Known Issues:
%   1.  A
% TODO:
%   1.  Pre Process 'mA' by normalizing its columns.
% Release Notes:
%   -   1.0.000     19/08/2019
%       *   First realease version.
% ----------------------------------------------------------------------------------------------- %

numRows = size(mA, 1);
numCols = size(mA, 2);

numElmBlock = numCols / numBlocks;
if(round(numElmBlock) ~= numElmBlock)
error('Number of Blocks Doesn''t Match Size of Arrays');
end

vActiveIdx      = false([numCols, 1]);
vR              = vB;
vX              = zeros([numCols, 1]);
activeBlckIdx   = [];

for ii = 1:paramK

maxCorr         = 0;

for jj = 1:numBlocks
vBlockIdx = (((jj - 1) * numElmBlock) + 1):(jj * numElmBlock);

currCorr = abs(mA(:, vBlockIdx).' * vR);
if(currCorr > maxCorr)
activeBlckIdx = jj;
maxCorr = currCorr;
end
end

vBlockIdx = (((activeBlckIdx - 1) * numElmBlock) + 1):(activeBlckIdx * numElmBlock);
vActiveIdx(vBlockIdx) = true();

vX(vActiveIdx) = mA(:, vActiveIdx) \ vB;
vR = vB - (mA(:, vActiveIdx) * vX(vActiveIdx));

resNorm = norm(vR);

if(resNorm < tolVal)
break;
end

end

end


• the "paramK"-- is it block sparsity Aug 20 '19 at 9:16
• As written in documentation Basically the maximal number of active blocks in the solution.
– Royi
Aug 20 '19 at 9:17
• what is the size of the number of rows for the random matrix which is used as a sampler. I mean it is O(KlogN) for conventional OMP but what is for BOMP? Aug 20 '19 at 19:32
• @sujitdas, I'm no sure what you mean. Could you point me to your reference?
– Royi
Aug 21 '19 at 14:53
• I said that when we compress a vector using a matrix M of dimension mxN where m is calculated as at least KlogN, where K is sparsity and N is the length of the input, for random gaussian or sub gaussian matrix in case of Orthogonal Matching Pursuit,. Now my question is how can we calculate m in case of BOMP. Aug 21 '19 at 18:23