Rank-revealing 𝑄𝑅 factorizations and the singular value decomposition

1992/01/01 by Y. P. Hong, Yoopyo Hong, C.-T. Pan · 18 citations
Computer Science · Engineering · #Matrix Theory and Algorithms #graph theory and CDMA systems #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.1090/s0025-5718-1992-1106970-4

Abstract

T. Chan has noted that, even when the singular value decomposition of a matrix <italic>A</italic> is known, it is still not obvious how to find a rank-revealing QR factorization (RRQR) of <italic>A</italic> if <italic>A</italic> has numerical rank deficiency. This paper offers a constructive proof of the existence of the RRQR factorization of any matrix <italic>A</italic> of size <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m times n"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo> × </mml:mo> <mml:mi>n</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">m × n</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with numerical rank <italic>r</italic> . The bounds derived in this paper that guarantee the existence of RRQR are all of order <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartRoot n r EndRoot"> <mml:semantics> <mml:msqrt> <mml:mi>n</mml:mi> <mml:mi>r</mml:mi> </mml:msqrt> <mml:annotation encoding="application/x-tex">√ nr</mml:annotation> </mml:semantics> </mml:math> </inline-formula> , in comparison with Chan’s <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper O left-parenthesis 2 Superscript n minus r Baseline right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mo> − </mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">O(2^{n - r})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> . It has been known for some time that if <italic>A</italic> is only numerically rank-one deficient, then the column permutation <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Pi"> <mml:semantics> <mml:mi mathvariant="normal"> Π </mml:mi> <mml:annotation encoding="application/x-tex">Π</mml:annotation> </mml:semantics> </mml:math> </inline-formula> of <italic>A</italic> that guarantees a small <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="r Subscript n n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>r</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>n</mml:mi> <mml:mi>n</mml:mi> </mml:mrow> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">r_nn</mml:annotation> </mml:semantics> </mml:math> </inline-formula> in the QR factorization of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A normal upper Pi"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mi mathvariant="normal"> Π </mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">AΠ</mml:annotation> </mml:semantics> </mml:math> </inline-formula> can be obtained by inspecting the size of the elements of the right singular vector of <italic>A</italic> corresponding to the smallest singular value of <italic>A</italic> . To some extent, our paper generalizes this well-known result.

Citations

• Numerical Linear Algebra

Cited by

• Efficient QR-based Column Subset Selection through Randomized Sparse Embeddings
• Faster Subset Selection for Matrices and Applications
• Greedy Frank-Wolfe Algorithm for Exemplar Selection
• Generalized Interlacing Families: New Error Bounds for CUR Matrix Decompositions
• Simple Approximate Varieties for Sets of Empirical Points
• Pass-efficient methods for compression of high-dimensional turbulent flow data
• Efficient construction of tensor ring representations from sampling
• Interpolatory Approximations of PMU Data: Dimension Reduction and Pilot Selection
• Randomized algorithms for matrices and data
• Exponential Inapproximability of Selecting a Maximum Volume Sub-matrix
• Convergence of Pivoted Cholesky Algorithm for Lipschitz Kernels
• The Singular Value Decomposition, Applications and Beyond
• New Lower Bounds for the Minimum Singular Value in Matrix Selection
• Efficient adaptive randomized algorithms for fixed-threshold low-rank matrix approximation
• Randomized algorithms for the low multilinear rank approximations of tensors
• QRP Variation of Cross--Approximation Iterations for Low Rank Approximation
• On applying the maximum volume principle to a basis selection problem in multivariate polynomial interpolation
• Fast Multipole Method as a Matrix-Free Hierarchical Low-Rank Approximation

Related

• A Rank Revealing Factorization Using Arbitrary Norms
• The PowerURV algorithm for computing rank-revealing full factorizations
• Blocked rank-revealing QR factorizations: How randomized sampling can be used to avoid single-vector pivoting
• On the Failure of Rank-Revealing QR Factorization Software -- A Case Study
• A randomized blocked algorithm for efficiently computing rank-revealing\n factorizations of matrices