Support Recovery for Orthogonal Matching Pursuit: Upper and Lower bounds
We study the problem of sparse regression where the goal is to learn a sparse vector that best optimizes a given objective function. Under the assumption that the objective function satisfies restricted strong convexity (RSC), we analyze orthogonal matching pursuit (OMP), a greedy algorithm that is used heavily in applications, and obtain a support recovery result as well as a tight generalization error bound for the OMP estimator. Further, we show a lower bound for OMP, demonstrating that both our results on support recovery and generalization error are tight up to logarithmic factors. To the best of our knowledge, these are the first such tight upper and lower bounds for any sparse regression algorithm under the RSC assumption.
##Summary##  The paper studies the support recovery performance of orthogonal matching pursuit, where the goal is to estimate the position of the non-zero elements of a high-dimensional signal from its compressed measurements. While results under the L_2 metric are well-known, and sharp RIP conditions have been established, there are still some theoretical gaps in understanding support recovery: what is the sharp condition? The work follows this line and present lower and upper bounds under natural assumprtions.  ##Detailed Comments##  I am satisfied with most of the discussion in the paper. Below are a few comments that I hope the authors could address in the feedback.  - I am curious how did the authors obtain better dependence on the condition number than [20,21,25]. Is it possible to sketch the main technique/idea right after Remark 3?  - The relaxed sparsity idea for OMP was used in [28]. What is the major difference between Theorem 3.1 and [28]?  - line 244: I did not really follow why noise helps recovery. In 1-bit matrix completion, noise does help distinguish the model. But what is the intuition here?  - The equation numbering is way strange. Authors need to improve the typeset in the revision. Authors should also keep the style of bib entries consistent.  ---Updates After Author Feedback---  Authors addressed my concerns and I feel this is a nice work. In particular, authors draw more careful analysis on the progress of OMP, and tightened the old bounds [28] that have been used for a decade. Personally I like their theoretical results. I hope they will sketch the proof technique and add more comparison to [20,21,25,28] in the main body, say list the bounds in a table. I believe it is a significant contribution for the community, and I increase my rating from "7" to "8".