Compute the restricted isometry constant (RIC) of a matrix at a specified sparsity level. Note that this is a certified NP-hard problem and only computationally tractable for small values of s (upto 4 or 5).

compute_RIC.m

function out = compute_RIC(A, s)
% This function computes the Restricted Isometry Constant of given matrix A
% at sparsity level s.
% Written by Alankar Kotwal ([email protected]), Dhruv Shah ([email protected])
	
    A = normc(A);
    nT = size(A, 2);
    combs = combnk(1:nT, s);
    out = 0;
    disp(size(combs, 1))
    % for i = 1:size(combs, 1)
    % Use the below if you have access to the Parallel Computing Toolbox, else use above
    parfor i = 1:size(combs, 1)
        if mod(i, 10000) == 0
            disp(i)
        end
        subsA = A(:, combs(i, :));
        dots = subsA' * subsA;
        dotsSub = dots - eye(size(dots));

        maxEig = max(abs(eig(dotsSub)));
        out = max(out, maxEig);
    end
end

Thanks