The coefficient matrix in (REF ) is of size \(n_h \times n_h\) , where \(n_h\)  is the number of pixels. Hence, we cannot use a direct solver.
Even for iterative solvers such as CG [1]}, we have to apply the coefficient matrix (as an operator) on an image of size \(n_h \times L_s\)  in each iteration. While the blur \(\mathbf {B}\)  and its transpose can be computed efficiently, the patch-extraction operation \({P}_{i\tau }^\top {P}_{i\tau }\)  has to be performed for each pair of neighboring pixels—this has a high computational cost of \(\mathcal {O}(n_h L_s |W|)\) . Thus, the straightforward splitting in (REF ) leads to an expensive \(\mathbf {X}\)  update, which slows down the overall ADMM algorithm.
We now show how we get around this issue by expressing patch variations using convolutions and by using a novel form of variable splitting.
<FIGURE>