New studies of randomized augmentation and additive preprocessing

DOI10.1016/J.LAA.2016.09.035MaRDI QIDQ332656zbMATH OpenOpenAlexFDO

Authors Victor Y. Pan, Liang Zhao

Publication date 8 November 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

low-rank approximationdualityderandomizationsingular valueill-conditioned matrixfundamental matrix computationGaussian random matricesrandomized matrix algorithmssingular subspaces of a matrixsparse and structured preprocessors

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Random matrices (algebraic aspects) (15B52) Ill-posedness and regularization problems in numerical linear algebra (65F22) Iterative numerical methods for linear systems (65F10)

Abstract: 1. A standard Gaussian random matrix has full rank with probability 1 and is well-conditioned with a probability quite close to 1 and converging to 1 fast as the matrix deviates from square shape and becomes more rectangular. 2. If we append sufficiently many standard Gaussian random rows or columns to any normalized matrix A, then the augmented matrix has full rank with probability 1 and is well-conditioned with a probability close to 1, even if the matrix A is rank deficient or ill-conditioned. 3. We specify and prove these properties of augmentation and extend them to additive preprocessing, that is, to adding a product of two rectangular Gaussian matrices. 4. By applying our randomization techniques to a matrix that has numerical rank r, we accelerate the known algorithms for the approximation of its leading and trailing singular spaces associated with its r largest and with all its remaining singular values, respectively. 5. Our algorithms use much fewer random parameters and run much faster when various random sparse and structured preprocessors replace Gaussian. Empirically the outputs of the resulting algorithms is as accurate as the outputs under Gaussian preprocessing. 6. Our novel duality techniques provides formal support, so far missing, for these empirical observations and opens door to derandomization of our preprocessing and to further acceleration and simplification of our algorithms by using more efficient sparse and structured preprocessors. 7. Our techniques and our progress can be applied to various other fundamental matrix computations such as the celebrated low-rank approximation of a matrix by means of random sampling.

Recommendations

• Advancing matrix computations with randomized preprocessing
• Additive preconditioning for matrix computations
• Additive Preconditioning for Matrix Computations
• Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
• A fast randomized algorithm for the approximation of matrices

Cites work

• scientific article; zbMATH DE number 1682655 (Why is no real title available?)
• scientific article; zbMATH DE number 5872173 (Why is no real title available?)
• scientific article; zbMATH DE number 3573787 (Why is no real title available?)
• scientific article; zbMATH DE number 1226426 (Why is no real title available?)
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• scientific article; zbMATH DE number 6159604 (Why is no real title available?)
• A theory of pseudoskeleton approximations
• Accuracy and Stability of Numerical Algorithms
• Additive Preconditioning for Matrix Computations
• Additive preconditioning and aggregation in matrix computations
• Additive preconditioning for matrix computations
• Additive preconditioning, eigenspaces, and the inverse iteration
• Condition Numbers of Gaussian Random Matrices
• Determinantal rings
• Effect of small rank modification on the condition number of a matrix
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Eigenvalues and Condition Numbers of Random Matrices
• Estimating the norms of random circulant and Toeplitz matrices and their inverses
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Homotopic residual correction processes
• How to find a good submatrix
• Improved analysis of the subsampled randomized Hadamard transform
• Local operator theory, random matrices and Banach spaces.
• Matrix computations and polynomial root-finding with preprocessing
• On Rank-Revealing Factorisations
• On perturbation bounds for the QR factorization
• On the existence and computation of rank-revealing LU factorizations
• Random matrix theory
• Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
• Randomized preprocessing of homogeneous linear systems of equations
• Randomized preprocessing versus pivoting
• Schur aggregation for linear systems and determinants
• Smoothed Analysis of the Condition Numbers and Growth Factors of Matrices
• Solving linear systems of equations with randomization, augmentation and aggregation
• Tails of Condition Number Distributions
• The maximal-volume concept in approximation by low-rank matrices

Cited in

(5)

• Random multipliers numerically stabilize Gaussian and block Gaussian elimination: proofs and an extension to low-rank approximation
• Sublinear Cost Low Rank Approximation via Subspace Sampling
• Numerically safe Gaussian elimination with no pivoting
• CUR LRA at Sublinear Cost Based on Volume Maximization
• Additive preconditioning for matrix computations

This page was built for publication: New studies of randomized augmentation and additive preprocessing

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