| Given an m-dimensional dictionary of size n and a number k, one might wish to represent an incoming datum using at most k non-zero weights. If k is given as a parameter, this problem is as known as the sparsity constraint linear optimization problem. We define the problem with the name of k-SPARSE. If the value of k is to be minimized, then the problem is also known as the sparsest solution of underdetermined linear equation system, which has been widely studied over the few decades as the central problem in the compressed sensing literature. Though in general such linear sparsity constrained problem is believed to be W[1]-hard, the complexity of k-SPARSE is obscure and yet open to be discussed, especially when the dictionary and the variables are over the different fields, the problems require more subtle classification under the context of complexity theory.;We give the definitions of the k-SPARSE problem over Boolean, Z and R. We also extend the definition of W Hierarchy to circuits with arbitrary modm gates and threshold gates. Using the extended parameterized W hierarchy classes, we show the hardness result of decision problem version of k-SPARSE with its variations. At the same time we also study the relation between classical parameterized problems and the k-SPARSE.;Next we move onto the search problem version of k-SPARSE. Though it is believed that W[1]-hard problems do not have an FPT algorithm (with the fact that if W[1] is not in FPT then P ≠ NP) and the solution cannot be polynomially approximated, there are still non-trivial approaches that can generate desired result under some constraint. Finally we talk about some classic method and the sketching as a possible way to reduce the problem size of the k-SPARSE. The trade-off between problem size n, parameter k and error r as well as the lower bound of sketching are left open for the future study. |
