Hi, I want to find the solution x with most zeros on its components as possible, to alt text for alt text (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 enter image description here subproblems of choosing a subset of enter image description here (set of indexes for variables who will be 0) and finding x, i.e. enter image description here, 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's gravatar image

accept rate: 0%

edited 29 Dec '14, 09:17

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

Your answer
toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • 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



Asked: 29 Dec '14, 08:01

Seen: 741 times

Last updated: 29 Dec '14, 09:17

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