1
$\begingroup$

I want to find the solution $x$ with most zeros in its components, to:

$Ax=b$ for $A\in \mathbb{R}^{k \times n}, b \in \mathbb{R}^k$ ($k < n$), where $x \in \mathbb{R}^n$ has no additional 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.

$\endgroup$
1
$\begingroup$

(This would have been a comment, if I had enough reputation, as this is not my field of expertise.)

This goes into a different direction than your initial thoughts, but have you looked at L1-regularized least squares (also called "lasso method")? It adds an artificial constraint $\| x \|_{L^1} \leq \beta$ to the least squares problem. As the unit ball in the L1-norm is a rhombus, sparse solutions, i.e. corner points of the unit ball, are favored. http://en.wikipedia.org/wiki/Least_squares#Lasso_method.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.