LOW-RANK MATRIX APPROXIMATIONS DO NOT NEED A SINGULAR VALUE GAP.

Low-rank approximations to a real matrix A can be computed from ZZT A, where Z is a matrix with orthonormal columns, and the accuracy of the approximation can be estimated from some norm of A - ZZT A. We show that computing A - ZZT A in the two-norm, Frobenius norms, and more generally any Schatten p-norm is a well-posed mathematical problem; and, in contrast to dominant subspace computations, it does not require a singular value gap. We also show that this problem is well-conditioned (insensitive) to additive perturbations in A and Z, and to dimension-changing or multiplicative perturbations in A--regardless of the accuracy of the approximation. For the special case when A does indeed have a singular values gap, connections are established between low-rank approximations and subspace angles. [ABSTRACT FROM AUTHOR]