Hi, I want to find the solution x with most zeros on its components as possible, to for (x is real and has no constraints) It's a known fact that it's NP-Complete. So I want to find 1) a heuristic or 2) another NP-Complete Problem to reduce the following problem (in order to apply the heuristics known for the second problem and then go back to the original one). I've been thinking about some intuitive or expectable properties of the sparse solutions but have not yet proved any. So I prefer editing once I am sure about them. I've identified the subproblems of choosing a subset of (set of indexes for variables who will be 0) and finding x, i.e. , and that in finding a sparse solution it is equivalent to fix a component to zero and to put its associate column in A to zeros. Have been thinking this would be an initial step towards finding an appropriate heuristic or reduction (for example, by taking the categories of problems with the same cadrinality of the subset chosen). I would appreciate some help of your part.
asked
dha92 |

Hello here is literature: http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf http://www.sciencedirect.com/science/article/pii/S1063520308000882 http://statweb.stanford.edu/~donoho/Reports/2004/l1l0approx.pdf http://www.math.vanderbilt.edu/~foucart/FL08.pdf http://statweb.stanford.edu/~donoho/Reports/2005/NonNegative-R5.pdf
answered
zBirdy |

is x real? and has x no constraints?

yes, x is real and has no constraints. Just added that information to the question, thanks for your observation.