Paper Info
Title
An Alternative Algorithm for the Refinement of ULV Decompositions
Abstract
The ULV decomposition (ULVD) is an important member of a class of rank-revealing two-sided orthogonal decompositions used to approximate the singular value decomposition (SVD). It is useful in applications of the SVD such as principal components where we are interested in approximating a matrix by one of lower rank. It can be updated and downdated much more quickly than an SVD. In many instances, the ULVD must be refined to improve the approximation it gives for the important right singular subspaces or to improve the matrix approximation. Present algorithms to perform this refinement require O(mn) operations if the rank of the matrix is k, where k is very close to 0 or n, but these algorithms require O(m n2) operations otherwise. Presented here is an alternative refinement algorithm that requires O(mn) operations no matter what the rank is. Our tests show that this new refinement algorithm produces similar improvement in matrix approximation and in the subspaces. We also propose slight improvements on the error bounds on subspaces and singular values computed by the ULVD.
Year
DOI
Venue
2005
10.1137/S0895479801372621
SIAM J. Matrix Analysis Applications
Keywords
Field
DocType
ulv decompositions,refinement,singular value decomposition,important right singular subspaces,matrix approximation,orthogonal decompositions,new refinement algorithm,subspace approximation,lower rank,important member,alternative refinement algorithm,alternative algorithm,present algorithm,ulv decomposition,singular value,principal component
Singular value decomposition,Discrete mathematics,Mathematical optimization,Singular value,Matrix (mathematics),Algorithm,Linear subspace,Low-rank approximation,Mathematics,Principal component analysis
Journal
Volume
Issue
ISSN
27
1
0895-4798
Citations 
PageRank 
References 
5
0.79
6
Authors
3
Name
Order
Citations
PageRank
Jesse L. Barlow19513.17
Hasan Erbay2115.32
Ivan Slapniucar350.79