Sparse Approximate Solutions to Linear Systems

By B. Natarajan. 1995

Subfields: Numerical Methods & Scientific Computing

How researchers see this paper

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

In Numerical Methods & Scientific Computing

Citations in the corpus

Data-Efficient Structured Pruning via Submodular Optimization (2022, background): “Solving Problem (1) exactly is NP-Hard [Natarajan, 1995].”
Is Feature Selection Secure against Training Data Poisoning? (2015, background): “As for the regularization term Ω(w), ideally, one would like to consider the `0-norm of w to exactly select a given number of features, which however makes the problem NP-hard (Natarajan, 1995).”
Extended Comparisons of Best Subset Selection, Forward Stepwise Selection, and the Lasso (2017, neutral): “On the other hand, the best subset selection problem (1) is nonconvex and is known to be NP-hard (Natarajan, 1995).”
GCR: Gradient Coreset based Replay Buffer Selection for Continual Learning (2021, neutral): “The optimization problem given in Eq (4) is weakly submodular [20, 33].”
Optimization with Sparsity-Inducing Penalties (2011, methodology): “Even though this problem can be shown to be NP-hard [84], greedy procedures can provide an approximate solution.”
Question Answering as Global Reasoning Over Semantic Abstractions (2018, background): “The second term is supposed to bring more sparsity to the desired solutions, just like how regularization terms act in machine learning models (Natarajan 1995).”
Non-convex Optimization for Machine Learning (2017, background): “Unfortunately however, sparse-recovery is an NP-hard problem [Natarajan, 1995].”
Restricted Strong Convexity Implies Weak Submodularity (2016, background): “This subset selection problem is NP-hard [3] even for the sparse linear regression objective, and a vast body of literature has analyzed different approximation algorithms under various assumptions.”
Recovery of exact sparse representations in the presence of bounded noise (2005, background): “Since searching for the sparsest representation is a nonpolynomial (NP) hard problem [1] that can only be solved by exhaustive search, one is tempted to replace the true search for the sparsest solution”
Handbook of Blind Source Separation: Independent Component Analysis and Applications (2010, background): “17) can be solved with simple linear algebra, but for τ = 0, the problem is a combinatorial one [31, 78] and a priori untractable.”
Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso) (2009, background): “3 show the numerical values of the theoretical upper and lower bounds on the threshold—that is, and , as deﬁned in (29).”
An efficient algorithm for total variation regularization with applications to the single pixel camera and compressive sensing (2010, methodology): “It has been proven that computing the sparsest solution directly generally requires prohibitive computations of exponential complexity [46], so several heuristic methods have been developed, such as Matching Pursuit [51], Basis Pursuit [53, 54], logbarrier method [55], iterative thresholding method ”
Collaborative Sparse Regression for Hyperspectral Unmixing (2014, methodology): “For this purpose, sparse linear regression techniques [14], [15] can be used.”
Optimization Models for Machine Learning: A Survey (2019, background): “Problem (7)–(9) is NPhard, as proven in [174].”
RODEO: Robust DE-aliasing autoencOder for real-time medical image reconstruction (2017, background): “But that is known to be NP hard [6].”
On Solutions of Sparsity Constrained Optimization (2015, background): “SCO is actually a combinatorial optimization problem and it is generally NP-hard even for quadratic objective function [1].”
Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization (2007, background): “This problem is commonly referred to as cardinality minimization, since we seek the vector whose support has the smallest cardinality, and is known to be NP-hard [11].”
Iterative Thresholding for Sparse Approximations (2008, background): “5) for general x and Φ is known to be an NP-hard optimisation problem [8, 9].”