Problem Statement
Show how the $L_1$-sparse reconstruction problem: $$\min_{x}{\left\lVert x\right\rVert}_1 \quad \text{subject to} \; y=Ax$$ can be reduced to a linear programming problem of form similar to: $$\min_{u}{b^Tu} \quad \text{subject to} \; Gu=h, Cu\le e.$$ We can assume that $y$ belongs to the range of $A$, typically because $A\in \mathbb{R}^{m\times n}$ is full-rank with $m\lt n$.
What I've Got
I have never worked with linear programming before, and though I think I understand the basics, I have no experience with this kind of reduction. So far, I have tried understanding the problem geometrically: any $x$ in the solution set to $y=Ax$ can be written as the sum of some arbitrary solution $x_0$ and a vector $v$ in the null space of $A$, so the solution set is a shifted copy of the null space. We are trying to expand the $L_1$-ball (or hyper-diamond? I don't know what to call it) until one of the corners hits that shifted subspace. My problem is, I don't know how to express that formally.
The best I can think of is to use a method similar to Converting Sum of Infinity Norm and $ {L}_{1} $ Norm to Linear Programming and let $t_i=\left\lvert x_i\right\rvert, i=1\dots n$ and rewrite the objective as:
$$\min_{t}{1^Tt} \quad \text{subject to} \; x\le t, -x\le t, y=Ax$$
But then $x$ is still floating around in the problem, which doesn't match the desired form (and isn't implementable with MATLAB's linprog function, which I will have to do later). And even if we find such a $t$, recovering the underlying $x$ doesn't seem straightforward to me either.
Am I even moving in the right direction? Any help is appreciated.
Figured it out! As Erwin pointed out, the formulation above is valid (save the fact that it should be optimized over x and t together). In order to write it in the form suggested by the problem, I needed to stack x and t:
$$\min_{u=[x^T\;t^T]^T}\begin{bmatrix}0\\1\end{bmatrix}^T\begin{bmatrix}x\\t\end{bmatrix} \quad \text{subject to}\; \begin{bmatrix}I & -I \\ -I & -I\end{bmatrix}\begin{bmatrix}x\\t\end{bmatrix}\le\begin{bmatrix}0\\0\end{bmatrix},\; \begin{bmatrix}A & 0\end{bmatrix}\begin{bmatrix}x\\t\end{bmatrix} = y,\;\begin{bmatrix}x\\t\end{bmatrix}\ge\begin{bmatrix}-\infty\\0\end{bmatrix}$$
(Please excuse my sloppy use of $0$ and $1$ for a vector/matrix of all zeros or all ones)