UC Berkeley

The truncated singular value decomposition (TSVD) is an important low-rank matrix approximation technique used in data science, machine learning, numerical linear algebra, and many other scientific fields. However, it is quite expensive for large matrices when only a very low-rank approximation is needed. Existing algorithms for TSVD typically assume the user knows the proper rank to use, but in practice, they may not know this rank beforehand. Thus, it is important to have versions of these algorithms that depend on a tolerance parameter, allowing the user to directly control the approximation error. We develop one such algorithm that runs quickly for matrices with rapidly decaying singular values, provide approximation error bounds that are within a constant factor away from optimal, and demonstrate its utility with matrices from a variety of applications.