Naslov
An alternative algorithm for refinement of ULV decomposition

Autori
Barlow, Jesse ; Erbay, Hasan ; Slapničar, Ivan

Izvornik
SIAM Journal on Matrix Analysis and Applications (0895-4798) 27 (2005), 1; 198-211

Vrsta, podvrsta i kategorija rada
Radovi u časopisima, članak, znanstveni

Ključne riječi
Two-sided orthogonal decompositions; ULV decomposition; subspaces estimation

Sažetak
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). The ULVD can be modified much faster than the SVD. In many instances, the ULVD must be refined to improve the approximation it gives for the importan 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(mn^2)$ 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.

Izvorni jezik
Engleski

Znanstvena područja
Matematika

POVEZANOST RADA