Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
Petros Drineas, Ilse C. F. Ipsen · SIAM Journal on Matrix Analysis and Applications · 2019
Low-rank approximations to a real matrix $\mathbf{A}$ can be computed from $\mathbf{Z}\mathbf{Z}^T\mathbf{A}$, where $\mathbf{Z}$ is a matrix with orthonormal columns, and the accuracy of the approximation can be estimated from some norm of $\mathbf{A}-\mathbf{Z}\mathbf{Z}^T\mathbf{A}$. We show that computing $\mathbf{A}-\mathbf{Z}\mathbf{Z}^T\mathbf{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 $\mathbf{A}$ and $\mathbf{Z}$, and to dimension-changing or multiplicative perturbations in $\mathbf{A}$---regardless of the accuracy of the approximation. For the special case when $\mathbf{A}$ does indeed have a singular values gap, connections are established between low-rank approximations and subspace angles.