The truncated SVD as a method for regularization
From MaRDI portal
ill- posed problemsill-conditioned matrixmethod of regularizationnumerical rankperturbation theorytruncated singular value decompositionunconstrained linear least squares problem
Eigenvalues, singular values, and eigenvectors (15A18) Linear regression; mixed models (62J05) Probabilistic methods, stochastic differential equations (65C99) Numerical computation of eigenvalues and eigenvectors of matrices (65F15) Numerical solutions to overdetermined systems, pseudoinverses (65F20)
The paper deals with the unconstrained linear least squares problem (1) \(\min \| Ax-B\|\), \(A\in {\mathbb{R}}^{m\times n}\), \(m\geq n\), for an ill-conditioned matrix A. There are two well-known attempts to deal with such ill-posed problems: the method of regularization by Tikhonov and Phillips and the truncated singular value decomposition (TSVD). Let \(A=U\Sigma V^ T\) be the singular value decomposition (SVD) of the matrix A; here \(U\in {\mathbb{R}}^{m\times m}\), \(V\in {\mathbb{R}}^{n\times n}\) are orthogonal, \(\Sigma =diag\{\sigma_ 1,\sigma_ 2,...,\sigma_ n\}\) and \(\sigma_ i\) are singular values of A. The TSVI solution of (1) is defined as \(x_ k=A^+_ kB\), where \(A^+_ k\) is the pseudoinverse of \(A_ k=U\Sigma_ kV^ T,\Sigma_ k=diag\{\sigma_ 1,...,\sigma_ k,0,...,0\}.\) To analyze the behaviour of TSVD solutions a perturbation theory is developed. It states that the perturbed TSVD solution can be guaranteed to be closed to the true solution if the relative gap \(\omega_ k=\| A-A_ k\| \cdot \| A^+_ k\| =\sigma_{k+1}/\sigma_ k\) between the singular values \(\sigma_ k\) and \(\sigma_{k+1}\) is small. This divides all ill-conditioned matrices into two classes: those with well-determined numerical rank and with ill-determined numerical rank. It is proved that for the matrices of the first class the TSVD solution is close to the regularized solution provided the regularization parameter is chosen properly. Finally, the case of matrices with ill-determined numerical rank is discussed.
Recommendations
- scientific article; zbMATH DE number 4078640
- Regularization, GSVD and truncated GSVD
- Truncated Singular Value Decomposition Solutions to Discrete Ill-Posed Problems with Ill-Determined Numerical Rank
- Accuracy of TSVD solutions computed from rank-revealing decompositions
- Numerical implementation of the canonical TSVD method
Cites work
- A Practical Examination of Some Numerical Methods for Linear Discrete Ill-Posed Problems
- A Technique for the Numerical Solution of Certain Integral Equations of the First Kind
- Algorithms for the regularization of ill-conditioned least squares problems
- An SVD analysis of linear algebraic equations derived from first kind integral equations
- Bayesian Methods in Nonlinear Digital Image Restoration
- Computation of supremal (A,B)-invariant and controllability subspaces
- scientific article; zbMATH DE number 3477343 (Why is no real title available?)
- scientific article; zbMATH DE number 3562346 (Why is no real title available?)
- scientific article; zbMATH DE number 883145 (Why is no real title available?)
- scientific article; zbMATH DE number 3892457 (Why is no real title available?)
- scientific article; zbMATH DE number 3227378 (Why is no real title available?)
- Numerical inversion of the Radon transform
- On the almost rank deficient case of the least squares problem
- On the Numerical Solution of Ill-Conditioned Linear Systems with Applications to Ill-Posed Problems
- Perturbation bounds in connection with singular value decomposition
- Perturbation theory for pseudo-inverses
- The generalized eigenstructure problem in linear system theory
Cited in
(only showing first 100 items - show all)- Ensemble Kalman filter with the unscented transform
- Computation of the singular value expansion
- Kronecker product and SVD approximations in image restoration
- A numerical algorithm for computing a basis for the root subspace at a nonderogatory eigenvalue of a multiparameter system
- Regularization tools: A Matlab package for analysis and solution of discrete ill-posed problems
- Polynomial basis conversion made stable by truncated singular value decomposition
- Bi-cross-validation of the SVD and the nonnegative matrix factorization
- A BEM formulation in conjunction with parametric equation approach for three-dimensional Cauchy problems of steady heat conduction
- Optimization methods for regularization-based ill-posed problems: a survey and a multi-objective framework
- Regularization, GSVD and truncated GSVD
- Regularization methods in dynamic MRI
- Structured low rank approximation
- Accuracy of TSVD solutions computed from rank-revealing decompositions
- Perturbation theory for orthogonal projection methods with applications to least squares and total least squares
- Unscented/ensemble transform-based variational filter
- Regularized least squares locality preserving projections with applications to image recognition
- The regularizing properties of global GMRES for solving large-scale linear discrete ill-posed problems with several right-hand sides
- Perturbation expansions and error bounds for the truncated singular value decomposition
- Tikhonov regularization with MTRSVD method for solving large-scale discrete ill-posed problems
- Intrusive and data-driven reduced order modelling of the rotating thermal shallow water equation
- Multi-frequency model reduction for uncertainty quantification in computational vibroacoutics
- Multiscale regression on unknown manifolds
- ``Regression anytime with brute-force SVD truncation
- Numerical inversion and uniqueness of a spherical Radon transform restricted with a fixed angular span
- Boundary knot method for the Cauchy problem associated with the inhomogeneous Helmholtz equation
- Quasi solution of a backward space fractional diffusion equation
- An efficient numerical algorithm for the inversion of an integral transform arising in ultrasound imaging
- A two-stage method for piecewise-constant solution for Fredholm integral equations of the first kind
- Data based regularization for discrete deconvolution problems
- A meshless method for some inverse problems associated with the Helmholtz equation
- Fast topological-shape optimization with boundary elements in two dimensions
- Compact discrepancy and chi-squared principles for over-determined inverse problems
- Multilevel model reduction for uncertainty quantification in computational structural dynamics
- A note on sparse least-squares regression
- A finite volume method based on radial basis functions for two-dimensional nonlinear diffusion equations
- Low rank approximation of the symmetric positive semidefinite matrix
- Relations between SVD and GSVD of discrete regularization problems in standard and general form
- Inverse heat conduction problem in two-dimensional anisotropic medium
- Tikhonov regularization and randomized GSVD
- Boundary particle method for Cauchy inhomogeneous potential problems
- Ill-conditioning of the truncated singular value decomposition, Tikhonov regularization and their applications to numerical partial differential equations.
- A weighted \(H^{1}\) seminorm regularization method for Fredholm integral equations of the first kind
- The exact condition number of the truncated singular value solution of a linear ill-posed problem
- A generalization of the Bott-Duffin inverse and its applications
- Model selection criteria for a linear model to solve discrete ill-posed problems on the basis of singular decomposition and random projection
- Fast quantum algorithms for least squares regression and statistic leverage scores
- Singular boundary method for inverse heat conduction problems in general anisotropic media
- Truncated Singular Value Decomposition Solutions to Discrete Ill-Posed Problems with Ill-Determined Numerical Rank
- DATA ANALYSIS OF GRAVITATIONAL WAVES USING A NETWORK OF DETECTORS
- A computational method for identifying a spacewise-dependent heat source
- Solving inverse heat conduction problem with discrete wavelet transform
- On the low-rank approximation arising in the generalized Karhunen-Loeve transform
- Optimal Choice of a Truncation Level for the Truncated SVD Solution of Linear First Kind Integral Equations When Data are Noisy
- scientific article; zbMATH DE number 4078640 (Why is no real title available?)
- A unified approach to solving ill-conditioned matrix problems
- The Modified Truncated SVD Method for Regularization in General Form
- scientific article; zbMATH DE number 1025978 (Why is no real title available?)
- Novel Fisher discriminant classifiers
- \(L^1\) regularization method in electrical impedance tomography by using the \(L^1\)-curve (Pareto frontier curve)
- Two direct factorization methods for inverse scattering problems
- Image reconstruction from radially incomplete spherical Radon data
- A new method for TSVD regularization truncated parameter selection
- Kernel methods in system identification, machine learning and function estimation: a survey
- Regularized symmetric positive definite matrix factorizations for linear systems arising from RBF interpolation and differentiation
- Cramér-Rao bound for damped/undamped exponential process with prior-knowledge
- A nonlinear method for imaging with acoustic waves via reduced order model backprojection
- Perturbation Analysis for Two-Sided (or Complete) Orthogonal Decompositions
- Application of the conditional source-term estimation model for turbulence-chemistry interactions in a premixed flame
- A novel method for estimating the distribution of convective heat flux in ducts: Gaussian filtered singular value decomposition
- Regularization in ultrasound tomography using projection-based regularized total least squares
- Determination of the time-dependent reaction coefficient and the heat flux in a nonlinear inverse heat conduction problem
- Stable computation of least squares problems of the OGM(1,N) model and short-term traffic flow prediction
- RANS simulation of a turbulent premixed bluff body flame using conditional source-term estimation
- Investigation of conditional source-term estimation applied to a non-premixed turbulent flame
- Fast quantum algorithms for least squares regression and statistic leverage scores
- A parameter choice rule for Tikhonov regularization based on predictive risk
- Collocation methods for Cauchy problems of elliptic operators via conditional stabilities
- Regularization techniques for the high-frequency electromagnetic field coupling problem with terminated lines
- Randomized Dynamic Mode Decomposition
- Role of the filter functions in noise spectroscopy
- Modern regularization methods for inverse problems
- On the Sensitivity of Singular and Ill-Conditioned Linear Systems
- The semi-analytical method for inversion of a weighted vector ray transform in three dimensions
- Vector extrapolation applied to truncated singular value decomposition and truncated iteration
- Numerical implementation of the canonical TSVD method
- Identification of structure errors of 3-PRS-XY mechanism with regularization method
- Robust and adaptive algorithms for online portfolio selection
- Bayesian damage identification of simply supported beams from elastostatic data
- Factorized structure of the long-range two-electron integrals tensor and its application in quantum chemistry
- A literature survey of matrix methods for data science
- Relaxation of conditions for convergence of dynamic regressor extension and mixing procedure
- Estimate of the spectrum of discrete sequences in ill-posed problems based on the study of the numerical rank of the trajectory matrix
- Identification of an inverse source problem in a fractional partial differential equation based on Sinc-Galerkin method and TSVD regularization
- Spatial correlation in weather forecast accuracy: a functional time series approach
- Solution of the backward problem for the space-time fractional diffusion equation related to the release history of a groundwater contaminant
- A new investigation into regularization techniques for the method of fundamental solutions
- The Steklov-Poincaré technique for data completion: preconditioning and filtering
- Modified method of fundamental solutions for steady state heat conduction equation in anisotropic medium
- Tensorial total variation-based image and video restoration with optimized projection methods
- Solution of inverse geometric problems using a non-iterative MFS
This page was built for publication: The truncated SVD as a method for regularization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1096333)
