Starting from a simple $L_1$ penalization: \begin{equation} min_x \frac{1}{2}||y-x||^2_2 + \lambda||Dx||_1 \end{equation} We can solve this with quadratic programming via the dual problem: \begin{equation} min_z \frac{1}{2} z^\intercal D D^\intercal z - y^\intercal D^\intercal z \\ u.c. -\lambda\mathbf{1} \leq z \leq \lambda\mathbf{1} \end{equation} and the final solution reads $ x = y - D^\intercal z$
Now let's assume I add a second $L_1$ penalty term: \begin{equation} min_x \frac{1}{2}||y-x||^2_2 + \lambda_1||D_1x||_1 + \lambda_2||D_2x||_1 \end{equation} I'd assume the formulation doesn't change much, and the dual problem is similar using $D = \bigl(\begin{smallmatrix} D_1\\ D_2 \end{smallmatrix} \bigr)$ and $\lambda = \bigl(\begin{smallmatrix} \lambda_1\\ \lambda_2 \end{smallmatrix} \bigr)$.
$D_1$ and $D_2$ are pretty well behaved. $D_1$ is a first-difference matrix and $D_2$ is a second-difference matrix. $$ D_1 = \begin{pmatrix} -1 & 1 & 0 & \cdots \\ 0 & -1 & 1 & \cdots \\ \vdots & \vdots & \vdots & \ddots \\ \end{pmatrix} D_2 = \begin{pmatrix} 1 & -2 & 1 & 0 & \cdots \\ 0 & 1 & -2 & 1 &\cdots \\ \vdots & \vdots & \vdots & \vdots &\ddots \\ \end{pmatrix} $$
The issue is that I find $D D^\intercal$ to be singular, so the quadratic program can't be solved.
Is there any way around it?
I would better use a second order conic formulation. Even if slightly boring, duality calculation are fairly easy (see http://blog.mosek.com/2014/03/how-to-write-dual-problem-in-nutshell.html). Defining $\lambda_2 = \lambda_2 \mathbb{1}$ $\lambda_1 = \lambda_1 \mathbb{1}$ your problem reads
$ \min t + \lambda_1^T w_1 + \lambda_2^T w_2$
$ s.t. $
$ r = y -x $
$(1,t, r) \in Q_r$
$ z_1 = D_1 x, z_2= D_2=x$
$ (w_{ij} , z_{ij})\in Q^2,\quad i\in\{1,2\}, j=1,\ldots$
where $Q^2$ is the ice-cream cone and $Q_r$ is the rotated one. The dual problem is, if I am not mistaken, the following
$ \max \mu_0 + y^t \mu_r$
$ s.t. $
$ \lambda_1 \geq \mu_1 $
$ \lambda_2 \geq \mu_2 $
$(1,-\mu_0, -\mu_r) \in Q_r$
$ D_1^T \mu_1 + D_2^T \mu_2 + \mu_r\leq 0$
That should be solvable by any conic quadratic solver (as MOSEK...but you see I am biased...look at my nickname...) or recast in a QP form.