Kernels for Incoherent Projection and Orthogonal Matching Pursuit

In compressed sensing, Orthogonal Matching Pursuit (OMP) is one of the most popular and simpler algorithms for finding a sparse description of the system Ax = b. The recovery guarantees of OMP depend on the coherence parameter (maximum off-diagonal entry - in magnitude - in the Gram matrix of normalized columns of A). Nevertheless, when A has a bad coherence (being close to 1), the OMP algorithm is likely to provide a pessimistic performance numerically, which is indeed the case in many applications where one uses the data-driven sensing matrices. With a view to improving the coherence of a highly coherent system Ax= b, we transform the columns of A as well as b via a map ϕ and formulate a new system ϕ(b) = ϕ(A) x0. Here ϕ(A) is understood in column-wise sense. We show that the execution of OMP on new system can be carried out using kernels, requiring thereby no explicit expression of ϕ. We use some standard kernels and show that the new system is highly incoherent (possessing reduced coherence) and better behaved (possessing improved condition number) compared to the original system. Notwithstanding the fact that both the systems have different sets of solutions, we demonstrate that the kernel-based OMP significantly improves the performance in the classification of heart-beats for their normal and abnormal patterns. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG