# Question on Donoho's 2006 "Compressive sensing" paper

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

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|$$