ALORA: Affine Low-Rank Approximations

• Published in: Journal of scientific computing 2019-05, Vol.79 (2), p.1135-1160
• Main Authors: Ayala, Alan, Claeys, Xavier, Grigori, Laura
• Format: Article
• Language: English
• Subjects: Accuracy; Algorithms; Approximation; Computational Mathematics and Numerical Analysis; Computer Science; Convergence; Iterative algorithms; Iterative methods; Linear algebra; Mathematical analysis; Mathematical and Computational Engineering; Mathematical and Computational Physics; Mathematics; Mathematics and Statistics; Numerical Analysis; Theoretical
• ISSN: 0885-7474; 1573-7691
• DOI: 10.1007/s10915-018-0885-5

In this paper we present the concept of affine low-rank approximation for an m × n matrix, consisting in fitting its columns into an affine subspace of dimension at most k ≪ min ( m , n ) . We present the algorithm ALORA that constructs an affine approximation by slightly modifying the application of any low-rank approximation method. We focus on approximations created with the classical QRCP and subspace iteration algorithms. For the former, we discuss existing pivoting techniques and provide a bound for the error when an arbitrary pivoting technique is used. For the case of fsubspace iteration, we prove a result on the convergence of singular vectors, showing a bound that agrees with the one recently proved for the convergence of singular values. Finally, we present numerical experiments using challenging matrices taken from different fields, showing good performance and validating the theoretical framework.