Ideas on Matrix Factorization / Transformations for $ {L}_{1} $ Minimization
Since $ \epsilon $ is a parameter you need to set why not trade it with another parameter you need to set to create an easily solvable problem (Relaxation of the Problem)?

You can transform the problem into the following form ($ {L}_{1} $ Regularized Least Squares):

$$ \arg \min_{x} \frac{1}{2} \left\| A x - z \right\|^{2} + \lambda \left\| x \right\|_{1} $$  

There are many solvers for that even for large sparse matrices.
For any $ \epsilon $ from the original problem there is $ \lambda $ such that the solutions are the same.
Since $ \epsilon $ it to be arbitrarily set in the original problem you can trade it for $ \lambda $.

This can be solved with many solvers easily without the need for Matrix Inversion.