In that paper on page 8, he wrote the classical compressive sensing problem as
$$\min_{\theta} \lVert \theta \rVert_1, s.t. \Phi \theta = y$$ can be reformulated as a linear programming problem
$$\min_{z} 1^{T}z,s.t., Az = y, \textbf{and } z \ge 0$$ where $A = \begin{bmatrix} \Phi & -\Phi \end{bmatrix}$.
The solution to the compressive sensing problem is simply $$\theta = u - v, z = \begin{bmatrix} u \\ v\end{bmatrix}.$$
My question
My major doubt is on the converting of L1 loss $\Vert \theta\Vert_1$. I can only see the following
$$\Vert \theta \Vert_1 = \Vert u-v \Vert_1 \le \Vert u \Vert_1 + \Vert v \Vert_1 = 1^{T}z$$
Therefore, the reformulated problem is only minimizing the upper bound of $\Vert \theta \Vert_1$, not directly minimize it. So where did I misunderstand Donoho's result?
Reference
1 Donoho, D. L. (2006). Compressed sensing. IEEE Transactions on Information Theory, 52(4), 1289–1306. https://doi.org/10.1109/TIT.2006.871582
The optimization problems are equivalent and it is not a minimization of its upper bound.
To minimize $|x|$, we can write $x=u-v$, impose the condition that $u,v \ge 0$, and minimize $u+v$ instead.
By doing so, at the optimal solution for each $i$, we either have $u_i=0$ or $v_i=0$. Suppose on the contrary that $u_i$ and $v_i$ are both positive, then we can let $\hat{u}_i=u_i-\min(u_i,v_i)$ and $\hat{v}_i = v_i - \min(u_i, v_i)$ and that would be a more optimal solution.
Hence $x_i = u_i$ or $x_i=-v_i$ and hence $|x|=u_i$ or $|x|=v_i$, that is $u_i+v_i=|x_i|$