We consider compressed sensing (CS) using partially coherent sensing matrices. Most of CS theory to date is focused on incoherent sensing, that is, columns from the sensing matrix are highly uncorrelated. However, sensing systems with naturally occurring correlations arise in many applications, such as signal detection, motion detection and radar. Moreover, in these applications it is often not necessary to know the support of the signal exactly, but instead small errors in the support and signal are tolerable. In this paper, we focus on @math -tol -erant recovery, in which support set reconstructions are considered accurate when their locations match the true locations within @math indices. Despite the abundance of work utilizing incoherent sensing matrices, for @math -tol -erant recovery we suggest that coherence is actually . This is especially true for situations with only a few and very noisy measurements as we demonstrate via numerical simulations. As a first step towards the theory of tolerant coherent sensing we introduce the notions of @math -co -herence and @math -tol -erant recovery. We then provide some theoretical arguments for a greedy algorithm applicable to @math -tol -erant recovery of signals with sufficiently spread support.
The literature on OMP related methods using partially coherent sensing matrices can be summarized as follows. In @cite_15 multiple extensions to existing algorithms were formulated. The authors proved and showed numerically that by introducing a band-exclusion method they were able to recover signals in a specific sense. Each non-zero of the original signal has a counterpart in the reconstruction, which is however allowed to be located . Thus the "tolerance" would be @math . Further, a condition related to the ERC @cite_6 is required, and the signals are assumed to have support which is spread enough so that coherent columns do not appear in the support indices. The work @cite_2 also considers spread signals, seeking accurate signal recovery and attempting to overcome coherence in the sampling matrix.
@cite_15 @cite_6 @cite_2
2116148865 2133285942
This article presents new results on using a greedy algorithm, orthogonal matching pursuit (OMP), to solve the sparse approximation problem over redundant dictionaries. It provides a sufficient condition under which both OMP and Donoho's basis pursuit (BP) paradigm can recover the optimal representation of an exactly sparse signal. It leverages this theory to show that both OMP and BP succeed for every sparse input signal from a wide class of dictionaries. These quasi-incoherent dictionaries offer a natural generalization of incoherent dictionaries, and the cumulative coherence function is introduced to quantify the level of incoherence. This analysis unifies all the recent results on BP and extends them to OMP. Furthermore, the paper develops a sufficient condition under which OMP can identify atoms from an optimal approximation of a nonsparse signal. From there, it argues that OMP is an approximation algorithm for the sparse problem over a quasi-incoherent dictionary. That is, for every input signal, OMP calculates a sparse approximant whose error is only a small factor worse than the minimal error that can be attained with the same number of terms. Compressive sensing (CS) is a new approach to simultaneous sensing and compression of sparse and compressible signals based on randomized dimensionality reduction. To recover a signal from its compressive measurements, standard CS algorithms seek the sparsest signal in some discrete basis or frame that agrees with the measurements. A great many applications feature smooth or modulated signals that are frequency-sparse and can be modeled as a superposition of a small number of sinusoids; for such signals, the discrete Fourier transform (DFT) basis is a natural choice for CS recovery. Unfortunately, such signals are only sparse in the DFT domain when the sinusoid frequencies live precisely at the centers of the DFT bins; when this is not the case, CS recovery performance degrades signicantly. In this paper, we introduce the spectral CS (SCS) recovery framework for arbitrary frequencysparse signals. The key ingredients are an over-sampled DFT frame and a restricted unionof-subspaces signal model that inhibits closely spaced sinusoids. We demonstrate that SCS signicantly outperforms current state-of-the-art CS algorithms based on the DFT while providing provable bounds on the number of measurements required for stable recovery. We also leverage line spectral estimation methods (specically Thomson’s multitaper method