Search

In [McDonald, Pestana, and Wathen, SIAM J. Sci. Comput., 40 (2018), pp. A1012--A1033], a block circulant preconditioner is proposed for all-at-once linear systems arising from evolutionary partial differential equations, in which the preconditioned matrix is proven to be diagonalizable and to have identity-plus-low-rank decomposition in the case of the heat equation. In this paper, we generalize the block circulant preconditioner by introducing a small parameter ϵ>0 into the top-right block of the block circulant preconditioner. The implementation of the generalized preconditioner requires the same computational complexity as that of the block circulant one. Theoretically, we prove that (i) the generalization preserves the diagonalizability and the identity-plus-low-rank decomposition; (ii) all eigenvalues of the new preconditioned matrix are clustered at 1 for sufficiently small\epsilon; (iii) GMRES method for the preconditioned system has a linear convergence rate independent of size of the linear system when\epsilon is taken to be smaller than or comparable to square root of time-step size. Numerical results are reported to confirm the efficiency of the proposed preconditioner and to show that the generalization improves the performance of block circulant preconditioner. [ABSTRACT FROM AUTHOR]

The l1-l2 regularization is a popular nonconvex yet Lipschitz continuous metric, which has been widely used in signal and image processing. The theory for the l1-l2 minimization method shows that it has superior sparse recovery performance over the classical l1 minimization method. The motivation and major contribution of this paper is to provide a positive answer to the open problem posed in [T.-H. Ma, Y. Lou, and T.-Z. Huang, SIAM J. Imaging Sci., 10 (2017), pp. 1346-1380] about the sufficient conditions that can be sharpened for the l1-l2 minimization method. The novel technique used in our analysis of the l1-l2 minimization method is a crucial sparse representation adapted to the l1-l2 metric which is different from the other state-of-the-art works in the context of the l1-l2 minimization method. The new restricted isometry property (RIP) analysis is better than the existing RIP based conditions to guarantee the exact and stable recovery of signals. [ABSTRACT FROM AUTHOR]