# Finding sparsest solution of a linear system

 1 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 29 Dec '14, 08:01 dha92 22●4 accept rate: 0% is x real? and has x no constraints? (29 Dec '14, 09:11) zBirdy yes, x is real and has no constraints. Just added that information to the question, thanks for your observation. (29 Dec '14, 09:17) dha92

 1 answered 29 Dec '14, 09:16 zBirdy 171●2●12 accept rate: 20%
 toggle preview community wiki

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags:

Asked: 29 Dec '14, 08:01

Seen: 741 times

Last updated: 29 Dec '14, 09:17

### Related questions

OR-Exchange! Your site for questions, answers, and announcements about operations research.