Efficient Decomposition-Based Algorithms for ${\mathrm{\ell }}_1$-Regularized Inverse Problems with Column-Orthogonal and Kronecker Product Matrices

We consider an ${\mathrm{\ell }}_1$-regularized inverse problem where both the forward and regularization operators have a Kronecker product structure. By leveraging this structure, a joint decomposition can be obtained using generalized singular value decompositions. We show how this joint decomposition can be effectively integrated into the Split Bregman and Majorization-Minimization methods to solve the ${\mathrm{\ell }}_1$-regularized inverse problem. Furthermore, for cases involving column-orthogonal regularization matrices, we prove that the joint decomposition can be derived directly from the singular value decomposition of the system matrix. As a result, we show that framelet and wavelet operators are efficient for these decomposition-based algorithms in the context of ${\mathrm{\ell }}_1$-regularized image deblurring problems.