Rank-Revealing UTV Decompositions

>> [p,R] = hurv(A,0.2)
p =
     4
R =
   -6.8957   -0.3857   -1.8243    1.4509    0.0000    0.0000    0.0000
         0    8.3497    2.7954    3.1016    0.0000    0.0000    0.0000
         0         0   -4.4848    0.5616    0.0000    0.0000    0.0000
         0         0         0    7.4355    0.0000    0.0000    0.0000
         0         0         0         0    0.1762    0.0001    0.0000
         0         0         0         0         0    0.0872    0.0024
         0         0         0         0         0         0    0.0663

Rank-Revealing UTV Decompositions

The research project was a collaboration between Prof. Per Christian Hansen at DTU Compute and Dr. Ricardo D. Fierro at CSUSM.

Rank-revealing decompositions are used in signal processing and many other applications where efficient and reliable updating algorithms are required, and where the reliable computatio and tracking of the numerical rank of a matrix is crucial.

UTV Tools and the Expansion Pack

The Matlab package UTV Tools provides 46 Matlab functions for computing and modifying rank-revealing URV and UTV decompositions, collectively known as UTV decompositions. Also included are functions for the ULLV decomposition, which generalizes the ULV decomposition to a pair of matrices. For completeness, we also include a few functions for computation of the RRQR decomposition. The package and the underlying theory is published in:

R.D. Fierro, P.C. Hansen and P.S.K. Hansen, UTV Tools: Matlab templates for rank-revealing UTV decompositions, Numerical Algorithms, 20 (1999), pp. 165-194.

The software can be used as is, or can be considered as templates for specialized implementations on signal porcessors and similar dedicated hardware platforms.

The Expansion Pack supplements and complements UTV Tools, and includes implementations of special-purpose algorithms for computing and modifying symmetric VSV decompositions, as well as ULLV algorithms for interference-type problems with a rank-deficient covariance matrix. We also provide a simple, yet robust and reliable, Lanczos algorithm for computing the dominant singular values and right singular vectors. This package is documented in:

R.D. Fierro and P.C. Hansen, UTV Expansion Pack: Special-purpose rank revaling algorithms, Numerical Algorithms, 40 (2005), pp. 47-66.

Rank-revevaling decompositions are discussed in many books; see, e.g.

P. C. Hansen, Rank-Deficient and Discrete Ill-Posed Problems: Numerical Aspects of Linear Inversion, SIAM, Philadelphia, 1998.
G. W. Stewart, Matrix Algorithms. Volume I: Basic Decompositions, SIAM, Philadelphia, 1998.

Software

The UTV Tool software consists of 55 files, while the Expansion Pack consists of 38 files. Both packages are available as compressed files:

UTV Tools: UTVtools.zip.
UTV Expansion Pack: UTVExpPack.zip.

Manual

The accompanying manuals, which also includes a discussion of rank-revealing decompositions and a survey of the underlying algorithms, are available:

UTV Tools: UTVtools.ps and UTVtools.pdf.
Expansion Pack: UTVExpPack.ps and UTVExpPack.pdf.

The hardcopy versions of the manuals are also available from IMM as Technical Report IMM-REP-99-2 and IMM-TR-2004-6, respectively.

>> [p,R] = hrrqr(A,0.2)
p =
     4
R =
    5.9319    2.4744    0.4952    1.6055    2.3535    4.7786    1.0345
         0    5.7113   -2.6717    1.7455    1.2884    1.0061    1.5985
         0         0   -5.1514   -2.1145   -3.0398    0.0705   -5.5669
         0         0         0    3.7443   -1.9533   -1.5623    1.6818
         0         0         0         0    0.2401   -0.0226    0.0515
         0         0         0         0         0    0.0978    0.0037
         0         0         0         0         0         0    0.1273