Orthogonal Matching Pursuit on Faulty Circuits

With the wide recognition that modern nanoscale devices will be error-prone, characterization of reliability of information processing systems built out of unreliable components has become an important topic. In this paper, we analyze the performance of orthogonal matching pursuit (OMP), a popular sparse recovery algorithm, running on faulty circuits. We identify sufficient conditions for correct recovery of the signal support and express these conditions in terms of the relationship among signal magnitudes, sparsity, and the mutual incoherence of the measurement matrix. We study both the effects of additive errors in arithmetic computations and logical errors in comparators. We find that the additive errors in the OMP computations have an impact on the overall performance comparable to that of the additive noise in the input measurements. We also show that parallel structures are more robust to logical errors than serial structures in the implementation of a noisy arg max operation, and thus lead to a better OMP performance.