I. Introduction
In modern times, low rank approximations have become extremely important both in theory and application, particularly as a dimensionality reduction or compression tool. Oftentimes, data matrices are well-approximated by a low rank matrix, i.e. are of the form , where A is low rank and E is some noise (deterministic or random). There are many classical factorizations of low-rank matrices which give rise to natural low-rank approximations of matrices. While the truncated Singular Value Decomposition (SVD) provides the best approximation (in the spectral or Frobenius norm) to a given matrix, it has an issue of interpretability and computational feasibility [9]. That is, if a matrix consists of data vectors whose interpretations are clear to a domain scientist (such as gene expression data), then using the SVD for dimension reduction could come at the cost of a clear interpretation, e.g. what is an eigengene or an eigenpatient? Additionally, computing even the truncated SVD of a huge matrix can be somewhat costly; the naïve algorithm takes O(k2 min{m, n}) operations for an m×n matrix, whereas finding the full SVD of the matrix has complexity O(min{mn2, m2n}). Finally, we note that storing a full SVD requires storing O(m2 + n2 + k) entries.