This paper is concerned with the hard thresholding technique which sets all but the $k$ largest absolute elements to zero. We establish a tight bound that quantitatively characterizes the deviation of the thresholded solution from a given signal. Our theoretical result is universal in the sense that it holds for all choices of parameters, and the underlying analysis only depends on fundamental arguments in mathematical optimization. We discuss the implications for the literature: Compressed Sensing. On account of the crucial estimate, we bridge the connection between restricted isometry property (RIP) and the sparsity parameter of $k$ for a vast volume of hard thresholding based algorithms, which renders an improvement on the RIP condition especially when the true sparsity is unknown. This suggests that in essence, many more kinds of sensing matrices or fewer measurements are admissible for the data acquisition procedure. Machine Learning. In terms of large-scale machine learning, a significant yet challenging problem is producing sparse solutions in online setting. In stark contrast to prior works that attempted the $\ell_1$ relaxation for promoting sparsity, we present a novel algorithm which performs hard thresholding in each iteration to ensure such parsimonious solutions. Equipped with the developed bound for hard thresholding, we prove global linear convergence for a number of prevalent statistical models under mild assumptions, even though the problem turns out to be non-convex.

本文研究了硬阈值算子，建立了一种紧致的理论界限，用于量化阈值处理后的信号与原始信号偏差的范围。研究结果在压缩感知和机器学习方面均具有应用，特别是在数据采集程序中允许使用更多种类的感知矩阵或更少的测量，并提出了一种随机算法来确保产生稀疏的解。

硬阈值化的紧致界限