HP Labs Technical Reports
Sparse Approximate Solutions to Linear Systems
Natarajan, Balas K.
Abstract: We consider the problem of computing a sparse approximate solution to a given linear system and tolerance, i.e., a vector with a minimum number of non-zero entries that satisfies the system within the given tolerance. While the problem is NP-hard, we prove that a well-known greedy heuristic is almost optimal.
Back to Index