In image deconvolution problems, the diagonalization of the underlying operators by means of the fast Fourier transform (FFT) usually yields very large speedups. When there are incomplete observations (e.g., in the case of unknown boundaries), standard deconvolution techniques normally involve non-diagonalizable operators, resulting in rather slow methods or, otherwise, use inexact convolution models, resulting in the occurrence of artifacts in the enhanced images. In this paper, we propose a new deconvolution framework for images with incomplete observations that allows us to work with diagonalized convolution operators, and therefore is very fast. We iteratively alternate the estimation of the unknown pixels and of the deconvolved image, using, e.g., an FFT-based deconvolution method. This framework is an efficient, high-quality alternative to existing methods of dealing with the image boundaries, such as edge tapering. It can be used with any fast deconvolution method. We give an example in which a state-of-the-art method that assumes periodic boundary conditions is extended, using this framework, to unknown boundary conditions. Furthermore, we propose a specific implementation of this framework, based on the alternating direction method of multipliers (ADMM). We provide a proof of convergence for the resulting algorithm, which can be seen as a “partial” ADMM, in which not all variables are dualized. We report experimental comparisons with other primal–dual methods, where the proposed one performed at the level of the state of the art. Four different kinds of applications were tested in the experiments: deconvolution, deconvolution with inpainting, superresolution, and demosaicing, all with unknown boundaries.
In @cite_41 , a method that has some resemblance to our proposed deconvolution framework was introduced, in the context of the solution of systems of linear equations with Toeplitz system matrices.
@cite_41
2029301183 2747169803 2045748842 2150059782
This paper explores a seemingly counter-intuitive idea: the possibility of accelerating the solution of certain linear equations by adding even more equations to the problem. The basic insight is to trade-off problem size by problem structure. We test this idea on Toeplitz equations, in which case the expense of a larger set of equations easily leads to circulant structure. The idea leads to a very simple iterative algorithm, which works for a certain class of Toeplitz matrices, each iteration requiring only two circular convolutions. In the symmetric definite case, numerical experiments show that the method can compete with the preconditioned conjugate gradient method (PCG), which achieves O(nlogn) performance. Because the iteration does not converge for all Toeplitz matrices, we give necessary and sufficient conditions to ensure convergence (for not necessarily symmetric matrices), and suggest an efficient convergence test. In the positive definite case we determine the value of the free parameter of the circulant that leads to the fastest convergence, as well as the corresponding value for the spectral radius of the iteration matrix. Although the usefulness of the proposed iteration is limited in the case of ill-conditioned matrices, we believe that the results show that the problem size problem structure trade-off deserves further study. In a typical communications problem, Toeplitz matrices Φ arise when modeling the task of determining an unknown impulse response a from a given probe signal φ. When a is sparse, then whenever Φ formed from the probe signal φ satisfy the Restricted Isometry Property (RIP), a can be robustly recovered from its measurements via l1-minimization. In this paper, we derived the RIP for compressive Toeplitz matrices whose number of rows of the matrices J is much smaller than the number of columns N . We show that J should scale like J ∼ S log(N), where S is the sparsity of the impulse response. While this is marginally worse than the state-of-the-art scaling currently achieved in the literature, the novelty of this work comes from making the relation between the Toeplitz matrix of interest to a block diagonal matrix. The proof of the RIP then follows from using recent results on the concentration of measure inequalities of block diagonal matrices, together with a standard covering-and-counting argument. The problem of recovering a sparse signal x Rn from a relatively small number of its observations of the form y = Ax Rk, where A is a known matrix and k « n, has recently received a lot of attention under the rubric of compressed sensing (CS) and has applications in many areas of signal processing such as data cmpression, image processing, dimensionality reduction, etc. Recent work has established that if A is a random matrix with entries drawn independently from certain probability distributions then exact recovery of x from these observations can be guaranteed with high probability. In this paper, we show that Toeplitz-structured matrices with entries drawn independently from the same distributions are also sufficient to recover x from y with high probability, and we compare the performance of such matrices with that of fully independent and identically distributed ones. The use of Toeplitz matrices in CS applications has several potential advantages: (i) they require the generation of only O(n) independent random variables; (ii) multiplication with Toeplitz matrices can be efficiently implemented using fast Fourier transform, resulting in faster acquisition and reconstruction algorithms; and (iii) Toeplitz-structured matrices arise naturally in certain application areas such as system identification. In this paper, we derive concentration of measure inequalities for compressive Toeplitz matrices (having fewer rows than columns) with entries drawn from an independent and identically distributed (i.i.d.) Gaussian random sequence. These inequalities show that the norm of a vector mapped by a Toeplitz matrix to a lower dimensional space concentrates around its mean with a tail probability bound that decays exponentially in the dimension of the range space divided by a factor that is a function of the sample covariance of the vector. Motivated by the emerging field of Compressive Sensing (CS), we apply these inequalities to problems involving the analysis of high-dimensional systems from convolution-based compressive measurements. We discuss applications such as system identification, namely the estimation of the impulse response of a system, in cases where one can assume that the impulse response is high-dimensional, but sparse. We also consider the problem of detecting a change in the dynamic behavior of a system, where the change itself can be modeled by a system with a sparse impulse response.