0
$\begingroup$

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?

$\endgroup$

closed as off-topic by MBaz, lennon310, Peter K. Aug 26 at 20:09

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." – Peter K.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Please add the image and describe what you want to do. $\endgroup$ – Royi Aug 20 at 7:51
  • $\begingroup$ 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. $\endgroup$ – sujit das Aug 20 at 9:13
  • $\begingroup$ You need to show the process you build the "Compressed Sampled" image. We'll assist you from there. $\endgroup$ – Royi Aug 20 at 9:16
0
$\begingroup$

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:

  1. An Optimal Condition for the Block Orthogonal Matching Pursuit Algorithm.
  2. Block Sparsity: Coherence and Efficient Recovery.

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


$\endgroup$
  • $\begingroup$ the "paramK"-- is it block sparsity $\endgroup$ – sujit das Aug 20 at 9:16
  • $\begingroup$ As written in documentation Basically the maximal number of active blocks in the solution. $\endgroup$ – Royi Aug 20 at 9:17
  • $\begingroup$ 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? $\endgroup$ – sujit das Aug 20 at 19:32
  • $\begingroup$ @sujitdas, I'm no sure what you mean. Could you point me to your reference? $\endgroup$ – Royi Aug 21 at 14:53
  • $\begingroup$ 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. $\endgroup$ – sujit das Aug 21 at 18:23

Not the answer you're looking for? Browse other questions tagged or ask your own question.