# Implementation of Block Orthogonal Matching Pursuit (BOMP) Algorithm [closed]

How would one implement the lock Orthogonal Matching Pursuit (BOMP) Algorithm?

## closed as off-topic by Matt L., Marcus Müller, MBaz, Peter K.♦Aug 26 at 20:06

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "Questions requesting working code written to a specification are off-topic as they are unlikely to benefit anyone else. Instead, describe the problem you're solving and where you're stuck." – Matt L., Marcus Müller, MBaz, Peter K.
If this question can be reworded to fit the rules in the help center, please edit the question.

• Since are already have something implemented and are getting "the correct indices", how about you post what you have in form of a mcve? – Florian Aug 19 at 11:34
• What @Florian said: Asking for code written to your specification is actually dedicatedly off-topic here. So, you'll need to show your own code, explain your own attempt, and ask a signal processing question that explicitly states which signal processing problem we can help you solve. You didn't even ask a proper question – you just asked us for code. – Marcus Müller Aug 19 at 12:11

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 MATLAB code is available at my StackExchange Signal Processing Q60197 GitHub Repository.
In the full code I compare the Block implementation to OMP to verify the implementation.

• Yes. I know but I am not getting the recovered values. what should I do? – sujit das Aug 19 at 17:43
• Thanx in advance – sujit das Aug 19 at 18:09
• Thank you very much – sujit das Aug 20 at 3:39
• of course...already done – sujit das Aug 20 at 5:34
• Have a look on i.imgur.com/Hu200ud.png. Also look at meta.stackexchange.com/a/5235/298337. – Royi Aug 20 at 6:15

The coefficients of transformed image and recovered values are ploted as![plots of recovered and original coefs]2

the recovered image mse is 612896.781119