2
$\begingroup$

In material science research, we have come across the following type of problem. Given a m by n matrix A, a m vector b, and error tolerance $\varepsilon$, we want to do this minimization $$\eqalign{ & \min \text{ # nonzero components of } x \cr & \text{s.t.} \cr & {\left\| {Ax - b} \right\|_\infty } \le \varepsilon \cr} $$

Is there some standard name or procedure in mathematics to do this? Could it be transformed into a LP or Convex Programming problem?

Thank you:)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ en.wikipedia.org/wiki/Sparse_approximation $\endgroup$
    – Steve Huntsman
    Commented Nov 14, 2014 at 3:45
  • 1
    $\begingroup$ For this particular case, the standard convex relaxation (which is to replace the sparsity minimization by the $\ell_1$-norm of $x$) is called the Dantzig selector (e.g. statweb.stanford.edu/~candes/papers/DantzigSelector.pdf ) $\endgroup$
    – Cristóbal Guzmán
    Commented Nov 14, 2014 at 5:23
  • $\begingroup$ @CristóbalGuzmán, this is not quite right. The Dantzig selector uses a specific, and different, error fitting criterion: i.e., instead of $\|Ax-b\|_\infty\leq\epsilon$, it's $\|A^T(Ax-b)\|_\infty\leq\epsilon$. $\endgroup$
    – Michael Grant
    Commented Nov 30, 2014 at 2:08
  • $\begingroup$ You are right. In fact, I don't know whether the relaxation for the model described by the OP has a particular name. The Dantzig selector comes close, but it is not the same. $\endgroup$
    – Cristóbal Guzmán
    Commented Nov 30, 2014 at 4:34

1 Answer 1

Reset to default
1
$\begingroup$

I am not sure if there is a standard name for these type of problems. I would call problems of this type sparse approximation problems because you want to solve a linear equation approximately (assuming that $\epsilon$ is small) and sparsely. In statistics these problems (where one really aims to minimize the number of nonzero entries in the solution) are called subset selection problems, since you want to select a subset of the columns of $A$ that should be used to represent $b$ (approximately).

In general, the problem you gave is not equivalent to a linear program and in fact is NP hard. Also it is not convex and may posses a huge number of different minima. However, the links already given in the comments to sparse approximation or the Dantzig selector (other buzzwords are Basis Pursuit are Compressed sensing) show that the problem admits a convex relaxation namely, you interpret the objective function $\# \text{nonzero entries in $x$}$ as $\sum |x_k|^0$ (with the convention that $0^0=0$) and then replace the exponent $0$ by the smallest one that makes the objective convex, and this is $1$, i.e. you end up with $\sum |x_k|$. The resulting problem (with the constraint in the $\infty$-norm) can then be casted as a linear program. Remarkably, this relaxation is frequently found to be exact, i.e. the optimum of the relaxed problem is (one of) the optima of the original problem. This can be explained by some theory, but happens much more often than theory predicts (and also, in most practical cases I have seen, the theory does not apply but the predicted results hold (approximately) nonetheless).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .