Iterative Thresholding for Sparse Approximations

By Thomas Blumensath, M. Davies. 2008

1,343 citations recorded by the source corpus.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Best Subset Selection via a Modern Optimization Lens (2015, methodology): “In these cases, the algorithm can be shown to have a linear convergence rate [9, 10], where the rate depends upon the RIP constants.”
Optimal Brain Compression: A Framework for Accurate Post-Training Quantization and Pruning (2022, neutral): “Although solving this problem optimally for sparsity or quantization constraints is NP-hard [2, 31], it is a key step in all state-of-the-art post-training compression methods, both for pruning [18, 9] and for quantization [31, 18, 24].”
Compressed Sensing (2014, neutral): “Una primer opción, que no será analizada en este trabajo, es utilizar algoritmos de tipo “Greedy”, entre los que destacan: “Orthogonal Matching Pursuit (OMP)” [58], OMP Regularizado (ROMP) [54], “Iterative hard thresholding (IHT)” [10] y “Compressive Sampling Matching Pursuit” (CoSaMP) [53].”
Rank Awareness in Joint Sparse Recovery (2010, methodology): “Commonly used strategies are typically based on convex relaxation [5], non-convex local optimisation [6] or greedy search strategies [3], [4], [7]–[9].”
SparseGPT: Massive Language Models Can Be Accurately Pruned in One-Shot (2023, background): “A key aspect of the the layer-wise pruning problem in (2) is that both the mask M as well as the remaining weights Ŵ` are optimized jointly, which makes this problem NP-hard [1].”
Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods (2013, methodology): “As mentioned in the introduction, these results offer a complementary view to the theoretical develoments of [11, 12].”
Sparse projections for high-dimensional binary codes (2015, methodology): “This is known as the m - sparsity constraint [3].”
Multi-label learning with millions of labels: recommending advertiser bid phrases for web pages (2013, methodology): “It is straightforward to show, using the technique of [7], that the iterative hard thresholding algorithm will converge”
Learning to Optimize: A Primer and A Benchmark (2021, methodology): “The former, also known as LASSO, can be solved by the iterative shrinkage-thresholding algorithm (ISTA) [28] and its variants.”
Solving inverse problems using data-driven models (2019, positive): “UCL, Institute of Education, on 18 Oct 2019 at 15:29:08, subject to the Cambridge Core terms of use, available at (hard) thresholding (Blumensath and Davies 2008, Blumensath 2013, Foucart 2016), where for an initial guess ξ(i0 and i = 0, 1, . . . one iterates ξ(i+1) = Ts(ξ (i) −A∗D(AD(ξ(i))− g)),…”
$L_{1/2}$ Regularization: A Thresholding Representation Theory and a Fast Solver (2012, neutral): “In the experiments, the hard algorithm ([22], [23]), the sof t algorithm ([26], [39]), the hal f algorithm, together with the representative L1-algorithm, L1-Magic ( [45]), and the newly suggested L1/2-algorithm, reweighed L1-algorithm (RL1 in brief, [7]), were simulated.”
Hard Thresholding Pursuit: An Algorithm for Compressive Sensing (2011, methodology): “This parallels a result of [2], where the convergence of (IHT) was also proved under the condition ‖A‖2→2 < 1.”
Calculus of the Exponent of Kurdyka–Łojasiewicz Inequality and Its Applications to Linear Convergence of First-Order Methods (2016, methodology): “4; this includes some prominent and widely used NP-hard optimization model problems, for example, the least squares problem with cardinality constraint [6].”