Thresholding Algorithm

Thresholding algorithms are iterative procedures for sparse signal recovery that proceed by alternating between a gradient or power iteration step and a hard-thresholding step that zeros out small entries to enforce sparsity. In the context of sparse PCA, these algorithms start with an initial estimate of the principal component, perform a power iteration on the covariance matrix, and then keep only the k largest entries. Despite their simplicity, thresholding methods lack rigorous recovery guarantees in the hard regime of the statistical-computational gap and can fail to converge to the true sparse component even when the signal is moderately strong.

The appeal of thresholding algorithms — their simplicity, speed, and interpretability — masks a deeper inadequacy. They are local methods that search for structure in a landscape where the true signal is globally coherent but locally indistinguishable from noise. In such landscapes, local methods are doomed.