Rang revealing QR factorizations
From MaRDI portal
This paper presents an algorithm for computing a column permutation, \(\Pi\), of an \(m\times n\) matrix A (m\(\geq n)\) so that in the QR factorization, \(A=QR\), rank deficiency of A is revealed in the lower right block of R. Such a factorization is convenient in many applications, such as least-squares for example. If r is the near-rank deficiency R is partitioned as \(R=\left[ \begin{matrix} R_{11}\\ 0\end{matrix} \begin{matrix} R_{12}\\ R_{22}\end{matrix} \right]\) \((R_{22}\) is \(r\times r)\) and certainly, if \(\| R_{22}\|\) is small in the \(\ell_ 2\) norm, A has at least r small singular values, though the converse is not true. \textit{G. H. Golub}, \textit{V. Klema} and \textit{G. W. Stewart} [Tech. Rep. STAN-CS-76-559 (1976)] have published a method based on the SVD of A. The present method does not make use of SVD but generalizes a method for revealing rank-one deficiency. The first step requires any QR-factorization of A, followed by a sequence of r iterations, each of which requires computation of the singular vector v of \(R_{11}\) by inverse iteration and the QR factorization of \(R_{11}P\), where P is a permutation matrix. It is shown that the elements of the final \(R_{11}\) are bounded by \(| r_{ij}| \leq 2^{j-i} \sigma_ in^{1/2},\) \(n-r<i\leq j\leq n\) where \(\sigma_ i\) is the ith singular value of A. The author also shows that the total work involved in the algorithm is roughly half that for the usual SVD of A. Numerical examples indicate that the algorithm, which is guaranteed to work for matrices of low rank deficiency, will almost always work for the high rank case as well.
Recommendations
Cites work
- A criterion for truncation of theQR-decomposition algorithm for the singular linear least squares problem
- An Interval Analysis Approach to Rank Determination in Linear Least Squares Problems
- Deflated Decomposition of Solutions of Nearly Singular Systems
- Handbook series linear algebra. Linear least squares solutions by Householder transformations
- 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 3331873 (Why is no real title available?)
- On computing bounds for the least singular value of a triangular matrix
- On the Existence and Computation of LU-Factorizations with Small Pivots
- On the Implicit Deflation of Nearly Singular Systems of Linear Equations
- Rank and null space calculations using matrix decomposition without column interchanges
- Rank Degeneracy
Cited in
(only showing first 100 items - show all)- On the computation of the rank of block bidiagonal Toeplitz matrices
- On selecting a maximum volume sub-matrix of a matrix and related problems
- The 2-norm of random matrices
- Iterative algorithms for Gram-Schmidt orthogonalization
- Generalized QR factorization and its applications
- Solving large dense systems of linear equations on systems with virtual memory and with cache
- A block algorithm for computing rank-revealing QR factorizations
- Rank revealing \(LU\) factorizations
- An efficient total least squares algorithm based on a rank-revealing two- sided orthogonal decomposition
- Fast orthogonal decomposition of rank deficient Toeplitz matrices
- A Krylov multisplitting algorithm for solving linear systems of equations
- Maximizing bilinear forms subject to linear constraints
- Computation of structural invariants of generalized state-space systems
- Improved bound for rank revealing LU factorizations
- Jacobian reuse in explicit integrators for higher index DAEs
- The behavior of the QR-factorization algorithm with column pivoting
- A new method for computing the stable invariant subspace of a real Hamiltonian matrix
- Computation of coprime factorizations of rational matrices
- Componentwise analysis of direct factorization of real symmetric and Hermitian matrices
- Methods and algorithms of solving spectral problems for polynomial and rational matrices
- Numerical methods in control
- Some new properties of the equality constrained and weighted least squares problem
- Numerical methods and questions in the organization of calculus. XII. Transl. from the Russian
- Integer matrix factorization for mesh defect detection
- Randomized LU decomposition
- A fast algorithm for index of annihilation computations
- Perturbation theory for the Eckart-Young-Mirsky theorem and the constrained total least squares problem
- One-sided reduction to bidiagonal form
- Tracking poles, representing Hankel operators, and the Nehari problem
- Pole-zero representation of descriptor systems
- Exponential inapproximability of selecting a maximum volume sub-matrix
- Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm
- Structural instability analyses based on generalised path-following
- A contour-integral based method for counting the eigenvalues inside a region
- An improved divide-and-conquer algorithm for the banded matrices with narrow bandwidths
- Theory of functional connections applied to quadratic and nonlinear programming under equality constraints
- Deviation maximization for rank-revealing QR factorizations
- Randomized QLP decomposition
- Regularized greedy column subset selection
- Randomized algorithms for the low multilinear rank approximations of tensors
- A contour-integral based method with Schur-Rayleigh-Ritz procedure for generalized eigenvalue problems
- \(J\) factorizations of a general discrete-time system
- Efficient algorithms for CUR and interpolative matrix decompositions
- A modified matrix sign function method for projected Lyapunov equations
- Time and space efficient generators for quasiseparable matrices
- Fast structured LU factorization for nonsymmetric matrices
- Fast linear algebra is stable
- Dynamic block GMRES: An iterative method for block linear systems
- Efficient algorithms for generalized algebraic Bernoulli equations based on the matrix sign function
- An efficient algorithm for rank and subspace tracking
- A note on properties and computations of matrix pseudospectra
- Indefinite QR factorization
- Solving stable Sylvester equations via rational iterative schemes
- Randomized algorithms for the approximations of Tucker and the tensor train decompositions
- Column subset selection problem is UG-hard
- A training set subsampling strategy for the reduced basis method
- Parallel spectral division using the matrix sign function for the generalized eigenproblem
- Rank-revealing decomposition of symmetric indefinite matrices via block anti-triangular factorization
- An efficient multicore implementation of a novel HSS-structured multifrontal solver using randomized sampling
- Gram-Schmidt orthogonalization: 100 years and more
- INFORMATION STORAGE SYSTEM
- A numerical approximation for the simple bifurcation problems
- The Probability of Large Diagonal Elements in the QR Factorization
- Row Ordering for a Sparse QR Decomposition
- Numerical aspects of computing the Moore-Penrose inverse of full column rank matrices
- scientific article; zbMATH DE number 6982912 (Why is no real title available?)
- Literature survey on low rank approximation of matrices
- Spectral division methods for block generalized Schur decompositions
- Infinite- and finite-buffer Markov fluid queues: a unified analysis
- Rounding errors in solving block Hessenberg systems
- Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
- Hierarchical algorithms on hierarchical architectures
- Low rank approximation of binary matrices: column subset selection and generalizations
- Efficient Krylov subspace techniques for model order reduction of automotive structures in vibroacoustic applications
- Approximate Generalized Inverses with Iterative Refinement for \epsilon-Accurate Preconditioning of Singular Systems
- Subspaces analysis for random projection UTV framework
- The Computation of Low Multilinear Rank Approximations of Tensors via Power Scheme and Random Projection
- An Algebraic Sparsified Nested Dissection Algorithm Using Low-Rank Approximations
- Randomized Projection for Rank-Revealing Matrix Factorizations and Low-Rank Approximations
- Low-Rank Approximation in the Frobenius Norm by Column and Row Subset Selection
- Sparse Hierarchical Preconditioners Using Piecewise Smooth Approximations of Eigenvectors
- Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
- A TT-based hierarchical framework for decomposing high-order tensors
- Subspace Iteration Randomization and Singular Value Problems
- A distributed-memory package for dense hierarchically semi-separable matrix computations using randomization
- A nonlinear QR algorithm for banded nonlinear eigenvalue problems
- Randomized QR with column pivoting
- Fast Estimation of Approximate Matrix Ranks Using Spectral Densities
- Matrix pencil methodologies for computing the greatest common divisor of polynomials: hybrid algorithms and their performance
- Fast hierarchical solvers for sparse matrices using extended sparsification and low-rank approximation
- Estimation of atmospheric PSF parameters for hyperspectral imaging.
- An algebraic multifrontal preconditioner that exploits the low-rank property.
- Compressing Rank-Structured Matrices via Randomized Sampling
- Information preserving regression-based tools for statistical disclosure control
- On rank and null space computation of the generalized Sylvester matrix
- A Framework for a Generalization Analysis of Machine-Learned Interatomic Potentials
- Simpler is better: a comparative study of randomized pivoting algorithms for CUR and interpolative decompositions
- An efficient randomized QLP algorithm for approximating the singular value decomposition
- Parallel Algorithms for Computing the Tensor-Train Decomposition
- QM/MM Methods for Crystalline Defects. Part 3: Machine-Learned MM Models
This page was built for publication: Rang revealing QR factorizations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q578845)
