# 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. – sujit das 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

## 1 Answer

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 – sujit das 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? – sujit das 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. – sujit das Aug 21 '19 at 18:23