2
$\begingroup$

The $l_0$-relaxation problem $$\min_x \Vert x \Vert_0 \text{ subject to Ax = b}$$ is non-convex. On the other hand, the $l_1$ problem $$\min_x \Vert x \Vert_1 \text{ subject to Ax = b}$$ is convex. We want to solve the $l_1$ problem in the hope that its solution is the same as the solution to the $l_0$-relaxation problem.

I learned nullspace property guarantees the two solutions to be the same.

Are there other theorems that guarantee the agreement?

$\endgroup$
2

0

You must log in to answer this question.

Browse other questions tagged .