In this paper we propose an approach to approximate a truncated singular value decomposition of a large structured matrix. By first decomposing the matrix into a sum of Kronecker products, our approach can be used to approximate a large number of singular values and vectors more efficiently than other well known schemes, such as randomized matrix algorithms or iterative algorithms based on Golub-Kahan bidiagonalization. We provide theoretical results and numerical experiments to demonstrate the accuracy of our approximation and show how the approximation can be used to solve large scale ill-posed inverse problems, either as an approximate filtering method, or as a preconditioner to accelerate iterative algorithms.
Since the publication by Kamm and Nagy @cite_4 , the algorithm has been extended in three general ways. First, the original 2D algorithm was modified to enable use on 3D problems @cite_26 . Second, Kilmer and Nagy extended the work from banded matrices to dense matrices @cite_31 . And third, the choices of boundary conditions have expanded to reflexive @cite_16 , anti-reflective @cite_24 , and whole-sample symmetric reflective boundary conditions @cite_14 , among others. All prior work uses the simple @math computations proposed in @cite_1 and @cite_4 .
@cite_26 @cite_4 @cite_14 @cite_1 @cite_24 @cite_31 @cite_16
2065900551 2277973662 2083407735 2166207339
Reflexive boundary conditions (BCs) assume that the array values outside the viewable region are given by a symmetry of the array values inside. The reflection guarantees the continuity of the image. In fact, there are usually two choices for the symmetry: symmetry around the meshpoint and symmetry around the midpoint. The first is called whole-sample symmetry in signal and image processing, the second is half-sample. Many researchers have developed some fast algorithms for the problems of image restoration with the half-sample symmetric BCs over the years. However, little attention has been given to the whole-sample symmetric BCs. In this paper, we consider the use of the whole-sample symmetric boundary conditions in image restoration. The blurring matrices constructed from the point spread functions (PSFs) for the BCs have block Toeplitz-plus-PseudoHankel with Toeplitz-plus-PseudoHankel blocks structures. Recently, regardless of symmetric properties of the PSFs, a technique of Kronecker product approximations was successfully applied to restore images with the zero BCs, half-sample symmetric BCs and anti-reflexive BCs, respectively. All these results extend quite naturally to the whole-sample symmetric BCs, since the resulting matrices have similar structures. It is interesting to note that when the size of the true PSF is small, the computational complexity of the algorithm obtained for the Kronecker product approximation of the resulting matrix in this paper is very small. It is clear that in this case all calculations in the algorithm are implemented only at the upper left corner submatrices of the big matrices. Finally, detailed experimental results reporting the performance of the proposed algorithm are presented. This paper introduces a parallel and distributed algorithm for solving the following minimization problem with linear constraints: @math minimizef1(x1)+ź+fN(xN)subject toA1x1+ź+ANxN=c,x1źX1,ź,xNźXN,where @math Nź2, @math fi are convex functions, @math Ai are matrices, and @math Xi are feasible sets for variable @math xi. Our algorithm extends the alternating direction method of multipliers (ADMM) and decomposes the original problem into N smaller subproblems and solves them in parallel at each iteration. This paper shows that the classic ADMM can be extended to the N-block Jacobi fashion and preserve convergence in the following two cases: (i) matrices @math Ai are mutually near-orthogonal and have full column-rank, or (ii) proximal terms are added to the N subproblems (but without any assumption on matrices @math Ai). In the latter case, certain proximal terms can let the subproblem be solved in more flexible and efficient ways. We show that @math źxk+1-xkźM2 converges at a rate of o(1 k) where M is a symmetric positive semi-definte matrix. Since the parameters used in the convergence analysis are conservative, we introduce a strategy for automatically tuning the parameters to substantially accelerate our algorithm in practice. We implemented our algorithm (for the case ii above) on Amazon EC2 and tested it on basis pursuit problems with >300 GB of distributed data. This is the first time that successfully solving a compressive sensing problem of such a large scale is reported. In this paper, we consider the approximation of dense block Toeplitz-plus-Hankel matrices by sums of Kronecker products of Toeplitz-plus-Hankel matrices. We present an algorithm for efficiently computing the matrix approximation that requires the factorization of matrices of much smaller dimension than that of the original. The main results are described for block Toeplitz matrices with Toeplitz-plus-Hankel blocks, but the algorithms can be readily adjusted for other related structures that arise in image processing applications, such as block Toeplitz with Toeplitz blocks and block Toeplitz-plus-Hankel with Toeplitz-plus-Hankel blocks. Our work extends the techniques in Kamm and Nagy (SIAM J. Matrix Anal. Appl. 2000; 22:155–172) and (SIAM J. Matrix Anal. Appl. 2004; 25:829–841), which consider similar matrices, but with the added restriction that the matrices have a banded block-banded structure. We illustrate the effectiveness of our algorithm by using the output of the algorithm to construct preconditioners for systems from two different applications: diffuse optical tomography and atmospheric image deblurring. Copyright © 2007 John Wiley & Sons, Ltd. We investigate the problem of reconstructing a high-dimensional nonnegative sparse vector from lower-dimensional linear measurements. While much work has focused on dense measurement matrices, sparse measurement schemes can be more efficient both with respect to signal sensing as well as reconstruction complexity. Known constructions use the adjacency matrices of expander graphs, which often lead to recovery algorithms which are much more efficient than minimization. However, prior constructions of sparse measurement matrices rely on expander graphs with very high expansion coefficients which make the construction of such graphs difficult and the size of the recoverable sets very small. In this paper, we introduce sparse measurement matrices for the recovery of nonnegative vectors, using perturbations of the adjacency matrices of expander graphs requiring much smaller expansion coefficients, hereby referred to as minimal expanders. We show that when minimization is used as the reconstruction method, these constructions allow the recovery of signals that are almost three orders of magnitude larger compared to the existing theoretical results for sparse measurement matrices. We provide for the first time tight upper bounds for the so called weak and strong recovery thresholds when minimization is used. We further show that the success of optimization is equivalent to the existence of a “unique” vector in the set of solutions to the linear equations, which enables alternative algorithms for minimization. We further show that the defined minimal expansion property is necessary for all measurement matrices for compressive sensing, (even when the non-negativity assumption is removed) therefore implying that our construction is tight. We finally present a novel recovery algorithm that exploits expansion and is much more computationally efficient compared to minimization.