Error estimates for orthogonal matching pursuit and random dictionaries (Q628676)

The authors investigate the efficiency of the Orthogonal Matching Pursuit algorithm (OMP) for random dictionaries. They also introduce a stronger Homogeneous Restricted Isometry Property which is satisfied with overwhelming probability for random dictionaries used in compressed sensing. The upper estimates for the error of approximation by OMP in terms of the error of the best n-term approximation is established. Some open problems about OMP are also discussed.