Compression approaches for the regularized solutions of linear systems from large-scale inverse problems

DOI10.1007/S13137-015-0073-9zbMATH Open1338.65110arXiv1404.5684OpenAlexW1495031820MaRDI QIDQ901334FDOQ901334

Authors: S. M. Voronin, Dylan Mikesell, Guust Nolet 

Publication date: 11 January 2016

Published in: GEM - International Journal on Geomathematics (Search for Journal in Brave)

Abstract: We introduce and compare new compression approaches to obtain regularized solutions of large linear systems which are commonly encountered in large scale inverse problems. We first describe how to approximate matrix vector operations with a large matrix through a sparser matrix with fewer nonzero elements, by borrowing from ideas used in wavelet image compression. Next, we describe and compare approaches based on the use of the low rank SVD, which can result in further size reductions. We describe how to obtain the approximate low rank SVD of the original matrix using the sparser wavelet compressed matrix. Some analytical results concerning the various methods are presented and the results of the proposed techniques are illustrated using both synthetic data and a very large linear system from a seismic tomography application, where we obtain significant compression gains with our methods, while still resolving the main features of the solutions.

Full work available at URL: https://arxiv.org/abs/1404.5684

Recommendations

• Regularization with randomized SVD for large-scale discrete inverse problems
• Randomized algorithms for large-scale inverse problems with general Tikhonov regularizations
• Exploiting compression in solving discretized linear systems
• Regularized Linear Inversion with Randomized Singular Value Decomposition
• Fast \(l_ p\) solution of large, sparse, linear systems: Application to seismic travel time tomography

zbMATH Keywords

waveletsregularizationrandomized algorithmsingular value decompositionsparse matrixerror bounddata compressionlinear ill-posed problemslower rank approximation

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Numerical solutions to overdetermined systems, pseudoinverses (65F20) Numerical methods for wavelets (65T60) Ill-posedness and regularization problems in numerical linear algebra (65F22)

Cites Work

• LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares
• Orthonormal bases of compactly supported wavelets
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• An iterative thresholding algorithm for linear inverse problems with a sparsity constraint
• Wavelets, approximation, and statistical applications
• Biorthogonal bases of compactly supported wavelets
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tikhonov regularization and the L-curve for large discrete ill-posed problems
• Low rank approximation. Algorithms, implementation, applications
• Large-scale Tikhonov regularization via reduction by orthogonal projection
• The ``cubed sphere: A new method for the solution of partial differential equations in spherical geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• A breviary of seismic tomography. Imaging the interior of the earth and sun
• Title not available (Why is that?)

Cited In (4)

• A compressive Landweber iteration for solving ill-posed inverse problems
• Low-Rank Eigenvector Compression of Posterior Covariance Matrices for Linear Gaussian Inverse Problems
• Pass-Efficient Randomized Algorithms for Low-Rank Matrix Approximation Using Any Number of Views
• Analysis and Exploitation of Matrix Structure Arising in Linearized Optical Tomographic Imaging

Uses Software

• LSQR
• RSVDPACK
• CRAIG

This page was built for publication: Compression approaches for the regularized solutions of linear systems from large-scale inverse problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q901334)