Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery

Jie Shen, Ping LiNeurIPS 2017 · OpenReview

Introduction

In fields like compressed sensing and high-dimensional statistics, recovering a "sparse" signal (one containing mostly zeros) from a small number of measurements is a fundamental challenge. Success in this domain is typically measured in two ways: parameter estimation, which focuses on getting an estimate that is close to the true signal in terms of distance (e.g., $\ell_2$ norm), and support recovery, which involves correctly identifying exactly which indices are non-zero (the "support").

Support recovery is generally much harder than parameter estimation. While many algorithms are known to get "close" to the true values, proving they will exactly identify the correct features often requires much stricter conditions. This paper bridges that gap by providing a unified, principled theoretical framework for how greedy, thresholding-based algorithms navigate the search space to find the true support. By analyzing the Partial Hard Thresholding (PHT) operator, the authors establish that a broad family of greedy algorithms can perfectly recover a signal's support, providing the strongest theoretical guarantees to date for popular methods like Hard Thresholding Pursuit (HTP).

The Partial Hard Thresholding (PHT) Framework

The authors center their analysis on the Partial Hard Thresholding (PHT) operator. Standard Hard Thresholding (HT) simply keeps the $k$ largest elements of a vector and sets the rest to zero. PHT introduces a "freedom parameter," denoted as $r$. In each step, the algorithm is allowed to change at most $r$ indices in the current support set.

This single parameter turns PHT into a generalized framework that encompasses several known algorithms:

  • If $r = k$, the algorithm behaves like standard Hard Thresholding.
  • If $r = 1$, it behaves like Orthogonal Matching Pursuit with Replacement (OMPR).

The paper provides a deterministic analysis using Restricted Strong Convexity (RSC) and Restricted Smoothness (RSS)—properties that describe how well-behaved a function is when restricted to sparse directions. Crucially, they also provide "RIP-free" (Restricted Isometry Property) results, which are highly applicable to real-world datasets where features are often highly correlated.

Key Findings and Theoretical Guarantees

The theoretical analysis yields several strong guarantees for support recovery, which the authors validate using simulated compressed sensing datasets ($y = Ax + e$, where $A$ is a Gaussian design matrix and $x$ is an $s$-sparse signal).

  • Iteration Complexity: Under proper conditions, PHT recovers an arbitrary $s$-sparse signal within $O(s\kappa \log \kappa)$ iterations, where $\kappa$ is the condition number of the problem. The fact that the number of iterations scales linearly with the sparsity $s$ confirms that these greedy methods are computationally efficient even for very high-dimensional problems.
  • Sample Complexity: For sparse linear regression, the authors show that $N = O(s \log d)$ measurements are sufficient for perfect support recovery. This matches the information-theoretic optimal rate.
  • The Power of Freedom: The freedom parameter $r$ dictates a clear trade-off. Increasing $r$ allows the algorithm to correct its mistakes faster (requiring fewer iterations), but it requires the problem to be "better conditioned" (having stronger RSC/RSS constants) to guarantee success. Simulations show that a small amount of freedom (e.g., $r=5$) is often enough to significantly reduce the number of iterations compared to $r=1$, though there are diminishing returns as $r$ increases further.
  • RIP-Free Recovery: The authors demonstrate that even if the standard RIP condition does not hold, support recovery can still be guaranteed by slightly "over-sampling" the sparsity—that is, setting the algorithm's sparsity parameter $k$ to be larger than the true sparsity $s$.

Limitations and Future Work

While the paper establishes state-of-the-art guarantees, the authors note a few limitations and avenues for future research:

  1. The Logarithmic Factor: The current iteration bound contains a $\log \kappa$ factor. Future work could investigate whether this can be removed to achieve a tighter $O(s\kappa)$ bound.
  2. SNR Condition: The theory currently requires a "signal-to-noise ratio" condition that scales with $\sqrt{\kappa}$. The authors suspect this is a theoretical artifact and that real-world performance might not be as sensitive to the condition number as the math suggests.
  3. Extension to Non-Sparse Signals: The analysis focuses strictly on "exactly sparse" signals. Extending these support recovery guarantees to "nearly sparse" signals—where most values are negligibly small but not exactly zero—remains an open challenge in the field.

Summary updated

Abstract

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 kappa log kappa) iterations where "kappa" is an appropriate condition number. Specifying the PHT operator, we obtain the best known result 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 compared to other popular recovery methods.
BibTeX
@inproceedings{shen2017partial,
  author = {Jie Shen and Ping Li},
  title = {{Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=Bk-9wvbd-H},
}
Figure