ThispaperdemonstratestheoreticallyandempiricallythatagreedyalgorithmcalledOrthogonalMatchingPursuit(OMP)canreliablyrecoverasignalwithmnonzeroentriesindimensiondgivenO(mlnd)randomlinearmeasurementsofthatsignal.