Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery
In machine learning and compressed sensing, it is of central importance to understand when a tractable algorithm recovers the support of a sparse signal from its compressed measurements. In this paper, we present a principled analysis on the support recovery performance for a family of hard thresholding algorithms. To this end, we appeal to the partial hard thresholding (PHT) operator proposed recently by Jain et al. [IEEE Trans. Information Theory, 2017]. We show that under proper conditions, PHT recovers an arbitrary s-sparse signal within O(sκ log κ) iterations where κ is an appropriate condition number. Specifying the PHT operator, we obtain the best known results for hard thresholding pursuit and orthogonal matching pursuit with replacement. Experiments on the simulated data complement our theoretical findings and also illustrate the effectiveness of PHT.
Review prior to rebuttal:
The paper provides analytical results on partial hard thresholding for sparse signal recovery that are based on RIP and on an alternative condition (RSC and RSS) and that is applicable to arbitrary signals.
The description of previous results is confusing at times. First, [4] has more generic results than indicated in this paper in line 51. Remark 7 provides a result for arbitrary signals, while Theorems 5 and 6 consider all sufficiently sparse signals. Second, [13] provides a guarantee for sparse signal recovery (Theorem 4), and so it is not clear what the authors mean by “parameter estimation only” on line 59. If exact recovery is achieved, it is obvious that the support is estimated correctly too. Third, it is also not clear why Theorem 2 is described as an RIP-based guarantee - how does RIP connect to the condition number, in particular since RIP is a property that can go beyond specific matrix constructions?
The simulation restricts itself to s-sparse signals, and so it is not clear that the authors are testing the aspects of the results that go beyond those available in existing work. It is also not clear how the results test the dependence on the condition number of the matrix.
Minor comments follow.
Title: “A Towards” is not grammatically correct.
Line 128: the names of the properties are grammatically incorrect: convex -> convexity, smooth -> smoothness? or add “property” at the end of each?
Line 136: calling M/m “the condition number of the problem” can be confusing, since this terminology is already used in linear algebra. Is there a relationship between these two quantities?
Line 140: there is no termination condition given in the algorithm. Does this mean when the gradient in the first step is equal to zero? When the support St does not change in consecutive iterations?
Line 185: the paper refers to a comparison of the analysis of [4] being “confined to a special signal” versus the manuscript’s “generalization… [to] a family of algorithms”. It is not clear how these two things compare to one another.
Line 301: degrade -> degradation
Line 304: reduces -> reduce
Response to rebuttal: The authors have addressed some of the points above (in particular relevant to the description of prior work), but the impact of the contribution appears to be "borderline" for acceptance. Given that the paper is acceptable if the authors implement the changes described in the rebuttal, I have set my score to "marginally above threshold".