Exact Recovery of Hard Thresholding Pursuit
The Hard Thresholding Pursuit (HTP) is a class of truncated gradient descent methods for finding sparse solutions of ℓ 0 -constrained loss minimization problems. The HTP-style methods have been shown to have strong approximation guarantee and impressive numerical performance in high dimensional statistical learning applications. However, the current theoretical treatment of these methods has traditionally been restricted to the analysis of parameter estimation consistency. It remains an open problem to analyze the support recovery performance (a.k.a., sparsistency) of this type of methods for recovering the global minimizer of the original NP-hard problem. In this paper, we bridge this gap by showing, for the first time, that exact recovery of the global sparse minimizer is possible for HTP-style methods under restricted strong condition number bounding conditions. We further show that HTP-style methods are able to recover the support of certain relaxed sparse solutions without assuming bounded restricted strong condition number. Numerical results on simulated data confirms our theoretical predictions.
This paper analyses the Hard Thresholding Pursuit (HTP) Algorithm which aims at solving problem (1) for a  smooth and convex loss function f. The contributions are Theorems 1, 2 and 3.  * Theorem 1 guarantees that under a RIP-like condition on the loss function (it must be strongly convex and strongly smooth on the set of s-sparse signals) and a condition on the minimal nonzero entry of x compared to the maximal entry of the gradient of f at x, the solution to (1) is unique and HTP recovers it in a finite number of iterations. * Theorem 2 guarantees that (under similar but slightly more restrictive conditions) HTP recovers perfectly the support of an arbitrary k-sparse solution. * Theorem 3, finally, without requiring the RIP-like conditions, guarantees that HTP will recover a support containing the support of a \bar{k}-sparse vector (where \bar{k} < k) as soon as the "rooted value gap" is small enough compared to the minimal entry of that vector. These theorems are deterministic sufficient conditions. They show that "HTP is powerful for exact recovery of signals even in noisy settings".
This paper is quite technical but is very interesting and promising as it provides sufficient conditions for exact recovery or sparsistency of the solutions of an quite broad class sparsity constrained smooth optimization problems using a very simple, yet powerful, class of greedy algorithms. Despite the technicality of the results, they are very clearly synthesized and nicely presented. I particularly like the summarizing tables.  I have only a few (but important) concerns: Line 26 : Problem (1) with a squared regression loss is IMO more general than compressed sensing. Depending on the forward model, it can tackle any noisy linear inverse problem such as optimal sparse representation in a dictionary, denoising, deblurring (or deconvolution),... Line 32 : There is also that paper : [1]A. Beck and Y. C. Eldar, “Sparsity Constrained Nonlinear Optimization: Optimality Conditions and Algorithms,” arXiv:1203.4580 [cs, math], Mar. 2012. Line 81: least squared -> least squares Line 121: In the definition of x^{-*} the constraint with strict inequality leads to something that is ill-posed. For example take f(x)=x^2 and k=n=1. Then we can take x as close to 0 as we want without ever reaching it. It should be something like an infimum rather than minimum which would allow a gap of 0. You should review this definition in any case. I guess that you meant "such that x has a different support than x^*" ? Please correct or justify as this has huge implications in the rest of the paper (proof of uniqueness for example). Line 129: same remark for \Delta^{-*}  In the proof of theorem 1 Part (b), supplementary material, line 416. As you wrote, the entries of the gradient and of x^(t-1) can but NOT HAVE TO be swapped. Therefore I do not agree with the next statement F^(t) \neq F^(t-1). I can provide a simple counter example where the above inequality would hold but the support would remain unchanged: eta Grad^(t-1) = -(1,2,3,4,5) x^(t-1) = (4.1,4.1,3,0,0) F^(t-1) = {1,2,3} F^* = {3,4,5} We have norm(4.1,4.1) < norm(4,5) but nevertheless \tilde{x}^(t) = (5.1,6.1,6,4,5) and therefore F^(t) = {1,2,3} = F^(t-1) Please correct me if I'm wrong or explain your development or correct the proof.  Line 215: You can also give other references for the Irrepresentability Condition such as Fuchs or Candès and Fernandes-granda, or others