0
$\begingroup$

Given $D$ is a $N \times M$ design matrix, $P$ is a $N \times 1$ target. I learned that to solve $$\text{argmin}_{c: Dc = P}\Vert c \Vert_0$$ is infeasible since the objective function is non-convex.

So instead, we solve $$\text{argmin}_{c: Dc = P}\Vert c \Vert_1$$ in the hope that its solution is the same as the solution of the first objective function.

I learned that it is the theory of compressed sensing that answers this question, but I don't really understand how. Basically, I cannot understand a theorem which states that:

Every $\Omega$-sparse vector $x$ is the unique solution of $\text{argmin}_{c: Dc = P}\Vert c \Vert_1$ with $P = Dx$ if, and only if, D has the NSP of order $Ω$. ($\Omega \in \{1, \cdots, M \}$)

  1. What is $\Omega$-sparse vector? Can I simply consider them to be vectors which have only $\Omega$ non-zero entries?

  2. What does it mean of 'every vector' is the 'unique solution'?

  3. How does this guarantees the solutions of the two objectives will coincide?

I have a very weak mathematical background, please give me an intuitive answer if possible, thank you!

$\endgroup$

1 Answer 1

0
$\begingroup$

1: $\Omega$-sparse means that a vector has at most $\Omega$ nonzero elements.

2: It means that if you take any $\Omega$-sparse $x$, and then solve the problem $\text{argmin}_{c: Dc = Dx}\Vert c \Vert_1$, then that problem has only one solution, and that solution is $x$.

$\endgroup$

You must log in to answer this question.

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