A basis pursuit problem can be converted to a linear programming problem by first noting that :\begin{align} \|x\|_1 &= |x_1| + |x_2| + \ldots + |x_n| \\ &= (x_1^+ + x_1^-) + (x_2^+ + x_2^-) + \ldots + (x_n^+ + x_n^-)\end{align} where x_i^+, x_i^- \geq 0. This construction is derived from the constraint x_i = x_i^+ - x_i^-, where the value of |x_i| is intended to be stored in x_i^+ or x_i^- depending on whether x_i is greater or less than zero, respectively. Although a range of x_i^+ and x_i^- values can potentially satisfy this constraint, solvers using the
simplex algorithm will find solutions where one or both of x_i^+ or x_i^- is zero, resulting in the relation |x_i| = (x_i^+ + x_i^-). From this expansion, the problem can be recast in
canonical form as: : \begin{align} & \text{Find a vector} && (\mathbf{x^+}, \mathbf{x^-}) \\ & \text{that minimizes} && \mathbf{1}^T \mathbf{x^+} + \mathbf{1}^T \mathbf{x^-} \\ & \text{subject to} && A \mathbf{x^+} - A \mathbf{x^-} = \mathbf{y} \\ & \text{and} && \mathbf{x^+}, \mathbf{x^-} \geq \mathbf{0}. \end{align} == See also ==