A variant of the greedy OMP algorithm for recovering K-sparse signals from compressed measurements y = Ax, specialized to sparse random combinatorial measurement matrices (0/1 columns each with exactly d ones). The method builds a 'confined set' from the structure of A and the signal and proves the signal's support lies inside it with probability 1 under a condition on the nonzero components, then restricts OMP's candidate indices to that set to cut complexity. A derived lower bound on exact-recovery probability shows that when the spark of A exceeds K, m = 2eK ln(n-K) measurements suffice for recovery with probability at least 1 - 1/(n-K), which also lets the column degree d be optimized; experiments show it beats standard OMP on this signal class.
This paper introduces 'confined orthogonal matching pursuit', a variant of the greedy OMP algorithm for recovering a K-sparse signal x from compressed linear measurements y = Ax, specialized to the c…