Timezone: »

 
Poster
Partial Hard Thresholding: Towards A Principled Analysis of Support Recovery
Jie Shen · Ping Li

Tue Dec 05 06:30 PM -- 10:30 PM (PST) @ Pacific Ballroom #47
in Posters Tue »

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.

Keywords: Sparsity and Compressed Sensing
[ Paper] 

Author Information

Jie Shen (Stevens Institute of Technology)
Ping Li (Rugters University)

More from the Same Authors