engleski

A new stable bidiagonal reduction algorithm

A new bidiagonal reduction method is proposed for X ∈ Rm×n. For m ⩾ n, it decomposes X into the product X = UBVT where U ∈ Rm×n has orthonormal columns, V ∈ Rn×n is orthogonal, and B ∈ Rn×n is upper bidiagonal. The matrix V is computed as a product of Householder transformations. The matrices U and B are constructed using a recurrence. If U is desired from the computation, the new procedure requires fewer operations than the Golub–Kahan procedure [SIAM J. Num. Anal. Ser. B 2 (1965) 205] and similar procedures. In floating point arithmetic, the columns of U may be far from orthonormal, but that departure from orthonormality is structured. The application of any backward stable singular value decomposition procedure to B recovers the left singular vectors associated with the leading (largest) singular values of X to near orthogonality. The singular values of B are those of X perturbed by no more than f(m, n)εM∥X∥F where f(m, n) is a modestly growing function and εM is the machine unit. Under certain assumptions, relative error bounds on the singular values are possible.

singular value decomposition, bidiagonal matrix, error analysis, orthogonality, left orthogonal matrix

nije evidentirano