HP Labs Technical Reports
Sparse Approximate Solutions to Linear Systems
Natarajan, Balas K.
HPL92167
Keyword(s):
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 nonzero entries that satisfies the system within the given tolerance. While the problem is NPhard, we prove that a wellknown greedy heuristic is almost optimal.
Back to Index
