Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
Low-Rank Matrix Approximations Do Not Need a Singular Value Gap
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 …