Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
This work provides a theoretical foundation for low-rank approximations, benefiting researchers and practitioners in numerical linear algebra and machine learning by removing a common assumption.
The paper proves that low-rank matrix approximations are always well-posed and do not require a singular value gap, showing that approximation errors in various norms are insensitive to certain perturbations.
This is a systematic investigation into the sensitivity of low-rank approximations of real matrices. We show that the low-rank approximation errors, in the two-norm, Frobenius norm and more generally, any Schatten p-norm, are insensitive to additive rank-preserving perturbations in the projector basis; and to matrix perturbations that are additive or change the number of columns (including multiplicative perturbations). Thus, low-rank matrix approximations are always well-posed and do not require a singular value gap. In the presence of a singular value gap, connections are established between low-rank approximations and subspace angles.