The paper introduces a greedy algorithm called Regularized Orthogonal Matching Pursuit (ROMP) for recovering a vector \( v \in \mathbb{R}^d \) from incomplete and inaccurate measurements \( x = \Phi v + e \), where \( \Phi \) is a \( N \times d \) measurement matrix with \( N \ll d \) and \( e \) is an error vector. ROMP combines the speed and ease of implementation of greedy methods with the strong guarantees of convex programming methods. Under the Uniform Uncertainty Principle, ROMP can recover a signal with \( O(n) \) nonzeros from its inaccurate measurements in at most \( n \) iterations, with each iteration solving a Least Squares Problem. The noise level of the recovery is proportional to \( \sqrt{\log n} \|e\|_2 \), and the reconstruction is exact if the error term \( e \) is zero.
The paper also discusses the stability of ROMP under measurement perturbations and signal perturbations. It proves that ROMP produces a good approximation to the original signal, with an error bound proportional to \( \sqrt{\log n} \|e\|_2 \). This stability result extends to approximately sparse signals, where ROMP can still recover a good approximation. Numerical experiments are provided to illustrate the effectiveness of ROMP in both perturbed measurements and signals.The paper introduces a greedy algorithm called Regularized Orthogonal Matching Pursuit (ROMP) for recovering a vector \( v \in \mathbb{R}^d \) from incomplete and inaccurate measurements \( x = \Phi v + e \), where \( \Phi \) is a \( N \times d \) measurement matrix with \( N \ll d \) and \( e \) is an error vector. ROMP combines the speed and ease of implementation of greedy methods with the strong guarantees of convex programming methods. Under the Uniform Uncertainty Principle, ROMP can recover a signal with \( O(n) \) nonzeros from its inaccurate measurements in at most \( n \) iterations, with each iteration solving a Least Squares Problem. The noise level of the recovery is proportional to \( \sqrt{\log n} \|e\|_2 \), and the reconstruction is exact if the error term \( e \) is zero.
The paper also discusses the stability of ROMP under measurement perturbations and signal perturbations. It proves that ROMP produces a good approximation to the original signal, with an error bound proportional to \( \sqrt{\log n} \|e\|_2 \). This stability result extends to approximately sparse signals, where ROMP can still recover a good approximation. Numerical experiments are provided to illustrate the effectiveness of ROMP in both perturbed measurements and signals.