2022/04/11 by Kyriakos Axiotis, Axiotis, Kyriakos, Maxim Sviridenko +1 · 2 citations
Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Optimization and Control (math.OC) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques
paper · pdf · doi:10.48550/arxiv.2204.08274
openalex publication_date 2022/04/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We propose a simple modification to the iterative hard thresholding (IHT) algorithm, which recovers asymptotically sparser solutions as a function of the condition number. When aiming to minimize a convex function f(x) with condition number κ subject to x being an s-sparse vector, the standard IHT guarantee is a solution with relaxed sparsity O(sκ2), while our proposed algorithm, regularized IHT, returns a solution with sparsity O(sκ). Our algorithm significantly improves over ARHT which also finds a solution of sparsity O(sκ), as it does not require re-optimization in each iteration (and so is much faster), is deterministic, and does not require knowledge of the optimal solution value f(x^*) or the optimal sparsity level s. Our main technical tool is an adaptive regularization framework, in which the algorithm progressively learns the weights of an ℓ2 regularization term that will allow convergence to sparser solutions. We also apply this framework to low rank optimization, where we achieve a similar improvement of the best known condition number dependence from κ2 to κ.